On some tractable classes in deduction and abduction

DOI10.1016/S0004-3702(99)00088-0MaRDI QIDQ1978251zbMATH OpenFDO

Authors Alvaro del Val

Publication date 4 June 2000

Published in Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

abductiondeductionautomated reasoningpropositional logicentailmenttractable inferencetractability of entailment

Mathematics Subject Classification ID

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

Recommendations

• What makes propositional abduction tractable
• A Complete Classification of the Complexity of Propositional Abduction
• scientific article; zbMATH DE number 2000816
• scientific article; zbMATH DE number 512816
• scientific article; zbMATH DE number 140373

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1256705 (Why is no real title available?)
• A hierarchy of tractable satisfiability problems
• Abduction versus closure in causal theories.
• Extended Horn sets in propositional logic
• Hierarchies of polynomially solvable satisfiability problems
• On the Relationship Between Abduction and Deduction
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognizing renamable generalized propositional Horn formulas is NP- complete
• Renaming a Set of Clauses as a Horn Set
• Support set selection for abductive and default reasoning
• The complexity of logic-based abduction
• Unit Refutations and Horn Sets

Cited in

(4)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1978251)