离散事件系统拟同余关系的改进算法

针对离散事件系统,本文主要研究计算最优拟同余关系时减少时间复杂度的算法.基于Paige&Tarjan提出且Fernandez修改的、可有效计算最粗粒度划分问题的算法,本文给出一种时间复杂度为O(mlogn)的计算最优拟同余关系的算法.该算法适用于离散事件系统比较复杂,尤其是可观事件很少的情况.与Ramadge和Wonham提出的时间复杂度为O(mn)的算法相比,该算法计算过程耗时较短.本文还讨论了计算拟同余关系的边界情况的改进方法.仿真结果表明所提出算法的有效性.