{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:17:42Z","timestamp":1725484662469},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425540"},{"type":"electronic","value":"9783540448020"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44802-0_8","type":"book-chapter","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T04:15:38Z","timestamp":1180671338000},"page":"99-114","source":"Crossref","is-referenced-by-count":2,"title":["An Existential Locality Theorem"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[]},{"given":"Stefan","family":"W\u00f6hrle","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,30]]},"reference":[{"key":"8_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974."},{"key":"8_CR2","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proceedings of the 14th International Workshop on Graph theoretic Concepts in Computer Science WG\u201988","author":"H.L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender. NC-algorithms for graphs with small treewidth. In J. van Leeuwen, editor, Proceedings of the 14th International Workshop on Graph theoretic Concepts in Computer Science WG\u201988, volume 344 of Lecture Notes in Computer Science, pages 1\u201310. Springer-Verlag, 1988."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"8_CR4","unstructured":"R. Diestel. Graph Theory. Springer-Verlag, second edition, 2000."},{"key":"8_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/3-540-62222-5_42","volume-title":"Proceedings of the 5th International Conference on Database Theory","author":"G. Dong","year":"1997","unstructured":"G. Dong, L. Libkin, and L. Wong. Local properties of query languages. In Proceedings of the 5th International Conference on Database Theory, volume 1186 of Lecture Notes in Computer Science, pages 140\u2013154. Springer-Verlag, 1997."},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"8_CR7","unstructured":"R.G. Downey, M.R. Fellows, and U. Taylor. The parameterized complexity of relational database queries and an improved characterization of W[1]. In Bridges, Calude, Gibbons, Reeves, and Witten, editors, Combinatorics, Complexity, and Logic-Proceedings of DMTCS\u2019 96, pages 194\u2013213. Springer-Verlag, 1996."},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, second edition, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275\u2013291, 2000.","journal-title":"Algorithmica"},{"key":"8_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/3-540-44503-X_2","volume-title":"Proceedings of the 8th International Conference on Database Theory","author":"J. Flum","year":"2001","unstructured":"J. Flum, M. Frick, and M. Grohe. Query evaluation via tree-decompositions. In Jan van den Bussche and Victor Vianu, editors, Proceedings of the 8th International Conference on Database Theory, volume 1973 of Lecture Notes in Computer Science, pages 22\u201338. Springer Verlag, 2001."},{"key":"8_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48523-6_30","volume-title":"Proceedings of the 26th International Colloquium on Automata, Languages and Programming","author":"M. Frick","year":"1999","unstructured":"M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposable structures. Currently available at http:\/\/www.mat0h.uic.edu\/~grohe . A preliminary version of the paper appeared in Proceedings of the 26th International Colloquium on Automata, Languages and Programming, LNCS 1644, Springer-Verlag, 1999."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium\u2019 81. North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"8_CR13","volume-title":"Technical Report AIB-2001-07","author":"M. Grohe","year":"2001","unstructured":"M. Grohe and S. W\u00f6hrle. An existential locality theorem. Technical Report AIB-2001-07, RWTH Aachen, 2001."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"L. Hella, L. Libkin, J. Nurmonen, and L. Wong. Logics with aggregate operators. In Proceedings of the 14th IEEE Symposium on Logic in Computer Science, 1999.","DOI":"10.1109\/LICS.1999.782583"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.2307\/2586810","volume":"64","author":"L. Hella","year":"1999","unstructured":"L. Hella, L. Libkin, and Y. Nurmonen. Notions of locality and their logical characterizations over finite models. Journal of Symbolic Logic, 64:1751\u20131773, 1999.","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/343369.343376","volume":"1","author":"L. Libkin","year":"2000","unstructured":"L. Libkin. Logics with counting and local properties. ACM Transaction on Computational Logic, 1:33\u201359, 2000.","journal-title":"ACM Transaction on Computational Logic"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P.D. Seymour. Graph minors III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36:49\u201364, 1984.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"8_CR18","unstructured":"L.J. Stockmeyer. The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"P. van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 1, pages 1\u201366. Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"8_CR21","series-title":"Diploma thesis","volume-title":"Lokalit\u00e4t in der Logik und ihre algorithmischen Anwendungen","author":"S. W\u00f6hrle","year":"2000","unstructured":"S. W\u00f6hrle. Lokalit\u00e4t in der Logik und ihre algorithmischen Anwendungen. Diploma thesis, Faculty of Mathematics, Albert-Ludwigs-University Freiburg, 2000."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44802-0_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T15:21:21Z","timestamp":1556464881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44802-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425540","9783540448020"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44802-0_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}