Technical Report No. 177 - Abstract

Felix Klaedtke, Harald Ruess
Parikh Automata and Monadic Second-Order Logics with Linear Cardinality Constraints

We contribute to the classical automaton-logic connection. On the one hand, we generalize the acceptance condition of word and tree automata by additionally requiring that the input satisfies certain arithmetic properties. On the other hand, we define extensions of monadic second-order logics on words and trees that allow us to compare cardinalities of sets. Although these extensions are undecidable we identify useful decidable fragments.