Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday
Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa
Article type: Research Article
Authors: Janicki, Ryszarda | Kleijn, Jettyb; * | Koutny, Maciejc | Mikulski, Łukaszd
Affiliations: [a] Department of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1, Canada. janicki@mcmaster.ca | [b] LIACS, Leiden University, P.O.Box 9512, NL-2300 RA, Leiden, The Netherlands. h.c.m.kleijn@liacs.leidenuniv.nl | [c] School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, UK. maciej.koutny@ncl.ac.uk | [d] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland. frodo@mat.umk.pl
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.
Keywords: step trace, step alphabet, dependence structure, order structure, invariant structure, simultaneity, sequentialisability, interleaving, mutual exclusion, weak causality, acyclicity
DOI: 10.3233/FI-2017-1562
Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 207-224, 2017
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl