基于决策图的复杂系统模型对称约减方法

Symmetry reduction method for complicated system model based on decision diagrams

针对复杂随机系统模型检测过程中的状态空间爆炸问题,提出一种用于支持迁移回报特征描述的概率模型对称约减方法。通过引入状态集等价关系唯一表示函数,约减了原模型中的状态集尺寸;通过加入回报特征描述,改进了传统的多终端二元决策图,用于表示概率回报模型中的迁移关系;基于迁移矩阵,提出了一种高效的对称约减算法,完成了迁移关系的约简。实验结果表明了该方法的可行性与有效性。

To solve the state space explosion problem of model checking process for complicated stochastic systems,a symmetry reduction method based probabilistic model which supports the transition reward characteristics is proposed.The size of the state set in the original model is decreased by using the exclusive representation function of the state set equivalence relations and the traditional multi-terminal binary decision diagram is improved by adding the return characteristics which is used to represent the transition relations of probabilistic reward model,an efficient symmetric reduction algorithm is proposed for reduce transition relations based on transition matrix.The example result shows the feasibility and validity of the method.