Lookup NU author(s): Professor Maciej Koutny,
Dr Lukasz Mikulski
This is the authors' accepted manuscript of an article that has been published in its final definitive form by IOS Press, 2017.
For re-use rights please refer to the publisher's terms and conditions.
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.
Author(s): Janicki R, Kleijn J, Koutny M, Mikulski L
Publication type: Article
Publication status: Published
Journal: Fundamenta Informaticae
Online publication date: 09/08/2017
Acceptance date: 07/06/2017
ISSN (print): 0169-2968
ISSN (electronic): 1875-8681
Publisher: IOS Press
Altmetrics provided by Altmetric