Counting complexity of propositional abduction

DOI10.1016/J.JCSS.2009.12.001MaRDI QIDQ988576zbMATH OpenOpenAlexFDO

Authors Miki Hermann, Reinhard Pichler

Publication date 18 August 2010

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2009.12.001

zbMATH Keywords

computational complexitycounting complexityHorndual Hornbijunctive formulasdefinite Hornpropositional abduction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Recommendations

• A Complete Classification of the Complexity of Propositional Abduction
• On the counting complexity of propositional circumscription
• scientific article; zbMATH DE number 4166861
• The computational complexity of abduction
• Complexity classifications for propositional abduction in Post's framework
• Compilability of propositional abduction
• scientific article; zbMATH DE number 3954902
• The complexity of logic-based abduction
• scientific article; zbMATH DE number 512816
• scientific article; zbMATH DE number 1390276

Cites work

• scientific article; zbMATH DE number 47350 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2000816 (Why is no real title available?)
• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• A Complete Classification of the Complexity of Propositional Abduction
• Complexity of counting the optimal solutions
• Computer Science Logic
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
• Generalizations of Opt P to the polynomial hierarchy
• Logic Programming and Nonmonotonic Reasoning
• On some tractable classes in deduction and abduction
• Probabilistic Horn abduction and Bayesian networks
• Subtractive reductions and complete problems for counting complexity classes
• The Complexity of Enumeration and Reliability Problems
• The complexity of computing the permanent
• The complexity of logic-based abduction
• The complexity of optimization problems
• The complexity of satisfiability problems
• The computational complexity of abduction
• What makes propositional abduction tractable

Cited in

(6)

• Compilability of propositional abduction
• On the complexity of inconsistency measurement
• What makes propositional abduction tractable
• On the complexity of second-best abductive explanations
• scientific article; zbMATH DE number 6970794 (Why is no real title available?)
• Counting Complexity of Minimal Cardinality and Minimal Weight Abduction

This page was built for publication: Counting complexity of propositional abduction

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