On the Reversibility of Well-Behaved Weighted Choice-Free Systems

International audienceA 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