On Kleene algebras of ternary co-relations (Q2714404)

In this paper, the author investigates algebras of ternary co-relations. Recall that an \(n\)-ary co-relation on a set \(X\) is a set of functions from \(X\) to \(n=\{0,1,2,\dots,n-1\}\), thus being dual to the notion of an \(n\)-ary relation. Hence an \(n\)-ary co-relation is in fact a family of colourings of the set \(X\) in \(n\) colours. The main result of the paper states that algebras of ternary co-relations equipped with the operations of union, composition, iteration, co-relational converse and two particular constants generate the same variety as language algebras equipped with the operations of union, concatenation, Kleene star (iteration), language reversal and the empty language and the language containing the empty word only as constants (Theorem 10). Thus the author concludes that the equational behaviour of the language reversal can be modelled by ternary co-relations, which is not true for the classical correspondence between language algebras and Kleene relation algebras. Finally, the author shows how it is possible to obtain Kleene algebras of relations from algebras of ternary co-relations (dropping the operation of converse).