Maximal and Minimal Dynamic Petri Net Slicing

• Autorzy: Llorens Marisa , Oliver Javier , Silva Josep , Tamarit Salvador

Identyfikatory

DOI

10.3233/FI-222148

• Języki publikacji: EN

Abstrakty

EN

Petri net slicing is a technique to reduce the size of a Petri net to ease the analysis or understanding of the original Petri net. Objective: Presenting two new Petri net slicing algorithms to isolate those places and transitions of a Petri net (the slice) that may contribute tokens to one or more places given (the slicing criterion). Method: The two algorithms proposed are formalized. The maximality of the first algorithm and the minimality of the second algorithm are formally proven. Both algorithms together with three other state-of-the-art algorithms have been implemented and integrated into a single tool so that we have been able to carry out a fair empirical evaluation. Results: Besides the two new Petri net slicing algorithms, a public, free, and open-source implementation of five algorithms is reported. The results of an empirical evaluation of the new algorithms and the slices they produce are also presented. Conclusions: The first algorithm collects all places and transitions that may contribute tokens (in any computation) to the slicing criterion, while the second algorithm collects the places and transitions needed to fire the shortest transition sequence that contributes tokens to some place in the slicing criterion. Therefore, the net computed by the first algorithm can reproduce any computation that contributes tokens to any place of interest. In contrast, the second algorithm loses this possibility, but it often produces a much more reduced subnet (which still can reproduce some computations that contribute tokens to some places of interest). The first algorithm is proven maximal, and the second one is proven minimal.

Słowa kluczowe

EN

Petri nets; Program slicing; Petri net slicing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 188, nr 4
• Strony: 239--267
• Opis fizyczny: Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Llorens Marisa

• VRAIN, Departamento de Sistemas Informáticos y Computación Universitat Politècnica de València

autor

Oliver Javier

• VRAIN, Departamento de Sistemas Informáticos y Computación Universitat Politècnica de València Valencia, Spain

autor

Silva Josep

• VRAIN, Departamento de Sistemas Informáticos y Computación Universitat Politècnica de València Valencia, Spain

autor

Tamarit Salvador

• VRAIN, Departamento de Sistemas Informáticos y Computación Universitat Politècnica de València Valencia, Spain

Bibliografia

• [1] Tip F. A Survey of Program Slicing Techniques. Journal of Programming Languages, 1995. 3:121-189.
• [2] Silva J. A Vocabulary of Program Slicing-based Techniques. ACM Computing Surveys, 2012. 44(3):12:1-12:41. doi:10.1145/2187671.2187674.
• [3] Chang C, Wang H. A Slicing Algorithm of Concurrency Modeling Based on Petri Nets. In: Proc. of the Int’l Conf. on Parallel Processing, ICPP’86. IEEE Computer Society Press, 1986 pp. 789-792.
• [4] Khan Y, Guelfi N. Survey of Petri Nets Slicing. Technical report, University of Luxembourg, Faculty of Science, Technology and Communication (FSTC), Computer Science and Communications Research Unit (CSC), Luxembourg, 2013. URL https://hdl.handle.net/10993/13606.
• [5] Khan Y, Konios A, Guelfi N. A Survey of Petri Nets Slicing. ACM Computing Surveys, 2018. 51:1-32. doi:10.1145/3241736.
• [6] Khan Y, Risoldi M. Optimizing Algebraic Petri Net Model Checking by Slicing. In: Int’l Workshop on Modeling and Business Environments, ModBE 2013, associated with Petri Nets 2013. 2013 pp. 275-294. doi:10.1007/978-3-642-40894-6_6.
• [7] Lee W, Cha S, Kwon Y, Kim H. A Slicing-based Approach to Enhance Petri Net Reachability Analysis. Journal of Research and Practice in Information Technology, 2000. 32(2):131-143.
• [8] Rakow A. Safety Slicing Petri Nets. In: Int’l Conf. on Application and Theory of Petri Nets and Concurrency, Petri Nets’12. Springer LNCS 7347, 2012 pp. 268-287. doi:10.1007/978-3-642-31131-4_15.
• [9] Yu W, Ding Z, Fang X. Dynamic Slicing of Petri Nets Based on Structural Dependency Graph and its Application in System Analysis. Asian Journal of Control, 2015. 17(4):1403-1414. doi:10.1002/asjc.1031.
• [10] Davidrajuh R. Experimenting with the Static Slicing of Petri Nets. In: Proc. of the IEEE 24th International Conference on Intelligent Engineering Systems (INES). IEEE, 2020 doi:10.1109/INES49302.2020.9147182.
• [11] Llorens M, Oliver J, Silva J, Tamarit S, Vidal G. Dynamic Slicing Techniques for Petri Nets. Electronic Notes in Theoretical Computer Science, 2008. 223:153-165. doi:10.1016/j.entcs.2008.12.037.
• [12] Davidrajuh R. Extracting Petri Modules From Large and Legacy Petri Net Models. IEEE Access, 2020.8(19975565):156539-156556. doi:10.1109/ACCESS.2020.3020213.
• [13] Wang J, Yu W. Research in modeling of complex adaptive petri net. In: Proc. of the International Multi-Conference of Engineers and Computer Scientists, volume 1. 2015.
• [14] Indri M, Trapani S. Programming robot work flows with a task modeling approach. In: Proc. of the IECON 2018-44th Annual Conference of the IEEE Industrial Electronics Society, volume 1. IEEE, 2018 p. 2619-2624. doi:10.1109/IECON.2018.8591629.
• [15] Yang S, Liu J, Arpaci-Dusseau A, Arpaci-Dusseau R. Principled schedule ability analysis for distributed storage systems using thread architecture models. In: Proc. of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 2018 p. 161-176. ISBN: 978-1-939133-08-3.
• [16] Rakow A. Slicing Petri Nets with an Application to Workflow Verification. In: Proc. of the 34th Conf. on Current Trends in Theory and Practice of Computer Science, SOFSEM’08. Springer LNCS 4910, 2008 pp. 436-447. doi:10.1007/978-3-540-77566-9_38.
• [17] Davidrajuh R, Roci A. Performance of static slicing algorithms for petri nets. International Journal of Simulation-Systems, Science and Technology, 2018. 20(S1):15.1-15.7. doi:10.5013/IJSSST.a.20.S1.15.
• [18] Murata T. Petri Nets: Properties, Analysis and Applications. Proc. of the IEEE, 1989. 77(4):541-580. doi:10.1109/5.24143.
• [19] Peterson J. Petri Net Theory and the Modeling of Systems. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1981. ISBN-10:0136619835, 13:978-0136619833.
• [20] Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies. Springer-Verlag Berlin Heidelberg, 2013. doi:10.1007/978-3-642-33278-4.
• [21] Desel J, Esparza J. Free choice Petri nets. Cambridge University Press, New York, NY, USA, 1995. doi:10.1017/CBO9780511526558.
• [22] Korel B, Laski J. Dynamic Program Slicing. Information Processing Letters, 1988. 29(3):155-163. doi:10.1016/0020-0190(88)90054-3.
• [23] Weiser M. Program Slicing. IEEE Transactions on Software Engineering, 1984. 10(4):352-357.
• [24] Rakow A. Slicing Petri Nets. Technical report, Department für Informatik, Carl von Ossietzky Universität, Oldenburg, 2007.
• [25] Parallele Systeme Group. APT: Analysis of Petri nets and labelled transition systems. URL https://github.com/CvO-theory/apt, accessed october 2022.
• [26] Llorens M, Oliver J, Silva J, Tamarit S. An Integrated Environment for Petri Net Slicing. In: Int’l Conf. on Application and Theory of Petri Nets and Concurrency, Petri Nets’17. Springer LNCS 10258, 2017 pp. 112-124. doi:10.1007/978-3-319-57861-3_8.
• [27] Graphviz - Graph Visualization Software. URL http://www.graphviz.org/, accessed october 2022.
• [28] Erlang/OTP framework. URL http://www.erlang.org/, accessed october 2022.
• [29] Docker. Docker: Empowering App Development for Developers. URL https://www.docker.com/accessed october 2022.
• [30] The Petri Net Markup Language reference site. URL http://www.pnml.org/, accessed october 2022
• [31] The Platform Independent Petri Net Editor version 5. URL http://sarahtattersall.github.io/PIPE/, accessed october 2022.
• [32] Khan Y. Property Based Model Checking of Structurally Evolving Algebraic Petri Nets. Ph.D. thesis, The Faculty of Sciences, Technology and Communication. Université du Luxembourg, 2015.
• [33] Rakow A. Slicing and Reduction Techniques for Model Checking Petri Nets. Ph.D. thesis, Fakultät II -Informatik, Wirtschafts- und Rechtswissenschaften, Department für Informatik, Carl von Ossietzky Universität, 2011.
• [34] Khan Y, Guelfi N. SLAPn: A tool for Slicing Algebraic Petri nets. In: Int’l Workshop on Petri Nets and Software Engineering (PNSE’14), CEUR Workshop Proceedings. CEUR-WS.org 1160, 2014 pp. 343-345. URL http://hdl.handle.net/10993/17464.
• [35] Karp RM, Miller RE. Parallel Program Schemata. Journal of Computer and System Sciences, 1969. 3(2):147-195. doi:10.1016/S0022-0000(69)80011-5