Browse Prior Art Database

ALGORITHMS FOR LIST STRUCTURE CONDENSATION

IP.com Disclosure Number: IPCOM000128601D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 10 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Gary Lindstrom: AUTHOR [+3]

Abstract

The need to detect and merge redundant information is a familiar problem in data management. This paper presents a particular defini-tion of redundancy in list structures, along with algorithms for its removal. The process, termed condensati.on, transforms a list struc-turt into a minimally-sized equivalent structure in which each cell has a unique information content. The resulting structure is often smaller than the original, and permits substructure equivalence testing to be done by trivial address identity comparison. Three algorithms are presented, two for non-cyclic structures and one for cyclic. The beat time result in both cases is 0(mn) for an n-cell structure with m cell equivalence classes. In the case of non-cyclic structures, that speed is attained under bounded workspace if a free mark bit is assumed in each cell. The cyclic algorithm is illustrated by application to the mode equivalence problem of Algol 68.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 10

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ALGORITHMS FOR LIST STRUCTURE CONDENSATION

Gary Lindstrom

September 27, 1973 Department of Computer Science University of Pittsburgh Pittsburgh, Pennsylvania 15260

Abstract

The need to detect and merge redundant information is a familiar problem in data management. This paper presents a particular defini-tion of redundancy in list structures, along with algorithms for its removal. The process, termed condensati.on, transforms a list struc-turt into a minimally- sized equivalent structure in which each cell has a unique information content. The resulting structure is often smaller than the original, and permits substructure equivalence testing to be done by trivial address identity comparison. Three algorithms are presented, two for non-cyclic structures and one for cyclic. The beat time result in both cases is 0(mn) for an n-cell structure with m cell equivalence classes. In the case of non-cyclic structures, that speed is attained under bounded workspace if a free mark bit is assumed in each cell. The cyclic algorithm is illustrated by application to the mode equivalence problem of Algol 68.

1. List structure condensation.

1.1. Data organization. Consider a data store organized into cells comprising two link fields, LUNK and RLINK. Each link field is capable of addressing any cell or of containing an uninterpreted atomic value from some atom set A. For convenience, a single bit 'MARK field will also be assumed in each cell. Cells and atoms together will be termed nodes.

1.2. Node ecuivalence. In the case of a binary tree represented using such cells, intuition directly provides a notion of subtree equivalence. In Fig. 1.1, for example, the subtrees rooted at cells 2 and 5 are visibly the same subtrees in structure and atomic values; only the addresses of their component cells differ. This notion of substructure equivalence is based on a natural concept of node infor-mation content. That concept will now be formalized with the aid of a few preliminary definitions.

Def. 1. A path is a string over the set IL, R j, i.e. an element

of PIJL, Rj*.

Def. 2. The reach of a path p from a node x, denoted

(Equation Omitted)

, is defined:

(Equation Omitted)

University of Pittsburgh Page 1 Dec 31, 1973

Page 2 of 10

ALGORITHMS FOR LIST STRUCTURE CONDENSATION

is nonatomic;

if x is nonatomic;

(Equation Omitted)

(Equation Omitted)

and

(Equation Omitted)

is undefined otherwise. Design an algorithm to test the equivalence of two list struc-tures in the sense that they have the same diagram when fully expanded." ((l) problem 11, p. 421; solution
p. 594)

1.3. List structure condensation. Given the node equivalence classes of a list structure, one may then proceed to remove redun-dant nodes. This is done by selecting one representative from each equivalence class and projecting the original structure onto this subset. More formally,

Def. 6. Let El, ..., Em be the node equivalence classes o...