首页    期刊浏览 2025年06月10日 星期二
登录注册

文章基本信息

  • 标题:On Decidability of Time-Bounded Reachability in CTMDPs
  • 本地全文:下载
  • 作者:Rupak Majumdar ; Mahmoud Salamati ; Sadegh Soudjani
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:168
  • 页码:133:1-133:19
  • DOI:10.4230/LIPIcs.ICALP.2020.133
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We consider the time-bounded reachability problem for continuous-time Markov decision processes. We show that the problem is decidable subject to Schanuel’s conjecture. Our decision procedure relies on the structure of optimal policies and the conditional decidability (under Schanuel’s conjecture) of the theory of reals extended with exponential and trigonometric functions over bounded domains. We further show that any unconditional decidability result would imply unconditional decidability of the bounded continuous Skolem problem, or equivalently, the problem of checking if an exponential polynomial has a non-tangential zero in a bounded interval. We note that the latter problems are also decidable subject to Schanuel’s conjecture but finding unconditional decision procedures remain longstanding open problems.
  • 关键词:CTMDP; Time bounded reachability; Continuous Skolem Problem; Schanuel’s Conjecture
国家哲学社会科学文献中心版权所有