3 papers
math.LO2021
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…
cs.LO2021
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…
cs.LO2021
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…