Turing machines with several read-write heads preliminary report
Albert R. Meyer, Arnold L. Rosenberg, et al.
SWAT 1967
Any assessment of the "cost" of encoding one data structure in another must take into account, among other issues, the intended patterns of traversing the guest structure. Two such "usage patterns," namely, worstedge traversal and all-edges-equally-likely traversal, are particularly significant, since any bounds on encoding costs relative to these patterns yield bounds relative to large classes of other patterns also. The foregoing remarks are formalized in this paper, and a number of techniques for bounding the costs of encodings relative to these special usage patterns are developed and exemplified. Specifically, data structures are represented here as undirected graphs; and a number of lower bounds on the costs of data encodings are derived by comparing various structural features of the guest and host graphs. Relevant features include both maximum and average vertex-degree, "volume," and "exposure," a measure of connectivity. © 1978 Springer-Verlag New York Inc.
Albert R. Meyer, Arnold L. Rosenberg, et al.
SWAT 1967
Arnold L. Rosenberg, Larry J. Stockmeyer, et al.
Theoretical Computer Science
Arnold L. Rosenberg
Mathematical Systems Theory
Michael J. Fischer, Arnold L. Rosenberg
SWAT 1968