An Incremental Unique Representation for Regular Trees

Laurent Mauborgne.
An Incremental Unique Representation for Regular Trees.
Nordic Journal of Computing, 7(4):290--311, 2000.
Compressed PostScript (212K), DVI (230K), PDF (282K).
Abstract: In 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 \cite{heintze:jaffar90a}, or \cite{heintze94}.

\bibitem{mauborgne00c}
{\sc Mauborgne, L.}
\newblock An incremental unique representation for regular trees.
\newblock {\em Nordic Journal of Computing 7}, 4 (2000), 290--311.

@article{mauborgne00c,
author = "Laurent Mauborgne",
title = "An Incremental Unique Representation for Regular Trees",
journal = "Nordic Journal of Computing",
volume = 7,
number = 4,
year = 2000,
pages = "290--311" }

Email: Laurent.Mauborgne@ens.fr