Classifying invariant structures of step traces

In the study of behaviours of concurrent systems, traces are sets of behaviourally equivalent action sequences. Traces can be represented by causal partial orders. Step traces, on the other hand, are sets of behaviourally equivalent step sequences, each step being a set of simultaneous actions. Step traces can be represented by relational structures comprising non-simultaneity and weak causality. In this paper, we propose a classification of step alphabets as well as the corresponding step traces and relational structures representing them. We also explain how the original trace model fits into the overall framework.Algorithms and the Foundations of Software technolog