Sarah Kleest-Meißner ; Jonas Marasus ; Matthias Niewerth - MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras

lmcs:10956 - Logical Methods in Computer Science, October 3, 2025, Volume 21, Issue 4 - https://doi.org/10.46298/lmcs-21(4:2)2025
MSO Queries on Trees: Enumerating Answers under Updates Using Forest AlgebrasArticle

Authors: Sarah Kleest-Meißner ; Jonas Marasus ; Matthias Niewerth

    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.


    Volume: Volume 21, Issue 4
    Published on: October 3, 2025
    Imported on: February 14, 2023
    Keywords: Logic in Computer Science, Data Structures and Algorithms

    Consultation statistics

    This page has been seen 503 times.
    This article's PDF has been downloaded 177 times.