Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Comparison of Different Algorithms to Synthesize a Petri Net from a Partial Language

  • Chapter

Part of the book series:Lecture Notes in Computer Science ((TOPNOC,volume 5800))

  • 604Accesses

Abstract

In this paper we present two new algorithms that effectively synthesize a finite place/transition Petri net (p/t-net) from a finite set of labeled partial orders (a finite partial language). Either the synthesized p/t-net has exactly the non-sequential behavior specified by the partial language, or there is no such p/t-net. The first algorithm is an improved version of a synthesis algorithm presented in [14], which uses the classical theory of regions applied to the set of step sequences generated by the given partial language. Instead of computing all step sequences, the new algorithm directly works on appropriate prefixes specified in the partial language. The second algorithm is based on the theory of token flow regions for partial languages developed in [16,15,14]. While in [15,14] a so called basis representation is applied, the new algorithm combines the concepts of separation representation and token flows. We implemented both synthesis algorithms in our framework VipTool. A comparison of the two new algorithms with the two predecessor algorithms presented in [14,15]shows that both perform better than their respective predecessor. Therefore, a detailed comparison of these two synthesis algorithms is presented.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Badouel, E., Darondeau, P.: On the Synthesis of General Petri Nets. Technical Report 3025, Inria (1996)

    Google Scholar 

  2. Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Synthesis of Petri Nets from Infinite Partial Languages. In: ACSD 2008, pp. 170–179. IEEE, Los Alamitos (2008)

    Google Scholar 

  3. Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: VipTool-Homepage (2009),http://viptool.ku-eichstaett.de

  4. 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), 315–325 (1997)

    Google Scholar 

  5. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Hardware and Petri Nets: Application to Asynchronous Circuit Design. In: Nielsen, M., Simpson, D. (eds.) ICATPN 2000. LNCS, vol. 1825, pp. 1–15. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  6. Darondeau, P.: Deriving Unbounded Petri Nets from Formal Languages. In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 533–548. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  7. 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), 315–368 (1989)

    Article MathSciNet  Google Scholar 

  8. Grabowski, J.: On Partial Languages. Fundamenta Informaticae 4(2), 428–498 (1981)

    MathSciNet  Google Scholar 

  9. Heiner, M., Koch, I., Will, J.: Model Validation of Biological Pathways Using Petri Nets - Demonstrated for Apoptosis. Journal BioSystems 75(1-3), 15–28 (2004)

    Article  Google Scholar 

  10. Hoogers, P., Kleijn, H., Thiagarajan, P.: A Trace Semantics for Petri Nets. Information and Computation 117(1), 98–114 (1995)

    Article MATH MathSciNet  Google Scholar 

  11. Josephs, M.B., Furey, D.P.: A Programming Approach to the Design of Asynchronous Logic Blocks. In: Cortadella, J., Yakovlev, A., Rozenberg, G. (eds.) Concurrency and Hardware Design. LNCS, vol. 2549, pp. 34–60. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  12. Kiehn, A.: On the Interrelation Between Synchronized and Non-Synchronized Behaviour of Petri Nets. Elektronische Informationsverarbeitung und Kybernetik 24(1/2), 3–18 (1988)

    MATH MathSciNet  Google Scholar 

  13. Liang, H., Dingel, J., Diskin, Z.: A Comparative Survey of Scenario-Based to State-Based Model Synthesis Approaches. In: SCESM 2006, pp. 5–12. ACM, New York (2006)

    Chapter  Google Scholar 

  14. Lorenz, R., Bergenthum, R., Desel, J., Mauser, S.: Synthesis of Petri Nets from Finite Partial Languages. Fundamenta Informaticae 88(4), 437–468 (2009)

    MathSciNet  Google Scholar 

  15. Lorenz, R., Bergenthum, R., Mauser, S., Desel, J.: Synthesis of Petri Nets from Finite Partial Languages. In: ACSD, pp. 157–166. IEEE, Los Alamitos (2007)

    Google Scholar 

  16. Lorenz, R., Juhás, G.: Towards Synthesis of Petri Nets from Scenarios. In: Donatelli, S., Thiagarajan, P.S. (eds.) ICATPN 2006. LNCS, vol. 4024, pp. 302–321. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Lorenz, R., Juhás, G., Mauser, S.: How to Synthesize Nets from Languages - a Survey. In: WSC, pp. 637–647. IEEE, Los Alamitos (2007)

    Google Scholar 

  18. Pratt, V.: Modelling Concurrency with Partial Orders. Int. Journal of Parallel Programming 15, 33–71 (1986)

    Article MATH MathSciNet  Google Scholar 

  19. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)

    Google Scholar 

  20. van der Aalst, W.M.P., van Dongen, B.F., Günther, C.W., Mans, R.S., de Medeiros, A.K.A., Rozinat, A., Rubin, V., Song, M., Verbeek, E., Weijters, A.J.M.M.: ProM 4.0: Comprehensive Support for Real Process Analysis. In: Kleijn, J., Yakovlev, A. (eds.) ICATPN 2007. LNCS, vol. 4546, pp. 484–494. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  21. 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), 1128–1142 (2004)

    Article  Google Scholar 

  22. Verbeek, E., van der Toorn, R.A.: Transit Case Study. In: Cortadella, J., Reisig, W. (eds.) ICATPN 2004. LNCS, vol. 3099, pp. 391–410. Springer, Heidelberg (2004)

    Google Scholar 

  23. Vogler, W.: Modular Construction and Partial Order Semantics of Petri Nets. LNCS, vol. 625. Springer, Heidelberg (1992)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt,  

    Robin Bergenthum, Jörg Desel & Sebastian Mauser

Authors
  1. Robin Bergenthum

    You can also search for this author inPubMed Google Scholar

  2. Jörg Desel

    You can also search for this author inPubMed Google Scholar

  3. Sebastian Mauser

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Faculty of Science, Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, 8200, Aarhus N, Denmark

    Kurt Jensen

  2. School of Electrical and Information Engineering, University of South Australia, Mawson Lakes Campus, 5095, Mawson Lakes, South Australia, Australia

    Jonathan Billington

  3. SCS, Newcastle University, NE1 7RU, Newcastle upon Tyne, UK

    Maciej Koutny

Rights and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Bergenthum, R., Desel, J., Mauser, S. (2009). Comparison of Different Algorithms to Synthesize a Petri Net from a Partial Language. In: Jensen, K., Billington, J., Koutny, M. (eds) Transactions on Petri Nets and Other Models of Concurrency III. Lecture Notes in Computer Science, vol 5800. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04856-2_9

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp