Documentation Documentation
Identifiant IdRef : 226723216
Notice de type Rameau

Point d'accès autorisé

Informations

Langue d'expression : Francais
Date de naissance :  2009
Note publique d''information : 
Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités. Nous prouvons que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de deux matrices booléennes ne peut pas être calculé en temps linéaire, alors toute requête conjonctive acyclique est évaluable à délai constant après prétraitement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous prouvons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée ; d'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.

Note publique d''information : 
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 two boolean matrices cannot be computed in linear time then any acyclic conjunctive 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.

Notices d'autorité liées

Autres identifiants

Utilisation dans Rameau

Le point d'accès peut être employé dans un point d'accès sujet

... Références liées : ...