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.2016.101
URN: urn:nbn:de:0030-drops-62362
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6236/
Go to the corresponding LIPIcs Volume Portal

Bertrand, Nathalie ; Bouyer, Patricia ; Brihaye, Thomas ; Carlier, Pierre

Analysing Decisive Stochastic Processes

pdf-format:
LIPIcs-ICALP-2016-101.pdf (0.5 MB)

Abstract

In 2007, Abdulla et al. introduced the elegant concept of decisive Markov chain. Intuitively, decisiveness allows one to lift the good properties of finite Markov chains to infinite Markov chains. For instance, the approximate quantitative reachability problem can be solved for decisive Markov chains (enjoying reasonable effectiveness assumptions) including probabilistic lossy channel systems and probabilistic vector addition systems with states. In this paper, we extend the concept of decisiveness to more general stochastic processes. This extension is non trivial as we consider stochastic processes with a potentially continuous set of states and uncountable branching (common features of real-time stochastic processes). This allows us to obtain decidability results for both qualitative and quantitative verification problems on some classes of real-time stochastic processes, including generalized semi-Markov processes and stochastic timed
automata

BibTeX - Entry

@InProceedings{bertrand_et_al:LIPIcs:2016:6236,
  author =	{Nathalie Bertrand and Patricia Bouyer and Thomas Brihaye and Pierre Carlier},
  title =	{{Analysing Decisive Stochastic Processes}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6236},
  URN =		{urn:nbn:de:0030-drops-62362},
  doi =		{10.4230/LIPIcs.ICALP.2016.101},
  annote =	{Keywords: Real-time stochastic processes, Decisiveness, Approximation Scheme}
}

Keywords: Real-time stochastic processes, Decisiveness, Approximation Scheme
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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