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

DOI10.1016/j.ic.2012.03.001zbMath1251.03071OpenAlexW2043790764MaRDI 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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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