Invariant Structures and Dependence Relations

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

Identyfikatory

DOI

10.3233/FI-2017-1574

• Języki publikacji: EN

Abstrakty

EN

A step trace is an equivalence class of step sequences which can be thought of as different observations of the same underlying concurrent history. Equivalence is determined on basis of a step alphabet that describes the relations between events in terms of potential simultaneity and sequentialisability. Step traces cannot be represented by standard partial orders, but require so-called invariant structures, extended order structures that capture the phenomena of mutual exclusion and weak causality. In this paper, we present an effective way of deciding whether an invariant structure represents a step trace over a given step alphabet. We also describe a method by which one can check whether a given invariant structure can represent a step trace over any step alphabet. Moreover, if the answer is positive, the method provides a suitable step alphabet.

Słowa kluczowe

EN

dependence graph; interleaving; invariant structure; mutual exclusion; partial order; sequentialisability; serialisability; simultaneity; step alphabet; step trace; synthesis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 1--29
• Opis fizyczny: Bibliogr. 25 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 A. Introduction to Trace Theory. In: Diekert V, Rozenberg G (eds.), The Book of Traces, pp. 3–42. World Scientific, 1995. doi:10.1142/9789814261456_0001.
• [3] 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, volume 354 of Lecture Notes in Computer Science, Springer, 1988, pp. 285–363.
• [4] Diekert V, Rozenberg G (eds.). The Book of Traces. World Scientific, River Edge, NJ, USA, 1995. ISBN: 978-981-02-2058-7.
• [5] Kleijn J, Koutny M. Formal Languages and Concurrent Behaviours. In: Enguix GB, Jiménez-López MD, Martín-Vide C (eds.), New Developments in Formal Languages and Applications, volume 113 of Studies in Computational Intelligence, Springer, 2008, pp. 125–182. ISBN: 978-3-540-78290-2.
• [6] Pratt V. Modeling concurrency with partial orders. International Journal of Parallel Programming, 1986; 15(1):33–71. doi:10.1007/BF01379149.
• [7] Hoogeboom HJ, Rozenberg G. Dependence Graphs. In: Diekert V, Rozenberg G (eds.), The Book of Traces, World Scientific, 1995, pp. 43–67.
• [8] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Generalising Traces. CS-TR 1436, Newcastle University, 2014.
• [9] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Order Structures for Subclasses of Generalised Traces. In: Dediu AH, Formenti E, Martín-Vide C, Truthe B (eds.), Language and Automata Theory and Applications, volume 8977 of Lecture Notes in Computer Science, Springer, 2015, pp. 689–700. doi:10.1007/978-3-319-15579-1_54.
• [10] 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.
• [11] van der Aalst WMP. Process Mining-Discovery, Conformance and Enhancement of Business Processes. Springer, 2011. doi:10.1007/978-3-642-19345-3. URL http://dx.doi.org/10.1007/978-3-642-19345-3.
• [12] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Springer-Verlag Berlin Heidelberg, 2015.
• [13] Ponce de León H, Rodríguez C, Carmona J, Heljanko K, Haar S. Unfolding-Based Process Discovery. In: Finkbeiner B, Pu G, Zhang L (eds.), Automated Technology for Verification and Analysis, volume 9364 of Lecture Notes in Computer Science, Springer, 2015 pp. 31–47. doi:10.1007/978-3-319-24953-7_4.
• [14] van der Aalst WMP, Stahl C. Modeling Business Processes-A Petri Net-Oriented Approach. Cooperative Information Systems series. MIT Press, 2011. ISBN 978-0-262-01538-7. URL http://mitpress.mit.edu/books/modeling-business-processes.
• [15] Petri CA. Kommunikation mit Automaten. Ph.D. Thesis, Bonn University, 1962.
• [16] Reisig W. Understanding Petri Nets - Modeling Techniques, Analysis Methods, Case Studies. Springer, 2013. doi:10.1007/978-3-642-33278-4. URL http://dx.doi.org/10.1007/978-3-642-33278-4.
• [17] Reisig W, Rozenberg G (eds.). Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, volume 1491 of Lecture Notes in Computer Science. Springer, 1998. doi:10.1007/3-540-65306-6.
• [18] Rozenberg G, Engelfriet J. Elementary Net Systems. In: Reisig W, Rozenberg G (eds.), Lectures on Petri Nets I: Basic Models, Advances in Petri Nets, volume 1491 of Lecture Notes in Computer Science, Springer, 1998, pp. 12–121. doi:10.1007/3-540-65306-6_14.
• [19] Janicki R, Koutny M. Semantics of Inhibitor Nets. Inf. Comput., 1995;123(1):1–16. URL https://doi.org/10.1006/inco.1995.1153.
• [20] Kleijn J, Koutny M. Mutex Causality in Processes and Traces of General Elementary Nets. Fundam. Inform., 2013;122(1-2):119–146. doi:10.3233/FI-2013-785.
• [21] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Order Structures for Subclasses of Generalised Traces. TR-CS 1437, Newcastle University, 2014. URL http://www.cs.ncl.ac.uk/publications/trs/papers/1437.pdf.
• [22] 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.
• [23] Janicki R, Kleijn J, Koutny M, Mikulski Ł. Characterising Concurrent Histories. Fundamenta Informaticae, 2015;139(1):21–42. doi:10.3233/FI-2015-1224.
• [24] Janicki R, Koutny M. Structure of Concurrency. Theor. Comput. Sci., 1993;112(1):5–52. doi:10.1016/0304-3975(93)90238-O.
• [25] Muscholl A. Automated Synthesis of Distributed Controllers. In: Halldórsson MM, Iwama K, Kobayashi N, Speckmann B (eds.), Automata, Languages, and Programming, Part II, volume 9135 of Lecture Notes in Computer Science, Springer, 2015, pp. 11–27. doi:10.1007/978-3-662-47666-6_2