Evènement pour le groupe Graphes et Logique


Date 2013-05-28  11:00-12:00
TitreTowards a characterisation of linear-time first-order existential queries 
Résumé(or three complexity dichotomy theorems for existential first-order) It is known that the data complexity of a Conjunctive Query (CQ) is determined only by the way its variables are shared between atoms, reflected by its hypergraph. In particular, Yannakakis [Yan81, BFMY83] proved that a CQ is decidable in linear time when it is alpha- acyclic, i.e. its hypergraph is alpha-acyclic; Bagan et al. [BDG07] even state: "Any CQ is decidable in linear time iff it is alpha-acyclic (under certain hypotheses)". They also prove a similar result for the enumeration problem. Since the complexity of a Negative Conjunctive Query (NCQ), a conjunctive query where all atoms are negated, also only depends on its hypergraph, there must be a similar dichotomy in this case. We show that: "Any NCQ is decidable in linear time iff it is beta-acyclic (under certain hypotheses)" and also give a similar result for the enumeration problem. If we consider Signed Conjunctive Query (SCQ), a conjunctive query where *some* atoms are negated, we need to introduce a notion of acyclicity of bicolored hypergraphs, that generalizes both alpha and beta acyclicities. With this notion, we finally generalize both previous dichotomy theorems in a single one, that deals with both the decision and the enumeration problems. This dichotomy theorem implies that beta-acyclic existential first-order queries are decidable in linear time, and that this hypergraph criterion is optimal. 
LieuSalle 076 
OrateurJohann Brault-Baron 
Emailjohann.brault-baron@unicaen.fr 
UrlGREYC 



Aucun document lié à cet événement.

Retour
Retour à l'index