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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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)