Beyond Decisiveness of Infinite Markov Chains - Université Paris-Est-Créteil-Val-de-Marne
Communication Dans Un Congrès Année : 2024

Beyond Decisiveness of Infinite Markov Chains

Patricia Bouyer
Serge Haddad

Résumé

Verification of infinite-state Markov chains is still a challenge despite several fruitful numerical or statistical approaches. For decisive Markov chains, there is a simple numerical algorithm that frames the reachability probability as accurately as required (however with an unknown complexity). On the other hand when applicable, statistical model checking is in most of the cases very efficient. Here we study the relation between these two approaches showing first that decisiveness is a necessary and sufficient condition for almost sure termination of statistical model checking. Afterwards we develop an approach with application to both methods that substitutes to a non decisive Markov chain a decisive Markov chain with the same reachability probability. This approach combines two key ingredients: abstraction and importance sampling (a technique that was formerly used for efficiency). We develop this approach on a generic formalism called layered Markov chain (LMC). Afterwards we perform an empirical study on probabilistic pushdown automata (an instance of LMC) to understand the complexity factors of the statistical and numerical algorithms. To the best of our knowledge, this prototype is the first implementation of the deterministic algorithm for decisive Markov chains and required us to solve several qualitative and numerical issues.

Fichier principal
Vignette du fichier
LIPIcs.FSTTCS.2024.8.pdf (1016.02 Ko) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte
Licence

Dates et versions

hal-04822969 , version 1 (06-12-2024)

Licence

Identifiants

Citer

Benoît Barbot, Patricia Bouyer, Serge Haddad. Beyond Decisiveness of Infinite Markov Chains. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024), Dec 2024, Gandhinagar, Gujarat, India. pp.8:1-8:22, ⟨10.48550/arXiv.2409.18670[3]⟩. ⟨hal-04822969⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

More