An algorithm for calculating indistinguishable states and clusters in finite-state automata with partially observable transitions
An algorithm for calculating indistinguishable states and clusters in finite-state automata with partially observable transitions
复制标题
DOI：
10.1016/j.sysconle.2007.03.006
复制
发表时间：
2007-09-01
影响因子：
2.6
通讯作者：
Lin, Feng
中科院分区：
文献类型：
--
作者：
Wang, Weilin;Lafortune, Stehane;Lin, Feng
本文提出了一种新算法，用于有效地计算有限状态自动机中的一对无法区分的状态，并部分可观察到的过渡。获得成对不可分割的状态的需求发生在与控制，诊断或分布式控制下与离散事件系统有关的部分观察，诊断或分布式控制。该算法在系统中的状态和事件数量中，在多项式时间内获得了所有无法区分的状态对。该算法的另一个特征是将状态分组为簇和识别难以区分的群集对。可以使用集群来解决部分观察到的系统的控制问题。 （c）2007 Elsevier B.V.保留所有权利。
This paper presents a new algorithm for efficiently calculating pairs of indistinguishable states in finite-state automata with partially observable transitions. The need to obtain pairs of indistinguishable states occurs in several classes of problems related to control under partial observation, diagnosis, or distributed control with communication for discrete event systems. The algorithm obtains all indistinguishable state pairs in polynomial time in the number of states and events in the system. Another feature of the algorithm is the grouping of states into clusters and the identification of indistinguishable cluster pairs. Clusters can be employed to solve control problems for partially observed systems. (c) 2007 Elsevier B.V. All rights reserved.