Wreath products create new representable distributive quasi relation algebras
Wreath products of distributive quasi relation algebra frames and their application to representability
Logic in Computer Science
Summary
Distributive quasi relation algebras are mathematical structures used to study relations. The authors adapt an old construction to combine two such structures into a new one, called a wreath product, that also meets important mathematical conditions. They introduce a way to represent these structures called frame networks and show how these help prove the new combined algebra is representable. This means their method can build more complex objects from simpler, known ones while preserving key properties.
What this means in practice
- •For algebraic logicians: Construct new representable distributive quasi relation algebras from known finite examples using wreath products and frame networks.
- •For formal methods engineers: Use representable distributive quasi relation algebras for modeling complex relational systems with guaranteed representability.
Authors
Wilmari Morton, Claudette Robinson
Abstract
We adapt a construction by Comer (1983) for polygroups to define the wreath product of the dual frames of two distributive quasi relation algebras satisfying certain conditions and show that it is itself a frame. Frames play a role analogous to that of atom structures for relation algebras. After introducing the notion of a frame network, we establish a correspondence between frame networks satisfying certain conditions and representability of finite distributive quasi relation algebras. Next we describe a frame network for the wreath product of two finite representable distributive quasi relation algebras that satisfies the aforementioned conditions, as well as additional conditions, and use this to conclude that the complex algebra of the wreath product is a representable distributive quasi relation algebra. Thus, our construction provides a method for obtaining representable DqRAs from certain finite DqRAs that are already known to be representable.