Parikh’s theorem for infinite alphabets

We investigate commutative images (Parikh 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 finite ones. We prove the following. 1. Parikh Images of one-register automata are not always semi-linear but are rational 2. We extend the above result to one-register context-free grammar. We also conjecture the same holds for automata and grammars for arbitrarily many registers. This is joint work with Piotr Hofman, Marta Juzepczuk, and Sławek Lasota.