AbstractIn order to deal with infinite regular trees (or other pointed graph structures) efficiently, we give new algorithms to store such structures. The trees are stored in such a way that their representation is unique and shares substructures as much as possible. This maximal sharing allows substantial memory gain and speed up over previous techniques. For example, equality testing becomes constant time (instead of O(n\log(n))). The algorithms are incremental, and as such allow good reactive behavior. These new algorithms are then applied in a representation of sets of trees. The expressive power of this new representation is exactly what is needed by the original set-based analyses of Heintze and Jaffar [1990], or Heintze [1994].
Categories and Subject Descriptors: D.1 [Programming Techniques]; E.1 [Data Structures]; G.2.2 [Discrete Mathematics]: Graph Theory; F.2 [Analysis of Algorithms and Problem Complexity]
Additional Key Words and Phrases: infinite trees, sharing, tree skeletons, cartesian approximation
Selected references
- Jiazhen Cai and Robert Paige. Using multiset discrimination to solve language processing problems without hashing. Theoretical Computer Science, 145(1-2):189-228, 10 July 1995.
- A. Cardon and M. Crochemore. Partitioning a graph in O(|A| log_2 |V|). Theoretical Computer Science, 19(1):85-98, July 1982.
- Nevin Heintze and Joxan Jaffar. A finite presentation theorem for approximating logic programs. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 197-209, San Francisco, California, January 1990.
- Neil D. Jones and Steven S. Muchnick. Flow analysis and optimization of Lisp-like structures. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pages 244-256, San Antonio, Texas, January 1979.