| 引用本文: | 张仁远,甘永梅,晁武杰,王兆安.离散事件系统拟同余关系的改进算法[J].控制理论与应用,2012,29(2):151~156.[点击复制] |
| ZHANG Ren-yuan,GAN Yong-mei,CHAO Wu-jie,WANG Zhao-an.Improved algorithm of quasi-congruence in discrete-event system[J].Control Theory and Technology,2012,29(2):151~156.[点击复制] |
|
| 离散事件系统拟同余关系的改进算法 |
| Improved algorithm of quasi-congruence in discrete-event system |
| 摘要点击 2424 全文点击 1900 投稿时间：2010-08-23 修订日期：2011-03-11 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/j.issn.1000-8152.2012.2.CCTA100975 |
| 2012,29(2):151-156 |
| 中文关键词 离散事件系统 最粗粒度划分问题 最优拟同余关系 |
| 英文关键词 discrete-event system relational coarsest partition problem quasi-congruence |
| 基金项目 |
|
| 中文摘要 |
| 针对离散事件系统, 本文主要研究计算最优拟同余关系时减少时间复杂度的算法. 基于Paige & Tarjan提出且Fernandez修改的、可有效计算最粗粒度划分问题的算法, 本文给出一种时间复杂度为O(mlog n)的计算最优拟同余关系的算法. 该算法适用于离散事件系统比较复杂, 尤其是可观事件很少的情况. 与Ramadge和Wonham提出的时间复杂度为O(mn)的算法相比, 该算法计算过程耗时较短. 本文还讨论了计算拟同余关系的边界情况的改进方法. 仿真结果表明所提出算法的有效性. |
| 英文摘要 |
| 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. |
|
|
|
|
|