2 papers
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.FL2015
Linear Context-Free Tree Languages and Inverse Homomorphisms
Johannes Osterholzer, Toni Dietze, Luisa Herrmann
We prove that the class of linear context-free tree languages is not closed under inverse linear tree homomorphisms. The proof is by contradiction: we encode Dyck words into a cont…