Reduction of event structures under history preserving bisimulation

Abstract

Event structures represent concurrent processes in terms of events and dependency relations between events like causality and conflict. Since the introduction of prime event structures, many variants of event structures have been proposed with different dependency relations and, hence, with differences in their expressive power. One of the possible benefits of using a more expressive event structure model is that of obtaining a more compact representation for the same behaviour using a smaller number of events. This article addresses the problem of reducing the size of an event structure while preserving its behaviour under a classical notion of behavioural equivalence in the true concurrenc..