On some tractable classes in deduction and abduction

DOI10.1016/S0004-3702(99)00088-0zbMath0940.03016MaRDI QIDQ1978251

Alvaro del Val

Publication date: 4 June 2000

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

automated reasoningpropositional logicdeductionabductionentailmenttractable inferencetractability of entailment

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05)

Related Items (4)

What makes propositional abduction tractable ⋮ On the complexity of second-best abductive explanations ⋮ Counting complexity of propositional abduction ⋮ Complexity results for explanations in the structural-model approach

Cites Work

• Unnamed Item
• Unnamed Item
• Abduction versus closure in causal theories.
• A hierarchy of tractable satisfiability problems
• Polynomial-time inference of all valid implications for Horn and related formulae
• Hierarchies of polynomially solvable satisfiability problems
• Recognizing renamable generalized propositional Horn formulas is NP- complete
• Support set selection for abductive and default reasoning
• On the Relationship Between Abduction and Deduction
• Unit Refutations and Horn Sets
• Renaming a Set of Clauses as a Horn Set
• Extended Horn sets in propositional logic
• The complexity of logic-based abduction

This page was built for publication: On some tractable classes in deduction and abduction