Symbolic Dependency Graphs for $$\text {PCTL}^{>}_{\le }$$ Model-Checking
Symbolic Dependency Graphs for $$\text {PCTL}^{>}_{\le }$$ Model-Checking
复制标题
$$ ext {PCTL}^{>}_{le }$$ 模型检查的符号依赖图
DOI：
10.1007/978-3-319-65765-3_9
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Larsen
中科院分区：
文献类型：
--
作者：
Anders Mariegaard;K. Larsen
我们考虑模型检查的概率CTL的一个子集的问题，解释（离散时间）马尔可夫奖励模型，允许指定的一组路径满足成本有界的路径公式的概率的下限。我们首先考虑减少固定点计算的图形结构，编码的问题划分成更小的子问题，由显式展开的给定公式成子公式。虽然是正确的，但构建的图的大小高度依赖于成本边界的大小。为此，我们提供了一个符号扩展，有效地确保图的大小和成本之间的独立性。
We consider the problem of model-checking a subset of probabilistic CTL, interpreted over (discrete-time) Markov reward models, allowing the specification of lower bounds on the probability of the set of paths satisfying a cost-bounded path formula. We first consider a reduction to fixed-point computations on a graph structure that encodes a division of the problem into smaller sub-problems by explicit unfolding of the given formula into sub-formulae. Although correct, the size of the graph constructed is highly dependent on the size of the cost bound. To this end, we provide a symbolic extension, effectively ensuring independence between the size of the graph and the cost-bound.