Improving the Representation of Infinite Trees to Deal with Sets of Trees

Laurent Mauborgne.
Improving the Representation of Infinite Trees to Deal with Sets of Trees.
In G. Smolka, editor, European Symposium on programming (ESOP 2000), volume 1782 of Lecture Notes in Computer Science, pages 275--289.
Springer-Verlag, 2000.
Compressed PostScript (109K), DVI (172K), PDF (325K).
Abstract: In order to deal efficiently with infinite regular trees (or other pointed graph structures), we give new algorithms to store such structures. The trees are stored in such a way that their representation is unique and shares as much as possible. This maximal sharing allows substantial memory gain and speed up. For example, equality testing becomes constant time. The algorithms are incremental, and as such allow good reactive behavior. These new algorithms are then applied to the representation of sets of trees. The expressive power of this new representation is exactly what is needed by set-based analysis.

\bibitem{mauborgn00a}
{\sc Mauborgne, L.}
\newblock Improving the representation of infinite trees to deal with sets of
  trees.
\newblock In {\em European Symposium on Programming (ESOP 2000)\/} (2000),
  G.~Smolka, Ed., vol.~1782 of {\em Lecture Notes in Computer Science},
  Springer-Verlag, pp.~275--289.

@inproceedings{mauborgn00a,
author = "Laurent Mauborgne",
title = "Improving the Representation of Infinite Trees to Deal with Sets of
Trees",
booktitle = "European Symposium on Programming (ESOP 2000)",
year = 2000,
volume = 1782,
editor = "G. Smolka",
pages = "275--289",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag" }

Email: Laurent.Mauborgne@ens.fr