Branching Processes of General Petri Nets

• Autorzy: Couvreur J. M. , Poitrenaud D. , Weil P.
• Języki publikacji: EN

Abstrakty

EN

We propose a new model of branching processes, suitable for describing the behavior of general Petri nets, without any finiteness or safeness assumption. In this framework, we define a new class of branching processes and unfoldings of a net N, which we call faithful. These coincide with the safe branching processes and unfoldings if N is safe, or weakly safe as in [Engelfriet 1991], but not in general. However, faithful branching processes and processes satisfy the good order-theoretic properties which make the safe processes of safe nets so useful in practice, and which are known not to hold for the safe processes of a general net. Faithful processes represent therefore good candidates to generalize the theory of safe nets to the general case.

Słowa kluczowe

EN

General Petri nets; unfolding; branching processes

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

Twórcy

autor

Couvreur J. M.

• Université d’Orléans, LIFO, Orléans, France

autor

Poitrenaud D.

• Universit´e Pierre et Marie Curie, LIP6, Paris, France

autor

Weil P.

• CNRS, LaBRI, UMR 5800, F-33400 Talence, France Univ. Bordeaux, LaBRI, UMR 5800, F-33400 Talence, France

Bibliografia

• [1] Best, E., Devillers, R.: Sequential and concurrent behaviour in Petri net theory, Theoretical Computer Science, 55, 1987, 87–136.
• [2] Couvreur, J.-M., Poitrenaud, D., Weil, P.: Branching Processes of General Petri Nets, Applications and Theory of Petri Nets, 6709, Springer, 2011, 129–148.
• [3] Engelfriet, J.: Branching Processes of Petri Nets, Acta Informatica, 28, 1991, 575–591.
• [4] van Glabbeek, R., Plotkin, G.: Configuration structures, event structures and Petri nets, Theoretical Computer Science, 410(41), September 2009, 4111–4159.
• [5] Haar, S.: Branching Processes of General S/T-Systems and their Properties, Electronic Notes in Theoretical Computer Science, 18, 1998.
• [6] Hayman, J., Winskel, G.: The unfolding of general Petri nets, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008) (R. Hariharan,M. Mukund, V. Vinay, Eds.), 2, Schloss Dagstuhl–Leibniz-Zentrumfuer Informatik, Dagstuhl, Germany, 2008, 223–234.
• [7] Hoogers, P., Kleijn, H., Thiagarajan, P.: An Event Structure Semantics for General Petri Nets, Theoretical Computer Science, 153, 1996, 129–170.
• [8] Keller,W.: Clustering for Petri Nets, Theoretical Computer Science, 308, 2003, 145–197.
• [9] Khomenko, V., Kondratyev, A., Koutny, M., Vogler, W.: Merged processes: a new condensed representation of Petri net behaviour, Acta Informatica, 43(5), 2006, 307–330.
• [10] McMillan, K. L., Probst, D. K.: A technique of state space search based on unfolding, Formal Methods in System Design, 6, 1995, 45–65.
• [11] Meseguer, J.,Montanari, U., Sassone, V.: On theModel of Computation of Place/Transition Petri Nets, Proc. of the 15th Int. Conference on Application and Theory of Petri Nets, 815, Springer Verlag, 1994, 16–38.
• [12] Murata, T.: Petri Nets: Properties, Analysis, and Applications, Proc. of the IEEE, 77(4), 1989, 541–580.
• [13] Nielsen, M., Plotkin, G., Winskel, G.: Petri Nets, Events Structures and Domains, Part I, Theoretical Computer Science, 13(1), 1981, 85–108.
• [14] Vogler, W.: Executions: A New Partial-order Semantics of Petri Nets., Theoretical Computer Science, 91, 1991, 205–238.