License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.30
URN: urn:nbn:de:0030-drops-115923
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11592/
Go to the corresponding LIPIcs Volume Portal

Baldan, Paolo ; Raffaetà, Alessandra

Minimisation of Event Structures

pdf-format:
LIPIcs-FSTTCS-2019-30.pdf (0.5 MB)

Abstract

Event structures are fundamental models in concurrency theory, providing a representation of events in computation and of their relations, notably concurrency, conflict and causality. In this paper we present a theory of minimisation for event structures. Working in a class of event structures that generalises many stable event structure models in the literature, (e.g., prime, asymmetric, flow and bundle event structures) we study a notion of behaviour-preserving quotient, taking hereditary history preserving bisimilarity as a reference behavioural equivalence. We show that for any event structure a uniquely determined minimal quotient always exists. We observe that each event structure can be seen as the quotient of a prime event structure, and that quotients of general event structures arise from quotients of (suitably defined) corresponding prime event structures. This gives a special relevance to quotients in the class of prime event structures, which are then studied in detail, providing a characterisation and showing that also prime event structures always admit a unique minimal quotient.

BibTeX - Entry

@InProceedings{baldan_et_al:LIPIcs:2019:11592,
  author =	{Paolo Baldan and Alessandra Raffaet{\`a}},
  title =	{{Minimisation of Event Structures}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11592},
  URN =		{urn:nbn:de:0030-drops-115923},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.30},
  annote =	{Keywords: Event structures, minimisation, history-preserving bisimilarity, behaviour-preserving quotient}
}

Keywords: Event structures, minimisation, history-preserving bisimilarity, behaviour-preserving quotient
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI