{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:23Z","timestamp":1779174803045,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540749141","type":"print"},{"value":"9783540749158","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74915-8_18","type":"book-chapter","created":{"date-parts":[[2007,8,24]],"date-time":"2007-08-24T05:13:35Z","timestamp":1187932415000},"page":"208-222","source":"Crossref","is-referenced-by-count":57,"title":["On Acyclic Conjunctive Queries and Constant Delay Enumeration"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Bagan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Etienne","family":"Grandjean","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","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)"},{"key":"18_CR2","unstructured":"Bagan, G., Durand, A., Grandjean, E., Olive, F.: Computing the jth element of a first-order query (submitted 2007)"},{"key":"18_CR3","unstructured":"Berge, C.: Graphs and hypergraphs, 2nd edn. Amsterdam (1973)"},{"key":"18_CR4","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201321 (1993)","journal-title":"Acta Cybernetica"},{"issue":"6","key":"18_CR5","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."},{"issue":"2","key":"18_CR6","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(99)00220-0","volume":"239","author":"C. Chekuri","year":"2000","unstructured":"Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theor. Comput. Sci.\u00a0239(2), 211\u2013229 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.: Group-theoretic algorithms for matrix multiplication. In: FOCS, pp. 379\u2013388 (2005)","DOI":"10.1109\/SFCS.2005.39"},{"key":"18_CR8","unstructured":"Courcelle, B.: Linear delay enumeration and monadic second-order logic. Discrete Applied Maths (to appear, 2006)"},{"issue":"1&2","key":"18_CR9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci.\u00a0109(1&2), 49\u201382 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Durand, A., Grandjean, E.: First-order queries on structures of bounded degree are computable with constant delay. Transactions on Computational Logic (to appear)","DOI":"10.1145\/1276920.1276923"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/11874683_22","volume-title":"Computer Science Logic","author":"A. Durand","year":"2006","unstructured":"Durand, A., Olive, F.: First-order queries over one unary function. In: \u00c9sik, Z. (ed.) CSL 2006. LNCS, vol.\u00a04207, pp. 334\u2013348. Springer, Heidelberg (2006)"},{"issue":"6","key":"18_CR12","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. J. ACM\u00a049(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"issue":"1","key":"18_CR13","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/S0097539799360240","volume":"32","author":"E. Grandjean","year":"2002","unstructured":"Grandjean, E., Schwentick, T.: Machine-independent characterizations and complete problems for deterministic linear time. SIAM J. Comput.\u00a032(1), 196\u2013230 (2002)","journal-title":"SIAM J. Comput."},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In: STOC, pp. 657\u2013666 (2001)","DOI":"10.1145\/380752.380867"},{"key":"18_CR15","doi-asserted-by":"crossref","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)"},{"issue":"3","key":"18_CR16","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C.H. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci.\u00a058(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR17","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes, 82\u201394 (1981)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74915-8_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:45:46Z","timestamp":1619520346000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74915-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540749141","9783540749158"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74915-8_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}