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

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

Improved algorithm of quasi-congruence in discrete-event system

We investigate the algorithm for reducing the time-complexity in computing the optimal quasi-congruence of discrete-event system (DES). Based on the algorithms provided by Paige, Tarjan and Ferandez, the algorithm related to the relational coarsest partition problem is adopted to figure out the optimal quasi-congruence with time complexity O(mlogn). This algorithm is applicable when the DES is complicated, especially when the number of observable events is small. Compared with the algorithm with time complexity O(mn) proposed by Ramadge and Wonham, this algorithm is less time-consuming. In addition, the improvement of boundary conditions in computing the optimal quasi-congruence is discussed. The effectiveness of the proposed algorithm is validated by simulation results.