infinity10

N. Bertrand, C. Morvan. Probabilistic Regular Graphs. In Infinity, EPTCS, Volume 39, Pages 77-90, Singapore, September 2010.

Download [help]

Download paper: Doi page

Download paper: Adobe portable document (pdf)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

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 [8], on probabilistic pushdown automata, using similar methods combined with graph grammars techniques

Contact

Nathalie Bertrand http://www.irisa.fr/prive/nbertran/
Christophe Morvan http://www-igm.univ-mlv.fr/~cmorvan/

BibTex Reference

@InProceedings{infinity10,
   Author = {Bertrand, N. and Morvan, C.},
   Title = {Probabilistic Regular Graphs},
   BookTitle = {Infinity},
   Volume = {    39},
   Pages = {77--90},
   Series = {EPTCS},
   Address = {Singapore},
   Month = {September},
   Year = {2010}
}

EndNote Reference [help]

Get EndNote Reference (.ref)