On the complexity of second-best abductive explanations

DOI10.1016/J.IJAR.2015.05.009MaRDI QIDQ899129zbMATH OpenOpenAlexFDO

Authors Paolo Liberatore, Marco Schaerf

Publication date 21 December 2015

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5859

zbMATH Keywords

abductionpropositional logicknowledge-based systemsknowledge representation techniques

Mathematics Subject Classification ID

Knowledge representation (68T30) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Logic in artificial intelligence (68T27)

Abstract: While looking for abductive explanations of a given set of manifestations, an ordering between possible solutions is often assumed. The complexity of finding/verifying optimal solutions is already known. In this paper we consider the computational complexity of finding second-best solutions. We consider different orderings, and consider also different possible definitions of what a second-best solution is.

Recommendations

• The complexity of logic-based abduction
• scientific article; zbMATH DE number 512816
• Complexity results for abductive logic programming
• scientific article; zbMATH DE number 4166861
• What makes propositional abduction tractable

Cites work

• scientific article; zbMATH DE number 4166861 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• scientific article; zbMATH DE number 877749 (Why is no real title available?)
• A Complete Classification of the Complexity of Propositional Abduction
• Abduction from logic programs: Semantics and complexity
• Complexity classifications for propositional abduction in Post's framework
• Computational Complexity
• Computer Science Logic
• Counting complexity of propositional abduction
• Monotonic reductions, representative equivalence, and compilation of intractable problems
• On some tractable classes in deduction and abduction
• On the complexity of second-best abductive explanations
• Preprocessing of intractable problems
• Semantics and complexity of abduction from default theories
• Support set selection for abductive and default reasoning
• The complexity of logic-based abduction
• The computational complexity of abduction
• What makes propositional abduction tractable

Cited in

(1)

• On the complexity of second-best abductive explanations

This page was built for publication: On the complexity of second-best abductive explanations

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