Logo del repository
  1. Home
 
Opzioni

Characterising Spectra of Equivalences for Event Structures, Logically

Paolo Baldan
•
Daniele Gorla
•
Tommaso Padoan
•
Ivano Salvo
2022
  • journal article

Periodico
INFORMATION AND COMPUTATION
Abstract
We present a logical characterisation of the equivalences in the spectrum for labelled Prime Event Structures (PESs) and use it for also studying how such spectrum changes when restricting to subclasses of event structures. We first show that a minor modification of the logic characterising hereditary history preserving bisimilarity induces PES isomorphism as logical equivalence. Then, we distill fragments of the logic that characterise all the equivalences in the aforementioned spectrum. In particular, we single out logics for interleaving/step/pomset trace equivalences and weak (pomset) history preserving bisimilarity, which were missing. Finally, we apply our logical characterisation to investigate how the spectrum simplifies when we restrict to subclasses of event structures: Coherence Spaces, where causality is absent, and Elementary Event Structures, where instead conflicts are not allowed. Inclusions between behavioural equivalences are proved by providing encodings between the corresponding sublogics, whereas the non-inclusion between equivalences is witnessed by using distinguishing formulae, i.e., by providing structures which are identified by an equivalence and distinguished by a formula in the logics of the other equivalence.
DOI
10.1016/j.ic.2022.104887
WOS
WOS:000886255300043
Archivio
https://hdl.handle.net/11368/3059086
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85126132610
https://www.sciencedirect.com/science/article/pii/S0890540122000293?via=ihub
Diritti
open access
license:copyright editore
license:creative commons
license uri:iris.pri02
license uri:http://creativecommons.org/licenses/by-nc-nd/4.0/
FVG url
https://arts.units.it/request-item?handle=11368/3059086
Soggetti
  • event structure

  • behavioural equivalen...

  • emantics of true conc...

  • modal logics

google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback