Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01556214
Contributor : Hal Ifip <>
Submitted on : Tuesday, July 4, 2017 - 5:45:38 PM
Last modification on : Tuesday, August 13, 2019 - 10:16:03 AM
Long-term archiving on: : Friday, December 15, 2017 - 2:31:26 AM

File

978-3-642-33475-7_4_Chapter.pd...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Hans 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⟩

Share

Metrics

Record views

127

Files downloads

386