AN EXTRINSIC CHARACHTERIZATION OF ADDRESSABLE DATA GRAPHS
Original Publication Date: 1972-Aug-02
Included in the Prior Art Database: 2007-Mar-30
Software Patent Institute
Rosenberg, Arnold L.: AUTHOR [+2]
AN EXTRINSIC CHARACTERIZATION Arnold L. Rosenberg
AN EXTRINSIC CHARACTERIZATION
Arnold L. Rosenberg
Mathematical Sciences Department IBM T. J. Watson Research Center Yorktown Heights, New York
Previous characterizations of the class of addressable data graphs have been intrinsic in nature. In this note, the auxiliary concept of a monoid system is used to derive an extrinsic characterization of the class. Specifically,
a partial transformation of the class of data graphs is found which fixes (up to isomorphism) precisely the addressable data graphs.
RC 3962 (#17931)
August 2, 1972
*This research was supported in part by ONR Contract N00014-69-C
LIMITED DISTRIBUTION NOTICE
This report has been submitted for publication elsewhere and has been issued as a Research Report for early dissemination of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.
Copies may be requested from:
IBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598
In earlier papers [1,3], we found four properties, each of which charac-
terizes the class of addressable data graphs. A l l of these characterizations are intrinsic in that they depend on uniformities in the structure of the data graph (such as rootedness, [I]) or on manipulations which the data graph admits (e.g., uniform self-insertability, [31). This note is devoted to establishing an extrinsic characterization of the addressable data graphs. Using the auxiliary notion of a monoid system, we specify a partial function from the class of data graphs into itself: The addressable data graphs are precisely the fixed points (up to isomorphism) of this function.
In this section we present the background on data graphs which is needed
in the sequel, and we introduce monoid systems.
2.1: Data Graphs and Their Morphisms
Definition. A data graph is a system r = (C, A) where
(a) C is a countable set of data cells;
(b) A is a finite set of partial transformations of C, the atomic link-transformations ;
subject to the condition (1)
(c) for a l l c, dcC, there is a SEA' such that c< = d.
One views the system (C, A) as specifying a labelled directed graph in the following manner. The graph has node set C. There is a directed edge from node ccC to node dcC, labelled with hen, precisely when cA = d.
Thus, node c has a A-edge leaving it precisely when cc domain(h). Condition
(c) above postulates the strong connectivity of data graphs.
Definition. Let I' = (C,A) and r' = (C', A') be data graphs. Let F =
be a pair of total maps:
F is a data graph morphism (in particular, a morphism of...