M. Ajtai and R. Fagin, Abstract, The Journal of Symbolic Logic, vol.49, issue.01, pp.113-150, 1990.
DOI : 10.1016/S0022-0000(70)80006-X

S. Arora and R. Fagin, On winning strategies in Ehrenfeucht-Fra??ss?? games, Theoretical Computer Science, vol.174, issue.1-2, pp.97-121, 1997.
DOI : 10.1016/S0304-3975(96)00015-1

V. [. Abiteboul and . Vianu, Fixpoint extensions of first-order logic and datalog-like languages, [1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science, pp.71-79, 1989.
DOI : 10.1109/LICS.1989.39160

V. [. Abiteboul and . Vianu, Computing with First-Order Logic, Journal of Computer and System Sciences, vol.50, issue.2, pp.309-335, 1995.
DOI : 10.1006/jcss.1995.1025

]. J. Bar77 and . Barwise, On Moschovakis closure ordinals, Journal of Symbolic Logic, vol.42, pp.292-296, 1977.

J. [. Caì-o and . Makowsky, The Ehrenfeucht-Fra¨?sséFra¨?ssé games for transitive closure logic. Unpublished manuscript, 1991.

]. K. Com83 and . Compton, Some useful preservation theorems, Journal of Symbolic Logic, vol.48, pp.427-440, 1983.

]. B. Cou90 and . Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Information and Computation, vol.85, pp.12-75, 1990.

]. B. Cou92 and . Courcelle, The monadic second-order logic of graphs VII: Graphs as relational structures, Theoretical Computer Science, vol.101, pp.3-33, 1992.

]. B. Cou96 and . Courcelle, The monadic second-order logic of graphs X: Linear orderings, Theoretical Computer Science, vol.160, pp.87-143, 1996.

L. [. Dong, L. Libkin, and . Wong, Local properties of query languages, Proc. Int. Conf. on Database Theory, pp.140-154, 1997.

[. Ebbinghaus and J. Flum, Finite Model Theory, 1995.

]. A. Ehr61 and . Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math, vol.49, pp.129-141, 1961.

]. R. Fag74 and . Fagin, Generalized first?order spectra and polynomial?time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, pp.43-73, 1974.

]. R. Fag97 and . Fagin, Easier ways to win logical games, Proceedings of the DIMACS Workshop on Finite Models and Descriptive ComplexityFra54] R. Fra¨?sséFra¨?ssé. Sur quelques classifications des systèmes de relations. Publ. Sci. Univ, 1997.

L. [. Fagin, M. Stockmeyer, and . Vardi, On monadic NP vs. monadic co-NP. Information and Computation, Preliminary version appeared in 1993 IEEE Conference on Structure in Complexity Theory, pp.78-92, 1995.

]. H. Gai82 and . Gaifman, On local and nonlocal properties, Logic Colloquium '81, pp.105-135, 1982.

]. M. Gppdb94, J. Gemis, P. Paredaens, J. Peelman, and . Van-den-bussche, A computational model for generic graph functions, Graph Transformations in Computer Science, number 776 in Lecture Notes in Computer Science, pp.170-187, 1994.

]. E. Grä92 and . Grädel, Capturing complexity classes by fragments of second order logic A preliminary version, Proceedings of 6th IEEE Conference on Structure in Complexity Theory, pp.35-57, 1991.

]. W. Han65 and . Hanf, Model-theoretic methods in the study of elementary logic, The Theory of Models, pp.132-145, 1965.

T. Schwentick and K. Barthelmann, Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences, vol.25, pp.76-98, 1982.

]. N. Imm86 and . Immerman, Relational queries computable in polynomial time, Information and Control, vol.68, pp.86-104, 1986.

]. N. Imm87 and . Immerman, Expressibility as a complexity measure: results and directions, Second Structure in Complexity Conference, pp.194-202, 1987.

]. D. Lei89 and . Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences, vol.39, pp.51-83, 1989.

]. L. Lib97 and . Libkin, On the forms of locality over finite models, Proc. 12th IEEE Symp. on Logic in Computer Science, 1997.

L. Libkin and L. Wong, Unary quantifiers, transitive closure, and relations of large degree, STACS 98, number 1373 in Lecture Notes in Computer Science, pp.183-193, 1998.
DOI : 10.1007/BFb0028560

]. R. Ten75 and . Tenney, Second-order Ehrenfeucht games and the decidability of the second-order theory of an equivalence relation, Journal of the Australian Mathematical Society, vol.20, pp.323-331, 1975.

]. W. Tho91 and . Thomas, On logics, tilings and automata, Proc. ICALP'91, number 510 in Lecture Notes in Computer Science, pp.441-453, 1991.

]. W. Tho97a and . Thomas, Automata theory on trees and partial orders, Proc. TAPSOFT'97, number 1214 in Lecture Notes in Computer Science, pp.20-38, 1997.

]. W. Tho97b and . Thomas, Elements of an automata theory over partial orders, Partial Order Methods in Verification, number 29 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1997.

]. M. Var82 and . Vardi, The complexity of relational query languages, Proc. 14th ACM Symp. on Theory of Computing, pp.137-146, 1982.