Addressable data graphs (Extended Abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Addressable data graphs (Extended Abstract)

Full text

Pdf (783 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the third annual ACM symposium on Theory of computing table of contents

Shaker Heights, Ohio, United States

Pages: 138 - 150

Year of Publication: 1971

Author

Arnold L. Rosenberg

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 5, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800157.805046 What is a DOI?

ABSTRACT

This paper continues the study of the classes of data graphs which are implementable in a random access memory using “relative addressing” and “relocatable realization”, which was initiated in [1]. A new characterization of the class of rooted (&equil;relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. These positive results somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (&equil;relocatability) in data graphs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.