{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:08Z","timestamp":1725663728505},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540566106"},{"type":"electronic","value":"9783540475989"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56610-4_89","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:22:02Z","timestamp":1330255322000},"page":"559-568","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["On the Ehrenfeucht-Fra\u00efss\u00e9 game in theoretical computer science"],"prefix":"10.1007","author":[{"given":"Wolfgang","family":"Thomas","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"volume-title":"Model-Theoretic Logics","year":"1985","key":"38_CR1","unstructured":"J. Barwise, S. Feferman (eds.), Model-Theoretic Logics, Springer-Verlag, Berin-Heidelberg, New York 1985."},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"U. Bosse, An \u201cEhrenfeucht-Fra\u00efss\u00e9 game\u201d for fixpoint logic and stratified fixpoint logic, manuscript, Math. Inst., Universit\u00e4t Freiburg, 1992.","DOI":"10.1007\/3-540-56992-8_8"},{"key":"38_CR3","volume-title":"Mathematical Logic","author":"H. D. Ebbinghaus","year":"1984","unstructured":"H.D. Ebbinghaus, J. Flum, W. Thomas, Mathematical Logic, Springer-Verlag, New York 1984 (revised and extended edition to appear 1993)."},{"key":"38_CR4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1961), 129\u2013141.","journal-title":"Fund. Math."},{"key":"38_CR5","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin, Monadic generalized spectra, Z. math. Logik u. Grundl. Math. 21 (1975), 123\u2013134.","journal-title":"Z. math. Logik u. Grundl. Math."},{"key":"38_CR6","unstructured":"R. Fagin, L. Stockmeyer, M.Y. Vardi, A simple proof that connectivity separates existential and universal monadic second-order logic over finite structures, IBM Rep. RJ 8647, 1992."},{"key":"38_CR7","first-page":"248","volume":"499","author":"J. Flum","year":"1975","unstructured":"J. Flum, First-order logic and its extensions, in: Proc. ISILC Logic Conf, Kiel, Springer Lect. Notes in Math. 499 (1975), 248\u2013310.","journal-title":"Proc. ISILC Logic Conf, Kiel, Springer Lect. Notes in Math."},{"key":"38_CR8","unstructured":"J. Flum, On bounded theories, in: Computer Science Logic (E. B\u00f6rger et al., eds.), Springer LNCS 626 (1992), 111\u2013118."},{"key":"38_CR9","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9, Sur quelques classifications des relations, bas\u00e9s sur des isomorphismes restreints, Publ. Sci. de l'Univ. Alger, S\u00e9r. A 1 (1954), 35\u2013182.","journal-title":"Publ. Sci. de l'Univ. Alger, S\u00e9r. A"},{"key":"38_CR10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0049-237X(08)71879-2","volume-title":"Proc. of the Herbrand Symposium, Logic Colloquium '81","author":"H. Gaifman","year":"1982","unstructured":"H. Gaifman, On local and non-local properties, in: Proc. of the Herbrand Symposium, Logic Colloquium '81 (J. Stern, ed.), North-Holland, Amsterdam 1982, pp. 105\u2013135."},{"key":"38_CR11","unstructured":"E. Gr\u00e4del, On transitive closure logic, in: Computer Science Logic (E. B\u00f6rger et al., eds.), Springer LNCS 626 (1992), 149\u2013165."},{"key":"38_CR12","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.2307\/2273673","volume":"48","author":"Y. Gurevich","year":"1983","unstructured":"Y. Gurevich, S. Shelah, Rabin's uniformization problem, J. Symb. Logic 48 (1983), 1105\u20131119.","journal-title":"J. Symb. Logic"},{"key":"38_CR13","first-page":"132","volume-title":"The Theory of Models","author":"W. P. Hanf","year":"1965","unstructured":"W.P. Hanf, Model-theoretic methods in the study of elementary logic, in: The Theory of Models (J.W. Addison, L. Henkin, A. Tarski, eds.), North-Holland, Amsterdam 1965, pp. 132\u2013145."},{"key":"38_CR14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/2455.2460","volume":"21","author":"M. Hennessy","year":"1985","unstructured":"M. Hennessy, R. Milner, Algebraic laws for nondeterminism and concurrency, J. Assoc. Comput. Mach. 21 (1985), 137\u2013161.","journal-title":"J. Assoc. Comput. Mach."},{"key":"38_CR15","unstructured":"J. Hintikka, Distributive normal forms in the calculus of predicates, Acta Philos. Fennica 6 (1953)."},{"key":"38_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/0022-0000(82)90011-3","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman, Upper and lower bounds for first-order expressibility, J. Comput. System Sci. 25 (1982), 76\u201398.","journal-title":"J. Comput. System Sci."},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0890-5401(89)90055-2","volume":"83","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, D. Kozen, Definability with a bounded number of bound variables, Inform. Comput. 83 (1989), 121\u2013139.","journal-title":"Inform. Comput."},{"key":"38_CR18","unstructured":"Ph. Kolaitis, M. Vardi, On the expressive power of Datalog: Tools and a case study, Proc. 9th ACM Symp. on Principles of Database Systems, 61\u201371."},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0019-9958(77)90443-0","volume":"33","author":"R. E. Ladner","year":"1977","unstructured":"R.E. Ladner, Application of model-theoretic games to discrete linear orders and finite automata, Inform. Contr. 33 (1977), 281\u2013303.","journal-title":"Inform. Contr."},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"D. Lippert, W. Thomas, Relativized star-free expressions, first-order logic, and a concatenation game, in: Semigroup Theory and Applications (H. J\u00fcrgensen et al. eds.), Springer Lect. Notes in Math. 1320 (1988), 194\u2013204.","DOI":"10.1007\/BFb0083433"},{"key":"38_CR21","first-page":"1201","volume-title":"Handbook of Theoretical Computer Science","author":"R. Milner","year":"1990","unstructured":"R. Milner, Operational and algebraic semantics of concurrent processes, in: Handbook of Theoretical Computer Science (J. v. Leeuwen, ed.), Vol. B, Elsevier Science Publ., Amsterdam 1990, pp. 1201\u20131241."},{"key":"38_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-9452-5","volume-title":"Mathematical Logic","author":"D. Monk","year":"1976","unstructured":"D. Monk, Mathematical Logic, Springer-Verlag, New York 1976."},{"key":"38_CR23","unstructured":"H. Oguzt\u00fcz\u00fcn, A fragment of first-order logic adequate for observation equivalence, in: Computer Science Logic (E. Borger et al., eds.), Springer LNCS 626 (1992), 287\u2013291."},{"key":"38_CR24","unstructured":"D. Park, Concurrency and automata on infinite sequences, in: Theoretical Computer Science (P. Deussen, ed.), Springer LNCS 104 (1981), 167\u2013183."},{"key":"38_CR25","unstructured":"A. Potthoff, Modulo counting quantifiers over finite trees, in: CAAP'92 (J.C. Raoult, ed.), LNCS 581 (1992), 265\u2013278."},{"key":"38_CR26","volume-title":"Linear Orderings","author":"J. G. Rosenstein","year":"1982","unstructured":"J.G. Rosenstein, Linear Orderings, Academic Press, New York 1982."},{"key":"38_CR27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-94-009-9860-5_5","volume-title":"Essays in Honour of Jaakko Hintikka","author":"D. Scott","year":"1979","unstructured":"D. Scott, A note on distributive normal forms, in: Essays in Honour of Jaakko Hintikka (E. Saarinen et al., eds.), Reidel, Dordrecht 1979, pp. 75\u201390."},{"key":"38_CR28","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","volume":"102","author":"S. Shelah","year":"1975","unstructured":"S. Shelah, The monadic theory of order, Ann. Math. 102 (1975), 379\u2013419.","journal-title":"Ann. Math."},{"key":"38_CR29","first-page":"11","volume":"16","author":"W. Thomas","year":"1984","unstructured":"W. Thomas, An application of the Ehrenfeucht-Fra\u00efss\u00e9 game in formal language theory, Bull. Soc. Math. France, Mem. 16 (1984), 11\u201321.","journal-title":"Bull. Soc. Math. France, Mem."},{"key":"38_CR30","unstructured":"W. Thomas, A concatenation game and the dot-depth hierarchy, in: Computation Theory and Logic (E. B\u00f6rger, ed.), LNCS 270 (1987), 415\u2013426."},{"key":"38_CR31","unstructured":"W. Thomas, On chain logic, path logic, and first-order logic over infinite trees, Proc. 2nd LICS, Ithaca, N.Y. 1987, 245\u2013256."},{"key":"38_CR32","unstructured":"W. Thomas, On logics, tilings, and automata, in: Proc. 18th ICALP, Madrid (J. Leach Albert et al., eds.), Springer LNCS 510 (1991), 441\u2013454."}],"container-title":["Lecture Notes in Computer Science","TAPSOFT'93: Theory and Practice of Software Development"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56610-4_89","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:15:02Z","timestamp":1578536102000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56610-4_89"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540566106","9783540475989"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-56610-4_89","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}