{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:08:04Z","timestamp":1766066884071,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T00:00:00Z","timestamp":1531353600000},"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":[[2018,10]]},"DOI":"10.1007\/s10601-018-9286-5","type":"journal-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T07:46:00Z","timestamp":1531381560000},"page":"451-480","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["From MDD to BDD and Arc consistency"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1539-9846","authenticated-orcid":false,"given":"Julien","family":"Vion","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Piechowiak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,12]]},"reference":[{"key":"9286_CR1","volume-title":"Anatomy of LISP","author":"J Allen","year":"1978","unstructured":"Allen, J. (1978). Anatomy of LISP. New York: McGraw-Hill, Inc. isbn: 0-07-001115-X."},{"key":"9286_CR2","unstructured":"Bagwell, P. (2001). Ideal hash trees. Tech. rep EPFL."},{"key":"9286_CR3","doi-asserted-by":"crossref","unstructured":"Bentley, J., & Floyd, R.W. (1987). Programming pearls: a sample of brilliance. In Commun (Vol. 30.9, pp. 754\u2013757), ACM.","DOI":"10.1145\/30401.315746"},{"key":"9286_CR4","doi-asserted-by":"crossref","unstructured":"Bergman, D., Cir\u00e9, A.A., van Hoeve, W.-J., Hooker, J. (2016). MDD Propagation for sequence constraints. In Decision diagrams for optimization (Chap. 10, pp. 183\u2013204). Springer.","DOI":"10.1007\/978-3-319-42849-9_10"},{"key":"9286_CR5","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C., & R\u00e9gin J.-C. (1996). MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. of the 12th itl. conf. on principle and practice of constraint programming (CP) (pp. 61\u201375).","DOI":"10.1007\/3-540-61551-2_66"},{"key":"9286_CR6","doi-asserted-by":"crossref","unstructured":"Bollig, B., & Wegener, I. (1996). Improving the variable ordering of OBDDs is NP-complete. In IEEE Transactions on computers (Vol. 45.9, pp. 993\u20131002).","DOI":"10.1109\/12.537122"},{"key":"9286_CR7","doi-asserted-by":"crossref","unstructured":"Briggs, P., & Torczon, L. (1993). An efficient representation for sparse sets. In ACM Letters on programming languages and systems (Vol. 2.1\u20134, pp. 59\u201369).","DOI":"10.1145\/176454.176484"},{"key":"9286_CR8","doi-asserted-by":"crossref","unstructured":"Bryant, R.E. (1986). Graph-based algorithms for boolean function manipulation. In IEEE Transactions on computers 100.8 (pp. 677\u2013691).","DOI":"10.1109\/TC.1986.1676819"},{"key":"9286_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, K.C.K., & Yap, R.H.C. (2010). An MDD-based GAC algorithm for positive and negative table constraints and some global constraints. In Constraints (Vol. 15.2, pp. 265\u2013304).","DOI":"10.1007\/s10601-009-9087-y"},{"key":"9286_CR10","unstructured":"Cheng, K.C.K., & Yap, R.H.C. (2006). Maintaining generalized arc consistency on ad-hoc n-ary boolean constraints. In Proc. ECAI-06 (pp. 78\u201382). IOS Press."},{"key":"9286_CR11","unstructured":"Cir\u00e9, A.A., & Hooker, J.N. (2014). The separation problem for binary decision diagrams. In Proc. ISAIM."},{"key":"9286_CR12","doi-asserted-by":"crossref","unstructured":"Codd, E.F. (1970). A relational model of data for large shared data banks. In Communications of the ACM (Vol. 13.6, pp. 377\u2013387).","DOI":"10.1145\/362384.362685"},{"key":"9286_CR13","unstructured":"Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., R\u00e9gin, J., Schaus, P. (2016). Compact-table: efficiently filtering table constraints with reversible sparse bit-sets. In Proc. CP\u20192016, (Vol. 9892 pp. 207\u2013223): LNCS. Springer."},{"key":"9286_CR14","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(89)90034-2","volume":"38","author":"JR Driscoll","year":"1989","unstructured":"Driscoll, J.R., Sarnak, N., Sleator, D., Tarjan, R. (1989). Making data structures persistent. Journal of Computer and System Science, 38, 86\u2013124.","journal-title":"Journal of Computer and System Science"},{"key":"9286_CR15","doi-asserted-by":"crossref","unstructured":"Fredkin, E. (1960). Trie memory. In Comm. ACM (Vol. 3.9, pp. 490\u2013499).","DOI":"10.1145\/367390.367400"},{"key":"9286_CR16","doi-asserted-by":"crossref","unstructured":"Gange, G., Stuckey, P.J., Szymanek, R. (2011). MDD propagators with explanation. In Constraints (Vol. 16.4, pp. 407\u2013429).","DOI":"10.1007\/s10601-011-9111-x"},{"key":"9286_CR17","unstructured":"Gent, I.P., Jefferson, C, Miguel, I., Nightingale, P. (2007). Data structures for generalised arc consistency for extensional constraints. In Proc. AAAI\u20192007 (pp. 191\u2013197)."},{"key":"9286_CR18","unstructured":"Gent, I.P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints. Tech. rep. APES-09-1999. http:\/\/www.csplib.org ."},{"key":"9286_CR19","unstructured":"Hadzic, T., Hansen, E.R., O\u2019Sullivan, B. (2008). On automata, MDDs and BDDs in constraint satisfaction. In Proc. ECAI Workshop on inference methods based on graphical structure of knowledge (WIGSK)."},{"key":"9286_CR20","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P Hentenryck van","year":"1992","unstructured":"van Hentenryck, P., Deville, Y., Teng, C.M. (1992). A generic AC algorithm and its specializations. Artificial Intelligence, 57, 291\u2013321.","journal-title":"Artificial Intelligence"},{"key":"9286_CR21","unstructured":"Lecoutre, C. (2006). Benchmarks 2.0 XML representation of CSP instances. http:\/\/www.cril.univ-artois.fr\/lecoutre\/research\/benchmarks ."},{"key":"9286_CR22","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s10601-011-9107-6","volume":"16.4","author":"C Lecoutre","year":"2011","unstructured":"Lecoutre, C. (2011). STR2: optimized simple tabular reduction for table constraints. Constraints, 16.4, 341\u2013371.","journal-title":"Constraints"},{"key":"9286_CR23","unstructured":"Lecoutre, C., & Hemery, F. (2007). A study of residual supports in arc consistency. In Proceedings of IJCAI\u20192007 (pp. 125\u2013130)."},{"key":"9286_CR24","unstructured":"Lecoutre, C., Likitvivatanavong, C., Yap, R.H.C. (2012). A path-optimal GAC algorithm for table constraints. In Proc. ECAI\u20192012 (pp. 510\u2013515)."},{"key":"9286_CR25","unstructured":"Lecoutre, C., & Roussel, O. (2008). XML representation of constraint networks, Version 2.1. In The Computing research repository arXiv: 0902.2362v1 ."},{"key":"9286_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8.1","author":"AK Mackworth","year":"1977","unstructured":"Mackworth, A.K. (1977). Consistency in networks of relations. Artificial Intelligence, 8.1, 99\u2013118.","journal-title":"Artificial Intelligence"},{"key":"9286_CR27","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s10601-013-9156-0","volume":"19.1","author":"J-B Mairy","year":"2014","unstructured":"Mairy, J.-B., van Hentenryck, P., Deville, Y. (2014). Optimal and efficient filtering algorithms for table constraints. Constraints, 19.1, 77\u2013120.","journal-title":"Constraints"},{"key":"9286_CR28","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1038\/218019a0","volume":"218","author":"D Michie","year":"1968","unstructured":"Michie, D. (1968). Memo functions and machine learning. Nature, 218, 19\u201322.","journal-title":"Nature"},{"key":"9286_CR29","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U. (1974). Network of constraints: fundamental properties and applications to picture processing. Information Science, 7, 95\u2013132.","journal-title":"Information Science"},{"key":"9286_CR30","unstructured":"Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G. (2007). Minizinc: towards a standard CP modelling language. In Bessi\u00e8re, C. (Ed.) Proc. CP\u20192007 (pp. 529\u2013543): LNCS 4741. Springer-Verlag."},{"key":"9286_CR31","unstructured":"Odersky, M., & et al. (2001). The scala programming language. http:\/\/www.scalalang.org\/ ."},{"key":"9286_CR32","unstructured":"Perez, G., & R\u00e9gin, J.-C. (2015). Efficient operations on MDDs for building constraint programming models. In Proc. 24th IJCAI (pp. 374\u2013380)."},{"key":"9286_CR33","unstructured":"Perez, G., & R\u00e9gin, J.-C. (2014). Improving GAC-4 for table and MDD constraints. In O\u2019Sullivan, B. (Ed.) Proc. 20th Conference on principles and practice of CP (pp. 606\u2013621): LNCS 8656. Springer."},{"key":"9286_CR34","doi-asserted-by":"publisher","unstructured":"Srinivasan, A., Ham, T., Malik, S., Brayton, R.K. (1990). Algorithms for discrete function manipulation. In 1990 IEEE International conference on computer-aided design. Digest of Technical Papers. pp. 92\u201395. https:\/\/doi.org\/10.1109\/ICCAD.1990.129849 .","DOI":"10.1109\/ICCAD.1990.129849"},{"key":"9286_CR35","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1609\/aimag.v35i2.2539","volume":"35.2","author":"PJ Stuckey","year":"2014","unstructured":"Stuckey, P.J., Feydy, T., Schutt, A., Tack, G., Fischer, J. (2014). The minizinc challenge 2008\u20132013. AI Magazine, 35.2, 55\u201360.","journal-title":"AI Magazine"},{"key":"9286_CR36","doi-asserted-by":"publisher","first-page":"3639","DOI":"10.1016\/j.ins.2007.03.030","volume":"177","author":"JR Ullmann","year":"2007","unstructured":"Ullmann, J.R. (2007). Partition search for non-binary constraint satisfaction. Information Science, 177, 3639\u20133678.","journal-title":"Information Science"},{"key":"9286_CR37","unstructured":"Vion, J. (2006). Concrete: a CSP Solving API for the JVM. http:\/\/github.com\/concrete-cp ."},{"key":"9286_CR38","unstructured":"Vion, J. (2013). Consistance d\u2019arc par MDD-R\u00e9duction. French. In Truchet, C. (ed) Actes des 9 e Journ\u00e9es Francophones de Programmation par Contraintes (JFPC) (pp. 323\u2013332)."},{"key":"9286_CR39","doi-asserted-by":"crossref","unstructured":"Vion, J., & Piechowiak, S. (2014). Maintenir des MDD persistants pour \u00e9tablir la consistance d\u2019arc. French. In Revue d\u2019Intelligence Artificielle (Vol. 28.5, pp. 547\u2013569).","DOI":"10.3166\/ria.28.547-569"},{"key":"9286_CR40","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.artint.2007.04.001","volume":"171","author":"K Xu","year":"2007","unstructured":"Xu, K., Boussemart, F., Hemery, F., Lecoutre, C. (2007). A simple model to generate hard satisfiable instances. Artificial Intelligence, 171, 514\u2013534.","journal-title":"Artificial Intelligence"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-018-9286-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9286-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9286-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:23:35Z","timestamp":1661592215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-018-9286-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["9286"],"URL":"https:\/\/doi.org\/10.1007\/s10601-018-9286-5","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2018,7,12]]},"assertion":[{"value":"12 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}