Generalizations of Relation Algebras from the perspective of (semi)lattices with operators
Peter Jipsen · 2010
In this talk we consider various classes of algebras that include (reducts of) relation algebras. For many applications it is useful to have an associative ‘composition’ operation with an identity element, so we mostly restrict to this case. In particular we consider positive relation algebras, sequential algebras, residuated Boolean monoids, lattice-ordered groups with converse, unisorted allegories, residuated lattices with a De Morgan operation, and (anti)domain-range semirings. We discuss how these classes are related to each other and consider questions of decidability and representability for them. They are all (semi)lattices with additional operators, and we show how to define the analogue of an atomstructure for many of these algebras. We then focus on the variety DmRL′ of residuated lattices with a unary De Morgan operation ′ since it has the same signature as relation algebras and is large enough to include most of the classes we consider. The subvariety qRA of quasirelation algebras is defined by adding equations that ensure ′ is a homomorphism from the residuated lattice to its dual. We then show how relation algebras are a natural subvariety of qRA, but that qRA has the distinct advantage of having a decidable equational theory. This type of result is only possible if the order structure of relation algebras is generalized to De Morgan lattices, since Kuruczs, Nemeti, Sain and Simon proved in 1993 that any ‘large enough’ variety with Boolean algebra reducts and with an associative operator has an undecidable equational theory. We also extend a result of Jonsson and Tsinakis [1993], where relation algebras are shown to be term-equivalent to a subvariety of residuated Boolean monoids, to the more general setting of quasi relation algebras. Much of the work reported here was done in collaboration with Nikolaos Galatos.