Modelling concurrency with comtraces and generalized comtraces (Q651308)

To faithfully capture operational semantics of concurrent systems one can represent their runs as sequences of symbols, each symbol corresponding to the execution of a basic atomic action. By taking into account only the essential causal relationships between the executed actions one can then group together different runs which only differ by the ordering of causally unrelated actions. In the resulting model of Mazurkiewicz traces, each abstract execution (trace) is an equivalence class of the quotient monoid of sequential executions which can be represented by a causal partial order on the actions involved in these executions. Comtraces (combined traces) are extensions of Mazurkiewicz traces that can also model the ``not later than'' relationship for runs represented as sequences of sets of simultaneously executed actions. The paper first introduces the novel notion of generalized comtraces, extending comtraces with a representation of ``non-simultaneity'' between executed actions. After that it studies some fundamental algebraic properties and canonical representations of comtraces and generalized comtraces. Finally, the authors discuss the relationship between generalized comtraces and generalized stratified order structures which are a counterpart of causal partial orders in the new theory. In particular, the paper shows that generalized comtraces can be represented by generalized stratified order structures.