On Kleene algebras of ternary co-relations

Abstract

In this paper we investigate identities satisfied by a class of algebras made of ternary co-relations - contravariant ("arrow-reversed") analogues of binary relations. These algebras are equipped with the operations of union, co-relational composition, iteration, converse and the empty co-relation and the so-called diagonal co-relation as constants. Our first result is that the converse-free part of the corresponding equational theory consists precisely of Kleenean equations for relations, or, equivalently, for (regular) languages. However, the rest of the equations, involving the symbol of the converse, are relatively axiomatized by involution axioms only, so that the co-relational converse behaves more like the reversal of languages, rather than the relational converse. Actually, the language reversal is explicitely used to prove this result. Therefore, we conclude that co-relations can offer a better framework than relations for the mathematical modeling of formal languages, as well as many other notions from computer science.