Kleene algebra

In mathematics, a Kleene algebra (/ˈkleɪni/ KLAY-nee; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator. It generalizes the operations known from regular expressions.

Various inequivalent definitions of Kleene algebras and related structures have been given in the literature. Here we will give the definition that seems to be the most common nowadays.

A Kleene algebra is a set A together with two binary operations + : A × A → A and · : A × A → A and one function ^* : A → A, written as a + b, ab and a^* respectively, so that the following axioms are satisfied.

The above axioms define a semiring. We further require:

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 two axioms about the operation ^*:

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, in the sense that a ≤ b implies ax ≤ bx. The idea behind the star operator is a^* = 1 + a + aa + aaa + ... From the standpoint of programming language theory, one may also interpret + as "choice", · as "sequencing" and ^* as "iteration".

...
Wikipedia