Inproceedings3383

PublikationenPublications

• Nach AutorBy Author
  • Luisa HerrmannLuisa Herrmann
• Nach ForschungsgruppeBy Research Group
  • Computational LogicComputational Logic

Toggle side column

Global One-Counter Tree Automata

Luisa HerrmannLuisa Herrmann,  Richard MörbitzRichard Mörbitz

• ISBN: 978-3-031-71111-4
• DOI Link

Luisa Herrmann, Richard Mörbitz
Global One-Counter Tree Automata
In Szilárd Zsolt Fazekas, eds., 28th International Conference on Implementation and Application of Automata (CIAA 2024), volume 15015 of Lecture Notes in Computer Science, 166--179, September 2024. Springer

• Details
• Bibtex

• KurzfassungAbstract
  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.
• Weitere Informationen unter:Further Information: Link
• Projekt:Project: ScaDS.AI
• Forschungsgruppe:Research Group: Computational LogicComputational Logic

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-031-71112-1_12.

@inproceedings{HM2024,
  author    = {Luisa Herrmann and Richard M{\"{o}}rbitz},
  title     = {Global One-Counter Tree Automata},
  editor    = {Szil{\'{a}}rd Zsolt Fazekas},
  booktitle = {28th International Conference on Implementation and Application
               of Automata (CIAA 2024)},
  series    = {Lecture Notes in Computer Science},
  volume    = {15015},
  publisher = {Springer},
  year      = {2024},
  month     = {September},
  pages     = {166--179},
  doi       = {10.1007/978-3-031-71112-1_12}
}