Global One-Counter Tree Automata.
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
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.
Details
| Original language | English |
|---|---|
| Title of host publication | Implementation and Application of Automata |
| Editors | Szilárd Zsolt Fazekas |
| Publisher | Springer |
| Pages | 166-179 |
| Number of pages | 14 |
| ISBN (electronic) | 978-3-031-71112-1 |
| ISBN (print) | 978-3-031-71111-4 |
| Publication status | Published - 2024 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Computer Science, Volume 15015 |
|---|---|
| ISSN | 0302-9743 |
Conference
| Title | 28th International Conference on Implementation and Application of Automata |
|---|---|
| Abbreviated title | CIAA 2024 |
| Conference number | 28 |
| Duration | 3 - 6 September 2024 |
| Website | |
| Degree of recognition | International event |
| Location | Atorion |
| City | Akita |
| Country | Japan |
External IDs
| Scopus | 85204379955 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- global counter, one-counter automata, tree automata