Skip to Main content Skip to Navigation
New interface
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 Connect in order to contact the contributor
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 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⟩

Share

Metrics

Record views

36

Files downloads

62