On the complexity of belief network synthesis and refinement

DOI10.1016/0888-613X(92)90007-MMaRDI QIDQ1207964zbMATH OpenOpenAlexFDO

Authors Marco Valtorta, Donald W. Loveland

Publication date 16 May 1993

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

Full work available at URL https://doi.org/10.1016/0888-613x(92)90007-m

zbMATH Keywords

Bayesian networkssynthesisNP-completenessknowledge acquisitionexpert systemsDempster-Shafer theory of evidenceknowledge base refinementbelief netsDempster- Shafer networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35)

Recommendations

• Fusion, propagation, and structuring in belief networks
• Approximating probabilistic inference in Bayesian belief networks is NP- hard
• scientific article; zbMATH DE number 51715
• Belief networks and local computations
• Thirty years of credal networks: specification, algorithms and complexity

Cites work

• scientific article; zbMATH DE number 3786157 (Why is no real title available?)
• scientific article; zbMATH DE number 67614 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• A logic-based analysis of Dempster-Shafer theory
• A method for managing evidential reasoning in a hierarchical hypothesis space: a retrospective
• Adapting connectionist learning to Bayes networks
• Bayesian and non-Bayesian evidential updating
• Belief functions and default reasoning
• Dempster's rule of combination is {\#}P-complete
• Propagating belief functions in qualitative Markov trees
• The computational complexity of probabilistic inference using Bayesian belief networks

Cited in

(3)

• A model for compressing probabilities in belief networks
• Approximating MAPs for belief networks is NP-hard and other theorems
• Knowledge base refinement: A bibliography

This page was built for publication: On the complexity of belief network synthesis and refinement

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