S. Abiteboul, M. Y. Vardi, and V. Vianu, Fixpoint logics, relational machines, and computational complexity, Proceedings of the 7th IEEE Symposium on Logic in Computer Science, pp.156-168, 1992.

C. C. Chang and H. J. Keisler, Model theory, Studies in Logic and the Foundations of Mathematics, vol.73, 1973.

K. J. Compton, An algebra and a logic for nc 1, Proceedings of the 3rd IEEE Symposium on Logic in Computer Science, pp.12-21, 1988.

H. Ebbinghaus and J. Flum, Finite model theory, 1995.

R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, vol.7, pp.3-31, 1974.

M. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of np-completeness, 1979.

A. Goerdt, Characterizing complexity classes by higher-type primitive-recursive definitions, Proceedings of the 4th IEEE Symposium on Logic in Computer Science, pp.364-374, 1989.

E. Grandjean, Universal quantifiers and time complexity of random access machines, Mathematical Systems Theory, vol.13, pp.438-451, 1984.
URL : https://hal.archives-ouvertes.fr/hal-00254875

E. Grandjean and F. Olive, Monadic logical definability of nondeterministic linear time
URL : https://hal.archives-ouvertes.fr/hal-00255036

Y. Gurevich, Logic and the challenge of computer science, Current trends in theoretical computer science, Algebras of feasible functions, Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, vol.14, pp.1-57, 1983.

Y. Gurevich and S. Shelah, Fixed-point extensions of first-order logic, Annals of Pure and Applied Logic, vol.32, pp.265-280, 1986.

D. Harel and D. Peleg, Static logics, dynamic logics, and complexity classes, Information and Control, pp.86-102, 1984.

W. Hodges, A shorter model theory, 1997.

N. Immerman, Nondeterministic space is closed under complement, Relational queries computable in polynomial time, vol.68, pp.75-91, 1986.

T. Jech, Set theory, 1978.

P. G. Kolaitis and M. Y. Vardi, 0-1 laws and decision problems for fragments of secondorder logic, Information and Computation, vol.87, pp.302-338, 1990.

K. J. Lange, B. Jenner, and B. Kirsig, The logarithmic hierarchy collapses: A? L 2 = A? L 2, Proceedings of the 14th International Conference on Automata, Languages, and Programming, 1987.

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

A. B. Livchak, The relational model for systems of automatic testing, Automatic Documentation and Mathematical Linguistics, vol.4, pp.27-29, 1982.

J. F. Lynch, The quantifier structure of sentences that characterize nondeterministic time complexity, Mathematical Systems Theory, vol.15, pp.40-66, 1982.

W. J. Paul, N. Pippenger, E. Szemeredi, and W. T. Trotter, On determinism versus nondeterminism and related problems, Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pp.429-438, 1983.

B. Poizat, Cours de théorie des modèles, OFFILIB, 1985.

V. Yu and . Sazonov, A logical approach to the problem of p=np, Proceedings of the 9th Conference on Mathematical Foundations of Computer Science, vol.88, pp.319-323, 1980.

L. J. Stockmeyer, The polynomial time hierarchy, Theoretical Computer Science, vol.3, pp.1-22, 1977.

J. Tiuryn and P. Urzyczyn, Some relationships between logic of programs and complexity theory, Theoretical Computer Science, vol.60, pp.83-108, 1988.

M. Y. Vardi, The complexity of relational query languages, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp.137-146, 1982.