EFSM最小可达图的同步生成算法

摘要

针对EFSM可达性分析过程中的状态空间爆炸问题,提出了一种基于变量值域划分的EFSM最小可达图的同步生成算法.该算法将EFSM可达图的生成与最小化两个过程结合在一起同步进行,引入特征配置的思想,依据特征配置指出变迁有效性组合,以及变迁的赋值动作与终止状态分组变量值域的关系,在进行可达性分析的同时仅对可达的状态分组进行稳定性判定及必要的分裂,直到所有可达状态分组均稳定为止,EFSM最小可达图即构造完毕.文中算法最大限度地减小了中间结果如不可达分组等对求解过程的影响,从而降低了传统算法因可达性分析与最小化过程相分离而引起的时间与空间上的巨大代价.