{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:15:47Z","timestamp":1778807747311,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,12,2]],"date-time":"2009-12-02T00:00:00Z","timestamp":1259712000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s00224-009-9248-9","type":"journal-article","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T16:18:54Z","timestamp":1259684334000},"page":"444-464","source":"Crossref","is-referenced-by-count":24,"title":["Tractable Structures for Constraint Satisfaction with\u00a0Truth Tables"],"prefix":"10.1007","volume":"48","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,2]]},"reference":[{"key":"9248_CR1","unstructured":"Adler, I.: Width functions for hypertree decompositions. PhD thesis, Albert-Ludwigs-Universit\u00e4t Freiburg (2006)"},{"key":"9248_CR2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/LICS.2003.1210072","volume-title":"18th Annual IEEE Symposium on Logic in Computer Science (LICS\u201903)","author":"A.A. Bulatov","year":"2003","unstructured":"Bulatov, A.A.: Tractable conservative constraint satisfaction problems. In: 18th Annual IEEE Symposium on Logic in Computer Science (LICS\u201903), p.\u00a0321. IEEE Computer Society, Los Alamitos (2003)"},{"issue":"1","key":"9248_CR3","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/1120582.1120584","volume":"53","author":"A.A. Bulatov","year":"2006","unstructured":"Bulatov, A.A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM 53(1), 66\u2013120 (2006)","journal-title":"J. ACM"},{"key":"9248_CR4","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A., Krokhin, A.A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 667\u2013674 (2001)","DOI":"10.1145\/380752.380868"},{"key":"9248_CR5","unstructured":"Chen, H., Grohe, M.: Constraint satisfaction problems with succinctly specified relations. (2006). Manuscript. Preliminary version in Dagstuhl Seminar Proceedings 06401: Complexity of Constraints"},{"key":"9248_CR6","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"1","key":"9248_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","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. Comput. 28(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"9248_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"9248_CR9","unstructured":"Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proc. of AAAI-90, pp.\u00a04\u20139, Boston, MA (1990)"},{"key":"9248_CR10","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 579\u2013627 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"9248_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0004-3702(02)00182-0","volume":"138","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Scarcello, F., Sideri, M.: Fixed-parameter complexity in AI and nonmonotonic reasoning. Artif. Intell. 138(1\u20132), 55\u201386 (2002)","journal-title":"Artif. Intell."},{"key":"9248_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The structure of tractable constraint satisfaction problems. In: MFCS 2006, pp.\u00a058\u201372 (2006)","DOI":"10.1007\/11821069_5"},{"issue":"1","key":"9248_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M. Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1 (2007)","journal-title":"J. ACM"},{"key":"9248_CR14","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/1109557.1109590","volume-title":"SODA\u201906: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. Grohe","year":"2006","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: SODA\u201906: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 289\u2013298. ACM, New York (2006)"},{"key":"9248_CR15","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1145\/380752.380867","volume-title":"STOC\u201901: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing","author":"M. Grohe","year":"2001","unstructured":"Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In: STOC\u201901: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 657\u2013666. ACM, New York (2001)"},{"issue":"4","key":"9248_CR16","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9248_CR17","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D.A., Gyssens, M.: Closure properties of constraints. J. ACM 44(4), 527\u2013548 (1997)","journal-title":"J. ACM"},{"issue":"2","key":"9248_CR18","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"2000","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302\u2013332 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9248_CR19","doi-asserted-by":"crossref","unstructured":"Marx, D.: Can you beat treewidth? In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907), pp.\u00a0169\u2013179 (2007)","DOI":"10.1109\/FOCS.2007.27"},{"key":"9248_CR20","doi-asserted-by":"crossref","unstructured":"Marx, D.: Approximating fractional hypertree width. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909) (2009)","DOI":"10.1137\/1.9781611973068.98"},{"key":"9248_CR21","doi-asserted-by":"crossref","unstructured":"Scarcello, F., Gottlob, G., Greco, G.: Uniform constraint satisfaction problems and database theory. In: Complexity of Constraints, pp.\u00a0156\u2013195 (2008)","DOI":"10.1007\/978-3-540-92800-3_7"},{"key":"9248_CR22","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1145\/800133.804350","volume-title":"Conference Record of the Tenth Annual ACM Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, San Diego, CA, 1978, pp. 216\u2013226. ACM, New York (1978)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9248-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9248-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9248-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:38Z","timestamp":1558698698000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9248-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,2]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9248"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9248-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,2]]}}}