Mutex Causality in Processes and Traces of General Elementary Nets

• Autorzy: Kleijn J. , Koutny M.
• Języki publikacji: EN

Abstrakty

EN

A concurrent history represented by a causality structure that captures the intrinsic, invariant dependencies between its actions, can be interpreted as defining a set of closely related observations (e.g., step sequences). Depending on the relationships observed in the histories of a system, the concurrency paradigm to which it adheres may be identified, with different concurrency paradigms underpinned by different kinds of causality structures. Elementary net systems with inhibitor arcs and mutex arcs (ENIM-systems) are a system model that through its process semantics and associated causality structures fits the least restrictive concurrency paradigm. One can also investigate the abstract behaviour of an ENIM-system by grouping together step sequences in equivalence classes (generalised comtraces) using the structural relations between its transitions. The resulting concurrent histories of the ENIM-system are consistent with the generalised stratified order structures underlying its processes. The paper establishes a link between ENIM-systems and trace theory allowing one to discuss different observations of concurrent behaviour in a way that is consistent with the causality semantics defined by the operationally defined processes.

Słowa kluczowe

EN

concurrency paradigm; elementary net system; inhibitor arc; mutex arc; step sequence; causality; generalised stratified order structure; process semantics; generalised comtrace

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 1-2
• Strony: 119--146
• Opis fizyczny: Bibliogr. 27 poz., rys.

Twórcy

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, U.K.

Bibliografia

• [1] Best, E., Devillers, R.: Sequential and Concurrent Behaviour in Petri Net Theory. Theoretical Computer Science 55 (1987) 87–136
• [2] Billington, J.: Protocol Specification Using P-Graphs, a Technique Based on Coloured Petri Nets. In: Part II of [25] (1998) 331–385
• [3] Darondeau, P., Koutny, M., Pietkiewicz-Koutny M., Yakovlev, A.: Synthesis of Nets with Step Firing Policies. Fundamenta Informaticae 94 (2009) 275–303
• [4] Diekert, V., Rozenberg, G. (eds.) The Book of Traces, World Scientific (1995)
• [5] Donatelli, S., Franceschinis, G.: Modelling and Analysis of Distributed Software Using GSPNs. In: Part II of [25], (1998) 438–476
• [6] Esparza, J., Bruns, G.: Trapping Mutual Exclusion in the Box Calculus. Theoretical Computer Science 153 (1996) 95–128
• [7] Hoogeboom, H.J., Rozenberg, G.: Dependence Graphs: In [4], 43–67
• [8] Gaifman, H., Pratt, V.R.: Partial Order Models of Concurrency and the Computation of Functions. In: LICS, IEEE Computer Society (1987) 72–85
• [9] Guo, G., Janicki, R.: Modelling Concurrent Behaviours by Commutativity and Weak Causality Relations. Lecture Notes in Computer Science 2422 (2002) 178–191
• [10] Janicki, R.: Relational Structures Model of Concurrency. Acta Informatica 45 (2008) 279–320
• [11] Janicki, R., Koutny,M.: Structure of Concurrency. Theoretical Computer Science 112 (1993) 5–52
• [12] Janicki, R., Koutny,M.: Semantics of Inhibitor Nets. Information and Computation 123 (1995) 1–16
• [13] Janicki, R., Koutny, M.: Order Structures and Generalisations of Szpilrajn’s Theorem. Acta Informatica 34 (1997) 367–388
• [14] Janicki, R., Kleijn, J., Koutny, M.: Quotient Monoids and Concurrent Behaviours. In: Scientific Applications of Language Methods, Carlos Mart´n-Vide (ed.). Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory 2, World Scientific (2010) 313–386
• [15] Janicki, R. L, D.T.M.: Modelling Concurrency with Quotient Monoids. Lecture Notes in Computer Science 5062 (2008) 251–269
• [16] Janicki, R. L, D.T.M.: Modelling Concurrency with Comtraces and Generalized Comtraces. Information and Computation 209 (2011) 1355–1389
• [17] Juhás, G., Lorenz, R., Mauser, S.: Causal Semantics of Algebraic Petri Nets Distinguishing Concurrency and Synchronicity. Fundamenta Informaticae 86 (2008) 255–298
• [18] Kleijn, H.C.M., Koutny, M.: Process Semantics of General Inhibitor Nets. Information and Computation 190 (2004) 18–69
• [19] Kleijn, J., Koutny, M.,: Formal Languages and Concurrent Behaviours. In: New Developments in Formal Languages and Applications, Gemma Bel-Enguix, M. Dolores Jiménez-Lopez, Carlos Martn-Vide (eds.). Studies in Computational Intelligence, Volume 2, Springer (2008) 125–182
• [20] Kleijn, J., Koutny, M.: The Mutex Paradigm of Concurrency. Lecture Notes in Computer Science 6709 (2011) 228–247
• [21] Kleijn, J., Koutny, M., Rozenberg, G.: Petri Net Semantics for Membrane Systems. Journal of Automata, Languages, and Combinatorics 11 (2006) 321–340
• [22] L, D.T.M.: On Three Alternative Characterizations of Combined Traces. Fundamenta Informaticae 113 (2011) 265–293
• [23] Lengauer, C., Hehner, E.C.R.: A Methodology for Programming with Concurrency: An Informal Presentation. Science of Computer Programming 2 (1982) 1–18
• [24] Mazurkiewicz, A.: Concurrent Program Schemes and their Interpretations. Technical Report DAIMI-78, University of Aarhus (1977)
• [25] Reisig, W., Rozenberg, G. (eds.): Lectures on Petri Nets. Lecture Notes in Computer Science 1491,1492 (1998)
• [26] Rozenberg, G., Engelfriet, J.: Elementary Net Systems. In: Part I of [25] (1998) 12–121
• [27] Szpilrajn, E.: Sur l’extension de l’ordre partiel. Fundamenta Mathematicae 16 (1930) 386–389