Synthesis of Petri Nets from Term Based Representations of Infinite Partial Languages

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

Abstrakty

EN

In this paper we present an algorithm to synthesize a finite unlabelled place/transition Petri net (p/t-net) from a possibly infinite partial language, which is given by a term over a finite set of labelled partial orders using operators for union, iteration, parallel composition and sequential composition. The synthesis algorithm is based on the theory of regions for partial languages presented in [17] and produces a p/t-net having minimal net behaviour including the given partial language. The algorithm uses linear programming techniques that were already successfully applied in [22] for the synthesis of p/t-nets from finite partial languages. Also, an equality test algorithm to check whether the behaviour of the synthesized p/t-net equals the given partial language is shown. Moreover, we present an implementation of the developed synthesis algorithm together with an example case study. Finally, a possible generalization of the presented term based representation of infinite partial languages is discussed.

Słowa kluczowe

EN

Petri net; algorithm; synthesis of Petri nets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 95, nr 1
• Strony: 187--217
• Opis fizyczny: Bibliogr. 27 poz., wykr.

Twórcy

autor

Bergenthum R.

autor

Desel J.

autor

Mauser S.

autor

Lorenz R.

• Department of Computer Science, University of Augsburg, Germany,

Bibliografia

• [1] van der Aalst, W. M. P., van Dongen, B. F., G¨unther, C. W., Mans, R. S., de Medeiros, A. K. A., Rozinat, A., Rubin, V., Song, M., Verbeek, H. M. W., Weijters, A. J. M. M.: ProM 4.0: Comprehensive Support for real Process Analysis, ICATPN 2007, LNCS 4546, Springer, 2007.
• [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.: Theory of Regions, Lectures on Petri Nets I: BasicModels, LNCS 1491, Springer, 1998.
• [4] Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Synthesis of Petri Nets from Infinite Partial Languages, ACSD 2008, IEEE, 2008.
• [5] Bergenthum, R., Desel, J., Lorenz, R.,Mauser, S.: Synthesis of Petri Nets fromScenarios with VipTool, Petri Nets 2008, LNCS 5062, Springer, 2008.
• [6] Bergenthum, R., Desel, J., Mauser, S.: Comparison of Different Algorithms to Synthesize a Petri Net from a Partial Language, Workshop CHINA at Petri Nets 2008, Xi'an, 2008.
• [7] Bergenthum, R., Desel, J., Mauser, S.: Synthesis of Petri Nets for Business Process Design, Workshop Verhaltensmodellierung: Best Practices und neue Erkenntnisse an der Modellierung 2008, Berlin, 2008.
• [8] Bergenthum, R., Mauser, S.: Synthesis of Petri Nets from Infinite Partial Languages with VipTool, Workshop AWPN 2008, Rostock, 2008.
• [9] Cortadella, J., Kishinevsky,M., Kondratyev,A., Lavagno, L., Yakovlev, A.: Petrify: A Tool forManipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, IEICE Trans. of Informations and Systems, E80-D(3), 1997, 315-325.
• [10] Cortadella, J., Kishinevsky,M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Hardware and Petri Nets: Application to Asynchronous Circuit Design, ICATPN 2000, LNCS 1825, Springer, 2000.
• [11] Darondeau, P.: Deriving Unbounded Petri Nets from Formal Languages, CONCUR 1998, LNCS 1466, Springer, 1998.
• [12] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem / Part II: State Spaces of Concurrent Systems, Acta Inf., 27(4), 1989, 315-368.
• [13] Grabowski, J.: On Partial Languages, Fundamenta Informaticae, 4(2), 1981, 428-498.
• [14] Hoogers, P., Kleijn, H., Thiagarajan, P.: A Trace Semantics for Petri Nets, Information and Computation, 117(1), 1995, 98-114.
• [15] Hoogers, P., Kleijn, H., Thiagarajan, P.: An Event Structure Semantics for General Petri Nets, Theoretical Computer Science, 153(1&2), 1996, 129-170.
• [16] Josephs, M. B., Furey, D. P.: A Programming Approach to the Design of Asynchronous Logic Blocks, Concurrency and Hardware Design 2002, LNCS 2549, Springer, 2002.
• [17] Juhás, G., Lorenz, R.: Towards Synthesis of Petri Nets from Scenarios, ICATPN 2006, LNCS 4024, Springer, 2006.
• [18] Juhás, G., Lorenz, R., Mauser, S.: How to Synthesize Nets from Languages - a Survey, Wintersimulation Conference 2007, Washington, 2007.
• [19] Kuske, D., Morin, R.: Pomsets for Local Trace Languages - Recognizability, Logic & Petri Nets, CONCUR 2000, LNCS 1877, Springer, 2000.
• [20] Lodaya, K., Weil, P.: Series-Parallel Posets: Algebra, Automata and Languages, STACS 1998, LNCS 1373, Springer, 1998.
• [21] Lodaya, K., Weil, P.: Series-Parallel Languages and the Bounded-Width Property, Theor. Comput. Sci., 237(1-2), 2000, 347-380.
• [22] Lorenz, R., Bergenthum, R., Desel, J., Mauser, S.: Synthesis of Petri Nets from Finite Partial Languages, ACSD, IEEE Computer Society, 2007.
• [23] Pratt, V.: Modelling Concurrency with Partial Orders, Int. Journal of Parallel Programming, 15, 1986, 33-71.
• [24] Reisig, W.: Petrinetze - Eine Einf¨uhrung., 2. edition, Springer, 1986.
• [25] Schrijver, A.: Theory of Linear and Integer Programming, Wiley, 1986.
• [26] Vogler, W.: Partial Words Versus Processes: a Short Comparison, Advances in Petri Nets: The DEMON Project, LNCS 609, Springer, 1992.
• [27] Zhou, M., Cesare, F. D.: Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer, 1993.