Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 5062))
Included in the following conference series:
915Accesses
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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Best, E., Devillers, R.: Sequential and concurrent behaviour in petri net theory. Theoretical Computer Science 55(1), 87–136 (1987)
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
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)
Desel, J., Juhás, G., Lorenz, R.: Viptool-homepage (2003),http://www.informatik.ku-eichstaett.de/projekte/vip/
Engelfriet, J.: Branching processes of petri nets. Acta Informatica 28(6), 575–591 (1991)
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)
Esparza, J., Römer, S., Vogler, W.: An improvement of mcmillan’s unfolding algorithm. Formal Methods in System Design 20(3), 285–310 (2002)
Goltz, U., Reisig, W.: The non-sequential behaviour of petri nets. Information and Control 57(2/3), 125–147 (1983)
Haar, S.: Branching processes of general s/t-systems and their properties. Electr. Notes Theor. Comput. Sci. 18 (1998)
Hoogers, P., Kleijn, H., Thiagarajan, P.: An event structure semantics for general petri nets. Theoretical Computer Science 153(1&2), 129–170 (1996)
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)
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)
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)
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)
Khomenko, V., Koutny, M., Vogler, W.: Canonical prefixes of petri net unfoldings. Acta Inf. 40(2), 95–118 (2003)
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)
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)
Meseguer, J., Montanari, U., Sassone, V.: On the semantics of place/transition petri nets. Mathematical Structures in Computer Science 7(4), 359–397 (1997)
Nielsen, M., Plotkin, G.D., Winskel, G.: Petri nets, event structures and domains, part i. Theoretical Computer Science 13, 85–108 (1981)
Winskel, G.: Event structures. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 255, pp. 325–392. Springer, Heidelberg (1987)
Author information
Authors and Affiliations
Department of Applied Computer Science, Catholic University of Eichstätt-Ingolstadt,
Robin Bergenthum, Robert Lorenz & Sebastian Mauser
- Robin Bergenthum
You can also search for this author inPubMed Google Scholar
- Robert Lorenz
You can also search for this author inPubMed Google Scholar
- Sebastian Mauser
You can also search for this author inPubMed Google Scholar
Editor information
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
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-68745-0
Online ISBN:978-3-540-68746-7
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative