{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T10:39:33Z","timestamp":1770287973825,"version":"3.49.0"},"reference-count":63,"publisher":"IEEE","license":[{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T00:00:00Z","timestamp":1559347200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1109\/lics.2019.8785679","type":"proceedings-article","created":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T01:15:55Z","timestamp":1565054155000},"page":"1-14","source":"Crossref","is-referenced-by-count":9,"title":["On the Termination Problem for Probabilistic Higher-Order Recursive Programs"],"prefix":"10.1109","author":[{"given":"Naoki","family":"Kobayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ugo","family":"Dal Lago","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charles","family":"Grellois","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.015"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45413-6_21"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480933"},{"key":"ref32","first-page":"325","article-title":"On the lambdaY calculus","volume":"130","author":"statman","year":"2004","journal-title":"APAL"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1109\/QEST.2005.8"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45931-6_15"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1145\/2159531.2159534"},{"key":"ref36","article-title":"Complexity of model checking recursion schemes for fragments of the modal mu-calculus","volume":"7","author":"kobayashi","year":"2011","journal-title":"LMCS"},{"key":"ref35","article-title":"On the termination problem for probabilistic higher-order recursive programs","volume":"abs 1811 2133","author":"kobayashi","year":"2018","journal-title":"CoRR"},{"key":"ref34","author":"matiyasevich","year":"1993","journal-title":"Hilbert's Tenth Problem"},{"key":"ref60","article-title":"Inclusion between the frontier language of a nondeterministic recursive program scheme and the Dyck language is undecidable","author":"kobayashi","year":"2019","journal-title":"to appear in TCS special issue in memory of Maurice Nivat"},{"key":"ref62","author":"jagannathan","year":"2014","journal-title":"POPL 2014"},{"key":"ref61","first-page":"527","article-title":"Probabilistic automata on finite words: Decidable and undecidable problems","volume":"6199","author":"gimbert","year":"2010","journal-title":"ICALP 2010 ser LNCS"},{"key":"ref63","volume":"9234","author":"italiano","year":"2015","journal-title":"MFCS 2015 ser LNCS"},{"key":"ref28","first-page":"333","article-title":"Automated random testing in multiple dispatch languages","author":"poulding","year":"2017","journal-title":"ICST 2017"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54434-1_15"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1145\/3242744.3242747"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-010"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/2487241.2487246"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993525"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.29"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_20"},{"key":"ref23","first-page":"260","article-title":"Relational semantics of linear logic and higher-order model checking","volume":"41","author":"grellois","year":"2015","journal-title":"CSL 2015 ser LIPIcs"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_12"},{"key":"ref25","first-page":"78: 1","article-title":"Compositional higher-order model checking via ?-regular games over Böhm trees","author":"tsukada","year":"2014","journal-title":"CSL-LICS 2014"},{"key":"ref50","first-page":"525","article-title":"Seman-tics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints","author":"staton","year":"2016","journal-title":"LICS 2016"},{"key":"ref51","first-page":"669","article-title":"Boolean-valued semantics for the stochastic ?-calculus","author":"bacci","year":"2018","journal-title":"LICS 2018"},{"key":"ref59","article-title":"On intersection types and probabilistic lambda calculi","author":"breuvart","year":"2018","journal-title":"PPDP 2018"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129503004122"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/237721.240882"},{"key":"ref56","first-page":"1024","article-title":"A new approach to probabilistic programming inference","volume":"33","author":"wood","year":"2014","journal-title":"Int Conf on Artificial Intelligence and Statistics ser Proc of Machine Learning Research"},{"key":"ref55","first-page":"220","article-title":"Church: A language for generative models","author":"goodman","year":"2008","journal-title":"UAI"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/11539452_15"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837651"},{"key":"ref52","first-page":"209","article-title":"On probabilistic applicative bisimulation and call-by-value A-calculi","volume":"8410","author":"crubill\u00e9","year":"2014","journal-title":"ESOP 2014 ser LNCS"},{"key":"ref10","first-page":"297","article-title":"On coinductive equivalences for higher-order probabilistic functional programs","author":"dal lago","year":"2014","journal-title":"POPL 2014"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005137"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"ref12","author":"baier","year":"2008","journal-title":"Principles of Model Checking"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10575-8"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1462153.1462154"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2699431"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-012-0166-0"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.07.001"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.38"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2008.34"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1969-0249221-4"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"ref6","first-page":"442","article-title":"Probabilistic LCF","volume":"64","author":"saheb-djahromi","year":"1978","journal-title":"MFCS 1978 ser LNCS"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2012012"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/507382.507385"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1989.39173"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(05)80216-6"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535865"},{"key":"ref46","first-page":"132","article-title":"On probabilistic term rewriting","volume":"10818","author":"avanzini","year":"2018","journal-title":"FLOPS 2018 ser LNCS"},{"key":"ref45","first-page":"33: 1","article-title":"A new proof rule for almost-sure termination","author":"mciver","year":"2018","journal-title":"POPL 2018"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_24"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_34"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31424-7_14"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32033-3_24"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009873"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677001"}],"event":{"name":"2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)","location":"Vancouver, BC, Canada","start":{"date-parts":[[2019,6,24]]},"end":{"date-parts":[[2019,6,27]]}},"container-title":["2019 34th Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/8765678\/8785654\/08785679.pdf?arnumber=8785679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,19]],"date-time":"2022-07-19T20:18:53Z","timestamp":1658261933000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8785679\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6]]},"references-count":63,"URL":"https:\/\/doi.org\/10.1109\/lics.2019.8785679","relation":{},"subject":[],"published":{"date-parts":[[2019,6]]}}}