Reduction of event structures under history preserving bisimulation

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 concurrency spectrum, namely history preserving bisimulation. In particular, we investigate this problem on two generalisations of prime event structures: asymmetric event structures, which rely on an asymmetric form of conflict, and flow event structures, which support a form of disjunctive causality. We single out conditions under which distinct events in an event structure can be seen as occurrences of the same activity in different contexts and thus can be folded into a single event without altering the original behaviour. By iterating the folding operation, any finite event structure can be reduced to a minimal form, behaviourally equivalent to the original one. This is not unique in general, as it depends on the order on which the folding operations are applied.