Improving the Representation of Infinite Trees to Deal with Sets of Trees
Improving the Representation of Infinite Trees to Deal with Sets of Trees
复制标题
改进无限树的表示以处理树集
DOI：
10.1007/3-540-46425-5_18
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Laurent Mauborgne
中科院分区：
文献类型：
--
作者：
Laurent Mauborgne
为了有效地处理无限正则树(或其他有向图结构)，我们给出了存储这种结构的新算法。这些树以这样一种方式存储，即它们的表示是唯一的，并且尽可能地共享。这种最大程度的共享可以显著增加内存并提高速度。例如，相等性测试就变成了恒定的时间。算法是递增的，因此允许良好的反应行为。然后将这些新算法应用到树集的表示中。这种新表示的表现力正是基于集合的分析所需要的。
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. This 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.