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