We study the dynamic membership problem for regular tree languages under
relabeling updates: we fix an alphabet ${\Sigma}$ and a regular tree language
$L$ over ${\Sigma}$ (expressed, e.g., as a tree automaton), we are given a tree
$T$ with labels in ${\Sigma}$, 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$. (The shape and size of the tree remain the
same throughout.)
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 algorithms that achieve $O(\log n)$. This generalizes the known $O(\log n
/ \log \log n)$ upper bound over words, and it matches the lower bound of
${\Omega}(\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 done in constant time per update.
Almost-commutative languages generalize both commutative languages and finite
languages, and 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 prefix-U1 problem from
(Amarilli, Jachiet, Paperman, ICALP’21) also does not admit a constant-time
algorithm.

Este artículo explora los viajes en el tiempo y sus implicaciones.

Descargar PDF: