Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis

• Autorzy: Devillers Raymond

Identyfikatory

DOI

10.3233/FI-2021-2080

• Języki publikacji: EN

Abstrakty

EN

In order to speed up the synthesis of Petri nets from labelled transition systems, a divide and conquer strategy consists in defining decompositions of labelled transition systems, such that each component is synthesisable iff so is the original system. Then corresponding Petri Net composition operators are searched to combine the solutions of the various components into a solution of the original system. The paper presents two such techniques, which may be combined: products and articulations. They may also be used to structure transition systems, and to analyse the performance of synthesis techniques when applied to such structures.

Słowa kluczowe

EN

labelled transition systems; composition; decomposition; Petri net synthesis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 1-2
• Strony: 1--31
• Opis fizyczny: Bibliogr. 24 poz., rys., wykr.

Twórcy

autor

Devillers Raymond

• Département d’Informatique, Université Libre de Bruxelles

Bibliografia

• [1] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, 2015. ISBN:978-3-662-47967-4. doi:10.1007/978-3-662-47967-4.
• [2] 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.
• [3] Best E, Schlachter U. Analysis of Petri Nets and Transition Systems. In: Proceedings 8th Interaction and Concurrency Experience, ICE 2015, Grenoble, France, 4-5th June 2015. 2015 pp. 53-67. doi:10.4204/EPTCS.189.6.
• [4] Best E, Devillers R, Schlachter U. Bounded choice-free Petri net synthesis: algorithmic issues. Acta Inf., 2018. 55(7):575-611. doi:10.1007/s00236-017-0310-9.
• [5] Schlachter U. Over-Approximative Petri Net Synthesis for Restricted Subclasses of Nets. In: Language and Automata Theory and Applications - 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings. 2018 pp. 296-307. doi:10.1007/978-3-319-77313-1_23.
• [6] Badouel E, Bernardinello L, Darondeau P. Polynomial Algorithms for the Synthesis of Bounded Nets. In: TAPSOFT’95: Theory and Practice of Software Development, 6th International Joint Conference CAAP/FASE, Aarhus, Denmark. 1995 pp. 364-378. doi:10.1007/3-540-59293-8_207.
• [7] Badouel E, Bernardinello L, Darondeau P. The Synthesis Problem for Elementary Net Systems is NP-Complete. Theor. Comput. Sci., 1997. 186(1-2):107-134. doi:10.1016/S0304-3975(96)00219-8.
• [8] Devillers R. Factorisation of transition systems. Acta Informatica, 2018. 55(4):339-362. doi:10.1007/s00236-017-0300-y.
• [9] Devillers R, Schlachter U. Factorisation of Petri Net Solvable Transition Systems. In: Application and Theory of Petri Nets and Concurrency - 39th International Conference, PETRI NETS 2018, Bratislava, Slovakia. 2018 pp. 82-98. doi:10.1007/978-3-319-91268-4_5.
• [10] Devillers R. Articulation of Transition Systems and its Application to Petri Net Synthesis. In: Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings. 2019 pp. 113-126. doi:10.1007/978-3-030-21571-2_8.
• [11] Arnold A. Finite Transition Systems - Semantics of Communicating Systems. Prentice Hall international series in computer science. Prentice Hall, 1994. ISBN:978-0-13-092990-7.
• [12] Desel J, Reisig W. The Synthesis Problem of Petri Nets. Acta Inf., 1996. 33(4):297-315. doi:10.1007/s002360050046.
• [13] Devillers R. Products of Transition Systems and Additions of Petri Nets. In: 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.R. Devillers / Articulations and Products of Transition Systems and their Applications to Petri Net Synthesis 31
• [14] Keller RM. A Fundamental Theorem of Asynchronous Parallel Computation. In: Sagamore Computer Conference, August 20-23 1974, LNCS Vol. 24. 1975 pp. 102-112. doi:10.1007/3-540-07135-0_113.
• [15] Hopcroft JE, Tarjan RE. Efficient Algorithms for Graph Manipulation [H] (Algorithm 447). Commun. ACM, 1973. 16(6):372-378. doi:10.1145/362248.362272.
• [16] Westbrook J, Tarjan RE. Maintaining Bridge-Connected and Biconnected Components On-Line. Algorithmica, 1992. 7(5&6):433-464. doi:10.1007/BF01758773.
• [17] Best E, Devillers R, Koutny M. The Box Algebra = Petri Nets + Process Expressions. Inf. Comput., 2002.178(1):44-100. doi:10.1006/inco.2002.3117.
• [18] Best E, Devillers RR, Erofeev E. A New Property of Choice-Free Petri Net Systems. In: Application and Theory of Petri Nets and Concurrency - 41st International Conference, PETRI NETS 2020, Paris, France, June 24-25, 2020, Proceedings. 2020 pp. 89-108. doi:10.1007/978-3-030-51831-8_5.
• [19] Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984. 4(4):373-396. doi:10.1007/BF02579150.
• [20] Dantzig G. Maximization of a linear function of variables subject to linear inequalities. In: Koopmans T(ed.), Activity Analysis of Production and Allocation, Proceedings. Wiley, New York, 1951 p. 339-347.
• [21] Klee V, Minty G. How Good Is the Simplex Algorithm? In: Shisha O (ed.), Inequalities III, Proceedings. Academic Press, New York, 1951 p. 159-175.
• [22] SMTInterpol, an Interpolating SMT Solver. https://ultimate.informatik.uni-freiburg.de/smtinterpol/.
• [23] Kroening D, Leroux J, Rümmer P. Interpolating Quantifier-Free Presburger Arithmetic. In: Logic for Programming, Artificial Intelligence, and Reasoning - 17th International Conference, LPAR-17, Yogyakarta, Indonesia, October 10-15, 2010. Proceedings. 2010 pp. 489-503. doi:10.1007/978-3-642-16242-8_35.
• [24] Tredup R. Hardness Results for the Synthesis of b-bounded Petri Nets. In: Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings. 2019 pp. 127-147. doi:10.1007/978-3-030-21571-2_9

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)