Browse Prior Art Database

Original Publication Date: 1973-Sep-27
Included in the Prior Art Database: 2007-Apr-01
Document File: 36 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Lindstrom, Gary: AUTHOR [+2]


Technical Report 73 -14 ALGORITHMS

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 11% of the total text.

Page 1 of 36

Technical Report 73 -14



Gary Lindstroxn

September 27, 1973

Department of Computer Science

University of Pittsburgh

Pittsburgh, Pennsylvania 152 60

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

Page 2 of 36

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

Page 3 of 36


   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 condensation, transforms a list struc-
ture into a minimally-sized equivalent structure in which each cell
has a unique information content. The r~easulting structure is often
smaller than the original, and permits siubstructure equivalence
testing to be done by trivial address identity comparison. Three
algorithms are presented, two for non-cyclic structures and one for
cyclic. The best time result in both cases is O(mn) for an n-cell
structure with 2 cell equivalence claaises. In tbe 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 page contains 1 picture or other non-text object]

Page 4 of 36

1. List structure condensation.

   1.1. Data organization. Consider a data store organized into cells
comprising two link fields, LLfNK 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


1.2. Node? equivalence. 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 eame subtrees in structure and atomic values;
only the addresses of their component cells differ. This notion of
substructure equivalence is based on e natural concept of node infor-
mation content. That concept will now be formalized with the aid of a
few preliminary definitions.

Dcf. 1. A path is a string over the set (L, R 1 , i.e. an element


of P={L,

Def. 2. The reach of a path E from a node 5, denoted Rch(~,p)~


fa defined:


i) Rch(+,LwJ = Rck(LLPNK(x) ,XI if g is nonatomic;
ii) Rch(x,Rw) a RchQREPIW(x) ,w) f

f x is nonatomic;

iii) Reh(x,A) = x, and
iv) Rch(5,p) is undefined otherwise.

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

Page 5 of 36

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

   1.3. structure condensation. Given the nsde equivalence
classes of a list st...