A model for finite data graphs with relocatable realizations

Abstract

A data structure model is presented that is characteristic of a class of structures called data graphs. Data structures are considered to be a collection of data items together with a set of relations defined on these items. It is assumed that there are many situations which yield to an analysis of a data structure which does not depend on particular data items stored in the structure. A data graph is a graph such that from each vertex there exists a linkage to any other vertex. The model presented in this research is used as a basis for studying the formal concepts of relative addressing and relocatability. This model is then studied to expose the algebraic properties of finite data graphs which have a relocatable realization. A method is presented to detect the conditions that are both necessary and sufficient for a finite data graph to be relocatably realizable. The method consists of a way of viewing the elements of the monoid as boolean matrices together with an efficient way to generate these elements. Also a procedure is given that yields the construction of the relocation of a nontrivial data graph. The concept of a connective function is developed in order to better analyze the properties of finite data graphs with relocatable realizations. It is shown that any finite relocatable data graph which has a connective function in its set of transformation functions is isomorphic to a circular list.