Szabolcs Mikulás

Equational theories of extended Kleene algebras

(joint work with Hajnal Andréka and István Németi)

D. Kozen defined the class KA of Kleene algebras as a finitely axiomatised quasi-variety. Sound interpretations of KA include regular languages and families of binary relations. The corresponding classes of algebras are language Kleene algebras, LKA, and relational Kleene algebras, RKA. It is known that they generate the same variety: V(LKA)=V(RKA), but this variety is not finitely axiomatisable. Hence there is no finite, equational axiomatisation of the valid equations. Nevertheless, there is a finite, quasi-equational axiomatisation, since KA generates the same variety as LKA and RKA: V(KA)=V(LKA)=V(RKA).

A natural extension of Kleene algebras is Kleene lattices, KL, where we include meet in the signature. We show that language and relational Kleene lattices, LKL and RKL respectively, generate different varieties, though V(LKL) remains finitely axiomatised over V(RKL). However, if we omit the identity constant, then the generated varieties coincide.

V. Pratt suggested another, residuated extension of KA: action algebras, AA. He showed that action algebras form a variety (the quasi-equations in the axiomatisation of KA can be expressed as equations using the residuals of composition). Kozen further extended the signature by meet, resulting in action lattices, AL. We show that, similarly to the Kleene algebra case, relational action algebras, RAA, and lattices, RAL, generate non-finitely axiomatisable varieties. We also show that, unlike in the Kleene algebra case, these varieties cannot be generated by finitely axiomatised quasi-varieties (as long as we require the soundness of the axiomatisation in relational interpretations).