## 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 language | English |
---|---|

Title of host publication | Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings |

Editors | J.C.M. Baeten, T. Ball, F.S. de Boer |

Publisher | Springer |

Pages | 43-56 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-642-33475-7 |

ISBN (Print) | 9783642334740 |

DOIs | |

Publication status | Published - 2012 |

Event | 7th IFIP International Conference on Theoretical Computer Science (TCS 2012) - Amsterdam, Netherlands Duration: 26 Sep 2012 → 28 Sep 2012 Conference number: 7 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7604 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | 7th IFIP International Conference on Theoretical Computer Science (TCS 2012) |
---|---|

Abbreviated title | TCS 2012 |

Country | Netherlands |

City | Amsterdam |

Period | 26/09/12 → 28/09/12 |