Paper: Star Complexity of Parikh Images of Languages over Infinite Alphabets (at LICS 2026)

Authors: Yoav Danieli

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.35

Abstract

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.

BibTeX

  @InProceedings{Danieli-StarComplexityofPar,
    author = 	 {Yoav Danieli},
    title = 	 {Star Complexity of Parikh Images of Languages over Infinite Alphabets},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {35:1--35:26},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.35}
  }