Grammar-Based Compression of Unranked Trees
Grammar-Based Compression of Unranked Trees
复制标题
DOI：
10.1007/s00224-019-09942-y
复制
发表时间：
2018-02
影响因子：
0.5
通讯作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber
中科院分区：
文献类型：
--
作者：
Adrià Gascón;Markus Lohrey;S. Maneth;C. Reh;K. Sieber
我们引入森林直线规划(FSLP)作为无等级有序节点标记树的压缩表示。FSLP基于森林代数的运算，推广了树的直线规划。我们将FSLP的简洁性与其他两种未排序树的压缩方案进行了比较：Top DAG和第一个孩子/下一个兄弟姐妹编码的树直线程序。提供了这些形式主义之间的有效翻译。最后，我们证明了在某些符号是结合的和/或可交换的情况下，可以在多项式时间内检验未排序树的等价性。这推广了以前测试压缩无序排序树同构的结果。这篇论文的扩展摘要发表在Gascóon等人(2018年)上。
We introduce forest straight-line programs (FSLPs for short) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative and/or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees. An extended abstract of this paper appeared in Gascóon et al.(2018).