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

DOI10.1016/J.IC.2012.03.001MaRDI QIDQ714500zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(3)

• The ^2 fragment of the first-order theory of atomic set constraints is _1⁰-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)