eprintid: 10134566
rev_number: 15
eprint_status: archive
userid: 608
dir: disk0/10/13/45/66
datestamp: 2021-09-17 10:54:10
lastmod: 2022-03-22 07:10:19
status_changed: 2021-09-17 10:54:10
type: article
metadata_visibility: show
creators_name: Hirsch, R
creators_name: Stokes, T
title: Axioms for signatures with domain and demonic composition
ispublished: pub
divisions: UCL
divisions: B04
divisions: C05
divisions: F48
keywords: Demonic composition, demonic refinement, binary relation, non-deterministic program, total correctness, axiomatisation.
note: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
abstract: Demonic composition ∗ is an associative operation on binary relations, and demonic refinement ⊑ is a partial order on binary relations. Other operations on binary relations considered here include the unary domain operation D and the left restrictive multiplication operation ∘ given by s∘t=D(s)∗t. We show that the class of relation algebras of signature {⊑,D,∗}, or equivalently {⊆,∘,∗}, has no finite axiomatisation. A large number of other non-finite axiomatisability consequences of this result are also given, along with some further negative results for related signatures. On the positive side, a finite set of axioms is obtained for relation algebras with signature {⊑,∘,∗}, hence also for {⊆,∘,∗}.
date: 2021-05
date_type: published
publisher: SPRINGER BASEL AG
official_url: https://doi.org/10.1007/s00012-021-00719-4
oa_status: green
full_text_type: other
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1855742
doi: 10.1007/s00012-021-00719-4
lyricists_name: Hirsch, Robin
lyricists_id: RHIRS08
actors_name: Hirsch, Robin
actors_id: RHIRS08
actors_role: owner
full_text_status: public
publication: Algebra universalis
volume: 82
number: 2
article_number: 24
pages: 19
citation:        Hirsch, R;    Stokes, T;      (2021)    Axioms for signatures with domain and demonic composition.                   Algebra universalis , 82  (2)    , Article 24.  10.1007/s00012-021-00719-4 <https://doi.org/10.1007/s00012-021-00719-4>.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10134566/1/demonic-revised-post-review.pdf