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