Parikh's theorem in commutative Kleene algebra
Mark Hopkins, Dexter C. Kozen · 2003
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 finite system of polynomial inequalities f/sub i/(x/sub 1/,...,x/sub n/)/spl les/x/sub i/, 1/spl les/i/spl les/n, over a commutative Kleene algebra K has a unique least solution in K/sup n/; moreover, the components of the solution are given by polynomials in the coefficients of the f/sub i/. We also give a closed-form solution in terms of the Jacobian matrix of the system.