Notes on equational theories of relations (Q1344844)

The paper is a contribution to the equational theory of semirings, Kleene algebras and relation algebras. It studies several equational varieties. The equational class \(\text{REL}^\vee\) is generated by all algebras of binary relations on a set \(A\), with operations union, composition, converse and star (reflexive transitive closure), and constants empty and identity relation. A subclass is given by the theory of full, i.e. total and surjective, relations. The variety \(L^\vee\) is generated by all algebras of formal languages in a free monoid, with operations union, concatenation, reverse and Kleene star, and constants empty language and language consisting of the empty word only. The main results are explicit descriptions of the free algebras in these classes and proofs that the corresponding equational theories are decidable. These results are interesting for formal languages, relations and dynamic algebras.