Hirsch, R;
Šemrl, J;
(2021)
Finite representability of semigroups with demonic refinement.
Algebra universalis
, 82
(2)
, Article 28. 10.1007/s00012-021-00718-5.
Preview |
Text
Hirsch_Hirsch-Šemrl2021_Article_FiniteRepresentabilityOfSemigr.pdf - Published Version Download (521kB) | Preview |
Abstract
The motivation for using demonic calculus for binary relations stems from the behaviour of demonic turing machines, when modelled relationally. Relational composition (; ) models sequential runs of two programs and demonic refinement (⊑) arises from the partial order given by modeling demonic choice (⊔) of programs (see below for the formal relational definitions). We prove that the class R(⊑,;) of abstract (≤,∘) structures isomorphic to a set of binary relations ordered by demonic refinement with composition cannot be axiomatised by any finite set of first-order (≤,∘) formulas. We provide a fairly simple, infinite, recursive axiomatisation that defines R(⊑,;). We prove that a finite representable (≤,∘) structure has a representation over a finite base. This appears to be the first example of a signature for binary relations with composition where the representation class is non-finitely axiomatisable, but where the finite representation property holds for finite structures.
| Type: | Article |
|---|---|
| Title: | Finite representability of semigroups with demonic refinement |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00012-021-00718-5 |
| Publisher version: | https://doi.org/10.1007/s00012-021-00718-5 |
| Language: | English |
| Additional information: | © 2021 Springer Nature Switzerland AG. This article is licensed under a Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/). |
| Keywords: | Relation algebra, Demonic refinement, Ordered semigroups, Finite representability property |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10115466 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
