{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:28:02Z","timestamp":1779334082842,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,23]],"date-time":"2014-05-23T00:00:00Z","timestamp":1400803200000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00224-014-9543-y","type":"journal-article","created":{"date-parts":[[2014,5,22]],"date-time":"2014-05-22T02:34:39Z","timestamp":1400726079000},"page":"1202-1249","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Structural Tractability of Counting of Solutions to Conjunctive Queries"],"prefix":"10.1007","volume":"57","author":[{"given":"Arnaud","family":"Durand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,23]]},"reference":[{"key":"9543_CR1","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)"},{"issue":"8","key":"9543_CR2","doi-asserted-by":"crossref","first-page":"2167","DOI":"10.1016\/j.ejc.2007.04.013","volume":"28","author":"I Adler","year":"2007","unstructured":"Adler, I., Gottlob, G., Grohe, G.: Hypertree width and related hypergraph invariants. Eur. J. Comb. 28(8), 2167\u20132181 (2007)","journal-title":"Eur. J. Comb."},{"key":"9543_CR3","doi-asserted-by":"crossref","unstructured":"Bagan, G., Durand, A., Grandjean, G.: On acyclic conjunctive queries and constant delay enumeration. In: CSL\u201907, 16th Annual Conference of the EACSL, LNCS, vol. 4646, pp 208\u2013222. Springer (2007)","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"9543_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp 226\u2013234. ACM (1993)","DOI":"10.1145\/167088.167161"},{"issue":"1-2","key":"9543_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1-2), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9543_CR6","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1016\/j.jcss.2011.09.006","volume":"78","author":"A Bulatov","year":"2012","unstructured":"Bulatov, A., Dalmau, V., Grohe, M., Marx, D.: Enumerating homomorphisms. J. Comput. Syst. Sci. 78(2), 638\u2013650 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9543_CR7","unstructured":"Chen, H.: On the Complexity of Existential Positive Queries. ArXiv e-prints (2012)"},{"key":"9543_CR8","doi-asserted-by":"crossref","unstructured":"Chen, H., Dalmau, V.: Beyond hypertree width: decomposition methods without decompositions. In: 11th international conference principles and practice of constraint programming, CP \u201905, pp 167\u2013181 (2005)","DOI":"10.1007\/11564751_15"},{"key":"9543_CR9","doi-asserted-by":"crossref","unstructured":"Chen, H., Dalmau, V.: Decomposing quantified conjunctive (or disjunctive) formulas. LICS (2012)","DOI":"10.1109\/LICS.2012.31"},{"issue":"5","key":"9543_CR10","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.jcss.2007.08.001","volume":"74","author":"D Cohen","year":"2008","unstructured":"Cohen, D., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction problems. J. Comput. Syst. Sci. 74(5), 721\u2013743 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9543_CR11","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Graph Rewriting: An Algebraic and Logic Approach. In: Handbook of theoretical computer science, volume B: Formal models and sematics (B), pp. 193\u2013242 (1990)","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"issue":"1-3","key":"9543_CR12","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.tcs.2004.08.008","volume":"329","author":"V Dalmau","year":"2004","unstructured":"Dalmau, V., Jonsson, P.: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1-3), 315\u2013323 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9543_CR13","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory. 2005. Grad. Texts in Math (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"9543_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity, Vol. 3. Springer, New York (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9543_CR15","unstructured":"Durand, A., Mengel, S.: The Complexity of Weighted Counting for Acyclic Conjunctive Queries. Arxiv preprint arXiv: 1110.4201 (2011)"},{"issue":"6","key":"9543_CR16","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"key":"9543_CR17","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag, New York Inc (2006)"},{"issue":"2","key":"9543_CR18","doi-asserted-by":"crossref","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. Artif. Intell. 124(2), 243\u2013282 (2000)","journal-title":"Artif. Intell."},{"issue":"3","key":"9543_CR19","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(3), 579\u2013627 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9543_CR20","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Mikl\u00f3s, Z., Schwentick, T.: Generalized Hypertree Decompositions: NP-hardness and tractable variants. J. ACM 56(6) (2009)","DOI":"10.1145\/1568318.1568320"},{"key":"9543_CR21","doi-asserted-by":"crossref","unstructured":"Greco, G., Scarcello, F.: Structural Tractability of Enumerating CSP Solutions. In: Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming, CP \u201910, pp 236\u2013251 (2010)","DOI":"10.1007\/978-3-642-15396-9_21"},{"key":"9543_CR22","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1) (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"9543_CR23","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint Solving via Fractional Edge Covers. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp 289\u2013298. ACM, New York (2006)","DOI":"10.1145\/1109557.1109590"},{"key":"9543_CR24","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable?In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 657\u2013666. ACM (2001)","DOI":"10.1145\/380752.380867"},{"issue":"1","key":"9543_CR25","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.A.: Decomposing constraint satisfaction problems using database techniques. Artif. Intell. 66(1), 57\u201389 (1994)","journal-title":"Artif. Intell."},{"issue":"2","key":"9543_CR26","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"PG 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":"9543_CR27","doi-asserted-by":"crossref","unstructured":"Libkin, L.: Elements of Finite Model Theory, EATCS Series. Springer (2004)","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"2","key":"9543_CR28","first-page":"29:1","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Approximating fractional hypertree width. ACM Trans. Algoritm. 6(2), 29:1\u201329:17 (2010)","journal-title":"ACM Trans. Algoritm."},{"key":"9543_CR29","unstructured":"Mengel, S.: Conjunctive Queries, Arithmetic Circuits and Counting Complexity. Ph.D. Thesis, University of Paderborn (2013)"},{"key":"9543_CR30","unstructured":"Mikl\u00f3s, Z.: Understanding Tractable Decompositions for Constraint Satisfaction. Ph.D. Thesis, University of Oxford (2008)"},{"key":"9543_CR31","unstructured":"Pichler, R., Skritek, A.: Tractable Counting of the Answers to Conjunctive Queries. AMW (2011)"},{"key":"9543_CR32","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.: Graph minors II: algorithmic aspects of tree-width. J. Algoritm. 7(3) (1986)","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"9543_CR33","unstructured":"Yannakakis, M.: Algorithms for Acyclic Database Schemes, pp 82\u201394. VLDB (1981)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9543-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9543-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9543-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T14:42:02Z","timestamp":1565448122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9543-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,23]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9543"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9543-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,23]]}}}