Synthesis of Nets with Step Firing Policies

• Autorzy: Darondeau P. , Koutny M. , Pietkiewicz-Koutny M. , Yakovlev A.
• Języki publikacji: EN

Abstrakty

EN

The unconstrained step semantics of Petri nets is impractical for simulating and modelling applications. In the past, this inadequacy has been alleviated by introducing various flavours of maximally concurrent semantics, as well as priority orders. In this paper, we introduce a general way of controlling step semantics of Petri nets through step firing policies that restrict the concurrent behaviour of Petri nets and so improve their execution and modelling features. In a nutshell, a step firing policy disables at each marking a subset of enabled steps which could otherwise be executed. We discuss various examples of step firing policies and then investigate the synthesis problem for Petri nets controlled by such policies. Using generalised regions of step transition systems, we provide an axiomatic characterisation of those transition systems which can be realised as reachability graphs of Petri nets controlled by a given step firing policy. We also provide two different decision and synthesis algorithms for PT-nets and step firing policies based on linear rewards of steps, where the reward for firing a single transition is either fixed or it depends on the current net marking. The simplicity of the algorithms supports our claim that the proposed approach is practical.

Słowa kluczowe

EN

Petri net; step firing policy; step transition system; regions; synthesis problems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 94, nr 3/4
• Strony: 275--303
• Opis fizyczny: Bibliogr. 20 poz., wykr.

Twórcy

autor

Darondeau P.

autor

Koutny M.

autor

Pietkiewicz-Koutny M.

autor

Yakovlev A.

• Centre de recherche INRIA, Rennes-Bretagne Atlantique, campus de Beaulieu, F-35042 Rennes Cedex, France,

Bibliografia

• [1] http://www2.informatik.hu-berlin.de/˜starke/ina.html.
• [2] Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial Algorithms for the Synthesis of Bounded Nets, TAPSOFT (P. D. Mosses, M. Nielsen, M. I. Schwartzbach, Eds.), LNCS 915, Springer, 1995, 364-378.
• [3] Badouel, E., Darondeau, P.: On the Synthesis of General Petri Nets, Report 3025, INRIA-RR, 1996.
• [4] Badouel, E., Darondeau, P.: Theory of Regions, Petri Nets (W. Reisig, G. Rozenberg, Eds.), LNCS 1491, Springer, 1996, 529-586.
• [5] Bernardinello, L.,Michelis, G. D., Petruni, K., Vigna, S.: On the Synchronic Structure of Transition Systems, Structures in Concurrency Theory (J. Desel, Ed.), Springer, 1995.
• [6] Busi, N., Pinna, G.M.: Synthesis of Nets with Inhibitor Arcs, CONCUR (A.W. Mazurkiewicz, J. Winkowski, Eds.), LNCS 1243, Springer, 1997, 151-165.
• [7] Chernikova, N.: Algorithm for Finding a General Formula for the Non-negative Solutions of a System of Linear Inequalities, USSR Computational Mathematics and Mathematical Physics, 5, 1965, 228-233.
• [8] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, IEEE Trans. on CAD of Integrated Circuits and Systems, 21, 2002, 109-130.
• [9] Desel, J., Reisig, W.: The Synthesis Problem of Petri Nets, Acta Inf., 33(4), 1996, 297-315.
• [10] Ehrenfeucht, A., Rozenberg, G.: Theory of 2-Structures, Part I: Clans, Basic Subclasses, and Morphisms, Theor. Comput. Sci., 70(3), 1990, 277-303.
• [11] Ehrenfeucht, A., Rozenberg, G.: Theory of 2-Structures, Part II: Representation Through Labeled Tree Families, Theor. Comput. Sci., 70(3), 1990, 305-342.
• [12] Juhás, G., Lorenz, R., Neumair, C.: Modelling and Control with Modules of Signal Nets, Lectures on Concurrency and Petri Nets (J. Desel, W. Reisig, G. Rozenberg, Eds.), LNCS 3098, Springer, 2003, 585-625, ISBN 3-540-22261-8.
• [13] Kleijn, J., Koutny, M., Rozenberg, G.: Towards a Petri Net Semantics for Membrane Systems, Workshop on Membrane Computing (R. Freund, G. Paun, G. Rozenberg, A. Salomaa, Eds.), LNCS 3850, Springer, 2005, 292-309.
• [14] Koutny, M., Pietkiewicz-Koutny,M.: Transition Systems of Elementary Net Systems with Localities, CONCUR (C. Baier, H. Hermanns, Eds.), LNCS 4137, Springer, 2006, 173-187.
• [15] Koutny,M., Pietkiewicz-Koutny,M.: Synthesis of ElementaryNet Systems with Context Arcs and Localities, ICATPN (J. Kleijn, A. Yakovlev, Eds.), LNCS 4546, Springer, 2007, 281-300.
• [16] Mazurkiewicz, A.: Petri NetsWithout Tokens, ICATPN (J. Kleijn, A. Yakovlev, Eds.), LNCS 4546, Springer, 2007, 20-23.
• [17] Mukund,M.: Petri Nets and Step Transition Systems, Int. J. Found. Comput. Sci., 3(4), 1992, 443-478.
• [18] Pietkiewicz-Koutny, M.: The Synthesis Problem for Elementary Net Systems with Inhibitor Arcs, Fundam. Inform., 40(2-3), 1999, 251-283.
• [19] Schrijver, A.: Theory of Linear and Integer Programming, John Wiley, 1986.
• [20] Starke, P. H.: Some properties of timed nets under the earliest firing rule, European Workshop on Applications and Theory in Petri Nets (G. Rozenberg, Ed.), LNCS 424, Springer, 1988, 418-432, ISBN 3-540-52494-0.