Commutative Images of Languages Over Infinite Alphabets

Commutative images (Parikh images) are extensively studied for languages of finite automata and context-free grammars over finite alphabets. Parikh’s theorem is a well-known fundamental result stating that Parikh images of finite automata and context-free languages are equal, and coincide with semi-linear sets of vectors. In this thesis, we explore Parikh images for a widely studied extension of finite automata, non-deterministic register automata, which in contrast to a finite automata, input words over infinite alphabets. Our main objective is establishing to what extent Parikh’s theorem keeps holding true when one extends the setting from finite alphabets to infinite ones. As the first step, we demonstrate that semi-linear sets (suitably extended to infinite alpha bets) are not sufficient even for capturing Parikh images of one-register automata, and propose a larger class of rational sets (also suitably extended to infinite alphabets) in place thereof. This is motivated by the fact that in finite-alphabet case, semi-linear sets and rational sets of vec tors coincide. As our main result we obtain a version of Parikh’s theorem for non-deterministic one-register automata: Parikh images of their languages are always rational. Building on this result, we prove rationality of languages of hierarchical register automata, a syntactic subclass of non-deterministic register automata strictly extending one-register automata. Furthermore, also building on the main result, we show that the language of every one-register context-free grammar has rational Parikh image, and is therefore Parikh-equivalent to the language of some non-deterministic (and even hierarchical) register automaton. All the above-mentioned results may be seen as a partial confirmation of validity of Parikh’s theorem in the setting of infinite alphabets. Nevertheless, it still remains open if Parikh images of languages of all non-deterministic register automata are rational. Likewise, we do not know if the same property holds for languages of all context-free grammars. If this property holds, it would yield the full generalisation of Parikh’s theorem to infinite alphabets.