Axioms for signatures with domain and demonic composition (Q2663185)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Axioms for signatures with domain and demonic composition
scientific article

    Statements

    Axioms for signatures with domain and demonic composition (English)
    0 references
    16 April 2021
    0 references
    Let \(X\) be a non-empty set and \(\mathrm{Rel}(X)\) denote the set of all binary relations on \(X\). The authors consider certain so called ``demonic'' variants of standard ``angelic'' relational composition, union, inclusion. Particularly, the demonic composition \(a*b\) for \(a,b \in \mathrm{Rel}(X)\) is the intersection of the original composition of these relations and the relation \(\{(x,y)\in X\times X\mid a(x)\subseteq \mathrm {dom} (b)\}\), where \(a(x)=\{y\mid (x,y)\in a\}\) and \(\mathrm {dom} (b) =\{x\mid \exists y (x,y)\in b\}\). ``So \(a*b\) is a domain restriction of the ordinary composition of \(a\) and \(b\)''. Other demonic relations and operations are introduced: demonic refinement \(\sqsubseteq\), demonic join \(\sqcup\), left restrictive multiplication \(\circ\) and so on. Many new classes of relation algebras are obtained on this way. It is shown that many of them have no finite axiomatisation. On the other side for relation algebras with signature \(\{\sqsubseteq ,\circ , *\}\) a finite set of axioms is obtained.
    0 references
    demonic composition
    0 references
    demonic refinement
    0 references
    axiomatisation
    0 references
    ordered semigroup
    0 references
    left restriction semigroup
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references