{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:29:47Z","timestamp":1736486987120,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540372066"},{"type":"electronic","value":"9783540372073"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11814948_23","type":"book-chapter","created":{"date-parts":[[2006,7,18]],"date-time":"2006-07-18T10:12:38Z","timestamp":1153217558000},"page":"226-239","source":"Crossref","is-referenced-by-count":1,"title":["A Dichotomy Theorem for Typed Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Su","family":"Chen","sequence":"first","affiliation":[]},{"given":"Tomasz","family":"Imielinski","sequence":"additional","affiliation":[]},{"given":"Karin","family":"Johnsgard","sequence":"additional","affiliation":[]},{"given":"Donald","family":"Smith","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","volume-title":"Hypergraphs: Combinatorics of Finite Sets","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs: Combinatorics of Finite Sets. North-Holland, Amsterdam (1989)"},{"key":"23_CR2","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. ACM Transactions on Computational Logic (submitted)"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings of 43rd Annual IEEE Symposium of Foundation of Computer Science (FOCS 2002), pp. 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: Proceedings of 18th IEEE Symposium on Logic in Computer Science (LICS 2003), pp. 321\u2013330 (2003)","DOI":"10.1109\/LICS.2003.1210072"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-540-45193-8_13","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"A.A. Bulatov","year":"2003","unstructured":"Bulatov, A.A., Jeavons, P.: An algebraic approach to multi-sorted constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 183\u2013198. Springer, Heidelberg (2003)"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A.A. Bulatov","year":"2000","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"23_CR7","unstructured":"Cohen, D., Jeavons, P.: Handbook of Constraint Programming. In: The complexity of constraint languages, ch.6 Elsevier (to appear, 2006)"},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1006\/jcss.1995.1087","volume":"51","author":"N. Creignou","year":"1995","unstructured":"Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. J. Comput. Syst. Sci.\u00a051(3), 511\u2013522 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR9","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a07. SIAM, Philadelphia (2001)"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/978-3-540-45138-9_30","volume-title":"Mathematical Foundations of Computer Science 2003","author":"V. Dalmau","year":"2003","unstructured":"Dalmau, V., Ford, D.K.: Generalized satisfiability with limited occurrences per variable: A study through delta-matroid parity. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 358\u2013367. Springer, Heidelberg (2003)"},{"issue":"1-2","key":"23_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0304-3975(99)00288-1","volume":"255","author":"T. Feder","year":"2001","unstructured":"Feder, T.: Fanout limitations on constraint systems. Theor. Comput. Sci.\u00a0255(1-2), 281\u2013293 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR12","unstructured":"Feder, T., Ford, D.: Classification of bipartite boolean constraint satisfaction through delta-matroid intersection. Electronic Colloquium on Computational Complexity (ECCC), TR05(016) (2005) (to appear in SIAM J. Discrete Math)"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing\u00a028, 57\u2013104 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR14","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)"},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and onstraint satisfaction problems seen from the other side. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 552\u2013561 (2003)","DOI":"10.1109\/SFCS.2003.1238228"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Comb. Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"J. Comb. Theory, Series B"},{"key":"23_CR17","unstructured":"Istrate, G.: Looking for a version of Schaefer\u2019s dichotomy theorem when each variable occurs at most twice. Technical Report TR 652, U. Rochester, CS Dept. (1997)"},{"issue":"1\u20132","key":"23_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theor. Comput. Sci.\u00a0200(1\u20132), 185\u2013204 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"23_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. ACM\u00a022(1), 155\u2013171 (1975)","journal-title":"J. ACM"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"23_CR21","volume-title":"Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: Complexity of Boolean Functions. John Wiley and Sons, Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11814948_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T23:23:26Z","timestamp":1736465006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11814948_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540372066","9783540372073"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11814948_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}