Non-Global Parikh Tree Automata

Luisa HerrmannLuisa Herrmann, Johannes OsterholzerJohannes Osterholzer

DOI Link

Luisa Herrmann, Johannes Osterholzer
Non-Global Parikh Tree Automata
In Florin Manea, Giovanni Pighizzini, eds., 14th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2024), volume 407 of Electronic Proceedings in Theoretical Computer Science, 100--117, 2024. OPA

Details
Bibtex

KurzfassungAbstract
Parikh (tree) automata are an expressive and yet computationally well-behaved extension of finite automata – they allow to increment a number of counters during their computations, which are finally tested by a semilinear constraint. In this work, we introduce and investigate a new perspective on Parikh tree automata (PTA): instead of testing one counter configuration that results from the whole input tree, we implement a non-global automaton model. Here, we copy and distribute the current configuration at each node to all its children, incrementing the counters pathwise, and check the arith- metic constraint at each leaf. We obtain that the classes of tree languages recognizable by global PTA and non-global PTA are incomparable. In contrast to global PTA, the non-emptiness problem is undecidable for non-global PTA if we allow the automata to work with at least three counters, whereas the membership problem stays decidable. However, for a restriction of the model, where counter configurations are passed in a linear fashion to at most one child node, we can prove decidability of the non-emptiness problem.
Projekt:Project: ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{HO2024,
  author    = {Luisa Herrmann and Johannes Osterholzer},
  title     = {Non-Global Parikh Tree Automata},
  editor    = {Florin Manea and Giovanni Pighizzini},
  booktitle = {14th International Workshop on Non-Classical Models of Automata
               and Applications (NCMA 2024)},
  series    = {Electronic Proceedings in Theoretical Computer Science},
  volume    = {407},
  publisher = {OPA},
  year      = {2024},
  pages     = {100--117},
  doi       = {10.4204/EPTCS.407.8}
}