The Complexity of Synthesis of b-Bounded Petri Nets

• Autorzy: Tredup Ronny

Identyfikatory

DOI

10.3233/FI-2021-2084

• Języki publikacji: EN

Abstrakty

EN

For a fixed type of Petri nets τ, τ-SYNTHESIS is the task of finding for a given transition system A a Petri net N of type τ(τ-net, for short) whose reachability graph is isomorphic to A if there is one. The decision version of this search problem is called τ-SOLVABILITY. If an input A allows a positive decision, then it is called τ-solvable and a sought net N τ-solves A. As a well known fact, A is τ-solvable if and only if it has the so-called τ-event state separation property (τ-ESSP, for short) and the τ-state separation property (τ-SSP, for short). The question whether A has the τ-ESSP or the τ-SSP defines also decision problems. In this paper, for all b ∈ ℕ, we completely characterize the computational complexity of τ-SOLVABILITY, τ-ESSP and τ-SSP for the types of pure b-bounded Place/Transition-nets, the b-bounded Place/Transitionnets and their corresponding ℤb+1-extensions.

Słowa kluczowe

EN

Petri nets; synthesis; b-bounded; SSP; ESSP; solvability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 1-2
• Strony: 125--167
• Opis fizyczny: Bibb.ogr. 26 poz., rys., tab.

Twórcy

autor

Tredup Ronny

• Institut für Informatik, Theoretische Informatik, Universität Rostock

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] 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.
• [6] 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.
• [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] Schmitt V. Flip-Flop Nets. In: STACS, volume 1046 of Lecture Notes in Computer Science. Springer, 1996 pp. 517–528. doi:10.1007/3-540-60922-9\42.
• [9] Tredup R, Rosenke C. The Complexity of Synthesis for 43 Boolean Petri Net Types. In: Gopal TV, Watada J (eds.), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13-16, 2019, Proceedings, volume 11436 of Lecture Notes in Computer Science. Springer, 2019 pp. 615–634. doi:10.1007/978-3-030-14812-6\38.
• [10] Tredup R, Rosenke C. On the Hardness of Synthesizing Boolean Nets. In: ATAED@Petri Nets/ACSD, volume 2371 of CEUR Workshop Proceedings. CEUR-WS.org, 2019 pp. 71–86.
• [11] Tredup R, Rosenke C, Wolf K. Elementary Net Synthesis Remains NP-Complete Even for Extremely Simple Inputs. In: Petri Nets, volume 10877 of Lecture Notes in Computer Science. Springer, 2018 pp. 40–59. doi:10.1007/978-3-319-91268-4\3.
• [12] Tredup R. The Complexity of Synthesizing nop-Equipped Boolean Nets from g-Bounded Inputs (Technical Report), accepted for ToPNoC 2020. CoRR, 2019. abs/1911.05834. 1911.05834, URL http://arxiv.org/abs/1911.05834.
• [13] Pietkiewicz-Koutny M. Transition Systems of Elementary Net Systems with Inhibitor Arcs. In: Az éma P, Balbo G (eds.), Application and Theory of Petri Nets 1997, 18th International Conference, ICATPN ’97, Toulouse, France, June 23-27, 1997, Proceedings, volume 1248 of Lecture Notes in Computer Science. Springer, 1997 pp. 310–327. doi:10.1007/3-540-63139-9\43.
• [14] Montanari U, Rossi F. Contextual Nets. Acta Inf., 1995. 32(6):545–596. doi:10.1007/BF01178907
• [15] Badouel E, Darondeau P. Trace Nets and Process Automata. Acta Inf., 1995. 32(7):647–679. doi:10.1007/BF01186645. URL https://doi.org/10.1007/BF01186645.
• [16] Kleijn J, Koutny M, Pietkiewicz-Koutny M, Rozenberg G. Step semantics of boolean nets. Acta Inf., 2013. 50(1):15–39. doi:10.1007/s00236-012-0170-2.
• [17] Schlachter U, Wimmel H. k-Bounded Petri Net Synthesis from Modal Transition Systems. In: CONCUR, volume 85 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017 pp. 6:1–6:15. doi:10.4230/LIPIcs.CONCUR.2017.6.
• [18] Hiraishi K. Some Complexity Results on Transition Systems and Elementary Net Systems. Theor. Comput. Sci., 1994. 135(2):361–376. doi:10.1016/0304-3975(94)90112-0.
• [19] Tredup R, Rosenke C. Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems. In: CONCUR, volume 118 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018 pp.16:1–16:15. doi:10.4230/LIPIcs.CONCUR.2018.16.
• [20] 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.
• [21] 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.
• [22] Tredup R. Fixed Parameter Tractability and Polynomial Time 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. 148–168. doi:10.1007/978-3-030-21571-2\10.
• [23] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7.
• [24] Goldmann M, Russell A. The Complexity of Solving Equations over Finite Groups. Inf. Comput., 2002. 178(1):253–262. doi:10.1006/inco.2002.3173.
• [25] Tarjan RE. Finding optimum branchings. Networks, 1977. 7(1):25–35. doi:10.1002/net.3230070103.
• [26] Gorrieri R. Process Algebras for Petri Nets - The Alphabetization of Distributed Systems. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2017. ISBN 978-3-319-55558-4. doi:10.1007/978-3-319-55559-1.

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)