JavaScript is disabled for your browser. Some features of this site may not work without it.
On Kleene Algebras and Closed Semirings

Author
Kozen, Dexter
Abstract
Kleene algebras are an important class of algebraic structures that arise in diverse areas of computer science: program logic and semantics, relational algebra, automata theory, and the design and analysis of algorithms. The literature contains at several inequivalent definitions of Kleene algebras and related algebraic structures [2, 13, 14, 5, 6, 1, 9, 7]. In this paper we establish some new relationships among these structures. Our main results are: (1) There is a Kleene algebra in the sense of [6] that is not *-continuous. (2) The categories of *-continuous Kleene algebras [5, 6], closed semirings [1, 9] and S-algebras [2] are strongly related by adjunctions. (3) The axioms of Kleene algebra in the sense of [6] are not complete for the universal Horn theory of the regular events. This refutes a conjecture of Conway [2, p. 103]. (4) Right-handed Kleene algebras are not necessarily left-handed Kleene algebras. This verifies a weaker version of a conjecture of Pratt [14].
Date Issued
1990-05Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1131
Type
technical report