Abstract
A Petri net is reversible if its initial marking is a home marking, a marking reachable from any reachable marking. This property is fundamental in man-made systems as it lets a system return to its initial state using only internal operations.
Necessary and sufficient conditions are already known for the reversibility of well-formed Choice-Free and ordinary Free-Choice nets. Like the homogeneous Join-Free nets, these nets constitute subclasses of Equal-Conflict nets. In this larger class, the reversibility property is not well understood.
This paper provides the first characterization of reversibility for all the live Equal-Conflict systems by extending, in a weaker form, a known condition that applies to the Choice-Free and Free-Choice subclasses. We also show that this condition is tightly related to the Equal-Conflict class and does not apply to several other classes.
T. Hujsa — The work of this author is supported by Digiteo / Project Tatami.
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
Araki, T., Kasami, T.: Decidable Problems on the Strong Connectivity of Petri Net Reachability Sets. Theoretical Computer Science 4(1), 99–119 (1977)
Barkaoui, K., Couvreur, J.-M., Klai, K.: On the equivalence between liveness and deadlock-freeness in petri nets. In: Ciardo, G., Darondeau, P. (eds.) ICATPN 2005. LNCS, vol. 3536, pp. 90–107. Springer, Heidelberg (2005)
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)
de Frutos Escrig, D., Johnen, C.: Decidability of Home Space Property. Tech. Rep. LRI-503, Univ. de Paris-Sud, Centre d’Orsay, LRI (1989)
Desel, J., Esparza, J.: Free Choice Petri Nets, Cambridge Tracts in Theoretical Computer Science, vol. 40. Cambridge University Press, New York (1995)
Haddad, S., Mairesse, J., Nguyen, H.T.: Synthesis and Analysis of Product-form Petri Nets. Fundamenta Informaticae 122(1–2), 147–172 (2013)
Hujsa, T., Delosme, J.-M., Munier-Kordon, A.: On the reversibility of well-behaved weighted choice-free systems. In: Ciardo, G., Kindler, E. (eds.) PETRI NETS 2014. LNCS, vol. 8489, pp. 334–353. Springer, Heidelberg (2014)
Lee, E.A., Messerschmitt, D.G.: Synchronous Data Flow. Proceedings of the IEEE 75(9), 1235–1245 (1987)
López-Grao, J.-P., Colom, J.-M.: Structural Methods for the Control of Discrete Event Dynamic Systems – The Case of the Resource Allocation Problem. In: Seatzu, C., Silva Suárez, M., van Schuppen, J.H. (eds.) Control of Discrete-event Systems. LNCIS, vol. 433, pp. 257–278. Springer, Heidelberg (2013)
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)
Murata, T.: Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE 77(4), 541–580 (1989)
Recalde, L., Teruel, E., Silva, M.: SC*ECS: a class of modular and hierarchical cooperating systems. In: Billington, J., Reisig, W. (eds.) Application and Theory of Petri Nets 1996. LNCS, vol. 1091, pp. 440–459. Springer, Heidelberg (1996)
Sifakis, J.: Structural properties of petri nets. In: Winkowski, J. (ed.) Mathematical Foundations of Computer Science. LNCS, vol. 64, pp. 474–483. Springer, Heidelberg (1978)
Teruel, E., Chrzastowski-Wachtel, P., Colom, J.M., Silva, M.: On Weighted T-systems. In: Jensen, K. (ed.) Application and Theory of Petri Nets 1992. LNCS, vol. 616, pp. 348–367. Springer, Heidelberg (1992)
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., Silva, M.: Liveness and home states in equal-conflict systems. In: Marsan, M.A. (ed.) Application and Theory of Petri Nets 1993. LNCS, vol. 691, pp. 415–432. Springer, Heidelberg (1993)
Teruel, E., Silva, M.: Structure Theory of Equal Conflict Systems. Theoretical Computer Science 153(1&2), 271–300 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Hujsa, T., Delosme, JM., Munier-Kordon, A. (2015). On the Reversibility of Live Equal-Conflict Petri Nets. In: Devillers, R., Valmari, A. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2015. Lecture Notes in Computer Science(), vol 9115. Springer, Cham. https://doi.org/10.1007/978-3-319-19488-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-19488-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19487-5
Online ISBN: 978-3-319-19488-2
eBook Packages: Computer ScienceComputer Science (R0)