Abstract
A Petri net is reversible if its initial marking is a home marking, a marking reachable from any reachable marking. Under the assumption of well-behavedness we investigate the property of reversibility for strongly connected weighted Choice-Free Petri nets, nets which structurally avoid conflicts. Several characterizations of liveness and reversibility as well as exponential methods for building live and home markings are available for these nets. We provide a new characterization of reversibility leading to the construction in polynomial time of an initial marking with a polynomial number of tokens that is live and reversible. We also introduce a polynomial time transformation of well-formed Choice-Free systems into well-formed T-systems and we deduce from it a polynomial time sufficient condition of liveness and reversibility for well-formed Choice-Free systems. We show that neither one of these two approaches subsumes the other.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lee, E.A., Messerschmitt, D.G.: Synchronous Data Flow. Proceedings of the IEEE 75(9), 1235–1245 (1987)
Best, E., Darondeau, P.: Petri Net Distributability. In: Clarke, E., Virbitskaite, I., Voronkov, A. (eds.) PSI 2011. LNCS, vol. 7162, pp. 1–18. Springer, Heidelberg (2012)
Murata, T.: Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE 77(4), 541–580 (1989)
Teruel, E., Colom, J.M., Silva, M.: Choice-Free Petri Nets: A Model for Deterministic Concurrent Systems with Bulk Services and Arrivals. IEEE Transactions on Systems, Man and Cybernetics, Part A 27(1), 73–83 (1997)
Teruel, E., Chrzastowski-Wachtel, P., Colom, J.M., Silva, M.: On Weighted T-systems. In: Jensen, K. (ed.) ICATPN 1992. LNCS, vol. 616, pp. 348–367. Springer, Heidelberg (1992)
Barkaoui, K., Petrucci, L.: Structural Analysis of Workflow Nets with Shared Resources. In: van der Aalst, W.M.P., De Michelis, G., Ellis, C.A. (eds.) Proceedings of Workflow Management: Net-Based Concepts, Models, Techniques and Tools (WFM 1998). Computing Science Report, vol. 98/7, pp. 82–95 (1998)
Teruel, E., Silva, M.: Liveness and Home States in Equal Conflict Systems. In: Marsan, M.A. (ed.) ICATPN 1993. LNCS, vol. 691, pp. 415–432. Springer, Heidelberg (1993)
Recalde, L., Teruel, E., Silva, M.: Modeling and Analysis of Sequential Processes that Cooperate through Buffers. IEEE Transactions on Robotics and Automation 14(2), 267–277 (1998)
Berthelot, G., Lri-Iie: Checking Properties of Nets Using Transformations. In: Rozenberg, G. (ed.) APN 1985. LNCS, vol. 222, pp. 19–40. Springer, Heidelberg (1986)
Berthelot, G.: Transformations and Decompositions of Nets. In: Brauer, W., Reisig, W., Rozenberg, G. (eds.) APN 1986. LNCS, vol. 254, pp. 359–376. Springer, Heidelberg (1987)
Colom, J., Teruel, E., Silva, M., Haddad, S.: Structural Methods. In: Petri Nets for Systems Engineering, pp. 277–316. Springer, Heidelberg (2003)
Memmi, G., Roucairol, G.: Linear Algebra in Net Theory. In: Brauer, W. (ed.) Net Theory and Applications. LNCS, vol. 84, pp. 213–223. Springer, Heidelberg (1980)
Sifakis, J.: Structural Properties of Petri Nets. In: Winkowski, J. (ed.) MFCS 1978. LNCS, vol. 64, pp. 474–483. Springer, Heidelberg (1978)
Teruel, E., Silva, M.: Structure theory of Equal Conflict systems. Theoretical Computer Science 153(1&2), 271–300 (1996)
Keller, R.M.: A Fundamental Theorem of Asynchronous Parallel Computation. In: Feng, T.-Y. (ed.) Parallel Processing. LNCS, vol. 24, pp. 102–112. Springer, Heidelberg (1975)
Best, E., Darondeau, P.: Decomposition Theorems for Bounded Persistent Petri Nets. In: van Hee, K.M., Valk, R. (eds.) PETRI NETS 2008. LNCS, vol. 5062, pp. 33–51. Springer, Heidelberg (2008)
Lien, Y.E.: Termination Properties of Generalized Petri Nets. SIAM Journal on Computing 5(2), 251–265 (1976)
Delosme, J.M., Hujsa, T., Munier-Kordon, A.: Polynomial Sufficient Conditions of Well-behavedness for Weighted Join-Free and Choice-Free Systems. In: Proceedings of the 13th International Conference on Application of Concurrency to System Design (ACSD 2013), pp. 90–99 (2013)
Hujsa, T., Delosme, J.M., Munier-Kordon, A.: Polynomial Sufficient Conditions of Well-behavedness and Home Markings in Subclasses of Weighted Petri Nets. Transactions on Embedded Computing Systems (to appear, 2014)
Marchetti, O., Munier-Kordon, A.: A Sufficient Condition for the Liveness of Weighted Event Graphs. European Journal of Operational Research 197(2), 532–540 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hujsa, T., Delosme, JM., Munier-Kordon, A. (2014). On the Reversibility of Well-Behaved Weighted Choice-Free Systems. In: Ciardo, G., Kindler, E. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2014. Lecture Notes in Computer Science, vol 8489. Springer, Cham. https://doi.org/10.1007/978-3-319-07734-5_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-07734-5_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07733-8
Online ISBN: 978-3-319-07734-5
eBook Packages: Computer ScienceComputer Science (R0)