Synthesis of Pure and Impure Petri nets with Restricted Place-environments : Complexity Issues

• Autorzy: Devillers Raymond , Tredup Ronny

Identyfikatory

DOI

10.3233/FI-222135

• Języki publikacji: EN

Abstrakty

EN

Petri net synthesis consists in deciding for a given transition system A whether there exists a Petri net N whose reachability graph is isomorphic to A. Several works examined the synthesis of Petri net subclasses that restrict, for every place p of the net, the cardinality of its preset or of its postset or both in advance by small natural numbers̺ and κ, respectively, such as for example (weighted) marked graphs, (weighted) T-systems and choice-free nets. In this paper, we study the synthesis aiming at Petri nets which have such restricted place environments, from the viewpoint of classical and parameterized complexity: We first show that, for any fixed natural numbers̺ and κ, deciding whether for a given transition system A there is a Petri net N such that (1) its reachability graph is isomorphic to A and (2) for every place p of N the preset of p has at most̺ and the postset of p has at most κ elements is doable in polynomial time. Secondly, we introduce a modified version of the problem, namely ENVIRONMENT RESTRICTED SYNTHESIS (ERS, for short), where̺ and κ are part of the input, and show that ERS is NP-complete, regardless whether the sought net is impure or pure. In case of the impure nets, our methods also imply that ERS parameterized by̺ + κ is W [2]-hard.

Słowa kluczowe

EN

Computer Science; Formal Languages and Automata Theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: vol. 187 nr 2-4
• Strony: 139--165
• Opis fizyczny: Bibliogr. 40 poz., rys.

Twórcy

autor

Devillers Raymond

• Dèpartement d’Informatique - Universitè Libre de Bruxelles Boulevard du Triomphe, B1050 Brussels, Belgium

autor

Tredup Ronny

• Institut Für Informatik - Universität Rostock Albert-Einstein-Straße 22, D18059 Rostock, Germany

Bibliografia

• [1] Badouel E, Caillaud B, Darondeau P. Distributing Finite Automata Through Petri Net Synthesis. Formal Asp. Comput., 2002. 13(6):447-470. doi:10.1007/s001650200022.
• [2] van der Aalst WMP. Process Mining - Discovery, Conformance and Enhancement of Business Processes. Springer, 2011. doi:10.1007/978-3-642-19345-3.
• [3] Holloway LE, Krogh BH, Giua A. A Survey of Petri Net Methods for Controlled Discrete Event Systems. Discrete Event Dynamic Systems, 1997. 7(2):151-190. doi:10.1023/A:1008271916548.
• [4] Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. A region-based theory for state assignment in speed-independent circuits. IEEE Trans. on CAD of Integrated Circuits and Systems, 1997. 16(8):793-812. doi:10.1109/43.644602.
• [5] Ehrenfeucht A, Rozenberg G. Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem. Acta Inf., 1990. 27(4):315-342. doi:10.1007/BF00264611.
• [6] 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.
• [7] Badouel E, Bernardinello L, Darondeau P. Polynomial Algorithms for the Synthesis of Bounded Nets. In: TAPSOFT, volume 915 of Lecture Notes in Computer Science. Springer, 1995 pp. 364-378. doi: 10.1007/3-540-59293-8\ 207.
• [8] Commoner F, Holt AW, Even S, Pnueli A. Marked Directed Graphs. J. Comput. Syst. Sci., 1971. 5(5):511-523. doi:10.1016/S0022-0000(71)80013-2.
• [9] Best E. Structure Theory of Petri Nets: the Free Choice Hiatus. In: Advances in Petri Nets, volume 254 of Lecture Notes in Computer Science. Springer, 1986 pp. 168-205. doi:10.1007/BFb0046840.
• [10] Teruel E, Chrzastowski-Wachtel P, Colom JM, Su´arez MS. On Weighted T-Systems. In: Application and Theory of Petri Nets, volume 616 of Lecture Notes in Computer Science. Springer, 1992 pp. 348-367. doi:10.1007/3-540-55676-1 20.
• [11] Teruel E, Colom JM, Su´arez MS. Choice-free Petri nets: a model for deterministic concurrent systems with bulk services and arrivals. IEEE Trans. Systems, Man, and Cybernetics, Part A, 1997. 27(1):73-83. doi:10.1109/3468.553226.
• [12] Desel J, Esparza J. Free Choice Petri Nets. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995. doi:10.1017/CBO9780511526558.
• [13] Hujsa T, Delosme J, Kordon AM. On the Reversibility of Well-Behaved Weighted Choice-Free Systems. In: Petri Nets, volume 8489 of Lecture Notes in Computer Science. Springer, 2014 pp. 334-353.
• [14] Best E, Devillers RR. Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets. In: LATA, volume 8370 of Lecture Notes in Computer Science. Springer, 2014 pp. 161-172. doi: 10.1007/978-3-319-04921-2\_13.
• [15] Best E, Devillers RR, Schlachter U. Bounded choice-free Petri net synthesis: algorithmic issues. Acta Inf., 2018. 55(7):575-611. doi:10.1007/s00236-017-0310-9.
• [16] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. 47(8):859-882. doi:10.1109/12.707587.
• [17] Best E, Darondeau P. A decomposition theorem for finite persistent transition systems. Acta Informatica, 2009. 46(3):237-254. doi:10.1007/s00236-009-0095-6.
• [18] Best E, Devillers RR. Synthesis of Live and Bounded Persistent Systems. Fundam. Informaticae, 2015. 140(1):39-59. doi:10.3233/FI-2015-1244.
• [19] Best E, Hujsa T, Wimmel H. Sufficient conditions for the marked graph realisability of labelled transition systems. Theor. Comput. Sci., 2018. 750:101-116. doi:10.1016/j.tcs.2017.10.006.
• [20] Devillers RR, Erofeev E, Hujsa T. Synthesis of Weighted Marked Graphs from Constrained Labelled Transition Systems: A Geometric Approach. Trans. Petri Nets Other Model. Concurr., 2019. 14:172-191. doi:10.1007/978-3-662-60651-3\_7.
• [21] Devillers RR, Hujsa T. Analysis and Synthesis of Weighted Marked Graph Petri Nets: Exact and Approximate Methods. Fundam. Inform., 2019. 169(1-2):1-30. doi:10.3233/FI-2019-1837.
• [22] Devillers RR, Erofeev E, Hujsa T. Efficient Synthesis of Weighted Marked Graphs with Circular Reachability Graph, and Beyond. CoRR, 2019. abs/1910.14387. 1910.14387, URL http://arxiv.org/abs/1910.14387.
• [23] Downey RG, Fellows MR. Fixed Parameter Tractability and Completeness. In: Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992. 1992 pp. 191-225.
• [24] Downey RG, Fellows MR. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.
• [25] Tredup R. Synthesis of Petri Nets with Restricted Place-Environments: Classical and Parameterized. In: Application and Theory of Petri Nets and Concurrency - 42nd International Conference, PETRI NETS 2021, Virtual Event, June 23-25, 2021, Proceedings. 2021 pp. 292-311. doi:10.1007/978-3-030-76983-3_15.
• [26] Tredup R. Hardness Results for the Synthesis of b-bounded Petri Nets. In: Donatelli S, Haar S (eds.), Application and Theory of Petri Nets and Concurrency - 40th International Conference, PETRI NETS 2019, Aachen, Germany, June 23-28, 2019, Proceedings, volume 11522 of Lecture Notes in Computer Science. Springer, 2019 pp. 127-147. doi:10.1007/978-3-030-21571-2\_9.
• [27] Tredup R. The Complexity of Synthesizing sf nop-Equipped Boolean Petri Nets from g-Bounded Inputs. Trans. Petri Nets Other Model. Concurr., 2021. 15:101-125.
• [28] Tredup R. Synthesis of Structurally Restricted b-bounded Petri Nets: Complexity Results. In: Filiot E, Jungers RM, Potapov I (eds.), Reachability Problems - 13th International Conference, RP 2019, Brussels, Belgium, September 11-13, 2019, Proceedings, volume 11674 of Lecture Notes in Computer Science. Springer, 2019 pp. 202-217. doi:10.1007/978-3-030-30806-3\_16.
• [29] Tredup R. Parameterized Complexity of Synthesizing b-Bounded (m, n)-T-Systems. In: Chatzigeorgiou A, Dondi R, Herodotou H, Kapoutsis CA, Manolopoulos Y, Papadopoulos GA, Sikora F (eds.), SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science. Springer, 2020 pp. 223-235. doi: 10.1007/978-3-030-38919-2\_19.
• [30] Tredup R, Erofeev E. On the Parameterized Complexity of d-Restricted Boolean Net Synthesis. In: Theory and Applications of Models of Computation, volume 12337 of Theoretical Computer Science and General Issues. 2020 doi:10.1007/978-3-030-59267-7.
• [31] Tredup R, Erofeev E. On the Parameterized Complexity of Synthesizing Boolean Petri Nets With Restricted Dependency. In: Lange J, Mavridou A, Safina L, Scalas A (eds.), Proceedings 13th Interaction and Concurrency Experience, ICE 2020, Online, 19 June 2020, volume 324 of EPTCS. 2020 pp. 78-95. doi:10.4204/EPTCS.324.7.
• [32] Badouel E, Bernardinello L, Darondeau P. Petri Net Synthesis. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2015. doi:10.1007/978-3-662-47967-4.
• [33] Desel J, Reisig W. The Synthesis Problem of Petri Nets. Acta Inf., 1996. 33(4):297-315. doi:10.1007/s002360050046.
• [34] Rajan A. Theory of linear and integer programming, by Alexander Schrijver, Wiley, New York, 1986, 471 pp. Price $71.95. Networks, 1990. 20(6):801. doi:10.1002/net.3230200608.
• [35] Bradley SP, Hax AC, Magnanti TL. Applied Mathematical Programming, chapter 9: Integer Programming. Addison-Wesley, 1977.
• [36] Barrett CW, Sebastiani R, Seshia SA, Tinelli C. Satisfiability Modulo Theories. In: Handbook of Satisfiability, pp. 825-885. 2009. doi:10.3233/978-1-58603-929-5-825.
• [37] Karp RM. Reducibility Among Combinatorial Problems. In: Miller RE, Thatcher JW (eds.), Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series. Plenum Press, New York, 1972 pp. 85-103. doi:10.1007/978-1-4684-2001-2\_9.
• [38] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.
• [39] Amparore EG, Berthomieu B, Ciardo G, Dal-Zilio S, Gall`a F, Hillah L, Hulin-Hubard F, Jensen PG, Jezequel L, Kordon F, Botlan DL, Liebke T, Meijer J, Miner AS, Paviot-Adet E, Srba J, Thierry-Mieg Y, van Dijk T, Wolf K. Presentation of the 9th Edition of the Model Checking Contest. In: TACAS (3), volume 11429 of Lecture Notes in Computer Science. Springer, 2019 pp. 50-68.
• [40] Moore C, Robson JM. Hard Tiling Problems with Simple Tiles. Discrete & Computational Geometry, 2001. 26(4):573-590. doi:10.1007/s00454-001-0047-6.