Probabilistic inference and monadic second order logic

Marijke Hans L. Bodlaender

doi:10.1007/978-3-642-33475-7_4

Probabilistic inference and monadic second order logic

Marijke Hans L. Bodlaender

Algorithms

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

1 Citaat (Scopus)

2 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings
Redacteuren	J.C.M. Baeten, T. Ball, F.S. de Boer
Uitgeverij	Springer
Pagina's	43-56
Aantal pagina's	14
ISBN van elektronische versie	978-3-642-33475-7
ISBN van geprinte versie	9783642334740
DOI's	https://doi.org/10.1007/978-3-642-33475-7_4
Status	Gepubliceerd - 2012
Evenement	7th IFIP International Conference on Theoretical Computer Science (TCS 2012) - Amsterdam, Nederland Duur: 26 sep. 2012 → 28 sep. 2012 Congresnummer: 7

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7604 LNCS
ISSN van geprinte versie	03029743
ISSN van elektronische versie	16113349

Congres

Congres	7th IFIP International Conference on Theoretical Computer Science (TCS 2012)
Verkorte titel	TCS 2012
Land/Regio	Nederland
Stad	Amsterdam
Periode	26/09/12 → 28/09/12

Toegang tot document

10.1007/978-3-642-33475-7_4

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Bodlaender, M. H. L. (2012). Probabilistic inference and monadic second order logic. In J. C. M. Baeten, T. Ball, & F. S. de Boer (editors), Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings (blz. 43-56). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7604 LNCS). Springer. https://doi.org/10.1007/978-3-642-33475-7_4

Bodlaender, Marijke Hans L. / Probabilistic inference and monadic second order logic. Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings. redacteur / J.C.M. Baeten ; T. Ball ; F.S. de Boer. Springer, 2012. blz. 43-56 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f0ae8878c7b249dba6ebc1e98f84afe9,

title = "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.",

author = "Bodlaender, \{Marijke Hans L.\}",

year = "2012",

doi = "10.1007/978-3-642-33475-7\_4",

language = "English",

isbn = "9783642334740",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "43--56",

editor = "J.C.M. Baeten and T. Ball and \{de Boer\}, F.S.",

booktitle = "Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings",

address = "Germany",

note = "7th IFIP International Conference on Theoretical Computer Science (TCS 2012), TCS 2012 ; Conference date: 26-09-2012 Through 28-09-2012",

}

Bodlaender, MHL 2012, Probabilistic inference and monadic second order logic. in JCM Baeten, T Ball & FS de Boer (reds.), Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7604 LNCS, Springer, blz. 43-56, 7th IFIP International Conference on Theoretical Computer Science (TCS 2012), Amsterdam, Nederland, 26/09/12. https://doi.org/10.1007/978-3-642-33475-7_4

Probabilistic inference and monadic second order logic. / Bodlaender, Marijke Hans L.
Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings. reds. / J.C.M. Baeten; T. Ball; F.S. de Boer. Springer, 2012. blz. 43-56 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7604 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Probabilistic inference and monadic second order logic

AU - Bodlaender, Marijke Hans L.

N1 - Conference code: 7

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84866943776

U2 - 10.1007/978-3-642-33475-7_4

DO - 10.1007/978-3-642-33475-7_4

M3 - Conference contribution

AN - SCOPUS:84866943776

SN - 9783642334740

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

SP - 43

EP - 56

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

A2 - Baeten, J.C.M.

A2 - Ball, T.

A2 - de Boer, F.S.

PB - Springer

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

Y2 - 26 September 2012 through 28 September 2012

ER -

Bodlaender MHL. Probabilistic inference and monadic second order logic. In Baeten JCM, Ball T, de Boer FS, redacteurs, Theoretical Computer Science : 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012 : Proceedings. Springer. 2012. blz. 43-56. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-33475-7_4

Probabilistic inference and monadic second order logic

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit