Suffixes of addressable data graphs

Abstract

The notion of a self-insertion of a data graph yields a simple and natural definition of a suffix of a data graph. For addressable data graphs, addressing schemes yield a useful alternative definition of suffix, which also suggests a generalized version of suffix. Examples of addressable data graphs and their suffixes include: trees and their subtrees, and arrays with their (possibly lower dimensional) subarrays. Thus a suffix can be viewed as a highly structured type of substructure of a data graph. Necessary and sufficient conditions for a suffix of an addressable data graph to be addressable are derived. It is further shown that suffix data graphs, even when not addressable, often enjoy a slightly weaker property termed quasi-addressability; in fact suffixes of so-called deep-rooted data graphs are always quasi-addressable. © 1973 Academic Press, Inc.