|
In mathematics, a Kleene algebra (named after Stephen Cole Kleene, pronounced "clay-knee") is either of two different things: Euclid, Greek mathematician, 3rd century BC, known today as the father of geometry; shown here in a detail of The School of Athens by Raphael. ...
Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...
See lattice for other mathematical as well as non-mathematical meanings of the term. ...
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ...
In mathematics, an involution is a function that is its own inverse, so that f(f(x)) = x for all x in the domain of f. ...
note that demorgans laws are also a big part in circut design. ...
In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ...
In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ...
In computing, a regular expression (abbreviated as regexp or regex, with plural forms regexps, regexes, or regexen) is a string that describes or matches a set of strings, according to certain syntax rules. ...
Definition Various inequivalent definitions of Kleene algebras and related structures have been given in the literature. See [1] for a survey. 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. In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...
In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ...
- 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 elements 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: a1 = 1a = a.
- a0 = 0a = 0 for all a in A.
The above axioms define a semiring. We further require: In mathematics, associativity is a property that a binary operation can have. ...
In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ...
In mathematics, and in particular in abstract algebra, distributivity is a property of binary operations that generalises the distributive law from elementary algebra. ...
In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...
In abstract algebra, a semiring is an algebraic structure, similar to a ring, but without additive inverses. ...
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 this order we can formulate the last two axioms about the operation *: In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ...
In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...
It has been suggested that this article or section be merged with Logical biconditional. ...
- 1 + a(a*) ≤ a* for all a in A.
- 1 + (a*)a ≤ a* for all a in A.
- if a and x are in A such that ax ≤ x, then a*x ≤ x
- if a and x are in A such that xa ≤ x, then x(a*) ≤ x
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 theory, one may also interpret + as "choice", · as "sequencing" and * as "iteration".
Examples Let Σ be a finite set (an "alphabet") and let A be the set of all regular expressions over Σ. We consider two such regular expressions equal if they describe the same language. Then A forms a Kleene algebra. In fact, this is a 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. In computing, a regular expression (abbreviated as regexp or regex, with plural forms regexps, regexes, or regexen) is a string that describes or matches a set of strings, according to certain syntax rules. ...
The idea of a free object in mathematics is one of the basics of abstract algebra. ...
Again let Σ be an alphabet. Let A be the set of all regular languages over Σ (or the set of all context-free languages over Σ; or the set of all recursive languages over Σ; or the set of all languages over Σ). Then the union (written as +) and the 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. A regular language is a formal language (i. ...
The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...
A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. ...
In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ...
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ...
In mathematics and more specifically set theory, the empty set is the unique set which contains no elements. ...
Let M be a monoid with identity element e and let A be the set of all subsets 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* 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. In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...
A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ...
In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...
Suppose M is a set and A is the set of all binary relations on M. Taking + to be the union, · to be the composition and * to be the reflexive transitive hull, we obtain a Kleene algebra. In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...
Every boolean algebra with operations v and ^ turns into a Kleene algebra if we use v for +, ^ for · and set a* = 1 for all a. In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ...
A quite different Kleene algebra is useful when computing shortest paths in weighted directed graphs: let A be 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* 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. In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. ...
A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...
The extended real number line is obtained from the real number line R by adding two elements: +∞ and −∞ (which are not considered to be real numbers). ...
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, a1 + ... + an is the least upper bound of the elements a1, ..., an. In mathematics, the supremum of an ordered set S is the least element (not necessarily in S) which is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound. ...
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 * operation, we have 0* = 1 and 1* = 1, that * is monotonic (a ≤ b implies a* ≤ b*), and that an ≤ a* for every natural number n. Furthermore, (a*)(a*) = a*, (a*)* = a*, and a ≤ b* if and only if a* ≤ b*.
If A is a Kleene algebra and n is a natural number, then one can consider the set Mn(A) consisting of all n-by-n matrices with entries in A. Using the ordinary notions of matrix addition and multiplication, one can define a unique *-operation so that Mn(A) becomes a Kleene algebra. In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...
History Kleene algebras were not defined by Kleene; he introduced regular expressions and asked for a complet set of axioms which would allow derivation of all equations among regular expressions. The problem was first studied by John Horton Conway under the name of regular algebras. The axioms of Kleene algebras solve this problem, as was first shown by Dexter Kozen. John Horton Conway (born December 26, 1937, Liverpool, England) is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. ...
References - Dexter Kozen: On Kleene algebras and closed semirings. In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26-47. Springer, 1990. Online at http://www.cs.cornell.edu/~kozen/papers/kacs.ps
See also |
Feeds |
Contact