S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, 1974.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, issue.2, pp.308-340, 1991.
DOI : 10.1016/0196-6774(91)90006-K

G. Bagan, MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay, Conf. on Computer Science Logic (CSL), pp.167-181, 2006.
DOI : 10.1007/11874683_11

G. Bagan, Algorithmes et complexité desprobì emes d'´ enumération pour l'´ evaluation de requêtes logiques, 2009.

G. Bagan, A. Durand, E. Filiot, and O. Gauwin, Efficient Enumeration for Conjunctive Queries over X-underbar Structures, Conf. on Computer Science Logic (CSL), pp.80-94, 2010.
DOI : 10.1007/978-3-642-15205-4_10

URL : https://hal.archives-ouvertes.fr/hal-00489955

G. Bagan, A. Durand, and E. Grandjean, On Acyclic Conjunctive Queries and Constant Delay Enumeration, Conf. on Computer Science Logic (CSL), pp.208-222, 2007.
DOI : 10.1007/978-3-540-74915-8_18

URL : https://hal.archives-ouvertes.fr/hal-00195010

G. Bagan, A. Durand, E. Grandjean, and F. Olive, Computing the jth solution of a first-order query, pp.147-164, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00221730

M. Boja´nczykboja´nczyk, A. Muscholl, T. Schwentick, and L. Segoufin, Two-variable logic on data trees and XML reasoning, J. of the ACM, vol.56, issue.3, 2009.

M. Boja´nczykboja´nczyk and P. Parys, XPath evaluation in linear time, J. of the ACM, vol.58, issue.4, 2011.

T. Colcombet, A Combinatorial Theorem for Trees, In Intl. Coll. on Automata, Languages and Programming, pp.901-912, 2007.
DOI : 10.1007/978-3-540-73420-8_77

URL : https://hal.archives-ouvertes.fr/hal-00192024

D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing , STOC '87, pp.251-280, 1990.
DOI : 10.1145/28395.28396

B. Courcelle, Graph Rewriting: An Algebraic and Logic Approach, Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pp.193-242, 1990.
DOI : 10.1016/B978-0-444-88074-1.50010-X

B. Courcelle, Linear delay enumeration and monadic second-order logic, Discrete Applied Mathematics, vol.157, issue.12, pp.2675-2700, 2009.
DOI : 10.1016/j.dam.2008.08.021

URL : https://hal.archives-ouvertes.fr/hal-00333846

N. Creignou, F. Olive, and J. Schmidt, Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight, Theory and Applications of Satisfiability Testing (SAT), pp.120-133, 2011.
DOI : 10.1007/s00453-009-9284-5

URL : https://hal.archives-ouvertes.fr/hal-01195416

A. Dawar, M. Grohe, and S. Kreutzer, Locally Excluding a Minor, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp.270-279, 2007.
DOI : 10.1109/LICS.2007.31

A. Durand and E. Grandjean, First-order queries on structures of bounded degree are computable with constant delay, ACM Transactions on Computational Logic, vol.8, issue.4, 2007.
DOI : 10.1145/1276920.1276923

URL : https://hal.archives-ouvertes.fr/hal-00195016

A. Durand and S. Mengel, On Polynomials Defined by Acyclic Conjunctive Queries and Weighted Counting Problems. CoRR, abs, 1110.

A. Durand and Y. Strozecki, Enumeration Complexity of Logical Query Problems with Second-order Variables, Conf. on Computer Science Logic (CSL), pp.189-202, 2011.

Z. Dvo?ák, D. Král, and R. Thomas, Deciding First-Order Properties for Sparse Graphs, Symp. on Foundations of Computer Science (FOCS), pp.133-142, 2010.

Z. Dvorak, D. Král, and R. Thomas, Testing first-order properties for subclasses of sparse graphs. CoRR, abs/1109, 2011.

J. Flum and M. Grohe, Parameterized Complexity Theory, 2006.

M. Frick and M. Grohe, Deciding first-order properties of locally tree-decomposable structures, Journal of the ACM, vol.48, issue.6, pp.1184-1206, 2001.
DOI : 10.1145/504794.504798

M. Grohe, The complexity of first-order and monadic second-order logic revisited, Ann. Pure Appl. Logic, vol.130, issue.1-3, pp.3-31, 2004.

E. Grandjean, Sorting, linear time and the satisfiability problem, Annals of Mathematics and Artificial Intelligence, vol.A, issue.1, pp.183-236, 1996.
DOI : 10.1007/BF02127798

URL : https://hal.archives-ouvertes.fr/hal-00254952

M. Grohe and S. Kreutzer, Model Theoretic Methods in Finite Combinatorics, chapter Methods for Algorithmic Meta Theorems, 2011.

W. Kazana and L. Segoufin, Enumeration of first-order queries on classes of structures with bounded expansion, Proceedings of the 32nd symposium on Principles of database systems, PODS '13
DOI : 10.1145/2463664.2463667

URL : https://hal.archives-ouvertes.fr/hal-00908779

W. Kazana and L. Segoufin, First-order query evaluation on structures of bounded degree, Logical Methods in Computer Science, vol.7, issue.2, 2011.
DOI : 10.2168/LMCS-7(2:20)2011

W. Kazana and L. Segoufin, Enumeration of monadic second-order queries on trees, ACM Transactions on Computational Logic, vol.14, issue.4
DOI : 10.1145/2528928

URL : https://hal.archives-ouvertes.fr/hal-00916400

S. Kreutzer and A. Dawar, Parameterized complexity of first-order logic, Electronic Colloquium on Computational Complexity (ECCC), vol.16, p.131, 2009.

S. Lindell, A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES, International Journal of Foundations of Computer Science, vol.19, issue.01, pp.205-217, 2008.
DOI : 10.1142/S0129054108005632

J. Ne?et?il and P. O. De-mendez, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics, vol.29, issue.3, pp.760-776, 2008.
DOI : 10.1016/j.ejc.2006.07.013

J. Ne?et?il and P. O. De-mendez, On nowhere dense graphs, European Journal of Combinatorics, vol.32, issue.4, pp.600-617, 2011.
DOI : 10.1016/j.ejc.2011.01.006

C. H. Papadimitriou and M. Yannakakis, On the Complexity of Database Queries, Journal of Computer and System Sciences, vol.58, issue.3, pp.407-427, 1999.
DOI : 10.1006/jcss.1999.1626

R. Pichler and S. Skritek, Tractable counting of the answers to conjunctive queries, Alberto Mendelzon Intl. Workshop on Foundations of Data Management (AMW), 2011.
DOI : 10.1016/j.jcss.2013.01.012

D. Seese, Linear Time Computable Problems and First-Order Descriptions, Mathematical Structures in Computer Science, vol.6, issue.6, pp.505-526, 1996.

Y. Strozecki, Enumeration complexity and matroid decomposition, 2010.

Y. Strozecki, Enumeration of the Monomials of a Polynomial and Related Complexity Classes, Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), pp.629-640, 2010.
DOI : 10.1007/978-3-642-15155-2_55

T. Uno, Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs, Intl. Symp. on Algorithms and Computation, pp.92-101, 1997.
DOI : 10.1007/3-540-63890-3_11

M. Yannakakis, Algorithms for Acyclic Database Schemes, Intl. Conf. on Very Large Databases (VLDB), pp.82-94, 1981.