Some Basic Techniques allowing Petri Net Synthesis: Complexity and Algorithmic Issues

• Autorzy: Devillers Raymond , Tredup Ronny

Identyfikatory

DOI

10.3233/FI-222136

• Języki publikacji: EN

Abstrakty

EN

In Petri net synthesis we ask whether a given transition system A can be implemented by a Petri net N . Depending on the level of accuracy, there are three ways how N can implement A: an embedding, the least accurate implementation, preserves only the diversity of states of A; a language simulation already preserves exactly the language of A; a realization, the most accurate implementation, realizes the behavior of A exactly. However, whatever the sought implemen- tation, a corresponding net does not always exist. In this case, it was suggested to modify the input behavior – of course as little as possible. Since transition systems consist of states, events and edges, these components appear as a natural choice for modifications. In this paper we show that the task of converting an unimplementable transition system into an implementable one by removing as few states or events or edges as possible is NP-complete –regardless of what type of implementation we are aiming for; we also show that the corresponding parameterized problems are W [2]-hard, where the number of removed components is considered as the parameter; finally, we show there is no c-approximation algorithm (with a polynomial running time) for neither of these problems, for every constant c ≥ 1.

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: 167--196
• Opis fizyczny: Bibliogr. 26 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] Kordon F, Garavel H, Hillah LM, Hulin-Hubard F, Berthomieu B, Ciardo G, Colange M, Dal Zilio S, Amparore E, Beccuti M, Liebke T, Meijer J, Miner A, Rohr C, Srba J, Thierry-Mieg Y, van de Pol J, Wolf K. Complete Results for the 2017 Edition of the Model Checking Contest. http://mcc.lip6.fr/2017/results.php,2017.
• [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] de San Pedro J, Cortadella J. Mining structured Petri nets for the visualization of process behavior. In:Ossowski S (ed.), Proceedings of the 31st Annual ACM Symposium on Applied Computing, Pisa, Italy, April 4-8, 2016. ACM, 2016 pp. 839-846. doi:10.1145/2851613.2851645.
• [4] Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. A region-based theory for state assignment in speed-independent circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997. 16(8):793-812. doi:10.1109/43.644602.
• [5] Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. Logic Synthesis for Asynchronous Controllers and Interfaces. Springer Publishing Company, Incorporated, 2013. ISBN:3642627765.
• [6] 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.
• [7] Best E, Darondeau P. Petri Net Distributability. In: Ershov Memorial Conference, volume 7162 of Lecture Notes in Computer Science. Springer, 2011 pp. 1-18. doi:10.1007/978-3-642-29709-0\ 1.
• [8] 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.
• [9] Best E, Devillers RR. Synthesis and reengineering of persistent systems. Acta Inf., 2015. 52(1):35-60. doi:10.1007/s00236-014-0209-7.
• [10] 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.
• [11] Borde D, Dierkes S, Ferrari R, Gieseking M, Göbel V, Grunwald R, von der Linde B, Lückehe D, Schlachter U, Schierholz C, Schwammberger M, Spreckels V. Projektgruppe APT: Analyse von Petri-Netzen und Transitionssystemen. Final report of a project assignment, 2013. URL https://github.com/CvO-Theory/apt/blob/master/doc/APT.pdf.
• [12] Caillaud B. Synet : A Synthesizer of Distributable Bounded Petri-Nets from Finite Automata, 1999. URL https://www.irisa.fr/s4/tools/synet/.
• [13] Carmona J, Cortadella J, Kishinevsky M. Genet: A Tool for the Synthesis and Mining of Petri Nets. In: Ninth International Conference on Application of Concurrency to System Design, ACSD 2009, Augsburg, Germany, 1-3 July 2009. 2009 pp. 181-185. doi:10.1109/ACSD.2009.6.
• [14] Cortadella J, Kishinevsky M, Kondratyev A, Lavagno L, Yakovlev A. Petrify: A Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, 1997.
• [15] 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.
• [16] Verbeek HMW, Pretorius AJ, van der Aalst WMP, van Wijk JJ. Visualizing State Spaces with Petri Nets. Eindhoven University of Technology, Eindhoven, The Netherlands, 2007. URL https://publications.rwth-aachen.de/record/715007.
• [17] 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.
• [18] 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.
• [19] 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, URL https://arxiv.org/abs/2002.04841.
• [20] Tredup R. Finding an Optimal Label-Splitting to Make a Transition System Petri Net Implementable: a Complete Complexity Characterization. In: ICTCS, volume 2756 of CEUR Workshop Proceedings.CEUR-WS.org, 2020 pp. 131-144.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] Crescenzi P, Kann V, Silvestri R, Trevisan L. Structure in Approximation Classes. SIAM J. Comput., 1999. 28(5):1759-1782. doi:10.1137/S0097539796304220.
• [25] Dinur I, Steurer D. Analytical Approach to Parallel Repetition. CoRR, 2013. abs/1305.1979. 1305.1979, URL http://arxiv.org/abs/1305.1979.
• [26] Schlachter U. Petri net synthesis and modal specifications. Ph.D. thesis, University of Oldenburg, Germany, 2018.