{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:46Z","timestamp":1725488986523},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_2","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"2-12","source":"Crossref","is-referenced-by-count":6,"title":["Finite Model Theory on Tame Classes of Structures"],"prefix":"10.1007","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)"},{"key":"2_CR2","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1016\/S0022-0000(05)80071-6","volume":"49","author":"M. Ajtai","year":"1994","unstructured":"Ajtai, M., Gurevich, Y.: Datalog vs first-order logic. J.\u00a0of Computer and System Sciences\u00a049, 562\u2013588 (1994)","journal-title":"J.\u00a0of Computer and System Sciences"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1437","DOI":"10.1007\/11523468_116","volume-title":"Automata, Languages and Programming","author":"A. Atserias","year":"2005","unstructured":"Atserias, A., Dawar, A., Grohe, M.: Preservation under extensions on well-behaved finite structures. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1437\u20131449. Springer, Heidelberg (2005)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1145\/1131342.1131344","volume":"53","author":"A. Atserias","year":"2006","unstructured":"Atserias, A., Dawar, A., Kolaitis, P.G.: On preservation under homomorphisms and unions of conjunctive queries. Journal of the ACM\u00a053, 208\u2013237 (2006)","journal-title":"Journal of the ACM"},{"key":"2_CR5","first-page":"171","volume-title":"Proc.\u00a0of the 15th ACM Symp.\u00a0on the Theory of Computing","author":"L. Babai","year":"1983","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proc.\u00a0of the 15th ACM Symp.\u00a0on the Theory of Computing, pp. 171\u2013183. ACM Press, New York (1983)"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/11538363_20","volume-title":"Computer Science Logic","author":"M. Benedikt","year":"2005","unstructured":"Benedikt, M., Segoufin, L.: Towards a characterization of order-invariant queries over tame structures. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, pp. 276\u2013291. Springer, Heidelberg (2005)"},{"key":"2_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1997)"},{"issue":"4","key":"2_CR8","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J.-Y. Cai","year":"1992","unstructured":"Cai, J-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"2_CR9","first-page":"187","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"Courcelle, B.: The monadic second-order logic of graphs ii: Infinite graphs of bounded width. Theory of Computing Systems\u00a021, 187\u2013221 (1989)","journal-title":"Theory of Computing Systems"},{"key":"2_CR10","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Formal Models and Sematics (B)","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: An algebraic and logic approach. In: van Leeuwan, J. (ed.) Handbook of Theoretical Computer Science, Formal Models and Sematics (B), vol.\u00a0B, pp. 193\u2013242. Elsevier, Amsterdam (1990)"},{"doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proc. 22nd IEEE Symp. on Logic in Computer Science (2007)","key":"2_CR11","DOI":"10.1109\/LICS.2007.31"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"ICALP 2007: Proc. 34th International Colloquium on Automata, Languages and Programming","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N.: Model theory makes formulas large. In: ICALP 2007: Proc. 34th International Colloquium on Automata, Languages and Programming. LNCS, Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Dawar, A., Kreutzer, S., Grohe, M., Schweikardt, N.: Approximation schemes for first-order definable optimisation problems. In: Proc. 21st IEEE Symp. on Logic in Computer Science, pp. 411\u2013420 (2006)","key":"2_CR13","DOI":"10.1109\/LICS.2006.13"},{"unstructured":"Dawar, A., Malod, G.: forthcoming","key":"2_CR14"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","volume-title":"CSL 2007: Computer Science Logic","author":"A. Dawar","year":"2007","unstructured":"Dawar, A., Richerby, D.: The power of counting logics on restricted classes of finite structures. In: CSL 2007: Computer Science Logic. LNCS, Springer, Heidelberg (2007)"},{"key":"2_CR16","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"unstructured":"Ebbinghaus, H-D., Flum, J.: Finite Model Theory. 2nd edn., Springer, Heidelberg (1999)","key":"2_CR17"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica\u00a027, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation, SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373 (1974)","key":"2_CR19"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J. Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model checking. SIAM Journal on Computing\u00a031, 113\u2013145 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M. Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM\u00a048, 1184\u20131206 (2001)","journal-title":"Journal of the ACM"},{"key":"2_CR22","first-page":"105","volume-title":"Proceedings of the Herbrand Symposium Logic Colloquium 1981","author":"H. Gaifman","year":"1982","unstructured":"Gaifman, H.: On local and non-local properties. In: Stern, J. (ed.) Proceedings of the Herbrand Symposium Logic Colloquium 1981, pp. 105\u2013135. North-Holland, Amsterdam (1982)"},{"key":"2_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68804-8_3","volume-title":"Finite Model Theory and Its Applications","author":"E. Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Libkin, L., Marx, M., Spencer, J., Vardi, M.Y., Venema, Y., Weinstein, S.: Finite Model Theory and Its Applications. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-point logics on planar graphs. In: Proc. 13th IEEE Annual Symp. Logic in Computer Science, pp. 6\u201315 (1998)","key":"2_CR24","DOI":"10.1109\/LICS.1998.705639"},{"doi-asserted-by":"crossref","unstructured":"Grohe, M.: Isomorphism testing for embeddable graphs through definability. In: Proc. 32nd ACM Symp. Theory of Computing, pp. 63\u201372 (2000)","key":"2_CR25","DOI":"10.1145\/335305.335313"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","volume-title":"Database Theory - ICDT\u201999","author":"M. Grohe","year":"1998","unstructured":"Grohe, M., Mari\u00f1o, J.: Definability and descriptive complexity on databases of bounded tree-width. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, Springer, Heidelberg (1998)"},{"key":"2_CR27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W. Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Information and Control\u00a068, 86\u2013104 (1986)","journal-title":"Information and Control"},{"key":"2_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, Heidelberg (1999)"},{"key":"2_CR30","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.S.: Describing graphs: A first-order approach to graph canonization. In: Selman, A. (ed.) Complexity Theory Retrospective, Springer, Heidelberg (1990)"},{"unstructured":"Kolatis, P.G.: A tutorial on finite model theory. In: Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, LICS 1993, pp. 122\u2013122 (1993)","key":"2_CR31"},{"key":"2_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/10703163_9","volume-title":"Computer Science Logic","author":"M. Kreidler","year":"1999","unstructured":"Kreidler, M., Seese, D.: Monadic NP and graph minors. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) Computer Science Logic. LNCS, vol.\u00a01584, pp. 126\u2013141. Springer, Heidelberg (1999)"},{"key":"2_CR33","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":"1","key":"2_CR34","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0304-3975(91)90048-7","volume":"85","author":"S. Lindell","year":"1991","unstructured":"Lindell, S.: An analysis of fixed-point queries on binary trees. Theoretical Computer Science\u00a085(1), 75\u201395 (1991)","journal-title":"Theoretical Computer Science"},{"key":"2_CR35","first-page":"27","volume":"4","author":"A. Livchak","year":"1983","unstructured":"Livchak, A.: The relational model for process control. Automated Documentation and Mathematical Linguistics\u00a04, 27\u201329 (1983)","journal-title":"Automated Documentation and Mathematical Linguistics"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"E.M. Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences\u00a025, 42\u201365 (1982)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press (2001)","key":"2_CR37","DOI":"10.56021\/9780801866890"},{"doi-asserted-by":"crossref","unstructured":"Rossman, B.: Existential positive types and preservation under homomorphisisms. In: 20th IEEE Symposium on Logic in Computer Science, pp. 467\u2013476 (2005)","key":"2_CR38","DOI":"10.1109\/LICS.2005.16"},{"key":"2_CR39","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D. Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math. Struct. in Comp. Science\u00a06, 505\u2013526 (1996)","journal-title":"Math. Struct. in Comp. Science"},{"doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: The grad of a graph and classes with bounded expansion. International Colloquium on Graph Theory, 101\u2013106 (2005)","key":"2_CR40","DOI":"10.1016\/j.endm.2005.06.018"},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"15","DOI":"10.2307\/2964569","volume":"24","author":"W.W. Tait","year":"1959","unstructured":"Tait, W.W.: A counterexample to a conjecture of Scott and Suppes. Journal of Symbolic Logic\u00a024, 15\u201316 (1959)","journal-title":"Journal of Symbolic Logic"},{"doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proc.\u00a0of the 14th ACM Symp.\u00a0on the Theory of Computing, pp. 137\u2013146 (1982)","key":"2_CR42","DOI":"10.1145\/800070.802186"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T19:41:49Z","timestamp":1684006909000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}