{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T07:01:47Z","timestamp":1779087707290,"version":"3.51.4"},"publisher-location":"Cham","reference-count":50,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319898834","type":"print"},{"value":"9783319898841","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89884-1_7","type":"book-chapter","created":{"date-parts":[[2018,4,14]],"date-time":"2018-04-14T01:02:32Z","timestamp":1523667752000},"page":"186-213","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["How long, O Bayesian network, will I sample thee?"],"prefix":"10.1007","author":[{"given":"Kevin","family":"Batz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin Lucien","family":"Kaminski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joost-Pieter","family":"Katoen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Matheja","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,4,14]]},"reference":[{"issue":"1","key":"7_CR1","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0169-2070(95)00664-8","volume":"12","author":"B Abramson","year":"1996","unstructured":"Abramson, B., Brown, J., Edwards, W., Murphy, A., Winkler, R.L.: Hailfinder: a Bayesian system for forecasting severe weather. Int. J. Forecast. 12(1), 57\u201371 (1996)","journal-title":"Int. J. Forecast."},{"key":"7_CR2","unstructured":"Andreassen, S., Jensen, F.V., Andersen, S.K., Falck, B., Kj\u00e6rulff, U., Woldbye, M., S\u00f8rensen, A., Rosenfalck, A., Jensen, F.: MUNIN: an expert EMG Assistant. In: Computer-Aided Electromyography and Expert Systems, pp. 255\u2013277. Pergamon Press (1989)"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Batz, K., Kaminski, B.L., Katoen, J., Matheja, C.: How long, O Bayesian network, will I sample thee? arXiv extended version (2018)","DOI":"10.1007\/978-3-319-89884-1_7"},{"key":"7_CR4","volume-title":"Pattern Recognition and Machine Learning","author":"C Bishop","year":"2006","unstructured":"Bishop, C.: Pattern Recognition and Machine Learning. Springer, New York (2006)"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-32033-3_24","volume-title":"Term Rewriting and Applications","author":"O Bournez","year":"2005","unstructured":"Bournez, O., Garnier, F.: Proving positive almost-sure termination. In: Giesl, J. (ed.) RTA 2005. LNCS, vol. 3467, pp. 323\u2013337. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/978-3-540-32033-3_24"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/j.jcss.2014.06.005","volume":"81","author":"T Br\u00e1zdil","year":"2015","unstructured":"Br\u00e1zdil, T., Kiefer, S., Kucera, A., Varekov\u00e1, I.H.: Runtime analysis of probabilistic programs with unbounded recursion. J. Comput. Syst. Sci. 81(1), 288\u2013310 (2015)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/11526841_9","volume-title":"FM 2005: Formal Methods","author":"O Celiku","year":"2005","unstructured":"Celiku, O., McIver, A.: Compositional specification and analysis of cost-based properties in probabilistic programs. In: Fitzgerald, J., Hayes, I.J., Tarlecki, A. (eds.) FM 2005. LNCS, vol. 3582, pp. 107\u2013122. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11526841_9"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/978-3-642-39799-8_34","volume-title":"Computer Aided Verification","author":"A Chakarov","year":"2013","unstructured":"Chakarov, A., Sankaranarayanan, S.: Probabilistic program analysis with martingales. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 511\u2013526. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39799-8_34"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Fu, H., Novotn\u00fd, P., Hasheminezhad, R.: Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. In: POPL, pp. 327\u2013342. ACM (2016)","DOI":"10.1145\/2914770.2837639"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Novotn\u00fd, P., Zikelic, D.: Stochastic invariants for probabilistic termination. In: POPL, pp. 145\u2013160. ACM (2017)","DOI":"10.1145\/3093333.3009873"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.knosys.2012.07.008","volume":"36","author":"AC Constantinou","year":"2012","unstructured":"Constantinou, A.C., Fenton, N.E., Neil, M.: pi-football: a Bayesian network model for forecasting association football match outcomes. Knowl. Based Syst. 36, 322\u2013339 (2012)","journal-title":"Knowl. Based Syst."},{"issue":"2\u20133","key":"7_CR12","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0004-3702(90)90060-D","volume":"42","author":"GF Cooper","year":"1990","unstructured":"Cooper, G.F.: The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intell. 42(2\u20133), 393\u2013405 (1990)","journal-title":"Artif. Intell."},{"issue":"1","key":"7_CR13","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0004-3702(93)90036-B","volume":"60","author":"P Dagum","year":"1993","unstructured":"Dagum, P., Luby, M.: Approximating probabilistic inference in Bayesian belief networks is NP-hard. Artif. Intell. 60(1), 141\u2013153 (1993)","journal-title":"Artif. Intell."},{"issue":"8","key":"7_CR14","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/360933.360975","volume":"18","author":"EW Dijkstra","year":"1975","unstructured":"Dijkstra, E.W.: Guarded commands, nondeterminacy and formal derivation of programs. Commun. ACM 18(8), 453\u2013457 (1975)","journal-title":"Commun. ACM"},{"key":"7_CR15","volume-title":"A Discipline of Programming","author":"EW Dijkstra","year":"1976","unstructured":"Dijkstra, E.W.: A Discipline of Programming. Prentice-Hall, Upper Saddle River (1976)"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1462153.1462154","volume":"56","author":"K Etessami","year":"2009","unstructured":"Etessami, K., Yannakakis, M.: Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. JACM 56(1), 1:1\u20131:66 (2009)","journal-title":"JACM"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Fioriti, L.M.F., Hermanns, H.: Probabilistic termination: soundness, completeness, and compositionality. In: POPL, pp. 489\u2013501. ACM (2015)","DOI":"10.1145\/2676726.2677001"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Friedman, N., Linial, M., Nachman, I., Pe\u2019er, D.: Using Bayesian networks to analyze expression data. In: RECOMB, pp. 127\u2013135. ACM (2000)","DOI":"10.1145\/332306.332355"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1007\/978-3-319-40229-1_37","volume-title":"Automated Reasoning","author":"F Frohn","year":"2016","unstructured":"Frohn, F., Naaf, M., Hensel, J., Brockschmidt, M., Giesl, J.: Lower runtime bounds for integer programs. In: Olivetti, N., Tiwari, A. (eds.) IJCAR 2016. LNCS (LNAI), vol. 9706, pp. 550\u2013567. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40229-1_37"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Goodman, N.D.: The principles and practice of probabilistic programming. In: POPL, pp. 399\u2013402. ACM (2013)","DOI":"10.1145\/2429069.2429117"},{"key":"7_CR21","unstructured":"Goodman, N.D., Mansinghka, V.K., Roy, D.M., Bonawitz, K., Tenenbaum, J.B.: Church: A language for generative models. In: UAI, pp. 220\u2013229. AUAI Press (2008)"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Gordon, A.D., Graepel, T., Rolland, N., Russo, C.V., Borgstr\u00f6m, J., Guiver, J.: Tabular: a schema-driven probabilistic programming language. In: POPL, pp. 321\u2013334. ACM (2014)","DOI":"10.1145\/2535838.2535850"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Gordon, A.D., Henzinger, T.A., Nori, A.V., Rajamani, S.K.: Probabilistic programming. In: Future of Software Engineering, pp. 167\u2013181. ACM (2014)","DOI":"10.1145\/2593882.2593900"},{"key":"7_CR24","series-title":"Studies in Computational Intelligence","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-540-85066-3_3","volume-title":"Innovations in Bayesian Networks","author":"D Heckerman","year":"2008","unstructured":"Heckerman, D.: A tutorial on learning with Bayesian networks. In: Holmes, D.E., Jain, L.C. (eds.) Innovations in Bayesian Networks. Studies in Computational Intelligence, vol. 156, pp. 33\u201382. Springer, Heidelberg (2008)"},{"issue":"4","key":"7_CR25","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00165-010-0157-0","volume":"23","author":"ECR Hehner","year":"2011","unstructured":"Hehner, E.C.R.: A probability perspective. Formal Aspects Comput. 23(4), 391\u2013419 (2011)","journal-title":"Formal Aspects Comput."},{"issue":"1","key":"7_CR26","first-page":"1593","volume":"15","author":"MD Hoffman","year":"2014","unstructured":"Hoffman, M.D., Gelman, A.: The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res. 15(1), 1593\u20131623 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"7_CR27","first-page":"462","volume":"17","author":"X Jiang","year":"2010","unstructured":"Jiang, X., Cooper, G.F.: A Bayesian spatio-temporal method for disease outbreak detection. JAMIA 17(4), 462\u2013471 (2010)","journal-title":"JAMIA"},{"key":"7_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-662-48057-1_24","volume-title":"Mathematical Foundations of Computer Science 2015","author":"BL Kaminski","year":"2015","unstructured":"Kaminski, B.L., Katoen, J.-P.: On the hardness of almost\u2013sure termination. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9234, pp. 307\u2013318. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48057-1_24"},{"key":"7_CR29","doi-asserted-by":"crossref","unstructured":"Kaminski, B.L., Katoen, J.: A weakest pre-expectation semantics for mixed-sign expectations. In: LICS (2017)","DOI":"10.1109\/LICS.2017.8005153"},{"key":"7_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-662-49498-1_15","volume-title":"Programming Languages and Systems","author":"BL Kaminski","year":"2016","unstructured":"Kaminski, B.L., Katoen, J.-P., Matheja, C., Olmedo, F.: Weakest precondition reasoning for expected run\u2013times of probabilistic programs. In: Thiemann, P. (ed.) ESOP 2016. LNCS, vol. 9632, pp. 364\u2013389. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49498-1_15"},{"key":"7_CR31","volume-title":"Probabilistic Graphical Models - Principles and Techniques","author":"D Koller","year":"2009","unstructured":"Koller, D., Friedman, N.: Probabilistic Graphical Models - Principles and Techniques. MIT Press, Cambridge (2009)"},{"issue":"3","key":"7_CR32","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/0022-0000(81)90036-2","volume":"22","author":"D Kozen","year":"1981","unstructured":"Kozen, D.: Semantics of probabilistic programs. J. Comput. Syst. Sci. 22(3), 328\u2013350 (1981)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"7_CR33","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/0022-0000(85)90012-1","volume":"30","author":"D Kozen","year":"1985","unstructured":"Kozen, D.: A probabilistic PDL. J. Comput. Syst. Sci. 30(2), 162\u2013178 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"7_CR34","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/0020-0190(82)90065-5","volume":"14","author":"JL Lassez","year":"1982","unstructured":"Lassez, J.L., Nguyen, V.L., Sonenberg, L.: Fixed point theorems and semantics: a folk tale. Inf. Process. Lett. 14(3), 112\u2013116 (1982)","journal-title":"Inf. Process. Lett."},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"McIver, A., Morgan, C.: Abstraction, Refinement and Proof for Probabilistic Systems. Springer, New York (2004). http:\/\/doi.org\/10.1007\/b138392","DOI":"10.1007\/b138392"},{"key":"7_CR36","unstructured":"Minka, T., Winn, J.: Infer.NET (2017). http:\/\/infernet.azurewebsites.net\/ . Accessed Oct 17"},{"key":"7_CR37","unstructured":"Minka, T., Winn, J.M.: Gates. In: NIPS, pp. 1073\u20131080. Curran Associates (2008)"},{"key":"7_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-47764-0_7","volume-title":"Static Analysis","author":"D Monniaux","year":"2001","unstructured":"Monniaux, D.: An abstract analysis of the probabilistic termination of programs. In: Cousot, P. (ed.) SAS 2001. LNCS, vol. 2126, pp. 111\u2013126. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-47764-0_7"},{"key":"7_CR39","volume-title":"Probabilistic Methods for Financial and Marketing Informatics","author":"RE Neapolitan","year":"2010","unstructured":"Neapolitan, R.E., Jiang, X.: Probabilistic Methods for Financial and Marketing Informatics. Morgan Kaufmann, Burlington (2010)"},{"key":"7_CR40","doi-asserted-by":"crossref","unstructured":"Nori, A.V., Hur, C., Rajamani, S.K., Samuel, S.: R2: an efficient MCMC sampler for probabilistic programs. In: AAAI, pp. 2476\u20132482. AAAI Press (2014)","DOI":"10.1609\/aaai.v28i1.9060"},{"key":"7_CR41","doi-asserted-by":"crossref","unstructured":"Olmedo, F., Kaminski, B.L., Katoen, J., Matheja, C.: Reasoning about recursive probabilistic programs. In: LICS, pp. 672\u2013681. ACM (2016)","DOI":"10.1145\/2933575.2935317"},{"key":"7_CR42","unstructured":"Onisko, A., Druzdzel, M.J., Wasyluk, H.: A probabilistic causal model for diagnosis of liver disorders. In: Proceedings of the Seventh International Symposium on Intelligent Information Systems (IIS-98), pp. 379\u2013387 (1998)"},{"key":"7_CR43","unstructured":"Pearl, J.: Bayesian networks: a model of self-activated memory for evidential reasoning. In: Proceedings of CogSci, pp. 329\u2013334 (1985)"},{"key":"7_CR44","unstructured":"Pfeffer, A.: Figaro: an object-oriented probabilistic programming language. Charles River Analytics Technical Report 137, 96 (2009)"},{"key":"7_CR45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28699-5","volume-title":"Emerging Paradigms in Machine Learning","author":"S Ramanna","year":"2013","unstructured":"Ramanna, S., Jain, L.C., Howlett, R.J.: Emerging Paradigms in Machine Learning. Springer, Heidelberg (2013)"},{"key":"7_CR46","unstructured":"Scutari, M.: Bayesian Network Repository (2017). http:\/\/www.bnlearn.com"},{"issue":"2","key":"7_CR47","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1137\/0213021","volume":"13","author":"M Sharir","year":"1984","unstructured":"Sharir, M., Pnueli, A., Hart, S.: Verification of probabilistic programs. SIAM J. Comput. 13(2), 292\u2013314 (1984)","journal-title":"SIAM J. Comput."},{"key":"7_CR48","unstructured":"Wood, F., van de Meent, J., Mansinghka, V.: A new approach to probabilistic programming inference. In: JMLR Workshop and Conference Proceedings, AISTATS, vol. 33, pp. 1024\u20131032 (2014). JMLR.org"},{"issue":"9\u201310","key":"7_CR49","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.mcm.2005.05.020","volume":"43","author":"C Yuan","year":"2006","unstructured":"Yuan, C., Druzdzel, M.J.: Importance sampling algorithms for Bayesian networks: principles and performance. Math. Comput. Model. 43(9\u201310), 1189\u20131207 (2006)","journal-title":"Math. Comput. Model."},{"key":"7_CR50","unstructured":"Zweig, G., Russell, S.J.: Speech recognition with dynamic Bayesian networks. In: AAAI\/IAAI, pp. 173\u2013180. AAAI Press\/The MIT Press (1998)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89884-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,19]],"date-time":"2022-08-19T16:13:46Z","timestamp":1660925626000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-89884-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319898834","9783319898841"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89884-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}