10 Parikh's Theorem in Commutative Kleene Algebra January 15, 1999 CS-TR-v2.1 Hopkins, Mark Kozen, Dexter CORNELLCS:TR99-1724 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 and Pilling's theorems are special cases: Every system of polynomial inequalities $f_i(x_1,\ldots,x_n) \leq x_i$, $1\leq i\leq n$, over a commutative Kleene algebra $K$ has a unique least solution in $K^n$; moreover, the components of the solution are given by polynomials in the coefficients of the $f_i$. We also give a closed-form solution in terms of the Jacobian matrix. January 4, 1999