Publication
Journal of the ACM
Paper

Addressable Data Graphs

Download paper

Abstract

The classes of data graphs which are implementable in a random access memory using “relative addressing” and “relocatable realization” were characterized algebraically in a previous paper by the author. In the present paper the investigation of these classes is continued. A new characterization of the class of rooted (= relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. These combinatory operations somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (= relocatability) in data graphs. © 1972, ACM. All rights reserved.

Date

01 Apr 1972

Publication

Journal of the ACM

Authors

Topics

Resources

Share