On Synthesising Step Alphabets for Acyclic Invariant Structures

  1. Lookup NU author(s)
  2. Professor Maciej Koutny
  3. Dr Lukasz Mikulski
Author(s)Janicki R, Kleijn J, Koutny M, Mikulski L
Editor(s)Robin Berghentum, Josep Carmona, Wil van der Aalst
Publication type Conference Proceedings (inc. Abstract)
Conference NameATAED 2017
Conference LocationZaragoza, Spain
Year of Conference2017
Source Publication Date
Full text is available for this publication:
A step alphabet describes dependencies between the actions of a concurrent system in the form of two relations expressing potential simultaneity and sequentialisability. These form the basis for the identification of step sequences as observations of the same run of the system. The resulting equivalence classes - step traces - can be represented by (labelled) invariant structures with two relations, viz. mutex and weak causality.In this paper, we address the following synthesis problem for acyclic invariant structures which are structures corresponding to step traces with sequential realisations: given an acyclic invariant structure that can represent a step trace, construct a suitable step alphabet, ie provide suitable simultaneity and sequentialisability relations for its actions.The main result is that the set of all suitable alphabets forms a complete lattice with the ordering derived from the relative `strength' of the dependencies between individual actions.