Parikh Automata are equivalent to RBCM in their nondeterministic variant. It is known that the complement of the language of palindromes is not recognizable by a Parikh automaton. This is shown in the extended version of the paper introducing the model, by Klaedtke and Rueß (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.8019). Further techniques have been developed to show that some languages are outside this class (we present a few in this journal paper).
Michaël Cadilhac
- 4k
- 23
- 39