Kleene algebra

Summary

A Kleene algebra is an idempotent semiring with a star operation $a^*$ that behaves like "any number of repetitions of $a$". The model is the algebra of formal languages, with union, concatenation and the Kleene star. Kleene algebras give an equational theory of regular expressions, and they are used to reason about programs and automata. Binary relations on a set, with union, composition and reflexive transitive closure, also form a Kleene algebra.