Analysing Decisive Stochastic Processes

Abstract : In 2007, Abdulla et al. introduced the elegant concept of decisive Markov chain. Intuitively, de-cisiveness 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.
Type de document :
Communication dans un congrès
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016, Rome, Italy. 55, pp.14, 2016, LiPICS. 〈10.4230/LIPIcs.ICALP.2016.101〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01397794
Contributeur : Nathalie Bertrand <>
Soumis le : mercredi 16 novembre 2016 - 12:07:37
Dernière modification le : mercredi 21 février 2018 - 01:23:31
Document(s) archivé(s) le : jeudi 16 mars 2017 - 18:28:37

Fichier

BBBC-icalp16.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Pierre Carlier. Analysing Decisive Stochastic Processes. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), 2016, Rome, Italy. 55, pp.14, 2016, LiPICS. 〈10.4230/LIPIcs.ICALP.2016.101〉. 〈hal-01397794〉

Partager

Métriques

Consultations de la notice

571

Téléchargements de fichiers

44