Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Sixth Annual IEEE Symposium on

Logic in Computer Science (LICS 1991)

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
Authors: 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}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski