Reduction of event structures under history preserving bisimulation

DOI10.1016/J.JLAMP.2015.10.004MaRDI QIDQ338613zbMATH OpenOpenAlexFDO

Authors Abel Armas-Cervantes, Paolo Baldan, Luciano García-Bañuelos

Publication date 7 November 2016

Published in Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.7181

history-preserving bisimilarity prime event structures asymmetric event structures flow event structures reduction of event structures

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: Event structures represent concurrent processes in terms of events and dependencies between events modelling behavioural relations like causality and conflict. Since the introduction of prime event structures, many variants of event structures have been proposed with different behavioural relations and, hence, with differences in their expressive power. One of the possible benefits of using a more expressive event structure is that of having a more compact representation for the same behaviour when considering the number of events used in a prime event structure. Therefore, this article addresses the problem of reducing the size of an event structure while preserving behaviour under a well-known notion of equivalence, namely history preserving bisimulation. In particular, we investigate this problem on two generalisations of the prime event structures. The first one, known as asymmetric event structure, relies on a asymmetric form of the conflict relation. The second one, known as flow event structure, supports a form of disjunctive causality. More specifically, we describe the conditions under which a set of events in an event structure can be folded into a single event while preserving the original behaviour. The successive application of this folding operation leads to a minimal size event structure. However, the order on which the folding operation is applied may lead to different minimal size event structures. The latter has a negative implication on the potential use of a minimal size event structure as a canonical representation for behaviour.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Reduction of event structures under history preserving bisimulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338613)