Skip to main content

Parikh's Theorem through the ages (technical tutorial)

Dmitry Chistikov ( University of Oxford )

The Parikh theorem (1961) states that the commutative image of every context-free language is a semi-linear set (an ultimately periodic set in N^d). Put differently, every context-free language can be represented by a finite-state automaton---if two words are considered the same whenever they agree on the number of occurrences of each letter.

This theorem has become a standard tool in the theory of infinite-state systems, with many different proofs of the original statement and many extensions.

In this talk, we will survey constructions and ideas behind several proofs of this theorem, from Parikh's original construction to recent developments.

We will also see how the ideas behind these proofs apply in different contexts.

Short bio

Dmitry Chistikov is a research assistant at the University of Oxford, UK, hosted by Joël Ouaknine. Before that, he was a postdoctoral researcher at the Max Planck Institute for Software Systems in Kaiserslautern, Germany.

He obtained his PhD in 2011 at Moscow State University, Russia.

His research interests lie in theoretical computer science and verification.


Share this: