On some tractable classes in deduction and abduction

DOI10.1016/S0004-3702(99)00088-0zbMATH Open0940.03016MaRDI QIDQ1978251FDOQ1978251

Authors: Alvaro del Val 

Publication date: 4 June 2000

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

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

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)

Cites Work

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

Cited In (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

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)