Logic in Computer Science (LICS 1991)

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

Authors: Dexter 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 Kozen},
    title = 	 {A completeness theorem for Kleene algebras and the algebra of regular events },
    booktitle =  {Proceedings of the Sixth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1991},
    year =	 1991,
    editor =	 {Giles Kahn},
    month =	 {July}, 
    pages =      {214--225},
    location =   {Amsterdam, The Netherlands}, 
    publisher =	 {IEEE Computer Society Press}
  }