Enumeration of monadic second-order queries on trees
Enumeration of monadic second-order queries on trees
复制标题
树上一元二阶查询的枚举
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Segoufin
中科院分区：
文献类型：
--
作者：
Wojciech Kazana;L. Segoufin
本文研究树上一阶自由变量的一元二阶查询的枚举问题。在Bagan [2006]中，证明了这个问题存在于常数延迟中。一个枚举问题属于常数-延迟，如果对于一个大小为n的输入结构，它可以通过以下方式解决：
- O（n）预计算阶段，构建索引结构，
- 随后是枚举答案的阶段，没有重复，两个连续输出之间有恒定的延迟。
本文基于Colcombet [2007]的确定性因子分解森林分解定理给出了这个结果的一个不同的证明。
We consider the enumeration problem of Monadic Second-Order (MSO) queries with first-order free variables over trees. In Bagan [2006] it was shown that this problem is in CONSTANT-DELAYlin. An enumeration problem belongs to CONSTANT-DELAYlin if for an input structure of size n it can be solved by:
—an O(n) precomputation phase building an index structure,
—followed by a phase enumerating the answers with no repetition and a constant delay between two consecutive outputs.
In this article we give a different proof of this result based on the deterministic factorization forest decomposition theorem of Colcombet [2007].