On the Pi-2-P Completeness of the Containment Problem of Conjunctive Queries with Negation and Other Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2007

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

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).
No file

Dates and versions

lirmm-00129534 , version 1 (07-02-2007)

Identifiers

  • HAL Id : lirmm-00129534 , version 1

Cite

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⟩
166 View
0 Download

Share

Gmail Facebook X LinkedIn More