On the complexity of entailment in existential conjunctive first-order logic with atomic negation

DOI10.1016/J.IC.2012.03.001zbMATH Open1251.03071OpenAlexW2043790764MaRDI QIDQ714500FDOQ714500

Authors: Marie-Laure Mugnier, Geneviève Simonet, Michaël Thomazo 

Publication date: 11 October 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.03.001

Recommendations

• The complexity of equivalence, entailment, and minimization in existential positive logic
• On the containment problem for queries in conjunctive form with negation
• The ground-negative fragment of first-order logic is -complete
• Conjunctive-query containment and constraint satisfaction
• The complexity of minimum partial truth assignments and implication in negation-free formulae

zbMATH Keywords

complexitygraph homomorphismnegationentailmentquery containmentclause implicationconceptual graphfragment of first-order logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20) Complexity of proofs (03F20)

Cites Work

• Title not available (Why is that?)
• On truth-table reducibility to SAT
• Title not available (Why is that?)
• Conjunctive-query containment and constraint satisfaction
• The complexity of promise problems with applications to public-key cryptography
• Equivalences among Relational Expressions
• Answering queries using views: A survey
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Title not available (Why is that?)
• Inductive Logic Programming: Theory and methods
• Title not available (Why is that?)
• Subsumption and implication
• Implication of clauses is undecidable
• Title not available (Why is that?)
• Simple Conceptual Graphs with Atomic Negation and Difference

Cited In (3)

• The \(\exists\forall^2\) fragment of the first-order theory of atomic set constraints is \(\Pi_1^0\)-hard
• How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
• The complexity of equivalence, entailment, and minimization in existential positive logic

This page was built for publication: On the complexity of entailment in existential conjunctive first-order logic with atomic negation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714500)