On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets

• Autorzy: Devillers Raymond , Tredup Ronny

Identyfikatory

DOI

10.3233/FI-222161

• Języki publikacji: EN

Abstrakty

EN

Let us consider some class of (Petri) nets. The corresponding Synthesis problem consists in deciding whether a given labeled transition system (TS) A can be implemented by a net N of that class. In case of a negative decision, it may be possible to convert A into an implementable TS B by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if the considered class corresponds to so-called flip-flop nets or some flip-flop net derivatives.

Słowa kluczowe

EN

Petri net; Boolean Types; Label-Splitting; Edge-Removal; Event-Removal; State-Removal; Synthesis; Complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 3-4
• Strony: 261--296
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Devillers Raymond

• D´epartement d’Informatique Universit´e Libre de Bruxelles Boulevard du Triomphe C.P. 212, B-1050 Bruxelles, Belgium

autor

Tredup Ronny

• Geschwister-Scholl-Gymnasium Lӧbau Pestalozzistraße 21, 02708 Lӧbau 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] 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.
• [6] Carmona J. The Label Splitting Problem. Trans. Petri Nets Other Model. Concurr., 2012. 6:1-23. doi: 10.1007/978-3-642-35179-2 1. URL https://doi.org/10.1007/978-3-642-35179-2 1.
• [7] Cortadella J, Kishinevsky M, Lavagno L, Yakovlev A. Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. 47(8):859-882.
• [8] Schlachter U, Wimmel H. Relabelling LTS for Petri Net Synthesis via Solving Separation Problems. Trans. Petri Nets Other Model. Concurr., 2019. 14:222-254. doi:10.1007/978-3-662-60651-3 9.
• [9] Schlachter U, Wimmel H. Optimal Label Splitting for Embedding an LTS into an arbitrary Petri Net Reachability Graph is NP-complete. CoRR, 2020. abs/2002.04841. 2002.04841.
• [10] Tredup R. Finding an Optimal Label-Splitting to Make a Transition System Petri Net Implementable: a Complete Complexity Characterization. In: Proceedings of the 21st Italian Conference on Theoretical Computer Science, Ischia, Italy, September 14-16, 2020. 2020 pp. 131-144.
• [11] Devillers RR, Tredup R. Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorithmic Issues. CoRR, 2021. abs/2112.03605. 2112.03605, URL https://arxiv.org/abs/2112.03605.
• [12] Tredup R. Edge, Event and State Removal: The Complexity of Some Basic Techniques that Make Transition Systems Petri Net Implementable. In: Application and Theory of Petri Nets and Concurrency - 42nd International Conference, PETRI NETS 2021, Virtual Event, June 23-25, 2021, Proceedings. 2021 pp. 253-273. doi:10.1007/978-3-030-76983-3 13. [13] Badouel E, Darondeau P. Trace Nets and Process Automata. Acta Inf., 1995. 32(7):647-679. doi: 10.1007/BF01186645.
• [14] 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.
• [15] Montanari U, Rossi F. Contextual Nets. Acta Inf., 1995. 32(6):545-596. doi:10.1007/BF01178907. 296 R. Devillers and R. Tredup / The Complexity of Techniques That Make Transition Systems Implementable...
• [16] Pietkiewicz-Koutny M. Transition Systems of Elementary Net Systems with Inhibitor Arcs. In: ICATPN, volume 1248 of Lecture Notes in Computer Science. Springer, 1997 pp. 310-327. doi:10.1007/3-540-63139-9 43.
• [17] Rozenberg G, Engelfriet J. Elementary Net Systems. In: Petri Nets, volume 1491 of Lecture Notes in Computer Science. Springer, 1996 pp. 12-121. doi:10.1007/3-540-65306-6 14.
• [18] 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.
• [19] 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.
• [20] Tredup R. The Complexity of Synthesizing nop-Equipped Boolean Petri Nets from g-Bounded Inputs. Trans. Petri Nets Other Model. Concurr., 2021. 15:101-125.
• [21] Tredup R, Rosenke C. The Complexity of Synthesis for 43 Boolean Petri Net Types. In: TAMC, volume 11436 of Lecture Notes in Computer Science. Springer, 2019 pp. 615-634. doi:10.1007/978-3-030-14812-6.
• [22] 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.
• [23] Tredup R, Erofeev E. The Complexity of Boolean State Separation. In: Theoretical Aspects of Computing - ICTAC 2020 - 17th International Colloquium, Macau, China, November 30 - December 4, 2020, Proceedings. 2020 pp. 123-142. doi:10.1007/978-3-030-64276-1 7.
• [24] 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.
• [25] Tredup R. The Complexity of the Label-Splitting-Problem for Flip-Flop-Nets. In: Reachability Problems - 14th International Conference, RP 2020, Paris, France, October 19-21, 2020, Proceedings. 2020 pp. 148-163. doi:10.1007/978-3-030-61739-4 10.
• [26] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7