7 citations · 7 across the 6 of their papers we have counts for
7 papers
Minimal signatures with undecidability of representability by binary relations
Robin Hirsch, Marcel Jackson, Jaš Šemrl
A semigroup of binary relations (under composition) on a set is \emph{complemented} if it is closed under the taking of complements within . We resolve a 1991 proble…
Implication Algebras and Implication Semigroups of Binary Relations
Andrew Lewis-Smith Jaš Šemrl
Representable implication algebras are known to be axiomatised by a finite number of equations (making the representation and finite representation problems decidable here). We sho…
Representable and diagonally representable weakening relation algebras
Peter Jipsen, Jaš Šemrl
A binary relation defined on a poset is a weakening relation if the partial order acts as a both-sided compositional identity. This is motivated by the weakening rule in sequent ca…
Finite Representation Property for Relation Algebra Reducts
Jaš Šemrl
The decision problem of membership in the Representation Class of Relation Algebras (RRA) for finite structures is undecidable. However, this does not hold for many Relation Algebr…
Domain Range Semigroups and Finite Representations
Jaš Šemrl
Relational semigroups with domain and range are a useful tool for modelling nondeterministic programs. We prove that the representation class of domain-range semigroups with demoni…
Demonic Lattices and Semilattices in Relational Semigroups with Ordinary Composition
Robin Hirsch, Jaš Šemrl
Relation algebra and its reducts provide us with a strong tool for reasoning about nondeterministic programs and their partial correctness. Demonic calculus, introduced to model th…
Finite Representability of Semigroups with Demonic Refinement
Robin Hirsch, Jaš Šemrl
Composition and demonic refinement of binary relations are defined by \begin{align*} (x, y)\in (R;S)&\iff \exists z((x, z)\in R\wedge (z, y)\in S) R\sqsubseteq S&\iff…