About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.