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

Improved algorithm of quasi-congruence in discrete-event system

作　　者：张仁远[1] 甘永梅[1] 晁武杰[1] 王兆安[1] 

机构地区：[1]西安交通大学电气工程学院,陕西西安710049

出　　处：《控制理论与应用》2012年第2期151-156,共6页Control Theory & Applications

摘　　要：针对离散事件系统,本文主要研究计算最优拟同余关系时减少时间复杂度的算法.基于Paige&Tarjan提出且Fernandez修改的、可有效计算最粗粒度划分问题的算法,本文给出一种时间复杂度为O(mlogn)的计算最优拟同余关系的算法.该算法适用于离散事件系统比较复杂,尤其是可观事件很少的情况.与Ramadge和Wonham提出的时间复杂度为O(mn)的算法相比,该算法计算过程耗时较短.本文还讨论了计算拟同余关系的边界情况的改进方法.仿真结果表明所提出算法的有效性.We investigate the algorithm for reducing the timecomplexity in computing the optimal quasicongruence of discreteevent 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 quasicongruence 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 timeconsuming. In addition, the improvement of boundary conditions in computing the optimal quasicongruence is discussed. The effectiveness of the proposed algorithm is validated by simulation results.

关 键 词：离散事件系统 最粗粒度划分问题 最优拟同余关系 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]