Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Faster Unfolding of General Petri Nets Based on Token Flows

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 5062))

Included in the following conference series:

Abstract

In this paper we propose two new unfolding semantics for general Petri nets combining the concept of prime event structures with the idea of token flows developed in [11]. In contrast to the standard unfolding based on branching processes, one of the presented unfolding models avoids to represent isomorphic processes while the other additionally reduces the number of (possibly non-isomorphic) processes with isomorphic underlying runs. We show that both proposed unfolding models still represent the complete partial order behavior. We develop a construction algorithm for both unfolding models and present experimental results. These results show that the new unfolding models are much smaller and can be constructed significantly faster than the standard unfolding.

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. Best, E., Devillers, R.: Sequential and concurrent behaviour in petri net theory. Theoretical Computer Science 55(1), 87–136 (1987)

    Article MATH MathSciNet  Google Scholar 

  2. Couvreur, J.-M., Poitrenaud, D., Weil, P.: Unfoldings for general petri nets. University de Bordeaux I (Talence, France), University Pierre et Marie Curie (Paris, France) (2004),http://www.labri.fr/perso/weil/publications/depliage.pdf

  3. Desel, J., Neumair, C.: Finite unfoldings of unbounded petri nets. In: Cortadella, J., Reisig, W. (eds.) ICATPN 2004. LNCS, vol. 3099, pp. 157–176. Springer, Heidelberg (2004)

    Google Scholar 

  4. Desel, J., Juhás, G., Lorenz, R.: Viptool-homepage (2003),http://www.informatik.ku-eichstaett.de/projekte/vip/

  5. Engelfriet, J.: Branching processes of petri nets. Acta Informatica 28(6), 575–591 (1991)

    Article MATH MathSciNet  Google Scholar 

  6. Esparza, J., Heljanko, K.: Implementing ltl model checking with net unfoldings. In: Dwyer, M.B. (ed.) SPIN 2001. LNCS, vol. 2057, pp. 37–56. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  7. Esparza, J., Römer, S., Vogler, W.: An improvement of mcmillan’s unfolding algorithm. Formal Methods in System Design 20(3), 285–310 (2002)

    Article MATH  Google Scholar 

  8. Goltz, U., Reisig, W.: The non-sequential behaviour of petri nets. Information and Control 57(2/3), 125–147 (1983)

    Article MATH MathSciNet  Google Scholar 

  9. Haar, S.: Branching processes of general s/t-systems and their properties. Electr. Notes Theor. Comput. Sci. 18 (1998)

    Google Scholar 

  10. Hoogers, P., Kleijn, H., Thiagarajan, P.: An event structure semantics for general petri nets. Theoretical Computer Science 153(1&2), 129–170 (1996)

    Article MATH MathSciNet  Google Scholar 

  11. Juhás, G., Lorenz, R., Desel, J.: Can i execute my scenario in your net? In: Ciardo, G., Darondeau, P. (eds.) ICATPN 2005. LNCS, vol. 3536, pp. 289–308. Springer, Heidelberg (2005)

    Google Scholar 

  12. Khomenko, V., Kondratyev, A., Koutny, M., Vogler, W.: Merged processes: a new condensed representation of petri net behaviour. Acta Inf. 43(5), 307–330 (2006)

    Article MATH MathSciNet  Google Scholar 

  13. Khomenko, V., Koutny, M.: Towards an efficient algorithm for unfolding petri nets. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 366–380. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  14. Khomenko, V., Koutny, M.: Branching processes of high-level petri nets. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 458–472. Springer, Heidelberg (2003)

    Google Scholar 

  15. Khomenko, V., Koutny, M., Vogler, W.: Canonical prefixes of petri net unfoldings. Acta Inf. 40(2), 95–118 (2003)

    Article MATH MathSciNet  Google Scholar 

  16. McMillan, K.L.: Using unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. In: von Bochmann, G., Probst, D.K. (eds.) CAV 1992. LNCS, vol. 663, pp. 164–177. Springer, Heidelberg (1993)

    Google Scholar 

  17. Meseguer, J., Montanari, U., Sassone, V.: On the model of computation of place/transition petri nets. In: Valette, R. (ed.) ICATPN 1994. LNCS, vol. 815, pp. 16–38. Springer, Heidelberg (1994)

    Google Scholar 

  18. Meseguer, J., Montanari, U., Sassone, V.: On the semantics of place/transition petri nets. Mathematical Structures in Computer Science 7(4), 359–397 (1997)

    Article MATH MathSciNet  Google Scholar 

  19. Nielsen, M., Plotkin, G.D., Winskel, G.: Petri nets, event structures and domains, part i. Theoretical Computer Science 13, 85–108 (1981)

    Article MATH MathSciNet  Google Scholar 

  20. Winskel, G.: Event structures. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 255, pp. 325–392. Springer, Heidelberg (1987)

    Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Robin Bergenthum, Robert Lorenz & Sebastian Mauser

Authors
  1. Robin Bergenthum

    You can also search for this author inPubMed Google Scholar

  2. Robert Lorenz

    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

Kees M. van Hee Rüdiger Valk

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bergenthum, R., Lorenz, R., Mauser, S. (2008). Faster Unfolding of General Petri Nets Based on Token Flows. In: van Hee, K.M., Valk, R. (eds) Applications and Theory of Petri Nets. PETRI NETS 2008. Lecture Notes in Computer Science, vol 5062. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68746-7_6

Download citation

Publish with us


[8]ページ先頭

©2009-2025 Movatter.jp