Addressable Data Graphs

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.