What makes propositional abduction tractable
DOI10.1016/J.ARTINT.2008.02.001zbMATH Open1183.68600OpenAlexW2113666441MaRDI QIDQ2389658FDOQ2389658
Authors: 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
Recommendations
Reasoning under uncertainty in the context of artificial intelligence (68T37) Other nonclassical logic (03B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Logic in artificial intelligence (68T27)
Cites Work
- Consequence finding algorithms
- Title not available (Why is that?)
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Title not available (Why is that?)
- 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 satisfiability problems
- Knowledge compilation and theory approximation
- Closed systems of functions and predicates
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- Structure identification of Boolean relations and plain bases for co-clones
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Reasoning with models
- On Cores and Prime Implicants of Truth Functions
- The computational complexity of abduction
- Preprocessing of intractable problems
- Title not available (Why is that?)
- Semantics and complexity of abduction from default theories
- On computing all abductive explanations from a propositional Horn theory
- The complexity of logic-based abduction
- Logic for Programming, Artificial Intelligence, and Reasoning
- Horn approximations of empirical data
- Title not available (Why is that?)
- A Complete Classification of the Complexity of Propositional Abduction
- Abduction in logic programming: A new definition and an abductive procedure based on rewriting
- Bases for Boolean co-clones
- Complexity of Default Logic on Generalized Conjunctive Queries
- Hypothesis generation by machine
- Abduction from logic programs: Semantics and complexity
- On some tractable classes in deduction and abduction
- Counting complexity of propositional abduction
- Compilability of propositional abduction
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reasoning with ordered binary decision diagrams
Cited In (20)
- The ghosts of forgotten things: a study on size after forgetting
- Computer Science Logic
- Compilability of propositional abduction
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- Propensity and probability in depositional facies analysis and modeling
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Reasoning with ordered binary decision diagrams
- Parameterized complexity of abduction in Schaefer's framework
- Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
- Complexity Classifications for Logic-Based Argumentation
- Title not available (Why is that?)
- A Complete Classification of the Complexity of Propositional Abduction
- On the complexity of second-best abductive explanations
- Counting complexity of propositional abduction
- Title not available (Why is that?)
- Semantics and complexity of abduction from default theories
- Complexity classifications for propositional abduction in Post's framework
- Title not available (Why is that?)
- Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework
This page was built for publication: What makes propositional abduction tractable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389658)
