Abstract
The siphon-trap property, also known as Commoner-Hack property, establishes a relation between structural entities within a Petri net – the eponymous siphons and traps. The property is linked to the behavior of a Petri net, for instance to deadlock freedom and liveness of the net. It is nevertheless nontrivial to decide the property as a net can have exponentially many siphons and traps even if only minimal siphons are considered. Consequently, the value of the property depends on the availability of powerful decision procedures.
We contribute to this issue by proposing two new methods for deciding the siphon-trap property. One is a plain translation of the property into a Boolean satisfiability (SAT) problem, which exploits the fact that incredibly powerful SAT solvers are available. The second procedure has a divide-and-conquer nature which builds upon a decomposition of a Petri net into open nets and projects information about siphons and traps onto the interfaces of the components.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Barkaoui, K., Minoux, M.: A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets. In: Jensen, K. (ed.) ICATPN 1992. LNCS, vol. 616, pp. 62–75. Springer, Heidelberg (1992)
Desel, J., Esparza, J.: Free Choice Petri nets. Cambridge Tracts in Theoretical Computer Science, vol. 40. Cambridge University Press, Cambridge (1995)
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)
Esparza, J., Nielsen, M.: Decidability issues for Petri nets. Petri Nets Newsletter 52, 245–262 (1994)
Hack, M.H.T.: Analysis of Production Schemata by Petri Nets. Master’s thesis, MIT, Dept. Electrical Engineering, Cambridge, Mass (1972)
INA. Integrated Net Analyzer (2003), http://www2.informatik.hu-berlin.de/~starke/ina.html
Karatkevich, A.: Analysis by solving logical equations – calculation of siphons and traps. In: Dynamic Analysis of Petri Net-based Discrete Systems. LNCIS, vol. 356, pp. 87–93. Springer, Heidelberg (2007)
Mennicke, S., Oanea, O., Wolf, K.: Decomposition into open nets. In: AWPN 2009. CEUR Workshop Proceedings, vol. 501, pp. 29–34. CEUR-WS.org (2009)
MiniSat. Minimalistic, open-source SAT solver (2007), http://www.minisat.se
Minoux, M., Barkaoui, K.: Polynomial algorithms for proving or disproving Commoner’s property in Petri nets. In: Proceedings 9th Workshop on Theory and Applications of Petri Nets, vol. 1, pp. 113–125 (1988)
Zaitsev, D.A.: Decomposition of Petri nets. Cybernetics and Systems Analysis (5), 131–140 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oanea, O., Wimmel, H., Wolf, K. (2010). New Algorithms for Deciding the Siphon-Trap Property. In: Lilius, J., Penczek, W. (eds) Applications and Theory of Petri Nets. PETRI NETS 2010. Lecture Notes in Computer Science, vol 6128. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13675-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-13675-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13674-0
Online ISBN: 978-3-642-13675-7
eBook Packages: Computer ScienceComputer Science (R0)