Synthesis of Petri Nets from Finite Partial Languages

• Autorzy: Bergenthum R. , Desel J. , Lorenz R. , Mauser S.
• Języki publikacji: EN

Abstrakty

EN

In this paper we present two algorithms that effectively synthesize a finite place/transition Petri net (p/t-net) froma finite set of labeled partial orders (a finite partial language). The synthesized p/t-net either has exactly the non-sequential behavior specified by the partial language, or there is no such p/t-net. The first algorithm is based on the theory of token flow regions for partial languages developed by Lorenz and Juh´as. Thus, this paper shows the applicability of this concept. The second algorithm uses the classical theory of regions applied to the set of step sequences generated by the given partial language. We finally develop an algorithm to test whether the net synthesized by either of the two algorithms has exactly the non-sequential behavior specified by the partial language. We implemented all algorithms in our framework VipTool. In this paper, the implementations of the first two algorithms are used to compare the algorithms by means of experimental results.

Słowa kluczowe

EN

Petri net; synthesis of Petri nets

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 4
• Strony: 437--468
• Opis fizyczny: bibliogr. 29 poz., wykr.

Twórcy

autor

Bergenthum R.

autor

Desel J.

autor

Lorenz R.

autor

Mauser S.

• Department of Applied Computer Science Catholic University of Eichst¨att-Ingolstadt 85072 Eichst¨att, Germany,

Bibliografia

• [1] van der Aalst, W. M. P., van Dongen, B. F., Herbst, J., Maruster, L., Schimm, G., Weijters, A. J. M. M.: Workflow mining: A survey of issues and approaches., Data Knowl. Eng., 47(2), 2003, 237-267.
• [2] van der Aalst, W. M. P., Weijters, T., Maruster, L.: Workflow Mining: Discovering Process Models from Event Logs., IEEE Trans. Knowl. Data Eng., 16(9), 2004, 1128-1142.
• [3] Badouel, E., Darondeau, P.: On the Synthesis of General Petri Nets., Technical Report 3025, Inria, 1996.
• [4] Badouel, E., Darondeau, P.: Theory of Regions., Petri Nets (W. Reisig, G. Rozenberg, Eds.), Lecture Notes in Computer Science 1491, Springer, 1998, 529-586.
• [5] Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process Mining Based on Regions of Languages., BPM 2007 (G. Alonso, P. Dadam, M. Rosemann, Eds.), Lecture Notes in Computer Science 4714, Springer, 2007, 375-383.
• [6] Bergenthum, R., Lorenz, R., Mauser, S.: Faster Unfolding of General Petri Nets., Proceedings 14. Workshop Algorithmen und Werkzeuge f¨ur Petri Netze (AWPN), 2007, 63-68.
• [7] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: A tool for manipulating concurrent specifications and synthesis of asynchronous controllers., IEICE Trans. of Informations and Systems, E80-D(3), 1997, 315-325.
• [8] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Hardware and Petri Nets: Application to Asynchronous Circuit Design., ICATPN 2000 (M. Nielsen, D. Simpson, Eds.), Lecture Notes in Computer Science 1825, Springer, 2000, 1-15.
• [9] Darondeau, P.: Deriving Unbounded Petri Nets from Formal Languages., CONCUR 1998 (D. Sangiorgi, R. de Simone, Eds.), Lecture Notes in Computer Science 1466, Springer, 1998, 533-548.
• [10] Desel, J.: From Human Knowledge to Process Models., to appear in: Proceedings of UNISCON, 2008.
• [11] Desel, J., Lorenz, R., Mauser, S., Bergenthum, R.: VipTool-Homepage, 2008, Http://www.informatik.kueichstaett. de/projekte/vip/.
• [12] Desel, J., Reisig, W.: The Synthesis Problem of Petri Nets., Acta Inf., 33(4), 1996, 297-315.
• [13] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem., Acta Inf., 27(4), 1989, 315-342.
• [14] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part II: State Spaces of Concurrent Systems., Acta Inf., 27(4), 1989, 343-368.
• [15] Grabowski, J.: On partial languages., Fundamenta Informaticae, 4(2), 1981, 428-498.
• [16] Hoogers, P., Kleijn, H., Thiagarajan, P.: A trace semantics for Petri nets., Information and Computation, 117(1), 1995, 98-114.
• [17] Josephs, M. B., Furey, D. P.: A Programming Approach to the Design of Asynchronous Logic Blocks., Concurrency and Hardware Design (J. Cortadella, A. Yakovlev, G. Rozenberg, Eds.), Lecture Notes in Computer Science 2549, Springer, 2002, 34-60.
• [18] Juhás, G., Lorenz, R., Desel, J.: Can I Execute My Scenario in Your Net?, ICATPN 2005 (G. Ciardo, P. Darondeau, Eds.), Lecture Notes in Computer Science 3536, Springer, 2005, 289-308.
• [19] Kiehn, A.: On the Interrelation Between Synchronized and Non-Synchronized Behaviour of Petri Nets., Elektronische Informationsverarbeitung und Kybernetik, 24(1/2), 1988, 3-18.
• [20] Lorenz, R., Bergenthum, R., Desel, J., Mauser, S.: Synthesis of Petri Nets from Finite Partial Languages., ACSD 2007, IEEE Computer Society, 2007, 157-166.
• [21] Lorenz, R., Juhás, G.: Towards Synthesis of Petri Nets from Scenarios., ICATPN 2006 (S. Donatelli, P. S. Thiagarajan, Eds.), Lecture Notes in Computer Science 4024, Springer, 2006, 302-321.
• [22] Lorenz, R., Juhás, G., Mauser, S.: How to Synthesize Nets from Languages - a Survey., Proceedings of the Wintersimulation Confernce (WSC) 2007, IEEE Computer Society, 2007, 637-647.
• [23] Minkowski, H.: Geometrie der Zahlen, Teubner, 1896.
• [24] Motzkin, T.: Beiträge zur Theorie der linearen Ungleichungen, Ph.D. Thesis, Jerusalem, 1936.
• [25] Pratt, V.: Modelling Concurrency with Partial Orders., Int. Journal of Parallel Programming, 15, 1986, 33-71.
• [26] Schrijver, A.: Theory of Linear and Integer Programming, Wiley, 1986.
• [27] Tschernikow, S. N.: Algorithm for finding a general formula for the non-negative solutions of a system of linear inequalities., USSR Computational Mathematics and Mathematical Physics, 5(2), 1965, 228-233.
• [28] Vanderbei, R. J.: Linear Programming: Foundations and Extensions, Kluwer Academic Publishers, 1996.
• [29] Vogler, W.: Modular Construction and Partial Order Semantics of Petri Nets, vol. 625 of Lecture Notes in Computer Science, Springer, 1992.