Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Résultat majeur
Production scientifique
Résultat majeur : ON THE COMPLEXITY OF CONSISTENT QUERY ANSWERING IN THE PRESENCE OF SIMPLE ONTOLOGIES
ON THE COMPLEXITY OF CONSISTENT QUERY ANSWERING IN THE PRESENCE OF SIMPLE ONTOLOGIES
02 avril 2012

Meghyn Bienvenu, in Twenty-Sixth Conference on Artificial Intelligence (AAAI)
Consistent query answering is a standard approach for producing meaningful query answers when data is inconsistent.
Recent work on consistent query answering in the presence of ontologies has shown this problem to be intractable in data complexity even for ontologies expressed in lightweight description logics. In order to better understand the source of this intractability, we investigate the complexity of consistent query answering for simple ontologies consisting only of class subsumption and class disjointness axioms. We show that for conjunctive queries with at most one quantified variable,
the problem is first-order expressible; for queries with at most two quantified variables, the problem has polynomial data complexity but may not be first-order expressible; and for three quantified variables, the problem may become
coNP-hard in data complexity. For queries having at most two quantified variables, we further identify a necessary and sufficient condition for first-order expressibility. In order to be able to handle arbitary conjunctive queries, we propose a novel inconsistency-tolerant semantics and show that
under this semantics, first-order expressibility is always guaranteed. We conclude by extending our positive results to
DL-Lite ontologies without inverse.



Activités de recherche
  ° Ontologies
  ° Logique
  ° Complexité
  ° Raisonnement automatique

Equipe
  ° Intelligence Artificielle et Systèmes d'Inférence

Contact
  [aucun]
Résultats majeurs
INFORMATION-GEOMETRIC OPTIMIZATION ALGORITHMS: A UNIFYING PICTURE VIA INVARIANCE PRINCIPLES
02 mai 2017
Yann Ollivier, Ludovic Arnold, Anne Auger, Nikolaus Hansen - JMLR 18(18):1−65, 2017.

FORMAL MUTATION TESTING FOR CIRCUS
21 avril 2016
Alex Donizeti Betez Alberto, Ana Cavalcanti, Marie-Claude Gaudel, Adenilso Simao Journal of Infor

CELL-CELL COMMUNICATION ENHANCES THE CAPACITY OF CELL ENSEMBLES TO SENSE SHALLOW GRADIENTS DURING MORPHOGENESIS
09 février 2016
D. Ellison, A. Mugler, M.D. Brennan, S.H. Lee, R.J. Huebner, E.R. Shamir, L.A. Woo, J. Kim, P. Amar,

COMPUTING WITH SYNTHETIC PROTOCELLS
13 mai 2015
Alexis Courbet, Franck Molina and Patrick Amar

ICDE 2015 TUTORIAL: RDF DATA MANAGEMENT: REASONING ON WEB DATA
27 octobre 2014
François Goasdoué, Ioana Manolescu and Alexandra Roatiș