License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.133
URN: urn:nbn:de:0030-drops-125408
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12540/
Go to the corresponding LIPIcs Volume Portal

Majumdar, Rupak ; Salamati, Mahmoud ; Soudjani, Sadegh

On Decidability of Time-Bounded Reachability in CTMDPs

pdf-format:
LIPIcs-ICALP-2020-133.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{majumdar_et_al:LIPIcs:2020:12540,
  author =	{Rupak Majumdar and Mahmoud Salamati and Sadegh Soudjani},
  title =	{{On Decidability of Time-Bounded Reachability in CTMDPs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{133:1--133:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12540},
  URN =		{urn:nbn:de:0030-drops-125408},
  doi =		{10.4230/LIPIcs.ICALP.2020.133},
  annote =	{Keywords: CTMDP, Time bounded reachability, Continuous Skolem Problem, Schanuel’s Conjecture}
}

Keywords: CTMDP, Time bounded reachability, Continuous Skolem Problem, Schanuel’s Conjecture
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI