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
complexitygraph homomorphismnegationentailmentquery containmentclause implicationconceptual graphfragment of first-order logic
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