{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:06:27Z","timestamp":1761620787302,"version":"3.41.2"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1999,5,1]],"date-time":"1999-05-01T00:00:00Z","timestamp":925516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,5,1]],"date-time":"1999-05-01T00:00:00Z","timestamp":925516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[1999,5]]},"DOI":"10.1023\/a:1009890709297","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T18:53:29Z","timestamp":1040583209000},"page":"113-131","source":"Crossref","is-referenced-by-count":32,"title":["How to Determine the Expressive Power of Constraints"],"prefix":"10.1007","volume":"4","author":[{"given":"Peter","family":"Jeavons","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Gyssens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"205043_CR1","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/0004-3702(88)90023-9","volume":"35","author":"W. Bibel","year":"1988","unstructured":"Bibel, W. (1988). Constraint satisfaction from a deductive viewpoint. Artificial Intelligence 35:401\u2013413.","journal-title":"Artificial Intelligence"},{"key":"205043_CR2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. F. Codd","year":"1970","unstructured":"Codd, E. F. (1970). A relational model of data for large shared databanks. Communications of the ACM 13:377\u2013387.","journal-title":"Communications of the ACM"},{"key":"205043_CR3","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M. C. Cooper","year":"1994","unstructured":"Cooper, M. C., Cohen, D. A., Jeavons, P.G. (1994). Characterizing tractable constraints. Artificial Intelligence 65:347\u2013361.","journal-title":"Artificial Intelligence"},{"key":"205043_CR4","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","volume":"58","author":"R. Dechter","year":"1992","unstructured":"Dechter, R., & Pearl, J. (1992). Structure identification in relational data. Artificial Intelligence 58:237\u2013270.","journal-title":"Artificial Intelligence"},{"key":"205043_CR5","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"E. C. Freuder","year":"1985","unstructured":"Freuder, E. C. (1985). Asufficient condition for backtrack-bounded search. Journal of the ACM 32:755\u2013761.","journal-title":"Journal of the ACM"},{"key":"205043_CR6","volume-title":"Computers and Intractability: A Guide to NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to NP-Completeness. Freeman, San Francisco, California."},{"key":"205043_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M. Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P., Cohen, D. (1994). Decomposing constraint satisfaction problems using database techniques. Artificial Intelligence 66:57\u201389.","journal-title":"Artificial Intelligence"},{"key":"205043_CR8","doi-asserted-by":"crossref","unstructured":"Jeavons, P. G., Cohen, D. A. (1995). An algebraic characterization of tractable constraints. Lecture Notes in Computer Science 959:633\u2013642.","DOI":"10.1007\/BFb0030886"},{"key":"205043_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/3-540-60299-2_17","volume-title":"Proceedings 1st International Conference on Principles and Practice of Constraint Programming\u00b7CP '95","author":"P. Jeavons","year":"1995","unstructured":"Jeavons, P., Cohen D., Gyssens, M. (1995). A unifying framework for tractable constraints. In Proceedings 1st International Conference on Principles and Practice of Constraint Programming\u00b7CP '95 (Cassis, France, September 1995), Lecture Notes in Computer Science 976: Springer-Verlag, Berlin\/New York, 276\u2013291."},{"key":"205043_CR10","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"P. G. Jeavons","year":"1996","unstructured":"Jeavons, P. G., & Cooper, M. C. (1996). Tractable constraints on ordered domains. Artificial Intelligence 79:327\u2013339.","journal-title":"Artificial Intelligence"},{"key":"205043_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","volume":"64","author":"L. Kirousis","year":"1993","unstructured":"Kirousis, L. (1993). Fast parallel constraint satisfaction. Artificial Intelligence 64:147\u2013160.","journal-title":"Artificial Intelligence"},{"key":"205043_CR12","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P. B. Ladkin","year":"1994","unstructured":"Ladkin, P. B., & Maddux, R. D. (1994). On binary constraint problems. Journal of the ACM 41:435\u2013469.","journal-title":"Journal of the ACM"},{"key":"205043_CR13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. K. Mackworth","year":"1977","unstructured":"Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence 8:99\u2013118.","journal-title":"Artificial Intelligence"},{"key":"205043_CR14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U. (1974). Networks of constraints: fundamental properties and applications to picture processing. Information Sciences 7:95\u2013132.","journal-title":"Information Sciences"},{"key":"205043_CR15","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J. (1978). The complexity of satisfiability problems. Proc 10th ACM Symposium on Theory of Computing (STOC): 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"205043_CR16","unstructured":"Szendrei, A. (1986). Clones in Universal Algebra. Seminaires de Mathematiques Superieures 99, University of Montreal."},{"key":"205043_CR17","unstructured":"van Beek, P. (1992). On the Minimality and Decomposability of Row-Convex Constraint Networks. Proceedings of the Tenth National Conference on Artificial Intelligence, AAAI-92, MIT Press, 447\u2013452."},{"key":"205043_CR18","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P. Van Hentenryck","year":"1992","unstructured":"Van Hentenryck, P., Deville, Y., Teng, C-M. (1992). A generic arc-consistency algorithm and its specializations. Artificial Intelligence 57:291\u2013321.","journal-title":"Artificial Intelligence"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009890709297.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009890709297\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009890709297.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:00:46Z","timestamp":1752379246000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009890709297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,5]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1999,5]]}},"alternative-id":["205043"],"URL":"https:\/\/doi.org\/10.1023\/a:1009890709297","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[1999,5]]}}}