Action Algebra

An action algebra (A, ∨, 0, •, 1, ←, →, *) is an algebraic structure such that (A, ∨, •, 1, ←, →) forms a residuated semilattice while (A, ∨, 0, •, 1, *) forms a Kleene algebra. That is, it is any model of the joint theory of both classes of algebras. Now Kleene algebras are axiomatized with quasiequations, that is, implications between two or more equations, whence so are action algebras when axiomatized directly in this way. What makes action algebras of special interest is that they have an equivalent axiomatization that is purely equational.

In the following we write the inequality ab as an abbreviation for the equation ab = b. This allows us to axiomatize the theory using inequalities yet still have a purely equational axiomatization when the inequalities are expanded to equalities.

The equations axiomatizing action algebra are those for a residuated semilattice, together with the following equations for star.

1 ∨ a*•a* ∨ aa*
a* ≤ (ab)*
(aa)* ≤ aa

The first equation can be broken out into three equations, 1 ≤ a*, a*•a* ≤ a*, and aa*. These force a* to be reflexive, transitive, and greater or equal to a respectively. The second axiom asserts that star is monotone. The third axiom can be written equivalently as a•(aa)* ≤ a, a form which makes its role as induction more apparent. These two axioms in conjunction with the axioms for a residuated semilattice force a* to be the least reflexive transitive element of the semilattice greater or equal to a. Taking that as the definition of reflexive transitive closure of a, we then have that for every element a of any action algebra, a* is the reflexive transitive closure of a.

The equational theory of the star-free fragment of action algebras, those equations not containing star, can be shown to coincide with the equational theory of Kleene algebras, also known as the regular expression equations. In that sense the above axioms constitute a finite axiomatization of regular expressions. Redko showed in 1967 that these equations had no finite axiomatization, for which John Horton Conway gave a shorter proof in 1971. Salomaa gave an equation schema axiomatizing this theory which Kozen subsequently reformulated as a finite axiomatization using quasiequations or implications between equations, the crucial quasiequations being those of induction: if xax then xa* ≤ x, and if axx then a*•xx. Kozen defined a Kleene algebra to be any model of this finite axiomatization.

Conway showed that the equational theory of regular expressions admit models in which a* was not the reflexive transitive closure of a, by giving a four-element model 0 ≤ 1 ≤ aa* in which aa = a. In Conway's model, a is reflexive and transitive, whence its reflexive transitive closure should be a. However the regular expressions do not enforce this, allowing a* to be strictly greater than a. Such anomalous behavior is not possible in an action algebra.

Read more about Action Algebra:  Examples

Other articles related to "action algebra, algebra":

Action Algebra - Examples
... Any Heyting algebra (and hence any Boolean algebra) is made an action algebra by taking • to be ∧ and a* = 1 ... and sufficient for star because the top element 1 of a Heyting algebra is its only reflexive element, and is transitive as well as greater or equal to every ... all formal languages (sets of finite strings) over an alphabet Σ forms an action algebra with 0 as the empty set, 1 = {ε}, ∨ as union, • as concatenation, L←M as the set of all strings x such that xM ...

Famous quotes containing the words algebra and/or action:

    Poetry has become the higher algebra of metaphors.
    José Ortega Y Gasset (1883–1955)

    A dramatist is one who believes that the pure event, an action involving human beings, is more arresting than any comment that can be made upon it.
    Thornton Wilder (1897–1975)