3 papers
cs.FL2026
On smallest synchronizing terms over constant alphabets
Luisa Herrmann, Richard Mörbitz
We show a subexponential lower bound on the reset threshold of synchronizing deterministic finite tree automata (DTA) over alphabets of just two symbols. This significantly improve…
cs.FL2024
Non-Global Parikh Tree Automata
Luisa Herrmann, Johannes Osterholzer
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…
cs.FL2024
Global One-Counter Tree Automata
Luisa Herrmann, Richard Mörbitz
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 lexicographi…