[{"_id":"10004","doi":"10.1109/LICS52264.2021.9470595","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13, doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 1–13. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>.","ista":"Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Symposium on Logic in Computer Science, 1–13.","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13.","ieee":"K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,” in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Rome, Italy, 2021, pp. 1–13.","ama":"Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In: <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Institute of Electrical and Electronics Engineers; 2021:1-13. doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>","apa":"Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). Rome, Italy: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>"},"date_created":"2021-09-12T22:01:25Z","keyword":["Computer science","Heuristic algorithms","Memory management","Automata","Markov processes","Probability distribution","Complexity theory"],"acknowledgement":"We are grateful to the anonymous reviewers of LICS 2021 and of a previous version of this paper for insightful comments that helped improving the presentation. This research was partially supported by the grant ERC CoG 863818 (ForM-SMArt).","year":"2021","ec_funded":1,"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"page":"1-13","department":[{"_id":"KrCh"}],"quality_controlled":"1","publisher":"Institute of Electrical and Electronics Engineers","date_published":"2021-07-07T00:00:00Z","publication_status":"published","external_id":{"arxiv":["2104.07278"],"isi":["000947350400036"]},"abstract":[{"text":"Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs.","lang":"eng"}],"language":[{"iso":"eng"}],"publication":"Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science","title":"Stochastic processes with expected stopping time","oa":1,"date_updated":"2025-07-14T09:10:08Z","article_processing_charge":"No","scopus_import":"1","isi":1,"type":"conference","status":"public","author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Doyen","full_name":"Doyen, Laurent","first_name":"Laurent"}],"arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/2104.07278","open_access":"1"}],"oa_version":"Preprint","day":"07","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","conference":{"end_date":"2021-07-02","location":"Rome, Italy","start_date":"2021-06-29","name":"LICS: Symposium on Logic in Computer Science"},"month":"07","publication_identifier":{"issn":["1043-6871"],"isbn":["978-1-6654-4896-3"],"eisbn":["978-1-6654-4895-6"]}},{"publication_status":"submitted","ddc":["004"],"external_id":{"arxiv":["2109.10203"]},"abstract":[{"lang":"eng","text":"Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n"}],"date_published":"2021-09-21T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"VlKo"}],"year":"2021","date_created":"2021-09-27T10:48:23Z","citation":{"short":"M. Dvorak, V. Kolmogorov, ArXiv (n.d.).","ieee":"M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” <i>arXiv</i>. .","ama":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2109.10203\">10.48550/arXiv.2109.10203</a>","ista":"Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. arXiv, 2109.10203.","mla":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>ArXiv</i>, 2109.10203, doi:<a href=\"https://doi.org/10.48550/arXiv.2109.10203\">10.48550/arXiv.2109.10203</a>.","chicago":"Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2109.10203\">https://doi.org/10.48550/arXiv.2109.10203</a>.","apa":"Dvorak, M., &#38; Kolmogorov, V. (n.d.). Generalized minimum 0-extension problem and discrete convexity. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2109.10203\">https://doi.org/10.48550/arXiv.2109.10203</a>"},"keyword":["minimum 0-extension problem","metric labeling problem","discrete metric spaces","metric extensions","computational complexity","valued constraint satisfaction problems","discrete convex analysis","L-convex functions"],"article_number":"2109.10203","file_date_updated":"2021-09-27T10:54:51Z","_id":"10045","doi":"10.48550/arXiv.2109.10203","author":[{"full_name":"Dvorak, Martin","first_name":"Martin","orcid":"0000-0001-5293-214X","last_name":"Dvorak","id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425"},{"last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir"}],"arxiv":1,"month":"09","day":"21","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2109.10203"}],"oa_version":"Preprint","file":[{"creator":"mdvorak","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":603672,"success":1,"file_name":"Generalized-0-Ext.pdf","checksum":"e7e83065f7bc18b9c188bf93b5ca5db6","file_id":"10046","date_created":"2021-09-27T10:54:51Z","date_updated":"2021-09-27T10:54:51Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"preprint","status":"public","date_updated":"2023-05-03T10:40:16Z","oa":1,"article_processing_charge":"No","title":"Generalized minimum 0-extension problem and discrete convexity","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"arXiv"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"01","oa_version":"None","main_file_link":[{"url":"https://link.springer.com/book/10.1007/978-94-009-0435-4#toc"}],"publication_identifier":{"eissn":["978-94-009-0435-4"],"isbn":["978-0-412-40050-6"]},"month":"01","publication_status":"published","author":[{"first_name":"Nicholas H","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","last_name":"Barton"}],"quality_controlled":"1","page":"185 - 218","edition":"1","extern":"1","date_published":"1988-01-01T00:00:00Z","type":"book_chapter","status":"public","publisher":"Springer","scopus_import":"1","editor":[{"last_name":"Myers","full_name":"Myers, Alan","first_name":"Alan"},{"last_name":"Giller","first_name":"Paul","full_name":"Giller, Paul"}],"keyword":["biogeography","biology","complexity","distribution","evolution","geology"],"date_created":"2018-12-11T12:08:13Z","title":"Speciation","publist_id":"1736","citation":{"ama":"Barton NH. Speciation. In: Myers A, Giller P, eds. <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>. 1st ed. Springer; 1988:185-218. doi:<a href=\"https://doi.org/10.1007/978-94-009-0435-4\">10.1007/978-94-009-0435-4</a>","ieee":"N. H. Barton, “Speciation,” in <i>Analytical biogeography: An integrated approach to the study of animal and plant distributions</i>, 1st ed., A. Myers and P. Giller, Eds. Springer, 1988, pp. 185–218.","short":"N.H. Barton, in:, A. Myers, P. Giller (Eds.), Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions, 1st ed., Springer, 1988, pp. 185–218.","ista":"Barton NH. 1988.Speciation. In: Analytical biogeography: An integrated approach to the study of animal and plant distributions. , 185–218.","mla":"Barton, Nicholas H. “Speciation.” <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:<a href=\"https://doi.org/10.1007/978-94-009-0435-4\">10.1007/978-94-009-0435-4</a>.","chicago":"Barton, Nicholas H. “Speciation.” In <i>Analytical Biogeography: An Integrated Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers and Paul Giller, 1st ed., 185–218. Springer, 1988. <a href=\"https://doi.org/10.1007/978-94-009-0435-4\">https://doi.org/10.1007/978-94-009-0435-4</a>.","apa":"Barton, N. H. (1988). Speciation. In A. Myers &#38; P. Giller (Eds.), <i>Analytical biogeography: An integrated approach to the study of animal and plant distributions</i> (1st ed., pp. 185–218). Springer. <a href=\"https://doi.org/10.1007/978-94-009-0435-4\">https://doi.org/10.1007/978-94-009-0435-4</a>"},"year":"1988","article_processing_charge":"No","date_updated":"2022-02-08T09:19:50Z","doi":"10.1007/978-94-009-0435-4","publication":"Analytical biogeography: An integrated approach to the study of animal and plant distributions","language":[{"iso":"eng"}],"_id":"4317"}]