Action algebra

In algebraic logic, an action algebra is an algebraic structure which is both a residuated semilattice and a Kleene algebra. It adds the star or reflexive transitive closure operation of the latter to the former, while adding the left and right residuation or implication operations of the former to the latter. Unlike dynamic logic and other modal logics of programs, for which programs and propositions form two distinct sorts, action algebra combines the two into a single sort. It can be thought of as a variant of intuitionistic logic with star and with a noncommutative conjunction whose identity need not be the top element. Unlike Kleene algebras, action algebras form a variety, which furthermore is finitely axiomatizable, the crucial axiom being a•(a → a)* ≤ a. Unlike models of the equational theory of Kleene algebras (the regular expression equations), the star operation of action algebras is reflexive transitive closure in every model of the equations.

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. However, action algebras have the advantage that they also have an equivalent axiomatization that is purely equational. The language of action algebras extends in a natural way to that of action lattices, namely by the inclusion of a meet operation.

In the following we write the inequality a ≤ b as an abbreviation for the equation a ∨ b = 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.

...
Wikipedia