Toggle Main Menu Toggle Search

ePrints

On Synthesising Step Alphabets for Acyclic Invariant Structures

Lookup NU author(s): Professor Maciej Koutny, Dr Lukasz Mikulski

Downloads


Abstract

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.


Publication metadata

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 Name: ATAED 2017

Year of Conference: 2017

Acceptance date: 23/05/2017

Publisher: CEUR

URL: http://www.fernuni-hagen.de/ataed2017/


Share