A Survey of Regular Expressions and Their Applications Review

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

Definition [edit]

Various inequivalent definitions of Kleene algebras and related structures take been given in the literature.^[2] Here nosotros will give the definition that seems to be the well-nigh common nowadays.

A Kleene algebra is a set A together with 2 binary operations + : A × A → A and · : A × A → A and one function ^* : A → A, written every bit a + b, ab and a ^* respectively, then that the post-obit 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) + (air conditioning) 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 one in A such that for all a in A: aone = 1a = a.
Annihilation by 0: a0 = 0a = 0 for all a in A.

The above axioms ascertain a semiring. We further crave:

+ is idempotent: a + a = a for all a in A.

Information technology is now possible to define a partial order ≤ on A by setting a ≤ b if and just if a + b = b (or equivalently: a ≤ b if and only if at that place exists an ten in A such that a + ten = b; with whatever definition, a ≤ b ≤ a implies a = b). With this order nosotros can formulate the last iv axioms nearly the functioning ^*:

1 + a(a ^*) ≤ a ^* for all a in A.
i + (a ^*)a ≤ a ^* for all a in A.
if a and 10 are in A such that ax ≤ x, and then a ^* x ≤ x
if a and x are in A such that xa ≤ ten, and so x(a ^*) ≤ x ^[3]

Intuitively, one should remember of a + b as the "matrimony" 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".

Examples [edit]

Notational correspondence between
Kleene algebras and	+	·	^*	0	1
Regular expressions	\|	not written	^*	∅	ε

Let Σ exist a finite set (an "alphabet") and permit A exist the set of all regular expressions over Σ. Nosotros consider two such regular expressions equal if they depict the same linguistic communication. And so A forms a Kleene algebra. In fact, this is a complimentary 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 permit Σ exist an alphabet. Let A be the set of all regular languages over Σ (or the gear up of all context-free languages over Σ; or the set up of all recursive languages over Σ; or the set of all languages over Σ). And then the union (written as +) and the concatenation (written as ·) of two elements of A once more vest to A, and and then does the Kleene star operation applied to any element of A. Nosotros obtain a Kleene algebra A with 0 being the empty set and one being the gear up that only contains the empty string.

Let K be a monoid with identity chemical element due east and allow A exist the set of all subsets of G. For two such subsets S and T, allow Southward + T exist the marriage of S and T and set ST = {st : southward in S and t in T}. S ^* is defined as the submonoid of M generated by South, which can be described as {east} ∪ S ∪ SS ∪ SSS ∪ ... So A forms a Kleene algebra with 0 existence the empty set and 1 being {east}. An analogous construction can exist performed for any small category.

The linear subspaces of a unital algebra over a field grade a Kleene algebra. Given linear subspaces V and Due west, define 5 + W to exist the sum of the two subspaces, and 0 to be the trivial subspace {0}. Define 5 · Due west = span {5 · due west | five ∈ V, westward ∈ W}, the linear span of the production of vectors from Five and Due west respectively. Define ane = span {I}, the span of the unit of measurement of the algebra. The closure of V is the direct sum of all powers of V.

5^{*}=\bigoplus _{i=0}^{\infty }5^{i}

Suppose G is a fix and A is the gear up of all binary relations on M. Taking + to be the union, · to exist the composition and ^* to exist the reflexive transitive closure, we obtain a Kleene algebra.

Every Boolean algebra with operations $\lor$ and $\country$ turns into a Kleene algebra if we utilise $\lor$ for +, $\land$ for · and prepare a ^* = ane for all a.

A quite dissimilar Kleene algebra can be used to implement the Floyd–Warshall algorithm, computing the shortest path'south length for every two vertices of a 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, accept a + b to exist the minimum of a and b and ab to be the ordinary sum of a and b (with the sum of +∞ and −∞ existence defined as +∞). a ^* is defined to be the real number nothing for nonnegative a and −∞ for negative a. This is a Kleene algebra with zip element +∞ and one element the real number zero. A weighted directed graph can and 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'due south algorithm evaluates, in this particular Kleene algebra, to the shortest path length between the nodes.^[4]

Properties [edit]

Goose egg is the smallest element: 0 ≤ a for all a in A.

The sum a + b is the least upper leap of a and b: nosotros have a ≤ a + b and b ≤ a + b and if x is an chemical element of A with a ≤ ten and b ≤ x, then a + b ≤ x. Similarly, a ₁ + ... + a _n is the least upper leap of the elements a ₁, ..., a _n.

Multiplication and add-on are monotonic: if a ≤ b, and so

a + x ≤ b + x,
ax ≤ bx, and
xa ≤ xb

for all x in A.

Regarding the star operation, we have

0^* = one and ane^* = one,
a ≤ b implies a ^* ≤ b ^* (monotonicity),
a ⁿ ≤ a ^* for every natural number north, where a ^{due north} is defined every bit due north-fold multiplication of a,
(a ^*)(a ^*) = a ^*,
(a ^*)^* = a ^*,
one + a(a ^*) = a ^* = i + (a ^*)a,
ax = xb implies (a ^*)x = x(b ^*),
((ab)^*)a = a((ba)^*),
(a+b)^* = a ^*(b(a ^*))^*, and
pq = ane = qp implies q(a ^*)p = (qap)^*.^[5]

If A is a Kleene algebra and northward is a natural number, and so one can consider the gear up Chiliad_n(A) consisting of all n-by-northward matrices with entries in A. Using the ordinary notions of matrix addition and multiplication, 1 can define a unique ^*-performance so that M_north(A) becomes a Kleene algebra.

History [edit]

Kleene introduced regular expressions and gave some of their algebraic laws.^[vi] ^[7] Although he didn't define Kleene algebras, he asked for a conclusion procedure for equivalence of regular expressions.^[viii] Redko proved that no finite set up of equational axioms can characterize the algebra of regular languages.^[nine] Salomaa gave complete axiomatizations of this algebra, yet depending on problematic inference rules.^[ten] The trouble 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,^[eleven] notwithstanding, the bulk of his handling was infinitary. In 1981, Kozen gave a complete infinitary equational deductive organisation for the algebra of regular languages.^[12] In 1994, he gave the above finite axiom organization, which uses unconditional and conditional equalities (because 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 aforementioned language only if a = b follows from the to a higher place axioms.^[thirteen]

Generalization (or relation to other structures) [edit]

Kleene algebras are a particular case of closed semirings, also called quasi-regular semirings or Lehmann semirings, which are semirings in which every element has at least one quasi-inverse satisfying the equation: a* = aa* + 1 = a*a + ane. This quasi-changed is not necessarily unique.^[fourteen] ^[15] In a Kleene algebra, a* is the to the lowest degree solution to the fixpoint equations: X = aX + 1 and Ten = Xa + one.^[15]

Airtight semirings and Kleene algebras announced in algebraic path bug, a generalization of the shortest path problem.^[15]

Encounter also [edit]

Action algebra
Algebraic construction
Kleene star
Regular expression
Star semiring
Valuation algebra

Notes and references [edit]

^ Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. p. 246. ISBN978-1-118-01086-0.
^ For a survey, see: Kozen, Dexter (1990). "On Kleene algebras and airtight semirings" (PDF). In Rovan, Branislav (ed.). Mathematical foundations of computer scientific discipline, Proc. 15th Symp., MFCS '90, Banská Bystrica/Czech. 1990. Lecture Notes Computer science. Vol. 452. Springer-Verlag. pp. 26–47. Zbl 0732.03047.
^ Kozen (1990), sect.ii.1, p.three
^ Gross, Jonathan Fifty.; Yellen, Jay (2003), Handbook of Graph Theory, Discrete Mathematics and Its Applications, CRC Press, p. 65, ISBN9780203490204 .
^ Kozen (1990), sect.two.one.ii, p.5
^ South.C. Kleene (Dec 1951). Representation of Events in Nerve Nets and Finite Automata (PDF) (Technical written report). U.S. Air Force / RAND Corporation. p. 98. RM-704. Here: sect.7.2, p.52
^ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automata" (PDF). Automata Studies, Annals of Mathematical Studies. Princeton Univ. Press. 34. Hither: sect.7.2, p.26-27
^ Kleene (1956), p.35
^ Five.Due north. Redko (1964). "On defining relations for the algebra of regular events" (PDF). Ukrainskii Matematicheskii Zhurnal [united kingdom of great britain and northern ireland] . xvi (1): 120–126. (In Russian)
^ Arto Salomaa (Jan 1966). "Two complete axiom systems for the algebra of regular events" (PDF). Journal of the ACM. xiii (1): 158–169. doi:10.1145/321312.321326. S2CID 8445404.
^ Conway, J.H. (1971). Regular algebra and finite machines. London: Chapman and Hall. ISBN0-412-10620-5. Zbl 0231.94041. Chap.Iv.
^ Dexter Kozen (1981). "On induction vs. ^*-continuity" (PDF). In Dexter Kozen (ed.). Proc. Workshop Logics of Programs. Lect. Notes in Comput. Sci. Vol. 131. Springer. pp. 167–176.
^ Dexter Kozen (May 1994). "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events" (PDF). Data and Computation. 110 (ii): 366–390. doi:10.1006/inco.1994.1037. — An earlier version appeared equally: Dexter Kozen (May 1990). A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events (Technical study). Cornell. p. 27. TR90-1123.
^ Jonathan S. Golan (30 June 2003). Semirings and Affine Equations over Them. Springer Scientific discipline & Business Media. pp. 157–159. ISBN978-one-4020-1358-4.
^ ^a ^b ^c Marc Pouly; Jürg Kohlas (2011). Generic Inference: A Unifying Theory for Automated Reasoning. John Wiley & Sons. pp. 232 and 248. ISBN978-1-118-01086-0.

Kozen, Dexter. "CS786 Bound 04, Introduction to Kleene Algebra".

Petrie Compereed