2026-09-18T02:36:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24115 2026-09-05T18:33:15Z ddc:004 open_access

Dynamic Membership for Regular Tree Languages Amarilli, Antoine Barloy, Corentin Jachiet, Louis Paperman, Charles automaton dynamic membership incremental maintenance forest algebra We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet Σ and a regular tree language L over Σ (expressed, e.g., as a tree automaton), we are given a tree T with labels in Σ, and we must maintain the information of whether the tree T belongs to L while handling relabeling updates that change the labels of individual nodes in T. Our first contribution is to show that this problem admits an O(log n / log log n) algorithm for any fixed regular tree language, improving over known O(log n) algorithms. This generalizes the known O(log n / log log n) upper bound over words, and it matches the lower bound of Ω(log n / log log n) from dynamic membership to some word languages and from the existential marked ancestor problem. Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be decided in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages: they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i.e., a letter that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that the prefix-U1 problem from [Antoine Amarilli et al., 2021] also does not admit a constant-time algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Amarilli and Corentin Barloy and Louis Jachiet and Charles Paperman 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.8 urn:nbn:de:0030-drops-241155 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode