Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
复制标题
具有易于处理的组合复杂性和高效更新的树枚举
DOI：
10.1145/3294052.3319702
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Matthias Niewerth
中科院分区：
文献类型：
--
作者：
Antoine Amarilli;P. Bourhis;S. Mengel;Matthias Niewerth
我们给出了一个算法来枚举树的一元二阶（MSO）查询表示的不确定树自动机的结果。在线性时间预处理（在输入树中）之后，我们可以枚举具有线性延迟的答案（在每个答案中）。我们允许在树上的更新在任何时候发生，然后我们可以在树中的对数时间之后重新开始枚举。此外，我们所有的组合复杂度在自动机中是多项式的。我们的结果遵循我们以前的基于电路的枚举算法的基础上确定性树自动机，也受到我们以前的结果的启发，在文档speries的上下文中的单词和非确定性顺序扩展变量集自动机。我们扩展了这些结果，并将它们与Niewerth最近的树平衡计划联合收割机相结合，使我们的枚举结构支持在对数时间内更新底层树（叶插入，叶删除和节点重新标记）。我们的结果意味着，对于MSO查询与自由的一阶变量，我们可以枚举的结果与线性预处理和常数延迟和更新的基础树在对数时间，这改善了几个已知的结果的话和树。从数据结构研究的下限的基础上，我们还无条件地表明，我们的算法的更新时间的双对数因子是最佳的。因此，与其他设置不同，不可能存在具有恒定更新时间的算法。
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the input tree), we can enumerate answers with linear delay (in each answer). We allow updates on the tree to take place at any time, and we can then restart the enumeration after logarithmic time in the tree. Further, all our combined complexities are polynomial in the automaton. Our result follows our previous circuit-based enumeration algorithms based on deterministic tree automata, and is also inspired by our earlier result on words and nondeterministic sequential extended variable-set automata in the context of document spanners. We extend these results and combine them with a recent tree balancing scheme by Niewerth, so that our enumeration structure supports updates to the underlying tree in logarithmic time (with leaf insertions, leaf deletions, and node relabelings). Our result implies that, for MSO queries with free first-order variables, we can enumerate the results with linear preprocessing and constant-delay and update the underlying tree in logarithmic time, which improves on several known results for words and trees. Building on lower bounds from data structure research, we also show unconditionally that up to a doubly logarithmic factor the update time of our algorithm is optimal. Thus, unlike other settings, there can be no algorithm with constant update time.
在有界度数据库更新下回答 FO MOD 查询
DOI：
10.1145/3232056
发表时间：
2017
期刊：
ACM Transactions on Database Systems (TODS)
影响因子：
--
作者：
Christoph Berkholz;Jens Keppeler;Nicole Schweikardt
通讯作者：
Nicole Schweikardt
MSO 对树的查询：枚举更新下的答案
DOI：
10.1145/2603088.2603137
发表时间：
2014
期刊：
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
影响因子：
--
作者：
Katja Losemann;Wim Martens
通讯作者：
Wim Martens