Star-Height of Parikh Images over Infinite Alphabets

Prelegent(ci)

Yoav Danieli

Afiliacja

Technion Institute of Technology

Język referatu

angielski

Termin

13 listopada 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

Star-Height of Parikh Images over Infinite Alphabets

Seminarium

Seminarium „Teoria automatów”

---

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.

---