A Precise Characterisation of Step Traces and Their Concurrent Histories

Abstract

Step traces are an extension of Mazurkiewicz traces where each equivalence class (trace) consists of sequences of steps instead of sequences of atomic actions. Relations between the actions of the system are defined statically, as parameters of a concurrent step alphabet. By allowing only some of the possible relationships between actions, subclasses of step alphabets can be derived in a natural way. Properties of these classes can then be investigated in terms of invariant structures, i.e., the relational structures that represent the causal invariants that underlie the corresponding step traces. In this paper, we refine an earlier classification of subclasses of step alphabets and add eight new subclasses to this hierarchy. We divide these eight classes into three families on basis of the absence of a specific behavioural relation and then characterise the corresponding invariant structures.