Tree Automata with Global and Non-Global Counting

Talk by Luisa Herrmann

Location: APB 3027
Start: 12. December 2024 at 11:00 am
End: 12. December 2024 at 12:00 pm
Research group: Computational Logic
Event series: Research Seminar Logic and AI
iCal

Similar to the case of finite string automata, there is a long tradition of adding counting mechanisms to finite tree automata in order to increase their expressiveness, resulting in two interesting models (among others): Parikh tree automata (PTA) increment a number of counters when computing a tree and eventually test their membership in a semilinear set. On the other hand, one-counter tree automata (OCTA) use only one counter that can be incremented, decremented and tested for zero during a computation. The calculation principles for the counting mechanisms work orthogonally in both approaches – while OCTA split their computations at each node and execute them pathwise, PTA allow a global view: their counters are incremented over the whole input tree. When comparing the expressive power of the two models, one will find differences that stem not only from the specific storage types used, but also from the global or non-global view of the input.

This talk will report on two recent works, where we exchanged the computation mode of both tree automata models:

We introduce global one-counter tree automata (GOCTA) deviating from OCTA by working on one counter which is passed through the tree in lexicographical order, rather than duplicating the counter at every branching position. When comparing the capabilities of GOCTA and OCTA, we obtain that their classes of recognizable tree languages are incomparable. Moreover, we show that the non-emptiness problem of GOCTA is undecidable while, in stark contrast, their membership problem is in P.

In a similar spirit, we define a non-global version of Parikh tree automata. Here, we copy and distribute the current configuration at each node to all its children, incrementing the counters pathwise, and check the arithmetic constraint at each leaf. Again we obtain that, in contrast to the original definition of PTA, non-emptiness becomes undecidable if we allow the automaton to use at least three counters. However, we can prove decidability of non-emptiness for a (still powerful) restriction of the model.