## Paper: A completeness theorem for Kleene algebras and the algebra of regular events (at LICS 1991)

*Winner of the Test-of-Time Award in 2011***Dexter C. Kozen**

### Abstract

A finitary axiomatization of the algebra of regular events involving only equations and equational implications that is sound for all interpretations over Kleene algebras is given. Axioms for Kleene algebra are presented, and some basic consequences are derived. Matrices over a Kleene algebra are considered. The notion of an automaton over an arbitrary Kleen algebra is defined and used to derive the classical results of the theory of finite automata as a result of the axioms. The completeness of the axioms for the algebra of regular events is treated. Open problems are indicated

### BibTeX

@InProceedings{Kozen-Acompletenesstheore, author = {Dexter C. Kozen}, title = {A completeness theorem for Kleene algebras and the algebra of regular events }, booktitle = {Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science (LICS 1991)}, year = {1991}, month = {July}, pages = {214--225}, location = {Amsterdam, The Netherlands}, publisher = {IEEE Computer Society Press} }