JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Complexity of Reasoning in Kleene Algebra

Author
Kozen, Dexter
Abstract
We study the complexity of reasoning in Kleene algebra and *-continuous Kleene algebra in the presence of extra equational assumptions $E$; that is, the complexity of deciding the validity of universal Horn formulas $E\imp s=t$, where $E$ is a finite set of equations. We obtain various levels of complexity based on the form of the assumptions $E$. Our main results are: for *-continuous Kleene algebra, \begin{itemize} \item if $E$ contains only commutativity assumptions $pq=qp$, the problem is $\Pi_1^0$-complete; \item if $E$ contains only monoid equations, the problem is $\Pi_2^0$-complete; \item for arbitrary equations $E$, the problem is $\Pi_1^1$-complete. \end{itemize} The last problem is the universal Horn theory of the *-continuous Kleene algebras. This resolves an open question of Kozen (1994).
Date Issued
1997-03Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR97-1624
Type
technical report