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.
|Data di pubblicazione:||2019|
|Titolo:||Minimisation of event structures|
|Titolo del libro:||39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS)|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2019.30|
|Appare nelle tipologie:||4.1 Articolo in Atti di convegno|