Parikh Theorem for Infinite alphabets

We investigate commutative images of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of only finite ones. We prove that commutative images of languages of one-register automata are not always semi-linear, but they are always rational. We also lift the latter result to grammars: commutative images of one-register context-free languages are rational, and in consequence commutatively equivalent to register automata. We conjecture analogous results for automata and grammars with arbitrarily many registers. This is a joint work with Piotr Hofman, Marta Juzepczuk, Sławomir Lasota.

Authors

• Mohnish Pattathurajan

Keywords

No keywords are indexed for this paper.