Star-Height of Parikh Images over Infinite Alphabets

Speaker(s)

Yoav Danieli

Affiliation

Technion Institute of Technology

Language of the talk

English

Date

Nov. 13, 2026, 2:15 p.m.

Room

room 5440

Title in Polish

Star-Height of Parikh Images over Infinite Alphabets

Seminar

Seminar Automata Theory

---

Parikh’s theorem states that context-free grammars and finite-state automata have the same expressive power when letter order is forgotten. Their counting vectors form precisely the semi-linear sets, characterized both algebraically and by Presburger arithmetic.

We study this commutative perspective over infinite alphabets, where the natural algebraic extension admits rational expressions with nested stars. Their complexity is measured by star height: the minimum nesting depth required to define a set. We present star-height results for register automata and grammars and show that their expressive gap survives commutation: some register context-free languages have no commutatively equivalent register automaton.

---