, Foundations of Databases, 1995.
, The Design and Analysis of Computer Algorithms, 1974.
, 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
, 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
, Algorithmes et complexité desprobì emes d'´ enumération pour l'´ evaluation de requêtes logiques, 2009.
, 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
, 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
, Computing the jth solution of a first-order query, pp.147-164, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00221730
, Two-variable logic on data trees and XML reasoning, J. of the ACM, vol.56, issue.3, 2009.
, XPath evaluation in linear time, J. of the ACM, vol.58, issue.4, 2011.
, 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
, 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
, 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
, 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
, 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
, 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
, 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
, On Polynomials Defined by Acyclic Conjunctive Queries and Weighted Counting Problems. CoRR, abs, 1110.
, Enumeration Complexity of Logical Query Problems with Second-order Variables, Conf. on Computer Science Logic (CSL), pp.189-202, 2011.
, Deciding First-Order Properties for Sparse Graphs, Symp. on Foundations of Computer Science (FOCS), pp.133-142, 2010.
, Testing first-order properties for subclasses of sparse graphs. CoRR, abs/1109, 2011.
, Parameterized Complexity Theory, 2006.
, 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
, The complexity of first-order and monadic second-order logic revisited, Ann. Pure Appl. Logic, vol.130, issue.1-3, pp.3-31, 2004.
, 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
, Model Theoretic Methods in Finite Combinatorics, chapter Methods for Algorithmic Meta Theorems, 2011.
, 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
, 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
, 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
, Parameterized complexity of first-order logic, Electronic Colloquium on Computational Complexity (ECCC), vol.16, p.131, 2009.
, 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
, 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
, On nowhere dense graphs, European Journal of Combinatorics, vol.32, issue.4, pp.600-617, 2011.
DOI : 10.1016/j.ejc.2011.01.006
, 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
, 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
, Linear Time Computable Problems and First-Order Descriptions, Mathematical Structures in Computer Science, vol.6, issue.6, pp.505-526, 1996.
, Enumeration complexity and matroid decomposition, 2010.
, 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
, 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
, Algorithms for Acyclic Database Schemes, Intl. Conf. on Very Large Databases (VLDB), pp.82-94, 1981.