随机Petri网模型到马尔可夫链的转换算法的证明

随机Petri网具有很强的模型描述能力,马尔可夫链是一种常用的性能分析模型.为了有效利用随机Petri网进行性能的定量分析,给出了一个详细完整的随机Petri网模型转换为同构马尔可夫链的算法.运用Floyd不变式断言法证明了算法的部分正确性,运用良序集法证明了算法的终止性.算法是部分正确的且是可终止的,这个证明结论说明算法是完全正确的.为了佐证证明结论,基于Java和SQL Server设计开发了一个软件平台,在此平台上实现了转换算法,测试实例的测试结果验证了算法的正确性.对算法时间复杂性的分析表明算法是有效的.