Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.17536 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916909655523328 |
|---|---|
| author | Amarilli, Antoine Barloy, Corentin Jachiet, Louis Paperman, Charles |
| author_facet | Amarilli, Antoine Barloy, Corentin Jachiet, Louis Paperman, Charles |
| contents | 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 (Amarilli, Jachiet, Paperman, ICALP'21) also does not admit a constant-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17536 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dynamic Membership for Regular Tree Languages Amarilli, Antoine Barloy, Corentin Jachiet, Louis Paperman, Charles Formal Languages and Automata Theory Data Structures and Algorithms 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 (Amarilli, Jachiet, Paperman, ICALP'21) also does not admit a constant-time algorithm. |
| title | Dynamic Membership for Regular Tree Languages |
| topic | Formal Languages and Automata Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.17536 |