{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:21:53Z","timestamp":1725488513555},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_18","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T12:03:24Z","timestamp":1186056204000},"page":"217-229","source":"Crossref","is-referenced-by-count":2,"title":["Logics Capturing Local Properties"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Libkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"18_CR1","first-page":"274","volume":"41","author":"D.A.M. Barrington","year":"1990","unstructured":"D.A.M. Barrington, N. Immerman, H. Straubing. On uniformity within NC 1. JCSS, 41:274\u2013306,1990.","journal-title":"JCSS"},{"key":"18_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/3-540-62222-5_52","volume-title":"Proc. Int. Conf. on Database Theory (ICDT\u201997)","author":"M. Benedikt","year":"1997","unstructured":"M. Benedikt, H.J. Keisler. Expressive power of unary counters. Proc. Int. Conf. on Database Theory (ICDT\u201997), Springer LNCS 1186, January 1997, pages 291\u2013305."},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"J. Cai, M. F\u00fcrer and N. Immerman. On optimal lower bound on the number of variables for graph identification. Combinatorica, 12 (1992), 389\u2013410.","journal-title":"Combinatorica"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"G. Dong, L. Libkin and L. Wong. Local properties of query languages. Theoretical Computer Science, to appear. Extended abstract in ICDT\u201997, pages 140\u2013154.","DOI":"10.1007\/3-540-62222-5_42"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer Verlag, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"18_CR6","first-page":"400","volume":"54","author":"K. Etessami","year":"1997","unstructured":"K. Etessami. Counting quantifiers, successor relations, and logarithmic space, JCSS, 54 (1997), 400\u2013411.","journal-title":"JCSS"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1995","unstructured":"R. Fagin, L. Stockmeyer and M. Vardi, On monadic NP vs monadic co-NP, Information and Computation, 120 (1995), 78\u201392.","journal-title":"Information and Computation"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non-local properties, Proceedings of the Herbrand Symposium, Logic Colloquium\u2019 81, North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"E. Gr\u00e4del. On the restraining power of guards. J. Symb. Logic, to appear.","DOI":"10.2307\/2586808"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E. Gr\u00e4del","year":"1998","unstructured":"E. Gr\u00e4del and Y. Gurevich. Metafinite model theory. Information and Computation 140 (1998), 26\u201381.","journal-title":"Information and Computation"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"M. Grohe and T. Schwentick. Locality of order-invariant first-order formulas. In MFCS\u201998, pages 437\u2013445.","DOI":"10.1007\/BFb0055793"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"W. Hanf. Model-theoretic methods in the study of elementary logic. In J.W. Addison et al, eds, The Theory of Models, North Holland, 1965, pages 132\u2013145.","DOI":"10.1016\/B978-0-7204-2233-7.50020-4"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L. Hella","year":"1996","unstructured":"L. Hella. Logical hierarchies in PTIME. Information and Computation, 129 (1996), 1\u201319.","journal-title":"Information and Computation"},{"key":"18_CR14","unstructured":"L. Hella, L. Libkin and J. Nurmonen. Notions of locality and their logical characterizations over finite models. J. Symb. Logic, to appear. Extended abstract in LICS\u201997, pages 204\u2013215 (paper by the 2nd author)."},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"L. Hella, L. Libkin, J. Nurmonen and L. Wong. Logics with aggregate operators. In LICS\u201999, pages 35\u201344.","DOI":"10.1109\/LICS.1999.782583"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer Verlag, 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"18_CR17","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"N. Immerman and E. Lander. Describing graphs: A first order approach to graph canonization. In \u201cComplexity Theory Retrospective\u201d, Springer Verlag, Berlin, 1990."},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0168-0072(94)00025-X","volume":"74","author":"Ph. Kolaitis","year":"1995","unstructured":"Ph. Kolaitis and J. V\u00e4\u00e4n\u00e4nen. Generalized quantifiers and pebble games on finite structures. Annals of Pure and Applied Logic, 74 (1995), 23\u201375.","journal-title":"Annals of Pure and Applied Logic"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"L. Libkin. On counting logics and local properties. In LICS\u201998, pages 501\u2013512.","DOI":"10.1109\/LICS.1998.705683"},{"key":"18_CR20","doi-asserted-by":"crossref","unstructured":"L. Libkin. Logics capturing local properties. Bell Labs Technical Memo, 1999.","DOI":"10.1007\/3-540-46541-3_18"},{"key":"18_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/BFb0028560","volume-title":"STACS\u201998","author":"L. Libkin","year":"1998","unstructured":"L. Libkin and L. Wong. Unary quantifiers, transitive closure, and relations of large degree. In STACS\u201998, Springer LNCS 1377, pages 183\u2013193."},{"key":"18_CR22","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1093\/logcom\/6.6.779","volume":"6","author":"J. Nurmonen","year":"1996","unstructured":"J. Nurmonen. On winning strategies with unary quantifiers. J. Logic and Computation, 6 (1996), 779\u2013798.","journal-title":"J. Logic and Computation"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"M. Otto. Bounded Variable Logics and Counting: A Study in Finite Models. Springer Verlag, 1997.","DOI":"10.1007\/978-3-662-21676-7"},{"key":"18_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/BFb0028580","volume-title":"STACS\u201998","author":"T. Schwentick","year":"1998","unstructured":"T. Schwentick and K. Barthelmann. Local normal forms for first-order logic with applications to games and automata. In STACS\u201998, Springer LNCS 1377, 1998, pages 444\u2013454."},{"key":"18_CR25","unstructured":"M. Vardi. Why is monadic logic so robustly decidable? In Proc. DIMACS Workshop on Descriptive Complexity and Finite Models, AMS 1997."}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T14:10:01Z","timestamp":1556719801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}