Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/7378
Title: Parikh's Theorem in Commutative Kleene Algebra
Authors: Hopkins, Mark
Kozen, Dexter
Keywords: computer science
technical report
Issue Date: Jan-1999
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR99-1724
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.
URI: http://hdl.handle.net/1813/7378
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
99-1724.pdf235.27 kBAdobe PDFView/Open
99-1724.ps488.52 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us