{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:18Z","timestamp":1759638438651},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,4,10]],"date-time":"2015-04-10T00:00:00Z","timestamp":1428624000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s10601-015-9190-1","type":"journal-article","created":{"date-parts":[[2015,4,9]],"date-time":"2015-04-09T06:16:36Z","timestamp":1428560196000},"page":"251-276","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On enumerating minimal siphons in Petri nets using CLP and SAT solvers: theoretical and practical complexity"],"prefix":"10.1007","volume":"21","author":[{"given":"Faten","family":"Nabli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thierry","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Fages","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Soliman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,10]]},"reference":[{"issue":"3","key":"9190_CR1","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1093\/bioinformatics\/15.3.234","volume":"15","author":"R Backofen","year":"1999","unstructured":"Backofen, R., Will, S., & Bornberg-Bauer, E. (1999). Application of constraint programming techniques for structure prediction of lattice proteins with extended alphabets. Bioinformatics, 15(3), 234\u2013242.","journal-title":"Bioinformatics"},{"key":"9190_CR2","doi-asserted-by":"crossref","unstructured":"Birtwistle, M.R., Hatakeyama, M., Yumoto, N., Ogunnaike, B.A., Hoek, J.B., & Kholodenko, B.N. (2007). Ligand-dependent responses of the ErbB signaling network: experimental and modeling analysis. Molecular Systems Biology, 3(144).","DOI":"10.1038\/msb4100188"},{"key":"9190_CR3","doi-asserted-by":"crossref","unstructured":"Bockmayr, A., & Courtois, A. (2002). Using hybrid concurrent constraint programming to model dynamic biological systems. In: Proceedings of ICLP\u201902, International conference on logic programming of lecture notes in computer science, (Vol. 2401. pp. 85\u201399). Copenhagen: Springer.","DOI":"10.1007\/3-540-45619-8_7"},{"key":"9190_CR4","doi-asserted-by":"crossref","unstructured":"Calzone, L., Gelay, A., Zinovyev, A., Radvanyi, F., & Barillot, E. (2008). A comprehensive modular map of molecular interactions in RB\/E2F pathway. Molecular Systems Biology, 4(173).","DOI":"10.1038\/msb.2008.7"},{"issue":"1","key":"9190_CR5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.tcs.2004.03.063","volume":"325","author":"N Chabrier-Rivier","year":"2004","unstructured":"Chabrier-Rivier, N., Chiaverini, M., Danos, V., Fages, F., & Sch\u00e4chter, V. (2004). Modeling and querying biochemical interaction networks. Theoretical Computer Science, 325(1), 25\u201344.","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"9190_CR6","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1109\/70.650158","volume":"13","author":"F Chu","year":"1997","unstructured":"Chu, F., & Xie, X.-L. (1997). Deadlock analysis of petri nets using siphons and mathematical programming. IEEE Transactions on Robotics and Automation, 13(6), 793\u2013804.","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"9190_CR7","volume-title":"Deadlocks in petri nets","author":"F Commoner","year":"1972","unstructured":"Commoner, F. (1972). Deadlocks in petri nets. Wakefield: Applied Data Research Inc."},{"issue":"2","key":"9190_CR8","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.biosystems.2009.07.007","volume":"98","author":"F Corblin","year":"2009","unstructured":"Corblin, F., Tripodi, S., Fanchon, E., Ropers, D., & Trilling, L. (2009). A declarative constraint-based method for analyzing discrete genetic regulatory networks. Biosystems, 98(2), 91\u2013104.","journal-title":"Biosystems"},{"key":"9190_CR9","doi-asserted-by":"crossref","unstructured":"Cordone, R., Ferrarini, L., & Piroddi, L. (2002). Characterization of minimal and basis siphons with predicate logic and binary programming. In: Proceedings of IEEE international symposium on computer-aided control system design. (pp. 193\u2013198).","DOI":"10.1109\/CACSD.2002.1036952"},{"key":"9190_CR10","doi-asserted-by":"crossref","unstructured":"Cordone, R., Ferrarini, L., & Piroddi, L. (2003). Some results on the computation of minimal siphons in petri nets. In: Proceedings of the 42nd IEEE conference on decision and control. Maui.","DOI":"10.1109\/CDC.2003.1271733"},{"issue":"6","key":"9190_CR11","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1109\/TSMCA.2005.853504","volume":"35","author":"R Cordone","year":"2005","unstructured":"Cordone, R., Ferrarini, L., & Piroddi, L. (2005). Enumeration algorithms for minimal siphons in petri nets based on place constraints. IEEE Transactions on Systems, Man and Cybernetics. Part A, Systems and Humans, 35(6), 844\u2013854.","journal-title":"IEEE Transactions on Systems, Man and Cybernetics. Part A, Systems and Humans"},{"key":"9190_CR12","doi-asserted-by":"crossref","unstructured":"Courcelle, B. (1990). The monadic second-order logic of graphs i. recognizable sets of finite graphs. Information and computation.","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"9190_CR13","doi-asserted-by":"crossref","unstructured":"Courcelle, B., & Durand, I. (2012). Automata for the verification of monadic second-order graph properties. Journal of applied logic.","DOI":"10.1016\/j.jal.2011.07.001"},{"key":"9190_CR14","unstructured":"Crawford, J.M., & Auton, L.D. (1993). Experimental results on the crossover point in satisfiability problems. In: Proceedings of the 11th National Conference on Artificial Intelligence. (pp. 21\u201327): AAAI press."},{"issue":"1","key":"9190_CR15","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1093\/bioinformatics\/btn621","volume":"25","author":"LF de Figueiredo","year":"2009","unstructured":"de Figueiredo, L.F., Schuster, S., Kaleta, C., & Fell, D.A. (2009). Can sugars be produced from fatty acids? a test case for pathway analysis tools. Bioinformatics, 25(1), 152\u2013158.","journal-title":"Bioinformatics"},{"key":"9190_CR16","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1016\/S0092-8240(03)00061-2","volume":"65","author":"V Devloo","year":"2003","unstructured":"Devloo, V., Hansen, P., & Labbe, M. (2003). Identification of all steady states in large biological systems by logical analysis. Bulletin of Mathematical Biology, 65, 1025\u20131051.","journal-title":"Bulletin of Mathematical Biology"},{"key":"9190_CR17","unstructured":"Diaz, D., & Codognet, P. (2001). Design and implementation of the GNU Prolog system. Journal of functional and logic programming."},{"issue":"4","key":"9190_CR18","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1007\/s11538-006-9130-8","volume":"69","author":"P Dittrich","year":"2007","unstructured":"Dittrich, P., & di Fenizio, P. (2007). Chemical organisation theory. Bulletin of Mathematical Biology, 69(4), 1199\u20131231.","journal-title":"Bulletin of Mathematical Biology"},{"issue":"4","key":"9190_CR19","first-page":"241","volume":"9","author":"F Fages","year":"2004","unstructured":"Fages, F., Soliman, S., & Coolen, R. (2004). CLPGUI: a generic graphical user interface for constraint logic programming. Journal of Constraints, Special Issue on User-Interaction in Constraint Satisfaction, 9(4), 241\u2013262.","journal-title":"Journal of Constraints, Special Issue on User-Interaction in Constraint Satisfaction"},{"key":"9190_CR20","unstructured":"Fanchon, E., Corblin, F., Trilling, L., Hermant, B., & Gulino, D. (2004). Modeling the molecular network controlling adhesion between human endothelial cells: Inference and simulation using constraint logic programming. In: CMSB\u201904: proceedings of the 20 international conference on computational methods in systems biology. (pp. 104\u2013118): Springer."},{"key":"9190_CR21","doi-asserted-by":"crossref","first-page":"2000","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124, 2000.","journal-title":"Artificial Intelligence"},{"key":"9190_CR22","doi-asserted-by":"crossref","unstructured":"Goud, R., van Hee, K., Post, R., & van der Werf, J. (2006). Petriweb: A repository for petri nets. In S. Donatelli, & P. Thiagarajan (Eds.), Petri nets and other models of concurrency - ICATPN 2006 of lecture notes in computer science, (Vol. 4024. pp. 411\u2013420): Springer.","DOI":"10.1007\/11767589_24"},{"key":"9190_CR23","doi-asserted-by":"crossref","unstructured":"Heiner, M., Gilbert, D., & Donaldson, R. (2008). Petri nets for systems and synthetic biology. In M. Bernardo, P. Degano, & G. Zavattaro (Eds.), 8th int. school on formal methods for the design of computer, communication and software systems: computational systems biology SFM\u201908 of lecture notes in computer science, (Vol. 5016. pp. 215\u2013264). Bertinoro: Springer.","DOI":"10.1007\/978-3-540-68894-5_7"},{"key":"9190_CR24","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1042\/bj3570117","volume":"357","author":"S Helfert","year":"2001","unstructured":"Helfert, S., Estevez, A., Bakker, B., Michels, P., & Clayton, C. (2001). Roles of triosephosphate isomerase and aerobic metabolism in trypanosoma brucei. Biochemical Journal, 357, 117\u2013 125.","journal-title":"Biochemical Journal"},{"issue":"15","key":"9190_CR25","doi-asserted-by":"crossref","first-page":"1915","DOI":"10.1093\/bioinformatics\/btp332","volume":"25","author":"C Kaleta","year":"2009","unstructured":"Kaleta, C., Richter, S., & Dittrich, P. (2009). Using chemical organization theory for model checking. Bioinformatics, 25(15), 1915\u20131922.","journal-title":"Bioinformatics"},{"key":"9190_CR26","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. In R. E. Miller, & J. W. Thatcher (Eds.) Proceedings of a symposium on the complexity of computer computations. (pp. 85\u2013103). New York: IBM Research Symposia Series, Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9190_CR27","unstructured":"Kinuyama, M., & Murata, T. (1986). Generating siphons and traps by petri net representation of logic equations. In: Proceedings of 2th conference of the net theory SIG-IECE. (pp. 93\u2013100)."},{"issue":"4","key":"9190_CR28","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","volume":"8","author":"J Kneis","year":"2011","unstructured":"Kneis, J., Langer, A., & Rossmanith, P. (2011). Courcelle\u2019s theorem - a game-theoretic approach. Discrete Optimization, 8(4), 568\u2013594.","journal-title":"Discrete Optimization"},{"issue":"8","key":"9190_CR29","doi-asserted-by":"crossref","first-page":"2703","DOI":"10.1091\/mbc.10.8.2703","volume":"10","author":"KW Kohn","year":"1999","unstructured":"Kohn, K.W. (1999). Molecular interaction map of the mammalian cell cycle control and DNA repair systems. Molecular Biology of the Cell, 10(8), 2703\u20132734.","journal-title":"Molecular Biology of the Cell"},{"issue":"10","key":"9190_CR30","doi-asserted-by":"crossref","first-page":"2257","DOI":"10.1016\/j.dam.2008.06.039","volume":"157","author":"A Larhlimi","year":"2009","unstructured":"Larhlimi, A., & Bockmayr, A. (2009). A new constraint-based description of the steady-state flux cone of metabolic networks. Discrete Applied Mathematics, 157(10), 2257\u20132266. Networks in Computational Biology.","journal-title":"Discrete Applied Mathematics"},{"key":"9190_CR31","doi-asserted-by":"crossref","unstructured":"Lautenbach, K. (1987). Linear algebraic calculation of deadlocks and traps. In G. Voss, & Rozenberg (Eds.), Concurrency and nets advances in petri nets. (pp. 315\u2013336). New York: Springer.","DOI":"10.1007\/978-3-642-72822-8_21"},{"issue":"34","key":"9190_CR32","doi-asserted-by":"crossref","first-page":"D689","DOI":"10.1093\/nar\/gkj092","volume":"1","author":"N le Nov\u00e8re","year":"2006","unstructured":"le Nov\u00e8re, N., Bornstein, B., Broicher, A., Courtot, M., Donizelli, M., Dharuri, H., Li, L., Sauro, H., Schilstra, M., Shapiro, B., Snoep, J.L., & Hucka, M. (2006). BioModels Database: a free, centralized database of curated, published, quantitative kinetic models of biochemical and cellular systems. Nucleic Acid Research, 1(34), D689\u2013D691.","journal-title":"Nucleic Acid Research"},{"key":"9190_CR33","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0166-218X(90)90144-2","volume":"29","author":"M Minoux","year":"1990","unstructured":"Minoux, M., & Barkaoui, K. (1990). Deadlocks and traps in petri nets as horn-satisfiability solutions and some related polynomially solvable problems. Discrete Applied Mathematics, 29, 195\u2013210.","journal-title":"Discrete Applied Mathematics"},{"key":"9190_CR34","unstructured":"Mitchell, D., Selman, B., & Levesque, H. (1992). Hard and easy distributions of sat problems. In: Proceedings of the 10th national conference on artificial intelligence. (pp. 459\u2013465): AAAI press."},{"issue":"4","key":"9190_CR35","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/5.24143","volume":"77","author":"T Murata","year":"1989","unstructured":"Murata, T. (1989). Petri nets: properties, analysis and applications. Proceedings of the IEEE, 77(4), 541\u2013579.","journal-title":"Proceedings of the IEEE"},{"key":"9190_CR36","unstructured":"Nabli, F. (2011). Finding minimal siphons as a CSP. In: CP\u201911: the seventeenth international conference on principles and practice of constraint programming, doctoral program. (pp. 67\u201372)."},{"key":"9190_CR37","doi-asserted-by":"crossref","unstructured":"Nabli, F., Fages, F., Martinez, T., & Soliman, S. (2012). A boolean model for enumerating minimal siphons and traps in petri-nets. In: Proceedings of CP\u20192012, 18th international conference on principles and practice of constraint programming of lecture notes in computer science, (Vol. 7514. pp. 798\u2013814): Springer.","DOI":"10.1007\/978-3-642-33558-7_57"},{"key":"9190_CR38","unstructured":"Nabli, F., & Soliman, S. (2010). Steady-state solution of biochemical systems, beyond S-systems via T-invariants. In P. Quaglia (Ed.) CMSB\u201910: proceedings of the 8th international conference on computational methods in systems biology. (pp. 14\u201322): ACM."},{"key":"9190_CR39","doi-asserted-by":"crossref","unstructured":"Oanea, O., Wimmel, H., & Wolf, K. (2010). New algorithms for deciding the siphon-trap property. In: PETRI NETS\u201910 proceedings of the 31st international conference on applications and theory of petri nets. (pp. 267\u2013286): Springer.","DOI":"10.1007\/978-3-642-13675-7_16"},{"key":"9190_CR40","volume-title":"Petri net theory and the modeling of systems","author":"JL Peterson","year":"1981","unstructured":"Peterson, J.L. (1981). Petri net theory and the modeling of systems. New Jersey: Prentice Hall."},{"key":"9190_CR41","unstructured":"Reddy, V.N., Mavrovouniotis, M.L., & Liebman, M.N. (1993). Petri net representations in metabolic pathways. In L. Hunter, D. B. Searls, & J. W. Shavlik (Eds.), Proceedings of the 1st international conference on intelligent systems for molecular biology (ISMB). (pp. 328\u2013336): AAAI Press."},{"issue":"3","key":"9190_CR42","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., & Seymour, P. (1986). Graph minors. II. algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309\u2013322.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"9190_CR43","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1038\/nbt0402-370","volume":"20","author":"B Schoeberl","year":"2002","unstructured":"Schoeberl, B., Eichler-Jonsson, C., Gilles, E.D., & Muller, G. (2002). Computational modeling of the dynamics of the map kinase cascade activated by surface and internalized egf receptors. Nature Biotechnology, 20(4), 370\u2013375.","journal-title":"Nature Biotechnology"},{"key":"9190_CR44","doi-asserted-by":"crossref","unstructured":"Soliman, S. (2012). Invariants and other structural properties of biochemical models as a constraint satisfaction problem. Algorithms for Molecular Biology, 7(15).","DOI":"10.1186\/1748-7188-7-15"},{"key":"9190_CR45","volume-title":"Biochemistry","author":"L Stryer","year":"1995","unstructured":"Stryer, L. (1995). Biochemistry. New York: Freeman."},{"key":"9190_CR46","unstructured":"Tanimoto, S., Yamauchi, M., & Watanabe, T. (1996). Finding minimal siphons in general petri nets."},{"issue":"15","key":"9190_CR47","doi-asserted-by":"crossref","first-page":"1930","DOI":"10.1093\/bioinformatics\/btl267","volume":"22","author":"A von Kamp","year":"2006","unstructured":"von Kamp, A., & Schuster, S. (2006). Metatool 5.0: fast and flexible elementary modes analysis. Bioinformatics, 22(15), 1930\u20131931.","journal-title":"Bioinformatics"},{"key":"9190_CR48","unstructured":"Yamauchi, M., & Watanabe, T. (1999). Time complexity analysis of the minimal siphon extraction problem of petri nets, EICE trans. on fundamentals of electronics, communications and computer sciences. (pp. 2558\u20132565)."},{"key":"9190_CR49","unstructured":"Zevedei-Oancea, I., & Schuster, S. (2003). Topological analysis of metabolic networks based on petri net theory. In Silico Biology, 3(29)."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-015-9190-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-015-9190-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-015-9190-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:14:18Z","timestamp":1559243658000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-015-9190-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,10]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9190"],"URL":"https:\/\/doi.org\/10.1007\/s10601-015-9190-1","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,10]]}}}