What makes propositional abduction tractable

DOI10.1016/J.ARTINT.2008.02.001zbMath1183.68600OpenAlexW2113666441MaRDI QIDQ2389658

Gustav Nordh, Bruno Zanuttini

Publication date: 17 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.artint.2008.02.001

zbMATH Keywords

computational complexitypropositional logicabduction

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Logic in artificial intelligence (68T27) Reasoning under uncertainty in the context of artificial intelligence (68T37) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs ⋮ Propensity and probability in depositional facies analysis and modeling ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework ⋮ On the complexity of second-best abductive explanations ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Unnamed Item ⋮ Counting complexity of propositional abduction ⋮ The ghosts of forgotten things: a study on size after forgetting ⋮ The union of minimal hitting sets: parameterized combinatorial bounds and counting ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure identification of Boolean relations and plain bases for co-clones
• Counting complexity of propositional abduction
• Bases for Boolean co-clones
• The computational complexity of abduction
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Abduction from logic programs: Semantics and complexity
• Semantics and complexity of abduction from default theories
• Abduction in logic programming: A new definition and an abductive procedure based on rewriting
• Preprocessing of intractable problems
• Horn approximations of empirical data
• Reasoning with ordered binary decision diagrams
• On some tractable classes in deduction and abduction
• Closed systems of functions and predicates
• Hypothesis generation by machine
• Reasoning with models
• On computing all abductive explanations from a propositional Horn theory
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of logic-based abduction
• Knowledge compilation and theory approximation
• Compilability of propositional abduction
• The complexity of satisfiability problems
• Complexity of Default Logic on Generalized Conjunctive Queries
• A Complete Classification of the Complexity of Propositional Abduction
• On Cores and Prime Implicants of Truth Functions
• Logic for Programming, Artificial Intelligence, and Reasoning
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

This page was built for publication: What makes propositional abduction tractable