Global One-Counter Tree Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929394195365888 |
|---|---|
| author | Herrmann, Luisa Mörbitz, Richard |
| author_facet | Herrmann, Luisa Mörbitz, Richard |
| contents | We introduce global one-counter tree automata (GOCTA) which deviate from usual counter tree automata by working on only one counter which is passed through the tree in lexicographical order, rather than duplicating the counter at every branching position. We compare the capabilities of GOCTA to those of counter tree automata and obtain that their classes of recognizable tree languages are incomparable. Moreover, we show that the emptiness problem of GOCTA is undecidable while, in stark contrast, their membership problem is in P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15090 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Global One-Counter Tree Automata Herrmann, Luisa Mörbitz, Richard Formal Languages and Automata Theory We introduce global one-counter tree automata (GOCTA) which deviate from usual counter tree automata by working on only one counter which is passed through the tree in lexicographical order, rather than duplicating the counter at every branching position. We compare the capabilities of GOCTA to those of counter tree automata and obtain that their classes of recognizable tree languages are incomparable. Moreover, we show that the emptiness problem of GOCTA is undecidable while, in stark contrast, their membership problem is in P. |
| title | Global One-Counter Tree Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2406.15090 |