Probabilistic Inference and Monadic Second Order Logic - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Probabilistic Inference and Monadic Second Order Logic

Résumé

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.
Fichier principal
Vignette du fichier
978-3-642-33475-7_4_Chapter.pdf (533 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01556214 , version 1 (04-07-2017)

Licence

Paternité

Identifiants

Citer

Hans L. Bodlaender. Probabilistic Inference and Monadic Second Order Logic. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.43-56, ⟨10.1007/978-3-642-33475-7_4⟩. ⟨hal-01556214⟩
50 Consultations
66 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More