Browse Prior Art Database

AN EXTRINSIC CHARACHTERIZATION OF ADDRESSABLE DATA GRAPHS

IP.com Disclosure Number: IPCOM000148644D
Original Publication Date: 1972-Aug-02
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Rosenberg, Arnold L.: AUTHOR [+2]

Abstract

AN EXTRINSIC CHARACTERIZATION Arnold L. Rosenberg

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 21% of the total text.

Page 1 of 16

AN EXTRINSIC CHARACTERIZATION

Arnold L. Rosenberg

Mathematical Sciences Department IBM T. J. Watson Research Center Yorktown Heights, New York

ABSTRACT


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

-0023.

*This research was supported in part by ONR Contract N00014-69-C

[This page contains 1 picture or other non-text object]

Page 2 of 16

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

[This page contains 1 picture or other non-text object]

Page 3 of 16

1. INTRODUCTION


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.

[This page contains 1 picture or other non-text object]

Page 4 of 16

2. PRELIMINARIES


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...