Alphabets of Acyclic Invariant Structures

• Autorzy: Janicki R. , Kleijn J. , Koutny M. , Mikulski Ł.

Identyfikatory

DOI

10.3233/FI-2017-1562

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

step trace; step alphabet; dependence structure; order structure; invariant structure; simultaneity; sequentialisability; interleaving; mutual exclusion; weak causality; acyclicity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 207--224
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Janicki R.

• Department of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1, Canada

autor

Kleijn J.

• LIACS, Leiden University, P.O.Box 9512, NL-2300 RA, Leiden, The Netherlands

autor

Koutny M.

• School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, UK

autor

Mikulski Ł.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland

Bibliografia

• [1] Mazurkiewicz A. Concurrent Program Schemes and Their Interpretations. DAIMI Rep. PB 78, Aarhus University, 1977. URL http://dx.doi.org/10.7146/dpb.v6i78.7691.
• [2] Mazurkiewicz AW. Basic notions of trace theory. In: de Bakker JW, de Roever WP, Rozenberg G (eds.), Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency. Vol. 354 in Lecture Notes in Computer Science, Springer, 1988 pp. 285–363. doi:10.1007/BFb0013025.
• [3] Diekert V, Rozenberg G (eds.). The Book of Traces. World Scientific, River Edge, NJ, USA, 1995. ISBN-10:9810220588, 13:978-9810220587.
• [4] Pratt V. Modeling concurrency with partial orders. International Journal of Parallel Programming, 1986; 15(1):33–71. doi:10.1007/BF01379149.
• [5] Hoogeboom HJ, Rozenberg G. Dependence Graphs. In: Diekert V, Rozenberg G (eds.), The Book of Traces, World Scientific, 1995 pp. 43–67.
• [6] Janicki R, Koutny M. Structure of Concurrency. Theor. Comput. Sci., 1993;112(1):5–52. doi:10.1016/0304-3975(93)90238-O.
• [7] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Step traces. Acta Informatica, 2016;53:35–65. doi:10.1007/s00236-015-0244-z. URL http://dx.doi.org/10.1007/s00236-015-0244-z.
• [8] Ehrenfeucht A, Rozenberg G. Reaction Systems. Fundamenta Informaticae, 2007;75(1-4):263–280.
• [9] Grabowski J. On Partial Languages. Fundamenta Informaticae, 1983;4(2):125–147.
• [10] Rozenberg G, Verraedt R. Subset Languages of Petri Nets. Part I. Theoretical Computer Science, 1983; 26(3):301–326. URL https://doi.org/10.1016/0304-3975(83)90021-X.
• [11] Baldan P, Busi N, Corradini A, Pinna GM. Domain and event structure semantics for Petri nets with read and inhibitor arcs. Theoretical Computer Science, 2004;323(1-3):129–189. URL https://doi.org/10.1016/j.tcs.2004.04.001.
• [12] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Characterising Concurrent Histories. Fundamenta Informaticae, 2015;139(1):21–42. doi:10.3233/FI-2015-1224.
• [13] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Invariant Structures and Dependence Relations. Fundamenta Informaticae, 2017 in press.
• [14] Bergstra J, Ponse A, Smolka S (eds.). Handbook of Process Algebra. Elsevier, Amsterdam, 2001. ISBN-978-0-444-82830-9.
• [15] Montanari U, Rossi F. Contextual nets. Acta Informatica, 1995;32(6):545–596. doi:10.1007/BF01178907.
• [16] Vogler W. Partial order semantics and read arcs. Theoretical Computer Science, 2002;286(1):33–63.
• [17] Mikulski Ł, Koutny M. Folded Hasse diagrams of combined traces. Inf. Process. Lett., 2014;114(4):208–216. URL https://doi.org/10.1016/j.ipl.2013.11.009.
• [18] Szpilrajn E. Sur l’extension de l’ordre partiel. Fundamenta Mathematicae, 1930;16:386–389. URL http://eudml.org/doc/212499.
• [19] Janicki R, Kleijn J, Koutny M, Mikulski Ł. On Synthesising Step Alphabets for Acyclic Invariant Structures. Vol. 1847 in CEUR, 2017 pp. 76–88. URL http://www.fernuni-hagen.de/ataed2017/.