Affiliations: [a] Department of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1, Canada. [email protected] | [b] LIACS, Leiden University, P.O.Box 9512, NL-2300 RA, Leiden, The Netherlands. [email protected] | [c] School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, UK. [email protected] | [d] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland. [email protected]
Correspondence:
[*]
Address for correspondence: LIACS, Leiden University, P.O.Box 9512, NL-2300 RA, Leiden The Netherlands
Abstract: A step trace is an equivalence class of step sequences, where the equivalence is determined by dependencies between pairs of actions expressed as potential simultaneity and sequentialisability. Step traces can be represented by invariant structures with two relations: mutual exclusion and (possibly cyclic) weak causality. An important issue concerning invariant structures is to decide whether an invariant structure represents a step trace over a given step alphabet. For the general case this problem has been solved and an effective decision procedure has been proposed. In this paper, we restrict the class of order structures being considered with the aim of achieving a better characterisation. Requiring that the weak causality relation is acyclic, makes it possible to solve the problem in a purely local way, by considering pairs of events, rather than whole structures.
