{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:00:35Z","timestamp":1725487235580},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540727323"},{"type":"electronic","value":"9783540727347"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72734-7_21","type":"book-chapter","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T09:40:50Z","timestamp":1183023650000},"page":"293-309","source":"Crossref","is-referenced-by-count":1,"title":["On Complexity of Ehrenfeucht-Fra\u00efss\u00e9 Games"],"prefix":"10.1007","author":[{"given":"Bakhadyr","family":"Khoussainov","sequence":"first","affiliation":[]},{"given":"Jiamou","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00015-1","volume":"174","author":"S. Arora","year":"1997","unstructured":"Arora, S., Fagin, R.: On winning strategies in EF games. Theoretical Computer Science\u00a0174, 97\u2013121 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"21_CR2","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/inco.1995.1084","volume":"119","author":"A. Dawar","year":"1995","unstructured":"Dawar, A.: Infinitary logic and inductively definability over finite structures. Information and Computation\u00a0119(2), 160\u2013175 (1995)","journal-title":"Information and Computation"},{"key":"21_CR3","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"Ehrenfeucht, A.: An appliction of games to the completeness problem for formalized theories. Fundamenta Mathematicae\u00a049, 129\u2013141 (1961)","journal-title":"Fundamenta Mathematicae"},{"key":"21_CR4","first-page":"35","volume":"1","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"Fra\u00efss\u00e9, R.: Sur quelques classfications des syst\u00e8m de relations. Universit\u00e9 d Alger, Publication Scientifiques, S\u00e9r. A\u00a01, 35\u2013182 (1954)","journal-title":"Universit\u00e9 d Alger, Publication Scientifiques, S\u00e9r. A"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Equivalence in finite-variable logics is complete for polynomial time. In: Proceeding FOCS 96 (1996)","DOI":"10.1109\/SFCS.1996.548485"},{"key":"21_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511551574","volume-title":"Model theory","author":"W. Hodeges","year":"1993","unstructured":"Hodeges, W.: Model theory. Cambridge University Press, Cambridge (1993)"},{"key":"21_CR7","unstructured":"Immerman, N., Kozen, D.: Definability with bounded number of bounded variables. In: Logic in Computer Science, pp. 236\u2013244 (1987)"},{"key":"21_CR8","first-page":"407","volume-title":"The Theory of Models","author":"C. Karp","year":"1965","unstructured":"Karp, C.: Finite quantifier equivalence. In: Addison, J.W., Henkin, L., Tarski, A. (eds.) The Theory of Models, pp. 407\u2013412. North-Holland, Amsterdam (1965)"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1007\/978-3-540-45220-1_26","volume-title":"Computer Science Logic","author":"P. Kolaitis","year":"2003","unstructured":"Kolaitis, P., Panttaja, J.: On the complexity of existential pebble games. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 314\u2013329. Springer, Heidelberg (2003)"},{"key":"21_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/3-540-44693-1_40","volume-title":"STACS 2001","author":"C. Lautemann","year":"2001","unstructured":"Lautemann, C., Schweikardt, N.: An Ehrenfeucht-Fra\u00efss\u00e9 approach to collapse results for first-order queries over embedded databases. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 455\u2013466. Springer, Heidelberg (2001)"},{"key":"21_CR11","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)"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/3-540-48168-0_24","volume-title":"Computer Science Logic","author":"J. Marcinkowski","year":"1999","unstructured":"Marcinkowski, J.: Directed reachability: From ajtai-fagin to Ehrenfeucht-Fra\u00efss\u00e9 games. In: Flum, J., Rodr\u00edguez-Artalejo, M. (eds.) CSL 1999. LNCS, vol.\u00a01683, pp. 338\u2013349. Springer, Heidelberg (1999)"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Mekler, A., Shelah, S., V\u00e4\u00e4n\u00e4nen, J.: The EF-game of length \u03c9 1. Transactions of the American mathematical Society\u00a0339(2) (1993)","DOI":"10.2307\/2154287"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/10703163_11","volume-title":"Computer Science Logic","author":"E. Pezzoli","year":"1999","unstructured":"Pezzoli, E.: Computational complexity of Ehrenfeucht-Fra\u00efss\u00e9 games on finite structures. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) CSL 1998. LNCS, vol.\u00a01584, pp. 159\u2013170. Springer, Heidelberg (1999)"},{"key":"21_CR15","first-page":"329","volume-title":"The Theory of Models","author":"D. Scott","year":"1965","unstructured":"Scott, D.: Logic with denumerable long formulas and finite strings of quantifiers. In: Addison, J.W., Henkin, L., Tarski, A. (eds.) The Theory of Models, pp. 329\u2013341. North-Holland, Amsterdam (1965)"},{"key":"21_CR16","unstructured":"Schweikardt, N.: An EF game appraoch to collapse results in database theory. To appear in Information and Computation (2006)"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72734-7_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:04:46Z","timestamp":1605762286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72734-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540727323","9783540727347"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72734-7_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}