The computational complexity of abduction

DOI10.1016/0004-3702(91)90005-5zbMath0737.68076OpenAlexW2037481186MaRDI QIDQ1182159

Tom Bylander, John R. Josephson, Michael C. Tanner, Dean Allemang

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1016/0004-3702(91)90005-5

zbMATH Keywords

computational complexityNP-hardexplanationabduction

Mathematics Subject Classification ID

Related Items (33)

On an open problem in classification of languages ⋮ The complexity of propositional closed world reasoning and circumscription ⋮ Memory-limited model-based diagnosis ⋮ Large-Scale Cost-Based Abduction in Full-Fledged First-Order Predicate Logic with Cutting Plane Inference ⋮ What makes propositional abduction tractable ⋮ Perceiving the infinite and the infinitesimal world: unveiling and optical diagrams in mathematics ⋮ A Measure of Arbitrariness in Abductive Explanations ⋮ How many diagnoses do we need? ⋮ Exception diagnosis in multiagent contract executions ⋮ Super-Solutions ⋮ Identifying Efficient Abductive Hypotheses Using Multicriteria Dominance Relation ⋮ Abduction from logic programs: Semantics and complexity ⋮ On the complexity of second-best abductive explanations ⋮ Semantics and complexity of abduction from default theories ⋮ Inference to the stable explanations ⋮ A computational-level explanation of the speed of goal inference ⋮ Finding explanations of inconsistency in multi-context systems ⋮ AN ARTIFICIAL NETWORK FOR REASONING IN THE CANCELLATION CLASS WITH APPLICATION TO THE DIAGNOSIS OF CELLS DIVISION ⋮ Abductive reasoning in neural-symbolic systems ⋮ Model-based reasoning about learner behaviour ⋮ Mathematical aspects of concept analysis ⋮ Batch repair actions for automated troubleshooting ⋮ Special issue. Model-based reasoning in science: learning and discovery ⋮ Counting complexity of propositional abduction ⋮ Abduction-Based Search for Cooperative Answers ⋮ Reasoning about Exceptions to Contracts ⋮ Analysis of notions of diagnosis ⋮ Indefinite abductive explanations ⋮ Reasoning through doing. Epistemic mediators in scientific discovery ⋮ Process algebras for systems diagnosis. ⋮ The approximation of implicates and explanations ⋮ Complexity results for explanations in the structural-model approach ⋮ Multi-modal diagnosis combining case-based and model-based reasoning: a formal and experimental analysis

Uses Software

• MOLE

Cites Work

• Fusion, propagation, and structuring in belief networks
• Distributed revision of composite beliefs
• Diagnosing multiple faults
• A theory of diagnosis from first principles
• The computational complexity of probabilistic inference using Bayesian belief networks
• A Probabilistic Causal Model for Diagnostic Problem Solving Part I: Integrating Symbolic Causal Inference with Numeric Probabilistic Inference
• A Probabilistic Causal Model for Diagnostic Problem Solving Part II: Diagnostic Strategy
• The Complexity of Enumeration and Reliability Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The computational complexity of abduction