Reduction of event structures under history preserving bisimulation

DOI10.1016/J.JLAMP.2015.10.004zbMATH Open1392.68281arXiv1403.7181OpenAlexW1569109463MaRDI QIDQ338613FDOQ338613

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)

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.

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

Recommendations

• Conflict vs causality in event structures
• scientific article; zbMATH DE number 4018370
• Simultaneity in event structures
• scientific article; zbMATH DE number 86273
• scientific article; zbMATH DE number 1534589

zbMATH Keywords

history-preserving bisimilarityprime event structuresasymmetric event structuresflow event structuresreduction of event structures

Mathematics Subject Classification ID

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

Cites Work

• Petri nets, event structures and domains. I
• Concurrent bisimulations in Petri nets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Contextual Petri nets, asymmetric event structures, and processes
• Parallel product of event structures
• Title not available (Why is that?)
• Minimal transition systems for history-preserving bisimulation

Cited In (11)

• Conflict vs causality in event structures
• Title not available (Why is that?)
• On the expressive power of behavioral profiles
• Event structures with disabling/enabling relation and event automata
• Minimal transition systems for history-preserving bisimulation
• Unification and combination of a class of traversal strategies made with pattern matching and fixed-points
• Comparative Transition System Semantics for Cause-Respecting Reversible Prime Event Structures
• CONCUR 2005 – Concurrency Theory
• Concurrency-preserving minimal process representation
• Title not available (Why is that?)
• Minimisation of event structures

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)