Analysis and Synthesis of Weighted Marked Graph Petri Nets : Exact and Approximate Methods

• Autorzy: Devillers Raymond , Hujsa Thomas

Identyfikatory

DOI

10.3233/FI-2019-1837

• Języki publikacji: EN

Abstrakty

EN

Numerous real-world systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a labelled transition system (lts) describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. We provide new behavioural properties of WMGs expressed on their reachability graph, notably backward persistence and strong similarities between any two sequences sharing the same starting state and the same destination state. Besides, we design a general synthesis procedure aiming at the WMG class. Finally, when no solution to the synthesis problem exists, i.e., when the given lts is not WMG-solvable, we show how to construct a WMG whose reachability graph is a minimal over-approximation of the given lts.

Słowa kluczowe

EN

weighted Petri net; analysis; synthesis; marked graph; event graph; theory of regions; approximation; persistence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 169, nr 1-2
• Strony: 1--30
• Opis fizyczny: Bibliogr. 39 poz., rys.

Twórcy

autor

Devillers Raymond

• Département d’Informatique, Université Libre de Bruxelles, B-1050 Brussels, Belgium

autor

Hujsa Thomas

• LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France

Bibliografia

• [1] Desel J, Esparza J. Free Choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, New York, USA, 1995.
• [2] Hujsa T, Delosme JM, Munier-Kordon A. On Liveness and Reversibility of Equal-Conflict Petri Nets. Fundamenta Informaticae, 2016. 146(1):83-119. doi:10.3233/FI-2016-1376.
• [3] Hujsa T, Devillers R. On Liveness and Deadlockability in Subclasses of Weighted Petri Nets. Application and Theory of Petri Nets and Concurrency: 38th International Conference, Petri NETS 2017, Zaragoza, Spain, Proceedings, 2017. pp. 267-287. doi:10.1007/978-3-319-57861-3_16.
• [4] Silva M, Teruel E, Colom JM. Linear algebraic and linear programming techniques for the analysis of place/transition net systems. Lectures on Petri Nets I: Basic Models, LNCS 1491, 1998. pp. 309-373. doi:10.1007/3-540-65306-6_19.
• [5] Teruel E, Silva M. Structure theory of Equal Conflict systems. Theoretical Computer Science, 1996. 153(1&2):271-300. doi:10.1016/0304-3975(95)00124-7.
• [6] Lee EA, Messerschmitt DG. Synchronous Data Flow. Proceedings of the IEEE, 1987. 75(9):1235-1245.
• [7] Lee E, Messerschmidt D. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Transaction on Computers, C-36(1), 1987. pp. 24-35. doi:10.1109/TC.1987.5009446.
• [8] Pino JL, Bhattacharyya SS, Lee EA. A hierarchical multiprocessor scheduling framework for synchronous dataflow graphs. Technical report, University of California, Berkeley, 1995.
• [9] Sriram S, Bhattacharyya SS. Embedded multiprocessors: scheduling and synchronization. Signal Processing and Communications. CRC Press, 2009.
• [10] Teruel E, Chrzastowski-Wachtel P, Colom JM, Silva M. On weighted T-systems. 13th International Conference on Application and Theory of Petri Nets and Concurrency (ICATPN), LNCS 616, 1992. pp. 348-367. doi:/10.1007/3-540-55676-1_20.
• [11] Marchetti O, Munier-Kordon A. A sufficient condition for the liveness of Weighted Event Graphs. European Journal of Operational Research, 2009. 197(2):532-540. doi:10.1016/j.ejor.2008.07.037.
• [12] Hujsa T. Contribution to the study of weighted Petri nets. Ph.D. thesis, Pierre and Marie Curie University, Paris, France, 2014. URL https://tel.archives-ouvertes.fr/tel-01127406.
• [13] Hujsa T, Delosme J, Kordon AM. On the Reversibility of Well-Behaved Weighted Choice-Free Systems. Application and Theory of Petri Nets and Concurrency-35th International Conference, PETRI NETS 2014, Tunis, Tunisia, 2014. pp. 334-353. doi:10.1007/978-3-319-07734-5_18.
• [14] Best E, Devillers R. Synthesis of Bounded Choice-Free Petri Nets. 26th International Conference on Concurrency Theory, CONCUR 2015, Madrid, Spain, 2015. pp. 128-141. doi:10.4230/LIPIcs.CONCUR. 2015.128.
• [15] Best E, Devillers R, Schlachter U. Bounded Choice-Free Petri Net Synthesis: Algorithmic Issues. Acta Informaticae, 2018. 55(7):575-611. doi:10.1007/s00236-017-0310-9.
• [16] Devillers R, Erofeev E, Hujsa T. Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems. International Workshop on Algorithms & Theories for the Analysis of Event Data, Bratislava, Slovakia, Proceedings, 2018. pp. 75-90.
• [17] Schlachter U. Over-Approximative Petri Net Synthesis for Restricted Subclasses of Nets. LATA 2018, LNCS 10792, 2018. pp. 296-307.
• [18] Schlachter U. Petri Net Synthesis and Modal Specifications. Ph.D. thesis, University of Oldenburg, Germany, 2018. URL http://oops.uni-oldenburg.de/3755.
• [19] Best E, Devillers R. Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets. In: 8th International Conference on Language and Automata Theory and Applications (LATA 2014). 2014 pp. 161-172. doi:10.1007/978-3-319-04921-2_13.
• [20] Best E, Devillers R. State space axioms for T-systems. Acta Informaticae, 2015. 52(2-3):133-152. doi:10.1007/s00236-015-0219-0.
• [21] Best E, Devillers R. Characterisation of the State Spaces of Marked Graph Petri Nets. Information and Computation, 2017. 253(3):399-410. doi:10.1016/j.ic.2016.06.006.
• [22] Devillers R, Hujsa T. Analysis and Synthesis of Weighted Marked Graph Petri Nets. Application and Theory of Petri Nets and Concurrency-39th International Conference, PETRI NETS 2018, Bratislava, Slovakia, Proceedings, 2018. pp. 19-39. doi:10.1007/978-3-319-91268-4_2.
• [23] Hujsa T, Delosme JM, Munier-Kordon A. Polynomial Sufficient Conditions of Well-Behavedness and Home Markings in Subclasses of Weighted Petri Nets. ACM Trans. Embed. Comput. Syst., 2014. 13(4s):141:1-141:25. doi:10.1145/2627349.
• [24] Delosme J, Hujsa T, Munier-Kordon A. Polynomial Sufficient Conditions of Well-Behavedness for Weighted Join-Free and Choice-Free Systems. In: 13th International Conference on Application of Concurrency to System Design (ACSD 2013). 2013 pp. 90-99. doi:10.1109/ACSD.2013.12.
• [25] Crespi-Reghizzi S, Mandrioli D. A Decidability Theorem for a Class of Vector-Addition Systems. Inf. Process. Lett., 1975. 3(3):78-80. doi:10.1016/0020-0190(75)90020-4.
• [26] Teruel E, Colom JM, Silva M. Choice-Free Petri Nets: a Model for Deterministic Concurrent Systems with Bulk Services and Arrivals. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 1997. 27(1):73-83. doi:10.1109/3468.553226.
• [27] Best E, Devillers R. Synthesis and reengineering of persistent systems. Acta Informaticae, 2015. 52(1):35-60. doi:10.1007/s00236-014-0209-7.
• [28] Commoner F, Holt A, Even S, Pnueli A. Marked Directed Graphs. J. Comput. Syst. Sci, 1971. 5(5):511-523. doi:10.1016/S0022-0000(71)80013-2.
• [29] Keller RM. A Fundamental Theorem of Asynchronous Parallel Computation. Sagamore Computer Conference 1974, LNCS 24, 1975. pp. 102-112. doi:10.1007/3-540-07135-0_113.
• [30] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Springer-Verlag, 2015. ISBN 978-3-662-47966-7. doi:10.1007/978-3-662-47967-4.
• [31] Best E, Devillers R. Synthesis of Persistent Systems. Application and Theory of Petri Nets and Concurrency-35th International Conference, PETRI NETS 2014, Tunis, Tunisia, 2014. Proceedings, 2014. pp. 111-129. doi:10.1007/978-3-319-07734-5_7.
• [32] Best E, Devillers R. Synthesis of live and bounded persistent systems. Fundamenta Informaticae, 2015. 140:39-59. doi:10.3233/FI-2015-1244.
• [33] Devillers R. Products of Transition Systems and Additions of Petri Nets. Proc. 16th International Conference on Application of Concurrency to System Design (ACSD 2016) J. Desel and A. Yakovlev (eds), 2016. pp. 65-73. doi:10.1109/ACSD.2016.10.
• [34] Devillers R. Factorisation of transition systems. Acta Informaticae, 2018. 55(4):339-362. doi:10.1007/s00236-017-0300-y.
• [35] Devillers R, Schlachter U. Factorisation of Petri Net Solvable Transition Systems. Application and Theory of Petri Nets and Concurrency - 39th International Conference, PETRI NETS 2018, Bratislava, Slovakia, Proceedings, 2018. pp. 82-98. doi:10.1007/978-3-319-91268-4_5.
• [36] Ehrenfeucht A, Rozenberg G. Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem. Acta Informaticae, 1990. 27(4):315-342. doi:10.1007/BF00264611.
• [37] Ehrenfeucht A, Rozenberg G. A Characterization of Set Representable Labeled Partial 2-Structures Through Decompositions. Acta Informaticae, 1990. 28(1):83-94. doi:10.1007/BF02983375.
• [38] Darondeau P. Equality of languages coincides with isomorphism of reachable state graphs for bounded and persistent Petri nets. Inf. Process. Lett., 2005. 94(6):241-245. doi:10.1016/j.ipl.2005.03.002.
• [39] Best E, Darondeau P. A decomposition theorem for finite persistent transition systems. Acta Inf., 2009. 46(3):237-254. doi:10.1007/s00236-009-0095-6.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).