{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:03:51Z","timestamp":1725455031708},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642334740"},{"type":"electronic","value":"9783642334757"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33475-7_4","type":"book-chapter","created":{"date-parts":[[2012,9,8]],"date-time":"2012-09-08T06:43:09Z","timestamp":1347086589000},"page":"43-56","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic Inference and Monadic Second Order Logic"],"prefix":"10.1007","author":[{"given":"Marijke Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","volume":"208","author":"H.L. Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations I. Upper bounds. Information and Computation\u00a0208, 259\u2013275 (2010)","journal-title":"Information and Computation"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"1103","DOI":"10.1016\/j.ic.2011.04.003","volume":"209","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Treewidth computations II. Lower bounds. Information and Computation\u00a0209, 1103\u20131119 (2011)","journal-title":"Information and Computation"},{"key":"4_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics\u00a06, 181\u2013188 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/inco.2000.2958","volume":"167","author":"H.L. Bodlaender","year":"2001","unstructured":"Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Reduction algorithms for graphs of small treewidth. Information and Computation\u00a0167, 86\u2013119 (2001)","journal-title":"Information and Computation"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R.B. Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica\u00a07, 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Solving problems on recursively constructed graphs. ACM Computing Surveys\u00a041(4) (2008)","DOI":"10.1145\/1456650.1456654"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation\u00a085, 12\u201375 (1990)","journal-title":"Information and Computation"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-22256-6_24","volume-title":"Implementation and Application of Automata","author":"B. Courcelle","year":"2011","unstructured":"Courcelle, B., Durand, I.A.: Fly-Automata, Their Properties and Applications. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol.\u00a06807, pp. 264\u2013272. Springer, Heidelberg (2011)"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science\u00a0109, 49\u201382 (1993)","journal-title":"Theoretical Computer Science"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Computing pure Nash equilibria in graphical games via Markov random fields. In: Feigenbaum, J., Chuang, J.C.-I., Pennock, D.M. (eds.) Proceedings 7th ACM Conference on Electronic Commerce EC-2006, pp. 91\u201399. ACM (2006)","DOI":"10.1145\/1134707.1134718"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Elberfeld, M., Jakoby, A., Tantau, T.: Logspace versions of the theorems of Bodlaender and Courcelle, pp. 143\u2013152 (2010)","DOI":"10.1109\/FOCS.2010.21"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 520\u2013525 (1989)","DOI":"10.1109\/SFCS.1989.63528"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Jensen, F.V., Nielsen, T.D.: Bayesian Networks and Decision Graphs, 2nd edn. Information Science and Statistics. Springer (2007)","DOI":"10.1007\/978-0-387-68282-2"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/3-540-63165-8_233","volume-title":"Automata, Languages and Programming","author":"V. Kabanets","year":"1997","unstructured":"Kabanets, V.: Recognizability Equals Definability for Partial k-paths. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 805\u2013815. Springer, Heidelberg (1997)"},{"key":"4_CR18","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s004530010024","volume":"27","author":"D. Kaller","year":"2000","unstructured":"Kaller, D.: Definability equals recognizability of partial 3-trees and k-connected partial k-trees. Algorithmica\u00a027, 348\u2013381 (2000)","journal-title":"Algorithmica"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth. Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1002\/net.10046","volume":"40","author":"A.M.C.A. Koster","year":"2002","unstructured":"Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks\u00a040(3), 170\u2013180 (2002)","journal-title":"Networks"},{"key":"4_CR21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","volume":"50","author":"S.J. Lauritzen","year":"1988","unstructured":"Lauritzen, S.J., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. The Journal of the Royal Statistical Society. Series B (Methodological)\u00a050, 157\u2013224 (1988)","journal-title":"The Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"4_CR22","volume-title":"Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"J. Pearl","year":"1988","unstructured":"Pearl, J.: Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Palo Alto (1988)"},{"key":"4_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"4_CR24","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","volume":"82","author":"D. Roth","year":"1996","unstructured":"Roth, D.: On the hardness of approximate reasoning. Artificial Intelligence\u00a082, 273\u2013302 (1996)","journal-title":"Artificial Intelligence"},{"key":"4_CR25","unstructured":"van der Gaag, L.C.: Probability-Based Models for Plausible Reasoning. PhD thesis, University of Amsterdam (1990)"},{"key":"4_CR26","unstructured":"Wimer, T.V.: Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Computer Science, Clemson University (1987)"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33475-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T08:43:17Z","timestamp":1557218597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33475-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642334740","9783642334757"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33475-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}