{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:53:48Z","timestamp":1725562428768},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540219378"},{"type":"electronic","value":"9783540246749"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24674-9_1","type":"book-chapter","created":{"date-parts":[[2010,8,4]],"date-time":"2010-08-04T21:36:21Z","timestamp":1280957781000},"page":"1-2","source":"Crossref","is-referenced-by-count":1,"title":["Constraint Satisfaction, Complexity, and Logic"],"prefix":"10.1007","author":[{"given":"Phokion G.","family":"Kolaitis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three-element set. In: Proc. 43rd IEEE Symposium on Foundations of Computer Science, pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proc. 18th IEEE Symposium on Logic in Computer Science (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Proc. of Eighth International Conference on Principles and Practice of Constraint Programming, pp. 310\u2013326 (2002)","DOI":"10.1007\/3-540-46135-3_21"},{"key":"1_CR4","first-page":"185","volume-title":"Encyclopedia of Artificial Intelligence","author":"R. Dechter","year":"1992","unstructured":"Dechter, R.: Constraint networks. In: Shapiro, S.C. (ed.) Encyclopedia of Artificial Intelligence, pp. 185\u2013276. Wiley, New York (1992)"},{"issue":"1-2","key":"1_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","volume":"113","author":"R. Dechter","year":"1999","unstructured":"Dechter, R.: Bucket elimination: a unifying framework for reasoning. Artificial Intelligence\u00a0113(1-2), 41\u201385 (1999)","journal-title":"Artificial Intelligence"},{"key":"1_CR6","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artificial Intelligence, 353\u2013366 (1989)","DOI":"10.1016\/0004-3702(89)90037-4"},{"key":"1_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"#cr-split#-1_CR9.1","doi-asserted-by":"crossref","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. on Computing??28, 57???104 (1998);","DOI":"10.1137\/S0097539794266766"},{"key":"#cr-split#-1_CR9.2","unstructured":"Preliminary version in Proc. 25th ACM Symp. on Theory of Computing, May 1993, pp. 612???622 (1993)"},{"key":"1_CR10","volume-title":"Computers and Intractability - A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"issue":"2","key":"1_CR11","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Artificial Intelligence\u00a0124(2), 243\u2013282 (2000)","journal-title":"Artificial Intelligence"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-44683-4_5","volume-title":"Mathematical Foundations of Computer Science 2001","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions: A survey. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol.\u00a02136, pp. 37\u201357. Springer, Heidelberg (2001)"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. In: Proc. 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 552\u2013561 (2003)","DOI":"10.1109\/SFCS.2003.1238228"},{"issue":"1-2","key":"1_CR14","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"1_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0004-3702(98)00022-8","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.C.: Constraints, consistency and closure. Artificial Intelligence\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"1_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"issue":"1","key":"1_CR17","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1006\/jcss.1995.1055","volume":"51","author":"P.G. Kolaitis","year":"1990","unstructured":"Kolaitis, P.G., Vardi., M.Y.: On the expressive power of Datalog: tools and a case study. Journal of Computer and System Sciences\u00a051(1), 110\u2013134 (August 1995); Special Issue: Selections from Ninth Annual ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Nashville, TN, USA (April 2-4, 1990)","journal-title":"Journal of Computer and System Sciences"},{"key":"#cr-split#-1_CR18.1","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 302???332 (2000);","DOI":"10.1006\/jcss.2000.1713"},{"key":"#cr-split#-1_CR18.2","unstructured":"Earlier version in: Proc. 17th ACM Symp. on Principles of Database Systems (PODS 1998) (1998)"},{"key":"1_CR19","unstructured":"Kolaitis, P.G., Vardi, M.Y.: A game-theoretic approach to constraint satisfaction. In: Proc. of the 17th National Conference on Artificial Intelligence (AAAI 2000), pp. 175\u2013181 (2000)"},{"key":"1_CR20","unstructured":"Kolaitis, P.G.: Constraint satisfaction, databases, and logic. In: Proc. of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003), pp. 1587\u20131595 (2003)"},{"key":"1_CR21","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.: Networks of constraints: fundamental properties and application to picture processing. Information Science\u00a07, 95\u2013132 (1974)","journal-title":"Information Science"},{"key":"1_CR22","unstructured":"Pearson, J., Jeavons, P.: A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway University of London (1997)"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th ACM Symp. on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Methods and Applications of Artificial Intelligence"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24674-9_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:51:46Z","timestamp":1605743506000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24674-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540219378","9783540246749"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24674-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}