{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:25Z","timestamp":1753894405124,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Markov chains are the de facto finite-state model for stochastic dynamical\nsystems, and Markov decision processes (MDPs) extend Markov chains by\nincorporating non-deterministic behaviors. Given an MDP and rewards on states,\na classical optimization criterion is the maximal expected total reward where\nthe MDP stops after T steps, which can be computed by a simple dynamic\nprogramming algorithm. We consider a natural generalization of the problem\nwhere the stopping times can be chosen according to a probability distribution,\nsuch that the expected stopping time is T, to optimize the expected total\nreward. Quite surprisingly we establish inter-reducibility of the expected\nstopping-time problem for Markov chains with the Positivity problem (which is\nrelated to the well-known Skolem problem), for which establishing either\ndecidability or undecidability would be a major breakthrough. Given the\nhardness of the exact problem, we consider the approximate version of the\nproblem: we show that it can be solved in exponential time for Markov chains\nand in exponential space for MDPs.<\/jats:p>","DOI":"10.46298\/lmcs-20(4:11)2024","type":"journal-article","created":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T10:10:12Z","timestamp":1731406212000},"source":"Crossref","is-referenced-by-count":0,"title":["Stochastic Processes with Expected Stopping Time"],"prefix":"10.46298","volume":"Volume 20, Issue 4","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Laurent","family":"Doyen","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,11,12]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/14723\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/14723\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,12]],"date-time":"2024-11-12T10:10:13Z","timestamp":1731406213000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,12]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(4:11)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2104.07278v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2104.07278v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2104.07278","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2104.07278","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2024,11,12]]},"article-number":"9700"}}