Semantics and complexity of abduction from default theories

DOI10.1016/S0004-3702(96)00040-9zbMath1017.03515OpenAlexW2000042161MaRDI QIDQ1402749

Nicola Leone, Thomas Eiter, Georg Gottlob

Publication date: 28 August 2003

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

Full work available at URL: https://doi.org/10.1016/s0004-3702(96)00040-9

zbMATH Keywords

AbductionDefault logicAlgorithms and complexityTractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27) Logic in computer science (03B70)

Related Items

What makes propositional abduction tractable, Outlier detection using default reasoning, Unnamed Item, Super-Solutions, Outlier detection for simple default theories, On the complexity of second-best abductive explanations, Inference to the stable explanations, A weighted causal theory for acquiring and utilizing open knowledge, Seminormalizing a default theory, Abductive reasoning through filtering, Constructing NP-intermediate problems by blowing holes with parameters of various properties, Probabilistic qualification of attack in abstract argumentation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• Logic programming, abduction and probability. A top-down anytime algorithm for estimating prior and posterior probabilities
• Abduction versus closure in causal theories.
• A logical framework for default reasoning
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• A logic for default reasoning
• The computational complexity of abduction
• Hard problems for simple default logics
• On the complexity of propositional knowledge base revision, updates, and counterfactuals
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Probabilistic Horn abduction and Bayesian networks
• Structure and complexity of relational queries
• Tractable reasoning via approximation
• The complexity of default reasoning under the stationary fixed point semantics
• On the hardness of approximate reasoning
• On the Relationship Between Abduction and Deduction
• Second order logic and the weak exponential hierarchies
• On Approximation Algorithms for # P
• Complexity Results for Nonmonotonic Logics
• On the Complexity of Timetable and Multicommodity Flow Problems
• A survey of complexity results for non-monotonic logics
• Ground Nonmonotonic Modal Logics
• The complexity of logic-based abduction
• Complexity results for abductive logic programming
• Abductive Logic Programming