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.TIME.2020.7
URN: urn:nbn:de:0030-drops-129752
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12975/
Go to the corresponding LIPIcs Volume Portal

Ilie, Catalin-Andrei ; Worrell, James Ben

Parametric Model Checking Continuous-Time Markov Chains

pdf-format:
LIPIcs-TIME-2020-7.pdf (0.5 MB)

Abstract

CSL is a well-known temporal logic for specifying properties of real-time stochastic systems, such as continuous-time Markov chains. We introduce PCSL, an extension of CSL that allows using existentially quantified parameters in timing constraints, and investigate its expressiveness and decidability over properties of continuous-time Markov chains. Assuming Schanuel’s Conjecture, we prove the decidability of model checking the one-parameter fragment of PCSL on continuous-time Markov chains. Technically, the central problem we solve (relying on Schanuel’s Conjecture) is to decide positivity of real-valued exponential polynomial functions on bounded intervals. A second contribution is to give a reduction of the Positivity Problem for matrix exponentials to the PCSL model checking problem, suggesting that it will be difficult to give an unconditional proof of the decidability of model checking PCSL.

BibTeX - Entry

@InProceedings{ilie_et_al:LIPIcs:2020:12975,
  author =	{Catalin-Andrei Ilie and James Ben Worrell},
  title =	{{Parametric Model Checking Continuous-Time Markov Chains}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Emilio Mu{\~n}oz-Velasco and Ana Ozaki and Martin Theobald},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12975},
  URN =		{urn:nbn:de:0030-drops-129752},
  doi =		{10.4230/LIPIcs.TIME.2020.7},
  annote =	{Keywords: Probabilistic Continuous Stochastic Logic, Continuous-time Markov Chains, model checking, Schanuel’s Conjecture, positivity problem}
}

Keywords: Probabilistic Continuous Stochastic Logic, Continuous-time Markov Chains, model checking, Schanuel’s Conjecture, positivity problem
Collection: 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)
Issue Date: 2020
Date of publication: 15.09.2020

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