Event structures are one of the best known models for concurrency. Many variants of the basic model and many possible notions of equivalence for them have been devised in the literature. In this paper, we study how the spectrum of equivalences for Labelled Prime Event Structures built by Van Glabbeek and Goltz changes if we consider two simplified notions of event structures: the first is obtained by removing the causality relation (Coherence Spaces) and the second by removing the conflict relation (Elementary Event Structures). As expected, in both cases the spectrum turns out to be simplified, since some notions of equivalence coincide in the simplified settings; actually, we prove that removing causality simplifies the spectrum considerably more than removing conflict. Furthermore, while the labeling of events and their cardinality play no role when removing causality, both the labeling function and the cardinality of the event set dramatically influence the spectrum of equivalences in the conflict-free setting.

Conflict vs causality in event structures / Gorla, Daniele; Salvo, Ivano; Piperno, Adolfo. - In: ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. - ISSN 2075-2180. - 300:(2019), pp. 86-101. (Intervento presentato al convegno Combined 26th International Workshop on Expressiveness in Concurrency and 16th Workshop on Structural Operational Semantics, EXPRESS/SOS 2019 tenutosi a Amsterdam; Netherlands) [10.4204/EPTCS.300.6].

Conflict vs causality in event structures

Gorla, Daniele
;
Salvo, Ivano;Piperno, Adolfo
2019

Abstract

Event structures are one of the best known models for concurrency. Many variants of the basic model and many possible notions of equivalence for them have been devised in the literature. In this paper, we study how the spectrum of equivalences for Labelled Prime Event Structures built by Van Glabbeek and Goltz changes if we consider two simplified notions of event structures: the first is obtained by removing the causality relation (Coherence Spaces) and the second by removing the conflict relation (Elementary Event Structures). As expected, in both cases the spectrum turns out to be simplified, since some notions of equivalence coincide in the simplified settings; actually, we prove that removing causality simplifies the spectrum considerably more than removing conflict. Furthermore, while the labeling of events and their cardinality play no role when removing causality, both the labeling function and the cardinality of the event set dramatically influence the spectrum of equivalences in the conflict-free setting.
2019
Combined 26th International Workshop on Expressiveness in Concurrency and 16th Workshop on Structural Operational Semantics, EXPRESS/SOS 2019
event structures; concurrency; bisimilarity
04 Pubblicazione in atti di convegno::04c Atto di convegno in rivista
Conflict vs causality in event structures / Gorla, Daniele; Salvo, Ivano; Piperno, Adolfo. - In: ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE. - ISSN 2075-2180. - 300:(2019), pp. 86-101. (Intervento presentato al convegno Combined 26th International Workshop on Expressiveness in Concurrency and 16th Workshop on Structural Operational Semantics, EXPRESS/SOS 2019 tenutosi a Amsterdam; Netherlands) [10.4204/EPTCS.300.6].
File allegati a questo prodotto
File Dimensione Formato  
Gorla_conflict_2019.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 203.2 kB
Formato Adobe PDF
203.2 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1311148
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact