Parikh's Theorem in Commutative Kleene Algebra
| dc.contributor.author | Hopkins, Mark | en_US |
| dc.contributor.author | Kozen, Dexter | en_US |
| dc.date.accessioned | 2007-04-23T18:15:50Z | |
| dc.date.available | 2007-04-23T18:15:50Z | |
| dc.date.issued | 1999-01 | en_US |
| dc.description.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 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. | en_US |
| dc.format.extent | 240918 bytes | |
| dc.format.extent | 500240 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR99-1724 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7378 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Parikh's Theorem in Commutative Kleene Algebra | en_US |
| dc.type | technical report | en_US |