%0 Conference Proceedings
%T Probabilistic Inference and Monadic Second Order Logic
%+ Universiteit Utrecht / Utrecht University [Utrecht]
%A Bodlaender, Hans, L.
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 7th International Conference on Theoretical Computer Science (TCS)
%C Amsterdam, Netherlands
%Y Jos C. M. Baeten
%Y Tom Ball
%Y Frank S. Boer
%I Springer
%3 Theoretical Computer Science
%V LNCS-7604
%P 43-56
%8 2012-09-26
%D 2012
%R 10.1007/978-3-642-33475-7_4
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://inria.hal.science/hal-01556214/document
%2 https://inria.hal.science/hal-01556214/file/978-3-642-33475-7_4_Chapter.pdf
%L hal-01556214
%U https://inria.hal.science/hal-01556214
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-TC2
%~ IFIP-TCS
%~ IFIP-WG2-2
%~ IFIP-LNCS-7604