Probabilistic inference and monadic second order logic

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publicationTheoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings
EditorsJ.C.M. Baeten, T. Ball, F.S. de Boer
PublisherSpringer
Pages43-56
Number of pages14
ISBN (Electronic)978-3-642-33475-7
ISBN (Print)9783642334740
DOIs
Publication statusPublished - 2012
Event7th IFIP International Conference on Theoretical Computer Science (TCS 2012) - Amsterdam, Netherlands
Duration: 26 Sep 201228 Sep 2012
Conference number: 7

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7604 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference7th IFIP International Conference on Theoretical Computer Science (TCS 2012)
Abbreviated titleTCS 2012
CountryNetherlands
CityAmsterdam
Period26/09/1228/09/12

Fingerprint

Dive into the research topics of 'Probabilistic inference and monadic second order logic'. Together they form a unique fingerprint.

Cite this