Concurrency, Histories, and Nets
We discuss an approach to lift the partial order model of concurrency as exemplified by Mazurkiewicz traces and Elementary Net systems to the case that events may happen simultaneously. Now behavioural observations are no longer in terms of sequences (words), but based on steps i.e. sets of simultaneously occurring actions. To identify step sequences that represent observations of the same concurrent computation, additional information on the relationships between actions has to be provided. The resulting equivalence classes are referred to as step traces. Partial orders alone are not expressive enough to describe the invariant, common relationships between the symbol occurrences in the step sequences forming a step trace. Instead we use general invariant structures allowing to express ‘not later than’ and ‘mutual exclusion’ relations. A history is then a set of saturated labelled invariant structures that can be used to describe the elements of a step trace. Elementary Net systems extended with inhibitor arcs and mutex arcs provide a system model that fits THE concurrency paradigm for such histories.