Editing Kleene algebra

{{Short description|Idempotent semiring endowed with a closure operator}}
{{about|the Kleene algebra with a closure operation—a generalization of regular expressions|the Kleene algebra with involution—a generalization of Kleene's ternary logic—|Kleene algebra (with involution)}}

In [[mathematics]] and [[theoretical computer science]], a '''Kleene algebra''' ({{IPAc-en|ˈ|k|l|eɪ|n|i}} {{respell|KLAY|nee}}; named after [[Stephen Cole Kleene]]) is a [[semiring]] that generalizes the theory of [[regular expression]]s: it consists of a [[set (mathematics)|set]] supporting union (addition), concatenation (multiplication), and [[Kleene star]] operations subject to certain algebraic laws. The addition is required to be idempotent (<math>x + x = x</math> for all <math>x</math>), and induces a [[partially ordered set|partial order]] defined by <math>x \le y</math> if <math>x + y = y</math>. The Kleene star operation, denoted <math>x*</math>, must satisfy the laws of the [[closure operator]].<ref name="PoulyKohlas2012">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|page=246}}</ref>

Kleene algebras have their origins in the theory of regular expressions and [[regular language]]s introduced by Kleene in 1951 and studied by others including V.N. Redko and [[John Horton Conway]]. The term was introduced by [[Dexter Kozen]] in the 1980s, who fully characterized their algebraic properties and, in 1994, gave a finite axiomatization.

Kleene algebras have a number of extensions that have been studied, including Kleene algebras with tests (KAT) introduced by Kozen in 1997.<ref name=KAT>{{Cite journal |last=Kozen |first=Dexter |date=1997-05-01 |title=Kleene algebra with tests |url=https://dl.acm.org/doi/abs/10.1145/256167.256195 |journal=ACM Trans. Program. Lang. Syst. |volume=19 |issue=3 |pages=427–443 |doi=10.1145/256167.256195 |issn=0164-0925}}</ref> Kleene algebras and Kleene algebras with tests have applications in [[formal verification]] of computer programs.<ref>{{Cite book |last1=Kozen |first1=Dexter |last2=Smith |first2=Frederick |date=1997 |editor-last=van Dalen |editor-first=Dirk |editor2-last=Bezem |editor2-first=Marc |chapter=Kleene algebra with tests: Completeness and decidability |chapter-url=https://link.springer.com/chapter/10.1007/3-540-63172-0_43 |title=Computer Science Logic |series=Lecture Notes in Computer Science |volume=1258 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=244–259 |doi=10.1007/3-540-63172-0_43 |isbn=978-3-540-69201-0}}</ref> They have also been applied to specify and verify [[computer network]]s.<ref>{{Cite journal |last1=Anderson |first1=Carolyn Jane |last2=Foster |first2=Nate |last3=Guha |first3=Arjun |last4=Jeannin |first4=Jean-Baptiste |last5=Kozen |first5=Dexter |last6=Schlesinger |first6=Cole |last7=Walker |first7=David |date=2014-01-08 |title=NetKAT: semantic foundations for networks |url=https://dl.acm.org/doi/abs/10.1145/2578855.2535862 |journal=SIGPLAN Not. |volume=49 |issue=1 |pages=113–126 |doi=10.1145/2578855.2535862 |issn=0362-1340}}</ref>

== Definition ==

Various inequivalent definitions of Kleene algebras and related structures have been given in the literature.<ref>For a survey, see: {{cite book | zbl=0732.03047 | last=Kozen | first=Dexter | chapter=On Kleene algebras and closed semirings | title=Mathematical foundations of computer science, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990 | series=Lecture Notes Computer Science | volume=452 | pages=26–47 | year=1990 | author-link=Dexter Kozen | editor1-last=Rovan | editor1-first=Branislav | publisher=[[Springer-Verlag]] | chapter-url=http://ecommons.library.cornell.edu/bitstream/1813/6971/1/90-1131.pdf }}</ref> Here we will give the definition that seems to be the most common nowadays.

A Kleene algebra is a [[Set (mathematics)|set]] ''A'' together with two [[binary operation]]s + : ''A'' &times; ''A'' → ''A'' and · : ''A'' &times; ''A'' → ''A'' and one unary function <sup>*</sup> : ''A'' → ''A'', written as ''a'' + ''b'', ''ab'' and ''a''<sup>*</sup> respectively, so that the following axioms are satisfied.
* [[Associativity]] of + and ·: ''a'' + (''b'' + ''c'') = (''a'' + ''b'') + ''c'' and ''a''(''bc'') = (''ab'')''c'' for all ''a'', ''b'', ''c'' in ''A''.
* [[Commutativity]] of +: ''a'' + ''b'' = ''b'' + ''a'' for all ''a'', ''b'' in ''A''
* [[Distributivity]]: ''a''(''b'' + ''c'') = (''ab'') + (''ac'') and (''b'' + ''c'')''a'' = (''ba'') + (''ca'') for all ''a'', ''b'', ''c'' in ''A''
* [[Identity element]]s for + and ·: There exists an element 0 in ''A'' such that for all ''a'' in ''A'': ''a'' + 0 = 0 + ''a'' = ''a''. There exists an element 1 in ''A'' such that for all ''a'' in ''A'': ''a''1 = 1''a'' = ''a''.
* [[absorbing element|Annihilation]] by 0: ''a''0 = 0''a'' = 0 for all ''a'' in ''A''.
The above axioms define a [[semiring]]. We further require:
* + is [[idempotent]]: ''a'' + ''a'' = ''a'' for all ''a'' in ''A''.
It is now possible to define a [[partial order]] ≤ on ''A'' by setting ''a'' ≤ ''b'' [[if and only if]] ''a'' + ''b'' = ''b'' (or equivalently: ''a'' ≤ ''b'' if and only if there exists an ''x'' in ''A'' such that ''a'' + ''x'' = ''b''; with any definition, ''a'' ≤ ''b'' ≤ ''a'' implies ''a'' = ''b''). With this order we can formulate the last four axioms about the operation <sup>*</sup>:
* 1 + ''a''(''a''<sup>*</sup>) ≤ ''a''<sup>*</sup>  for all ''a'' in ''A''.
* 1 + (''a''<sup>*</sup>)''a'' ≤ ''a''<sup>*</sup>  for all ''a'' in ''A''.
* if ''a'' and ''x'' are in ''A'' such that ''ax'' ≤ ''x'', then ''a''<sup>*</sup>''x'' ≤ ''x''
* if ''a'' and ''x'' are in ''A'' such that ''xa'' ≤ ''x'', then ''x''(''a''<sup>*</sup>) ≤ ''x'' <ref>Kozen (1990), sect.2.1, p.3</ref>

Intuitively, one should think of ''a'' + ''b'' as the "union" or the "least upper bound" of ''a'' and ''b'' and of ''ab'' as some multiplication which is [[Monotonic function#Monotonicity in order theory|monotonic]], in the sense that ''a'' ≤ ''b'' implies ''ax'' ≤ ''bx''. The idea behind the star operator is ''a''<sup>*</sup> = 1 + ''a'' + ''aa'' + ''aaa'' + ... From the standpoint of [[programming language theory]], one may also interpret + as "choice", · as "sequencing" and <sup>*</sup> as "iteration".

== Examples ==

{| class="wikitable" style="float:right"
|+ Notational correspondence between 
|-
! [[#Definition|Kleene algebras]] and 
| + || · || <sup>*</sup> || 0 || 1
|-
! [[Regular expression#Formal language theory|Regular expressions]] 
| | | || not written  || <sup>*</sup> || ∅  || ε
|}
Let Σ be a finite set (an "alphabet") and let ''A'' be the set of all [[Regular expression#Formal language theory|regular expression]]s over Σ. We consider two such regular expressions equal if they describe the same [[formal language|language]]. Then ''A'' forms a Kleene algebra. In fact, this is a [[free object|free]] Kleene algebra in the sense that any equation among regular expressions follows from the Kleene algebra axioms and is therefore valid in every Kleene algebra.

Again let Σ be an alphabet. Let ''A'' be the set of all [[regular language]]s over Σ (or the set of all [[context-free language]]s over Σ; or the set of all [[recursive language]]s over Σ; or the set of ''all'' languages over Σ). Then the [[union (set theory)|union]] (written as +) and the [[concatenation#Concatenation of sets of strings|concatenation]] (written as ·) of two elements of ''A'' again belong to ''A'', and so does the [[Kleene star]] operation applied to any element of ''A''. We obtain a Kleene algebra ''A'' with 0 being the [[empty set]] and 1 being the set that only contains the [[empty string]].

Let ''M'' be a [[monoid]] with identity element ''e'' and let ''A'' be the set of all [[subset]]s of ''M''. For two such subsets ''S'' and ''T'', let ''S'' + ''T'' be the union of ''S'' and ''T'' and set ''ST'' = {''st'' : ''s'' in ''S'' and ''t'' in ''T''}. ''S''<sup>*</sup> is defined as the submonoid of ''M'' generated by ''S'', which can be described as {''e''} ∪ ''S'' ∪ ''SS'' ∪ ''SSS'' ∪ ... Then ''A'' forms a Kleene algebra with 0 being the empty set and 1 being {''e''}. An analogous construction can be performed for any small [[category theory|category]].

The [[linear subspace]]s of a unital [[algebra over a field]] form a Kleene algebra.  Given linear subspaces ''V'' and ''W'', define ''V'' + ''W'' to be the sum of the two subspaces, and 0 to be the trivial subspace {0}.  Define {{math|1=''V'' · ''W'' = span {{mset|v · w | v ∈ V, w ∈ W}}}}, the [[linear span]] of the product of vectors from ''V'' and ''W'' respectively.  Define {{math|1=1 = span {I}<nowiki/>}}, the span of the unit of the algebra.  The closure of ''V'' is the [[direct sum of modules|direct sum]] of all powers of ''V''.

<math display="block">V^{*} = \bigoplus_{i = 0}^{\infty} V^{i}</math>

Suppose ''M'' is a set and ''A'' is the set of all [[binary relation]]s on ''M''. Taking + to be the union, · to be the composition and <sup>*</sup> to be the [[reflexive transitive closure]], we obtain a Kleene algebra.

Every [[Boolean algebra (structure)|Boolean algebra]] with operations <math>\lor</math> and <math>\land</math> turns into a Kleene algebra if we use <math>\lor</math> for +, <math>\land</math> for · and set ''a''<sup>*</sup> = 1 for all ''a''.

A quite different Kleene algebra can be used to implement the [[Floyd–Warshall algorithm]], computing the [[shortest path problem|shortest path's length]] for every two vertices  of a [[graph theory|weighted directed graph]], by [[Kleene's algorithm]], computing a regular expression for every two states of a [[deterministic finite automaton]].
Using the [[extended real number line]], take ''a'' + ''b'' to be the minimum of ''a'' and ''b'' and ''ab'' to be the ordinary sum of ''a'' and ''b'' (with the sum of +∞ and −∞ being defined as +∞). ''a''<sup>*</sup> is defined to be the real number zero for nonnegative ''a'' and −∞ for negative ''a''. This is a Kleene algebra with zero element +∞ and one element the real number zero. 
A weighted directed graph can then be considered as a deterministic finite automaton, with each transition labelled by its weight.
For any two graph nodes (automaton states), the regular expressions computed from Kleene's algorithm evaluates, in this particular Kleene algebra, to the shortest path length between the nodes.<ref>{{citation|title=Handbook of Graph Theory| series=Discrete Mathematics and Its Applications|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press| year=2003|page=65|url=https://books.google.com/books?id=mKkIGIea_BkC&pg=PA65|isbn=9780203490204}}.</ref>

== Properties ==

Zero is the smallest element: 0 ≤ ''a'' for all ''a'' in ''A''.

The sum ''a'' + ''b'' is the [[least upper bound]] of ''a'' and ''b'': we have ''a'' ≤ ''a'' + ''b'' and ''b'' ≤ ''a'' + ''b'' and if ''x'' is an element of ''A'' with ''a'' ≤ ''x'' and ''b'' ≤ ''x'', then ''a'' + ''b'' ≤ ''x''. Similarly, ''a''<sub>1</sub> + ... + ''a''<sub>''n''</sub> is the least upper bound of the elements ''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>.

Multiplication and addition are monotonic: if ''a'' ≤ ''b'', then 
* ''a'' + ''x'' ≤ ''b'' + ''x'', 
* ''ax'' ≤ ''bx'', and 
* ''xa'' ≤ ''xb'' 
for all ''x'' in ''A''.

Regarding the star operation, we have 
* 0<sup>*</sup> = 1 and 1<sup>*</sup> = 1, 
* ''a'' ≤ ''b'' implies ''a''<sup>*</sup> ≤ ''b''<sup>*</sup> (monotonicity),
* ''a''<sup>''n''</sup> ≤ ''a''<sup>*</sup> for every [[natural number]] ''n'', where ''a''<sup>''n''</sup> is defined as ''n''-fold multiplication of ''a'',
* (''a''<sup>*</sup>)(''a''<sup>*</sup>) = ''a''<sup>*</sup>,
* (''a''<sup>*</sup>)<sup>*</sup> = ''a''<sup>*</sup>, 
* 1 + ''a''(''a''<sup>*</sup>) = ''a''<sup>*</sup> = 1 + (''a''<sup>*</sup>)''a'', 
* ''ax'' = ''xb'' implies (''a''<sup>*</sup>)''x'' = ''x''(''b''<sup>*</sup>),
* ((''ab'')<sup>*</sup>)''a'' = ''a''((''ba'')<sup>*</sup>),
* (''a''+''b'')<sup>*</sup> = ''a''<sup>*</sup>(''b''(''a''<sup>*</sup>))<sup>*</sup>, and
* ''pq'' = 1 = ''qp'' implies ''q''(''a''<sup>*</sup>)''p'' = (''qap'')<sup>*</sup>.<ref>Kozen (1990), sect.2.1.2, p.5</ref>

If ''A'' is a Kleene algebra and ''n'' is a natural number, then one can consider the set M<sub>''n''</sub>(''A'') consisting of all ''n''-by-''n'' [[matrix (mathematics)|matrices]] with entries in ''A''.
Using the ordinary notions of matrix addition and multiplication, one can define a unique <sup>*</sup>-operation so that M<sub>''n''</sub>(''A'') becomes a Kleene algebra.

== History ==

Kleene introduced regular expressions and gave some of their algebraic laws.<ref>{{cite tech report| author=S.C. Kleene| title=Representation of Events in Nerve Nets and Finite Automata|date=Dec 1951| number=RM-704| pages=98| institution=U.S. Air Force / RAND Corporation| url=http://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM704.pdf}} Here: sect.7.2, p.52</ref><ref>{{cite journal| author=Kleene, Stephen C.| title=Representation of Events in Nerve Nets and Finite Automata| journal=Automata Studies, Annals of Mathematical Studies| year=1956| volume=34| publisher=Princeton Univ. Press| url=http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf}} Here: sect.7.2, p.26-27</ref>
Although he didn't define Kleene algebras, he asked for a decision procedure for equivalence of regular expressions.<ref>Kleene (1956), p.35</ref>
Redko proved that no finite set of ''equational'' axioms can characterize the algebra of regular languages.<ref>{{cite journal|last=Redko |first=V.N. |url=http://umj.imath.kiev.ua/archiv/1964/01/umj_1964_01_10002_20139.pdf |title=Об определяющей совокупности соотношений алгебры регулярных событий |trans-title=On defining relations for the algebra of regular events| journal={{ill|Ukrainskii Matematicheskii Zhurnal|uk|Український математичний журнал}} | year=1964| volume=16| number=1 | pages=120–126 |language=ru |url-status=dead |archive-url=https://web.archive.org/web/20180329121044/http://umj.imath.kiev.ua/archiv/1964/01/umj_1964_01_10002_20139.pdf |archive-date=2018-03-29 }}</ref>
Salomaa gave complete axiomatizations of this algebra, however depending on problematic inference rules.<ref>{{cite journal| author=Arto Salomaa| title=Two complete axiom systems for the algebra of regular events| journal= Journal of the ACM|date=Jan 1966| volume=13| number=1| pages=158–169| url=http://www.diku.dk/hjemmesider/ansatte/henglein/papers/salomaa1966.pdf| doi=10.1145/321312.321326| s2cid=8445404| author-link=Arto Salomaa}}</ref>
The problem of providing a complete set of axioms, which would allow derivation of all equations among regular expressions, was intensively studied by [[John Horton Conway]] under the name of ''regular algebras'',<ref>{{cite book | first=J.H. | last=Conway | author-link=John Horton Conway | title=Regular algebra and finite machines | publisher=Chapman and Hall | year=1971 | isbn=0-412-10620-5 | zbl=0231.94041 | location=London }}  Chap.IV.</ref> however, the bulk of his treatment was infinitary.
In 1981, [[Dexter Kozen|Kozen]] gave a complete infinitary equational deductive system for the algebra of regular languages.<ref>{{cite book| author=Dexter Kozen| chapter=On induction vs. <sup>*</sup>-continuity| title=Proc. Workshop Logics of Programs| year=1981| volume=131| pages=167–176| publisher=Springer| editor=Dexter Kozen| series=Lect. Notes in Comput. Sci.| chapter-url=http://www.cs.cornell.edu/~kozen/papers/indvsstarcont.pdf}}</ref>
In 1994, he gave the [[#Definition|above]] finite axiom system, which uses unconditional and conditional equalities (considering ''a'' ≤ ''b'' as an abbreviation for ''a'' + ''b'' = ''b''), and is equationally complete for the algebra of regular languages, that is, two regular expressions ''a'' and ''b'' denote the same language only if ''a'' = ''b'' follows from the [[#Definition|above]] axioms.<ref>{{cite journal| author=Dexter Kozen| title=A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events| journal=Information and Computation|date=May 1994| volume=110| number=2| pages=366–390| url=http://www.cs.cornell.edu/~kozen/papers/ka.pdf| doi=10.1006/inco.1994.1037}} &mdash; An earlier version appeared as: {{cite tech report| author=Dexter Kozen| title=A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events|date=May 1990| number=TR90-1123| pages=27| institution=Cornell| url=http://ecommons.library.cornell.edu/handle/1813/6963}}</ref>

== Generalization (or relation to other structures) ==
Kleene algebras are a particular case of [[closed semiring]]s, also called [[quasi-regular semiring]]s or [[Lehmann semiring]]s, which are semirings in which every element has at least one quasi-inverse satisfying the equation: ''a''* = ''aa''* + 1 = ''a''*''a'' + 1. This quasi-inverse is not necessarily unique.<ref name="Golan2003">{{cite book|author=Jonathan S. Golan|title=Semirings and Affine Equations over Them|url=https://books.google.com/books?id=jw4Hmgz5ETQC&pg=PA157|date=30 June 2003|publisher=Springer Science & Business Media|isbn=978-1-4020-1358-4|pages=157–159}}</ref><ref name="PoulyKohlas2012b"/> In a Kleene algebra, ''a''* is the least solution to the [[fixpoint]] equations: ''X'' = ''aX'' + 1 and ''X'' = ''Xa'' + 1.<ref name="PoulyKohlas2012b"/>

Closed semirings and Kleene algebras appear in [[algebraic path problem]]s, a generalization of the [[shortest path]] problem.<ref name="PoulyKohlas2012b">{{cite book|author1=Marc Pouly|author2=Jürg Kohlas|title=Generic Inference: A Unifying Theory for Automated Reasoning|year=2011|publisher=John Wiley & Sons|isbn=978-1-118-01086-0|pages=232 and 248}}</ref>

==See also==
* [[Action algebra]]
* [[Algebraic structure]]
* [[Kleene star]]
* [[Regular expression]]
* [[Star semiring]]
* [[Valuation algebra]]

== References ==
{{reflist}}

== Further reading ==
* {{cite web  | last=Kozen | first=Dexter | author-link=Dexter Kozen | title=CS786 Spring 04, Introduction to Kleene Algebra | url=http://www.cs.cornell.edu/Courses/cs786/2004sp/ }}
* {{cite book|author=Peter Höfner|title=Algebraic Calculi for Hybrid Systems|url=https://books.google.com/books?id=40vn5XIMAtwC|year=2009|publisher=BoD – Books on Demand|isbn=978-3-8391-2510-6|pages=10–13}} The introduction of this book reviews advances in the field of Kleene algebra made in the last 20 years, which are not discussed in the article above.

[[Category:Algebraic structures]]
[[Category:Algebraic logic]]
[[Category:Formal languages]]
[[Category:Many-valued logic]]