{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T01:33:06Z","timestamp":1674091986492},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2002,11]]},"abstract":"A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the article, we consider arbitrary formulas on tree-like structures. We generalize a theorem of Courcelle [1990] by showing that on structures of bounded tree-width a monadic second-order formula (with free first- and second-order variables) can be evaluated in time linear in the structure size plus the size of the output.In the second part, we study tree-like formulas on arbitrary structures. We generalize the notions of acyclicity and bounded tree-width from conjunctive queries to arbitrary first-order formulas in a straightforward way and analyze the complexity of evaluating formulas of these fragments. Moreover, we show that the acyclic and bounded tree-width fragments have the same expressive power as the well-known guarded fragment and the finite-variable fragments of first-order logic, respectively.<\/jats:p>","DOI":"10.1145\/602220.602222","type":"journal-article","created":{"date-parts":[[2003,1,10]],"date-time":"2003-01-10T14:31:05Z","timestamp":1042209065000},"page":"716-752","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":132,"title":["Query evaluation via tree-decompositions"],"prefix":"10.1145","volume":"49","author":[{"given":"J\u00f6rg","family":"Flum","sequence":"first","affiliation":[{"name":"Albert-Ludwigs-Universit\u00e4t Freiburg, Freiburg, Germany"}]},{"given":"Markus","family":"Frick","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, Scotland, UK"}]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, Scotland, UK"}]}],"member":"320","published-online":{"date-parts":[[2002,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading Mass. Abiteboul S. Hull R. and Vianu V. 1995. Foundations of Databases. Addison-Wesley Reading Mass."},{"key":"e_1_2_1_2_1","unstructured":"Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading Mass. Aho A. V. Hopcroft J. E. and Ullman J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading Mass."},{"key":"e_1_2_1_3_1","unstructured":"Andr\u00e9ka H. van Benthem J. and N\u00e9meti I. 1996. Modal languages and bounded fragments of first-order logic. ILLC Research Report ML-96-03 University of Amsterdam. Andr\u00e9ka H. van Benthem J. and N\u00e9meti I. 1996. Modal languages and bounded fragments of first-order logic. ILLC Research Report ML-96-03 University of Amsterdam."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_7_1","first-page":"56","volume-title":"Proceedings of the 5th International Conference on Database Theory. Ph. Kolaitis and F. Afrati, Eds. Lecture Notes in Computer Science","volume":"1186","author":"Chekuri Ch."},{"key":"e_1_2_1_8_1","first-page":"194","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90019-1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90064-Z"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_12_1","unstructured":"Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory. 2nd ed. Springer-Verlag New York. Ebbinghaus H.-D. and Flum J. 1999. Finite Model Theory. 2nd ed. Springer-Verlag New York."},{"key":"e_1_2_1_13_1","first-page":"612","volume-title":"Proceedings of the 25th ACM Symposium on Theory of Computing. ACM","author":"Feder T."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 17th IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos Calif., 215--224","author":"Frick M."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/504077.504079"},{"key":"e_1_2_1_17_1","first-page":"706","volume-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos Calif.","author":"Gottlob G."},{"key":"e_1_2_1_18_1","first-page":"21","volume-title":"Proceedings of the 18th ACM Symposium on Principles of Database Systems. ACM","author":"Gottlob G."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 20th ACM Symposium on Principles of Database Systems. ACM","author":"Gottlob G."},{"key":"e_1_2_1_20_1","first-page":"657","volume-title":"Proceedings of the 33rd ACM Symposium on Theory of Computing. ACM","author":"Grohe M."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Immerman N. 1999. Descriptive Complexity. Springer-Verlag New York. Immerman N. 1999. Descriptive Complexity. Springer-Verlag New York.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_22_1","first-page":"205","volume-title":"Proceedings of the 17th ACM Symposium on Principles of Database Systems. ACM","author":"Kolaitis Ph. G."},{"key":"e_1_2_1_23_1","volume-title":"Handbook of Logic in Computer Science","author":"Makowsky J."},{"key":"e_1_2_1_24_1","unstructured":"Moret B. and Shapiro H. 1990. Algorithms from P to NP. Benjamin\/Cummings. Moret B. and Shapiro H. 1990. Algorithms from P to NP. Benjamin\/Cummings."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","article-title":"Generalised finite automata theory with an application to a decision problem of second-order logic","volume":"2","author":"Thatcher J. W.","year":"1968","journal-title":"Math. Syst. Theory"},{"key":"e_1_2_1_28_1","first-page":"1","volume-title":"Handbook of Theoretical Computer Science","author":"van Emde Boas P."},{"key":"e_1_2_1_29_1","first-page":"137","volume-title":"Proceedings of the 14th ACM Symposium on Theory of Computing. ACM","author":"Vardi M. Y.","year":"1982"},{"key":"e_1_2_1_30_1","first-page":"266","volume-title":"Proceedings of the 14th ACM Symposium on Principles of Database Systems. ACM","author":"Vardi M. Y.","year":"1995"},{"key":"e_1_2_1_31_1","first-page":"82","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases.","author":"Yannakakis M.","year":"1981"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/602220.602222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T19:03:59Z","timestamp":1672686239000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/602220.602222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["10.1145\/602220.602222"],"URL":"http:\/\/dx.doi.org\/10.1145\/602220.602222","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2002,11]]},"assertion":[{"value":"2002-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}