{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:32:00Z","timestamp":1762101120970},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642175107"},{"type":"electronic","value":"9783642175114"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17511-4_22","type":"book-chapter","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T06:24:40Z","timestamp":1291703080000},"page":"387-404","source":"Crossref","is-referenced-by-count":7,"title":["Counting and Enumeration Problems with Bounded Treewidth"],"prefix":"10.1007","author":[{"given":"Reinhard","family":"Pichler","sequence":"first","affiliation":[]},{"given":"Stefan","family":"R\u00fcmmele","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Woltran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-540-30570-5_26","volume-title":"Database Theory - ICDT 2005","author":"F.N. Afrati","year":"2004","unstructured":"Afrati, F.N., Chirkova, R.: Selecting and using views to compute aggregate queries. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol.\u00a03363, pp. 383\u2013397. Springer, Heidelberg (2004)"},{"issue":"2","key":"22_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012(2), 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/11874683_11","volume-title":"Computer Science Logic","author":"G. Bagan","year":"2006","unstructured":"Bagan, G.: MSO queries on tree decomposable structures are computable with linear delay. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 167\u2013181. Springer, Heidelberg (2006)"},{"issue":"6","key":"22_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"22_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83952-8","volume-title":"Logic Programming and Databases","author":"S. Ceri","year":"1990","unstructured":"Ceri, S., Gottlob, G., Tanca, L.: Logic Programming and Databases. Springer, Heidelberg (1990)"},{"key":"22_CR6","first-page":"155","volume-title":"Proc. PODS 1999","author":"S. Cohen","year":"1999","unstructured":"Cohen, S., Nutt, W., Serebrenik, A.: Rewriting aggregate queries using views. In: Proc. PODS 1999, pp. 155\u2013166. ACM, New York (1999)"},{"key":"22_CR7","first-page":"193","volume-title":"Handbook of Theoretical Computer Science","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: Handbook of Theoretical Computer Science, vol.\u00a0B, pp. 193\u2013242. Elsevier Science Publishers, Amsterdam (1990)"},{"issue":"12","key":"22_CR8","doi-asserted-by":"publisher","first-page":"2675","DOI":"10.1016\/j.dam.2008.08.021","volume":"157","author":"B. Courcelle","year":"2009","unstructured":"Courcelle, B.: Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics\u00a0157(12), 2675\u20132700 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR9","doi-asserted-by":"publisher","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. Springer, New York (1999)"},{"issue":"2-4","key":"22_CR10","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10472-008-9086-5","volume":"51","author":"T. Eiter","year":"2007","unstructured":"Eiter, T., Faber, W., Fink, M., Woltran, S.: Complexity results for answer set programming with bounded predicate arities and implications. Annals of Mathematics and Artificial Intelligence\u00a051(2-4), 123\u2013165 (2007)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"6","key":"22_CR11","doi-asserted-by":"publisher","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. Journal of the ACM\u00a049(6), 716\u2013752 (2002)","journal-title":"Journal of the ACM"},{"key":"22_CR12","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. In: Proc. LICS 2002, pp. 215\u2013224 (2002)","DOI":"10.1109\/LICS.2002.1029830"},{"key":"22_CR14","first-page":"165","volume-title":"Proc. PODS 2007","author":"G. Gottlob","year":"2007","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures with bounded treewidth. In: Proc. PODS 2007, pp. 165\u2013174. ACM, New York (2007)"},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/3-540-48168-0_3","volume-title":"Computer Science Logic","author":"M. Grohe","year":"1999","unstructured":"Grohe, M.: Descriptive and parameterized complexity. In: Flum, J., Rodr\u00edguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol.\u00a01683, pp. 14\u201331. Springer, Heidelberg (1999)"},{"issue":"8","key":"22_CR16","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s00236-004-0101-y","volume":"40","author":"S. Grumbach","year":"2004","unstructured":"Grumbach, S., Rafanelli, M., Tininini, L.: On the equivalence and rewriting of aggregate queries. Acta Inf.\u00a040(8), 529\u2013584 (2004)","journal-title":"Acta Inf."},{"key":"22_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-540-89439-1_31","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"M. Jakl","year":"2008","unstructured":"Jakl, M., Pichler, R., R\u00fcmmele, S., Woltran, S.: Fast counting with bounded treewidth. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol.\u00a05330, pp. 436\u2013450. Springer, Heidelberg (2008)"},{"key":"22_CR18","unstructured":"Kemp, D.B., Stuckey, P.J.: Semantics of logic programs with aggregates. In: Proc. ISLP, pp. 387\u2013401 (1991)"},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"3","key":"22_CR20","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1145\/322326.322332","volume":"29","author":"A.C. Klug","year":"1982","unstructured":"Klug, A.C.: Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM\u00a029(3), 699\u2013717 (1982)","journal-title":"J. ACM"},{"key":"22_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004)"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-540-85238-4_49","volume-title":"Mathematical Foundations of Computer Science 2008","author":"S. Szeider","year":"2008","unstructured":"Szeider, S.: Monadic second order logic on graphs with local cardinality constraints. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 601\u2013612. Springer, Heidelberg (2008)"},{"key":"22_CR23","first-page":"137","volume-title":"Proc. STOC 1982","author":"M.Y. Vardi","year":"1982","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proc. STOC 1982, pp. 137\u2013146. ACM, New York (1982)"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming, Artificial Intelligence, and Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17511-4_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T17:40:58Z","timestamp":1553276458000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17511-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175107","9783642175114"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17511-4_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}