Abstract
The need to detect and merge redundant information is a familiar problem in data management. This paper presents a particular definition of redundancy in list structures, along with algorithms for its removal. The process, termedcondensation, transforms a list structure 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 noncyclic structures and one for cyclic. The best time result in both cases isO(mn) for ann-cell structure withm cell equivalence classes. In the case of noncyclic 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 themode equivalence problem ofalgol 68.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Donald E. Knuth,Fundamental Algorithms (Addison-Wesley, Reading, Massachusetts, 1968).
C. H. A. Koster, “On infinite modes,”Algol Bulletin, contribution AB 30.3.3 (February 1969).
Gary Lindstrom, “Scanning list structures without stacks or tag bits,”Inf. Proc. Letters 2(2):47–51 (1973).
Richard M. Karp, Raymond E. Miller, and Arnold L. Rosenberg, “Rapid identification of repeated patterns in strings, trees and arrays,” inProc. 4th Ann. Symp. on Th. of Comp. (May 1972), pp. 125–136.
Gary Lindstrom, “Copying list structures using bounded workspace,”Comm. ACM 17:198–202 (1974).
J. Kral, “The equivalence of modes and the equivalence of finite automata,”Algol Bulletin, contribution AB 35.4.5 (March 1973).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lindstrom, G. Algorithms for list structure condensation. International Journal of Computer and Information Sciences 3, 197–216 (1974). https://doi.org/10.1007/BF00977255
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00977255