When are stochastic transition systems tameable?

Abstract : A decade ago, Abdulla, Ben Henda and Mayr introduced the elegant concept of decisiveness for denumerable Markov chains [1]. Roughly speaking, decisiveness allows one to lift most good properties from finite Markov chains to denumerable ones, and therefore to adapt existing verification algorithms to infinite-state models. Decisive Markov chains however do not encompass stochastic real-time systems, and general stochastic transition systems (STSs for short) are needed. In this article, we provide a framework to perform both the qualitative and the quantitative analysis of STSs. First, we define various notions of decisiveness (inherited from [1]), notions of fairness and of attractors for STSs, and make explicit the relationships between them. Then, we define a notion of abstraction, together with natural concepts of soundness and completeness, and we give general transfer properties, which will be central to several verification algorithms on STSs. We further design a generic construction which will be useful for the analysis of ω-regular properties, when a finite attractor exists, either in the system (if it is denumerable), or in a sound denumerable abstraction of the system. We next provide algorithms for qualitative model-checking, and generic approximation procedures for quantitative model-checking. Finally, we instantiate our framework with stochastic timed automata (STA), generalized semi-Markov processes (GSMPs) and stochastic time Petri nets (STPNs), three models combining dense-time and probabilities. This allows us to derive decidability and approximability results for the verification of these models. Some of these results were known from the literature, but our generic approach permits to view them in a unified framework, and to obtain them with less effort. We also derive interesting new approximability results for STA, GSMPs and STPNs.
Document type :
Journal articles
Complete list of metadatas

Contributor : Nathalie Bertrand <>
Submitted on : Wednesday, November 28, 2018 - 2:44:08 PM
Last modification on : Friday, April 19, 2019 - 5:02:11 PM

Links full text



Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Pierre Carlier. When are stochastic transition systems tameable?. Journal of Logical and Algebraic Methods in Programming, Elsevier, 2018, 99, pp.41-96. ⟨10.1016/j.jlamp.2018.03.004⟩. ⟨hal-01938135⟩



Record views