Paper Info
Title
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 [8], on probabilistic pushdown automata, using similar methods combined with graph grammars techniques.
Year
DOI
Venue
2010
10.4204/EPTCS.39.6
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE
Keywords
Field
DocType
model checking,formal language,pushdown automata,computation tree logic,automata theory,regular graph
Deterministic context-free grammar,Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Tree-depth,Chordal graph,Probabilistic CTL,Graph product,Pathwidth,Mathematics
Journal
Issue
ISSN
Citations 
39
2075-2180
0
PageRank 
References 
Authors
0.34
10
2
Name
Order
Citations
PageRank
Nathalie Bertrand125017.84
Christophe Morvan2817.50