Probabilistic Inference and Monadic Second Order Logic

Abstract : This paper combines two classic results from two different fields: the result by Lauritzen and Spiegelhalter [21] that the probabilistic inference problem on probabilistic networks can be solved in linear time on networks with a moralization of bounded treewidth, and the result by Courcelle [10] that problems that can be formulated in counting monadic second order logic can be solved in linear time on graphs of bounded treewidth. It is shown that, given a probabilistic network whose moralization has bounded treewidth and a property P of the network and the values of the variables that can be formulated in counting monadic second order logic, one can determine in linear time the probability that P holds.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.43-56, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_4〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556214
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:38
Dernière modification le : mardi 4 juillet 2017 - 17:47:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 02:31:26

Fichier

978-3-642-33475-7_4_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Hans Bodlaender. Probabilistic Inference and Monadic Second Order Logic. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.43-56, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_4〉. 〈hal-01556214〉

Partager

Métriques

Consultations de la notice

27

Téléchargements de fichiers

21