{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:41:27Z","timestamp":1742992887768,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230243"},{"type":"electronic","value":"9783540301240"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30124-0_16","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T12:27:59Z","timestamp":1267532879000},"page":"175-189","source":"Crossref","is-referenced-by-count":2,"title":["Game-Based Notions of Locality Over Finite Models"],"prefix":"10.1007","author":[{"given":"Marcelo","family":"Arenas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo","family":"Barcel\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Libkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Arenas, M., Barcel\u00f3, P., Fagin, R., Libkin, L.: Locally consistent transformations and query answering in data exchange. In: PODS 2004, pp. 229\u2013240 (2004)","DOI":"10.1145\/1055558.1055592"},{"issue":"1","key":"16_CR2","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1006\/inco.1998.2731","volume":"147","author":"M. Benedikt","year":"1998","unstructured":"Benedikt, M., Griffin, T., Libkin, L.: Verifiable properties of database transactions. Information and Computation\u00a0147(1), 57\u201388 (1998)","journal-title":"Information and Computation"},{"issue":"2","key":"16_CR3","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/inco.1995.1084","volume":"119","author":"A. Dawar","year":"1995","unstructured":"Dawar, A., Lindell, S., Weinstein, S.: Infinitary logic and inductive definability over finite structures. Information and Computation\u00a0119(2), 160\u2013175 (1995)","journal-title":"Information and Computation"},{"key":"16_CR4","first-page":"25","volume-title":"Model-Theoretic Logics","author":"H.-D. Ebbinghaus","year":"1985","unstructured":"Ebbinghaus, H.-D.: Extended logics: the general framework. In: Model-Theoretic Logics, pp. 25\u201376. Springer, Heidelberg (1985)"},{"issue":"3","key":"16_CR5","first-page":"400","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. JCSS\u00a054(3), 400\u2013411 (1997)","journal-title":"JCSS"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Fagin, R.: Easier ways to win logical games. In: Immerman, N., Kolaitis, P. (eds.) Descriptive Complexity and Finite Models, AMS, pp. 1\u201332 (1997)","DOI":"10.1090\/dimacs\/031\/01"},{"key":"16_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-36285-1_14","volume-title":"Database Theory - ICDT 2003","author":"R. Fagin","year":"2002","unstructured":"Fagin, R., Kolaitis, P.h., Miller, R., Popa, L.: Data exchange: Semantics and query answering. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol.\u00a02572, pp. 207\u2013224. Springer, Heidelberg (2002)"},{"issue":"1","key":"16_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1994","unstructured":"Fagin, R., Stockmeyer, L., Vardi, M.: On monadic NP vs monadic co-NP. Information and Computation\u00a0120(1), 78\u201392 (1994)","journal-title":"Information and Computation"},{"issue":"1","key":"16_CR9","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 J. Comput.\u00a031(1), 113\u2013145 (2001)","journal-title":"SIAM J. Comput."},{"key":"16_CR10","volume-title":"Logic Colloquium 1981","author":"H. Gaifman","year":"1982","unstructured":"Gaifman, H.: On local and non-local properties. In: Logic Colloquium 1981. North Holland, Amsterdam (1982)"},{"issue":"1","key":"16_CR11","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/343369.343386","volume":"1","author":"M. Grohe","year":"2000","unstructured":"Grohe, M., Schwentick, T.: Locality of order-invariant first-order formulas. TOCL\u00a01(1), 112\u2013130 (2000)","journal-title":"TOCL"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-44802-0_8","volume-title":"Computer Science Logic","author":"M. Grohe","year":"2001","unstructured":"Grohe, M., W\u00f6hrle, S.: An existential locality theorem. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol.\u00a02142, pp. 99\u2013114. Springer, Heidelberg (2001)"},{"key":"16_CR13","first-page":"132","volume-title":"The Theory of Models","author":"W. Hanf","year":"1965","unstructured":"Hanf, W.: Model-theoretic methods in the study of elementary logic. In: Addison, J.W., et al. (eds.) The Theory of Models, pp. 132\u2013145. North Holland, Amsterdam (1965)"},{"issue":"1","key":"16_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L. Hella","year":"1996","unstructured":"Hella, L.: Logical hierarchies in PTIME. Information and Computation\u00a0129(1), 1\u201319 (1996)","journal-title":"Information and Computation"},{"issue":"4","key":"16_CR15","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.2307\/2586810","volume":"64","author":"L. Hella","year":"1999","unstructured":"Hella, L., Libkin, L., Nurmonen, J.: Notions of locality and their logical characterizations over finite models. J. Symbolic Logic\u00a064(4), 1751\u20131773 (1999)","journal-title":"J. Symbolic Logic"},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1145\/502090.502100","volume":"48","author":"L. Hella","year":"2001","unstructured":"Hella, L., Libkin, L., Nurmonen, J., Wong, L.: Logics with aggregate operators. JACM\u00a048(4), 880\u2013907 (2001)","journal-title":"JACM"},{"key":"16_CR17","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.: Describing graphs: A first order approach to graph canonization. In: Complexity Theory Retrospective. Springer, Berlin (1990)"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.apal.2004.01.004","volume":"128","author":"H.J. Keisler","year":"2004","unstructured":"Keisler, H.J., Lotfallah, W.: Shrinking games and local formulas. Annals of Pure and Applied Logic\u00a0128, 215\u2013225 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0168-0072(94)00025-X","volume":"74","author":"P. Kolaitis","year":"1995","unstructured":"Kolaitis, P.h., V\u00e4\u00e4n\u00e4nen, J.: Generalized quantifiers and pebble games on finite structures. Annals of Pure and Applied Logic\u00a074, 23\u201375 (1995)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/343369.343376","volume":"1","author":"L. Libkin","year":"2000","unstructured":"Libkin, L.: On counting logics and local properties. TOCL\u00a01(1), 33\u201359 (2000)","journal-title":"TOCL"},{"issue":"1","key":"16_CR21","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0304-3975(01)00152-9","volume":"288","author":"L. Libkin","year":"2002","unstructured":"Libkin, L., Wong, L.: Lower bounds for invariant queries in logics with counting. TCS\u00a0288(1), 153\u2013180 (2002)","journal-title":"TCS"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J. Makowsky","year":"2004","unstructured":"Makowsky, J.: Algorithmic aspects of the Feferman-Vaught Theorem. Annals of Pure and Applied Logic\u00a0126, 159\u2013213 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"6","key":"16_CR23","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1093\/logcom\/6.6.779","volume":"6","author":"J. Nurmonen","year":"1996","unstructured":"Nurmonen, J.: On winning strategies with unary quantifiers. Journal of Logic and Computation\u00a06(6), 779\u2013798 (1996)","journal-title":"Journal of Logic and Computation"},{"issue":"1-2","key":"16_CR24","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1006\/inco.1999.2842","volume":"160","author":"J. Nurmonen","year":"2000","unstructured":"Nurmonen, J.: Counting modulo quantifiers on finite structures. Information and Computation\u00a0160(1-2), 62\u201387 (2000)","journal-title":"Information and Computation"},{"key":"16_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/BFb0028580","volume-title":"STACS 98","author":"T. Schwentick","year":"1998","unstructured":"Schwentick, T., Barthelmann, K.: Local normal forms for first-order logic with applications to games and automata. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 444\u2013454. Springer, Heidelberg (1998)"},{"issue":"6","key":"16_CR26","doi-asserted-by":"publisher","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. Mathematical Structures in Computer Science\u00a06(6), 505\u2013526 (1996)","journal-title":"Mathematical Structures in Computer Science"},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W. Thomas","year":"1997","unstructured":"Thomas, W.: Languages, automata, and logic. In: Handbook of Formal Languages, vol.\u00a03, pp. 389\u2013455. Springer, Heidelberg (1997)"},{"issue":"3","key":"16_CR28","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1023\/A:1008209019899","volume":"6","author":"J. V\u00e4\u00e4n\u00e4nen","year":"1997","unstructured":"V\u00e4\u00e4n\u00e4nen, J.: Unary quantifiers on finite models. J. Logic, Language and Information\u00a06(3), 275\u2013304 (1997)","journal-title":"J. Logic, Language and Information"}],"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-30124-0_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,23]],"date-time":"2020-01-23T00:25:01Z","timestamp":1579739101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30124-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230243","9783540301240"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30124-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}