一句话：本文给出树上的 MSO 查询在局部更新下的高效枚举算法，预处理 O(n)，答案延迟 O(log n)，更新后 O(log n) 恢复。
本文研究在树经历局部更新时，如何高效枚举 MSO 可定义查询的全部答案。作者以节点选择树自动机表示 MSO 查询，提出一种枚举算法：预处理耗时 O(n)，枚举答案时相邻答案延迟为 O(log n)；当树发生局部更新后，无需从头预处理，可在 O(log n) 时间内重启枚举。该结果改进了此前需要 O(log^2 n) 更新时间和 O(log^2 n) 延迟的工作。为构造算法，论文还引入森林代数公式语法树的平衡方案，该技术本身有望把字符串上的结果提升到树上。
We investigate efficient enumeration of answers to MSO-definable queries over trees which are subject to local updates. We exhibit an algorithm that uses an O(n) preprocessing phase and enumerates answers with O(log(n)) delay between them. When the tree is updated, the algorithm can avoid repeating expensive preprocessing and restart the enumeration phase within O(log(n)) time. This improves over previous results that require O(log2(n)) time after updates and have O(log2(n)) delay. Our algorithms and complexity results in the paper are presented in terms of node-selecting tree automata representing the MSO queries. To present our algorithm, we introduce a balancing scheme for parse trees of forest algebra formulas that is of its own interest to lift results from strings to trees.
DOI 原文 ·
@inproceedings{paperbot4329,
title = {MSO Queries on Trees},
author = {Matthias Niewerth},
booktitle = {LICS},
year = {2018},
doi = {10.1145/3209108.3209144}
}