Algorithmes et complexité des problèmes d'énumération pour l'évaluation de requêtes logiques
Guillaume Bagan · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
This thesis is dedicated to the evaluation of logical queries from the enumeration point of view. First, we deal with acyclic conjunctive formulas with inequalities; we show that such a query can be evaluated with linear delay in the size of the structure: this improves a result by Papadimitriou and Yannakakis. Then, we exhibit a subclass of acyclic formulas, so-called connex-acyclic formulas. Such queries can be evaluated with constant delay after some linear time preprocessing. We show that this result is maximal in the following sense: if the product of boolean matrices cannot be computed in linear time then any acyclic query is computable with constant delay after some linear time preprocessing if and only if it is connex-acyclic. Second, we prove that any MSO query over a class of bounded treewidth structures can be evaluated with a linear delay in the size of each solution after some linear preprocessing in the size of the structure. Third, we show that for each first-order query over bounded degree structures, one can compute the j-th solution of the query in constant time after some linear time preprocessing. Finally, we prove that unit interval graphs are of bounded local cliquewidth. Hence we deduce that any first-order statement over these graphs is decidable in linear time; Also, we show that this result is somehow maximal.