The complexity of logic-based abduction

DOI10.1145/200836.200838zbMath0886.68121OpenAlexW2100657934WikidataQ59259763 ScholiaQ59259763MaRDI QIDQ4369855

Thomas Eiter, Georg Gottlob

Publication date: 2 February 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/200836.200838

zbMATH Keywords

abduction

Mathematics Subject Classification ID

Related Items (62)

Explaining robust additive utility models by sequences of preference swaps ⋮ Reasoning with ordered binary decision diagrams ⋮ A decision method for nonmonotonic reasoning based on autoepistemic reasoning ⋮ An argumentative approach for handling inconsistency in prioritized Datalog ± ontologies ⋮ Propensity and probability in depositional facies analysis and modeling ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ Expressiveness of communication in answer set programming ⋮ Solving abduction by computing joint explanations. Logic programming formalization, applications to P2P data integration, and complexity results ⋮ A split-combination approach to merging knowledge bases in possibilistic logic ⋮ What makes propositional abduction tractable ⋮ Semantic forgetting in answer set programming ⋮ Outlier detection using default reasoning ⋮ Parameterized complexity classes beyond para-NP ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints ⋮ Super-Solutions ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Identifying Efficient Abductive Hypotheses Using Multicriteria Dominance Relation ⋮ Abduction from logic programs: Semantics and complexity ⋮ Morphologic for knowledge dynamics: revision, fusion and abduction ⋮ Outlier detection for simple default theories ⋮ Abductive consequence relations ⋮ On the complexity of second-best abductive explanations ⋮ On look-ahead heuristics in disjunctive logic programming ⋮ Semantics and complexity of abduction from default theories ⋮ Inference to the stable explanations ⋮ Inconsistency-Tolerant Querying of Description Logic Knowledge Bases ⋮ Classical logic, argument and dialectic ⋮ Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results ⋮ Unnamed Item ⋮ Algorithms for generating arguments and counterarguments in propositional logic ⋮ Counting Complexity of Minimal Cardinality and Minimal Weight Abduction ⋮ Solving conflicts in information merging by a flexible interpretation of atomic propositions ⋮ Explanatory relations in arbitrary logics based on satisfaction systems, cutting and retraction ⋮ An extension-based approach to belief revision in abstract argumentation ⋮ Comparing action descriptions based on semantic preferences ⋮ On some tractable classes in deduction and abduction ⋮ On the parameterized complexity of non-monotonic logics ⋮ A semiring-based framework for the deduction/abduction reasoning in access control with weighted credentials ⋮ Belief extrapolation (or how to reason about observations and unpredicted change) ⋮ Unnamed Item ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ A complexity theory for hard enumeration problems ⋮ Counting complexity of propositional abduction ⋮ Algorithms for Effective Argumentation in Classical Propositional Logic: A Connection Graph Approach ⋮ Consistency restoration and explanations in dynamic CSPs---Application to configuration ⋮ Generalized completeness for SOS resolution and its application to a new notion of relevance ⋮ Efficient Reasoning for Inconsistent Horn Formulae ⋮ Dischargeable Obligations in the 𝒮CIFF Framework ⋮ On the complexity of inconsistency measurement ⋮ Encoding deductive argumentation in quantified Boolean formulae ⋮ Succinctness as a source of complexity in logical formalisms ⋮ Prioritized logic programming and its application to commonsense reasoning ⋮ Default reasoning from conditional knowledge bases: Complexity and tractable cases ⋮ The Computational Complexity of Understanding Binary Classifier Decisions ⋮ Conditional independence in propositional logic. ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Semantic relevance ⋮ Ordered binary decision diagrams as knowledge-bases ⋮ Enhancing disjunctive logic programming systems by SAT checkers ⋮ Complexity results for explanations in the structural-model approach ⋮ Approximating cost-based abduction is NP-hard

This page was built for publication: The complexity of logic-based abduction