Star Complexity of Parikh Images of Languages over Infinite Alphabets
This resolves a long-standing conjecture about the rationality of Parikh images for register automata, providing both positive and negative results that clarify the limits of commutative expressiveness over infinite alphabets.
The paper proves that the Parikh image of any language recognized by a one-register automaton over an infinite alphabet has star height at most two, but shows that one-register context-free languages can have arbitrarily high star height. It also disproves the conjecture that Parikh images of languages recognized by automata with multiple registers are rational, demonstrating that Parikh's theorem fails for infinite alphabets.
It has been conjectured that the Parikh (commutative) image of every language over an infinite alphabet recognized by an automaton with registers is defined by a rational expression. This conjecture is known to hold for all languages recognized by one-register automata. We refine this result by proving that the star-height of the Parikh image of any language recognized by a one-register automaton is universally bounded by two. Furthermore, we show that one-register context-free languages have rational commutative images of arbitrarily high star height. We then disprove the conjecture for multiple registers, as well as disprove the equivalence of commutative expressive power between context-free grammars and automata over infinite alphabets. In other words, we show that Parikh's theorem fails for infinite alphabets.