On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems

Marie-Laure Mugnier 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : This research note proves the $\Pi_2^P$-completeness of several equivalent problems: deduction in the first-order logical fragment composed of existential conjunctive formulas, deduction in polarized graphs (which are simple conceptual graphs with negation on relations, built on a simplified vocabulary) and containment of conjunctive queries with negation. The exhibited reduction is essentially due to Guillaume Bagan (November 2004).
Type de document :
Rapport
RR-07004, 2007, pp.7
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00129534
Contributeur : Marie-Laure Mugnier <>
Soumis le : mercredi 7 février 2007 - 23:42:02
Dernière modification le : jeudi 11 janvier 2018 - 16:20:53

Identifiants

  • HAL Id : lirmm-00129534, version 1

Citation

Marie-Laure Mugnier. On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems. RR-07004, 2007, pp.7. 〈lirmm-00129534〉

Partager

Métriques

Consultations de la notice

179