Guest editor's introduction: Special issue on Relation Algebra and Kleene Algebra

摘要

Relation Algebra was originally introduced for compacting first-order logic formulas, by eliminating certain quantifiers, into a form that is amenable to simple algebraic manipulation, i.e., (in)equational reasoning. While initially only a fragment of predicate logic was covered, full expressiveness was achieved by the extension to Fork Algebra. In parallel, Kleene Algebra, originating in formal language theory, developed into a general algebraic system for calculating with sequential composition, choice and finite iteration. More recently it has also been extended to deal with infinite iteration and modal operators. Relation Algebra and Kleene Algebra fit well together, since the former is an enrichment of the latter by the operation of conversion and additional axioms. In the recent years, applications of both approaches to a wide variety of problems in practical and theoretical computer science have emerged. The present special issue is intended to show a number of substantial samples of this. They were selected from the submissions in a strict and thorough refereeing process.