# Parikh's theorem for infinite alphabets

arXiv: https://arxiv.org/abs/2104.12018 · HTML: https://mlsanity.com/paper/2104.12018/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [Solvability of orbit-finite systems of linear equations](https://mlsanity.com/paper/2201.09060/) (2022)

## Abstract (arXiv)

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.