Tim Stokes

Axioms for relational signatures containing demonic composition

Most natural signatures of relation algebra do not give finite axiomatisations, but there are some exceptions. One is algebras of relations under ("angelic") composition and the inclusion order as ordered semigroups, as shown by Zaretskii in 1959. We give a "demonic" conterpart to this, involving demonic refinement rather than inclusion. There are negative results for the signatures of angelic composition and demonic refinement as well as for demonic composition and inclusion.

Another important operation is domain. The relational signature of domain plus demonic composition is finitely axiomatised as left restriction semigroups (just like the functional case), but when demonic refinement (or equivalently in this case, inclusion) is added, there is no finite relational axiomatisation. On the positive side, we give a finite axiomatisation for the very closely related relational signature of domain restriction, demonic refinement and demonic composition. (In the functional setting, both these signatures give finite axiomatisations.)

This is joint work with Robin Hirsch and Szabolcs Mikulás.

Links:
https://doi.org/10.1093/jigpal/jzab026
https://doi.org/10.1007/s00012-021-00719-4