English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs) are natural models for recursive systems involving both probabilistic and non-probabilistic actions. As shown recently [10], fundamental problems about such models, e.g., termination, are undecidable in general, but decidable for the important class of 1-exit RMDPs and RSSGs. These capture controlled and game versions of multi-type Branching Processes, an important and well-studied class of stochastic processes. In this paper we provide efficient algorithms for the qualitative termination problem for these models: does the process terminate almost surely when the players use their optimal strategies? Polynomial time algorithms are given for both maximizing and minimizing 1-exit RMDPs (the two cases are not symmetric). For 1-exit RSSGs the problem is in NP∩coNP, and furthermore, it is at least as hard as other well-known NP∩coNP problems on games, e.g., Condon's quantitative termination problem for finite SSGs ([3]). For the class of linearly-recursive 1-exit RSSGs, we show that the problem can be solved in polynomial time.

Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games