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

DOI10.1016/j.ic.2012.03.001zbMath1251.03071MaRDI QIDQ714500

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

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

complexity; graph homomorphism; negation; entailment; query containment; clause implication; conceptual graph; fragment of first-order logic

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03B20: Subsystems of classical logic (including intuitionistic logic)

03F20: Complexity of proofs

Cites Work

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