Global one-counter tree automata

Luisa HerrmannLuisa Herrmann, Richard MörbitzRichard Mörbitz

DOI Link

Luisa Herrmann, Richard Mörbitz
Global one-counter tree automata
Theoretical Computer Science, 1071, 2026

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 membership problem of GOCTA is in P while, in stark contrast, their emptiness problem is undecidable in general. For the special case of reversal-bounded GOCTA, we show decidability of the emptiness problem.
Projekt:Project: ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{HM2026,
  author    = {Luisa Herrmann and Richard M{\"{o}}rbitz},
  title     = {Global one-counter tree automata},
  journal   = {Theoretical Computer Science},
  volume    = {1071},
  publisher = {Elsevier},
  year      = {2026},
  doi       = {https://doi.org/10.1016/j.tcs.2026.115840}
}