一句话：提出对数高度森林代数表示框架，实现树上 MSO 查询在局部更新下的高效答案枚举。
本文关注无秩树的动态表示与查询枚举问题。作者提出一种维护森林代数表示的框架，可在线性时间 O(n) 内构建，并在局部更新后以 O(log(n)) 时间更新，且表示高度为对数级。作为示例应用，该框架被用于在树发生局部更新时高效枚举 MSO 可定义查询的答案。算法以表示 MSO 查询的节点选择树自动机为形式化基础：预处理耗时 O(n)，枚举答案的延迟为 O(log(n))；当树更新后，可避免昂贵重预处理，并在 O(log(n)) 时间内重启枚举。该框架对复杂度依赖树深度的树数据结构与算法有潜在价值。
We describe a framework for maintaining forest algebra representations that are of logarithmic height for unranked trees. Such representations can be computed in O(n) time and updated in O(log(n)) time. The framework is of potential interest for data structures and algorithms for trees whose complexity depend on the depth of the tree (representation). We provide an exemplary application of the framework to the problem of efficiently enumerating 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. Our algorithms and complexity results in the paper are presented in terms of node-selecting tree automata representing the MSO queries.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2208-04180,
title = {MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras},
author = {Sarah Kleest-Meißner and Jonas Marasus and Matthias Niewerth},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 4},
year = {2025},
doi = {10.46298/lmcs-21(4:2)2025}
}