Probabilistic Regular Graphs

Abstract : Deterministic graph grammars generate regular graphs, that form a structural extension of configuration graphs of pushdown systems. In this paper, we study a probabilistic extension of regular graphs obtained by labelling the terminal arcs of the graph grammars by probabilities. Stochastic properties of these graphs are expressed using PCTL, a probabilistic extension of computation tree logic. We present here an algorithm to perform approximate verification of PCTL formulae. Moreover, we prove that the exact model-checking problem for PCTL on probabilistic regular graphs is undecidable, unless restricting to qualitative properties. Our results generalise those of [EKM06], on probabilistic pushdown automata, using similar methods combined with graph grammars techniques.
Type de document :
Communication dans un congrès
Yu-Fang Chen and Ahmed Rezine. Infinity (International Workshop on Verification of Infinite-State Systems), 2010, Singapour, Singapore. EPTCS, 39, pp.77-90, 2010, Proceedings 12th International Workshop on Verification of Infinite-State Systems (Infinity 2010). 〈http://arxiv.org/pdf/1011.0222v1〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00525388
Contributeur : Christophe Morvan <>
Soumis le : lundi 11 octobre 2010 - 17:04:26
Dernière modification le : mercredi 29 novembre 2017 - 15:09:49
Document(s) archivé(s) le : jeudi 25 octobre 2012 - 16:51:17

Fichier

final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00525388, version 1

Collections

Citation

Nathalie Bertrand, Christophe Morvan. Probabilistic Regular Graphs. Yu-Fang Chen and Ahmed Rezine. Infinity (International Workshop on Verification of Infinite-State Systems), 2010, Singapour, Singapore. EPTCS, 39, pp.77-90, 2010, Proceedings 12th International Workshop on Verification of Infinite-State Systems (Infinity 2010). 〈http://arxiv.org/pdf/1011.0222v1〉. 〈inria-00525388〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

78