## Paper: Parikh's Theorem in Commutative Kleene Algebra (at LICS 1999)

**Mark W. Hopkins Dexter C. Kozen**

### Abstract

Parikh's Theorem says that the commutative image of every context free language is the commutative image of some regular set. Pilling has shown that this theorem is essentially a statement about least solutions of polynomial inequalities. We prove the following general theorem of commutative Kleene algebra, of which Parikh's theorem is a special case: Every system of polynomial inequalities fi(x1,...,xn) \mathxi, 1 \mathi \math, over a commutative Kleene algebra K has a unique least solution in Kn; moreover, the components of the solution are given by polynomials in the coefficients of the fi. We also give a closed-form solution in terms of the Jacobian of the system.

### BibTeX

@InProceedings{HopkinsKozen-ParikhsTheoreminCom, author = {Mark W. Hopkins and Dexter C. Kozen}, title = {Parikh's Theorem in Commutative Kleene Algebra}, booktitle = {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)}, year = {1999}, month = {July}, pages = {394--401}, location = {Trento, Italy}, publisher = {IEEE Computer Society Press} }