Polynomial Time Verification of Decentralized Diagnosability of Discrete Event Systems

被引：132
作者：
Moreira, Marcos V. [1 ]
Jesus, Thiago C. [1 ]
Basilio, Joao C. [1 ]
机构：
[1] Univ Fed Rio de Janeiro, COPPE Programa Engn Eletr, BR-21949900 Rio De Janeiro, Brazil
来源：
IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 2011年 / 56卷 / 07期
关键词：
Automata; computational complexity; diagnosability verification; discrete-event systems (DES); failure diagnosis; FAILURE DIAGNOSIS; FAULT-DIAGNOSIS;
D O I：
10.1109/TAC.2011.2124950
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The first step in the diagnosis of failure occurrences in discrete event systems is the verification of the system diagnosability. Several works have addressed this problem using either diagnosers or verifiers for both centralized and decentralized architectures. In this technical note, we propose a new algorithm to verify decentralized diagnosability of discrete event systems. The proposed algorithm requires polynomial time in the number of states and events of the system and has lower computational complexity than all other methods found in the literature. In addition, it can also be applied to the centralized case.
引用
收藏
页码：1679 / 1684
页数：6
相关论文
共 22 条
[11]   Inference-Based Ambiguity Management in Decentralized Decision-Making: Decentralized Diagnosis of Discrete-Event Systems [J].
Kumar, Ratnesh ;
Takai, Shigemasa .
IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2009, 6 (03) :479-491
[12]  
Lin F., 1994, DISCRETE EVENT DYN S, V4, P197
[13]   Decentralized failure diagnosis of discrete event systems [J].
Qiu, WB ;
Kumar, R .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART A-SYSTEMS AND HUMANS, 2006, 36 (02) :384-395
[14]   THE CONTROL OF DISCRETE EVENT SYSTEMS [J].
RAMADGE, PJG ;
WONHAM, WM .
PROCEEDINGS OF THE IEEE, 1989, 77 (01) :81-98
[15]   Failure diagnosis using discrete-event models [J].
Sampath, M ;
Sengupta, R ;
Lafortune, S ;
Sinnamohideen, K ;
Teneketzis, DC .
IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY, 1996, 4 (02) :105-124
[16]   DIAGNOSABILITY OF DISCRETE-EVENT SYSTEMS [J].
SAMPATH, M ;
SENGUPTA, R ;
LAFORTUNE, S ;
SINNAMOHIDEEN, K ;
TENEKETZIS, D .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1995, 40 (09) :1555-1575
[17]   Diagnosability of stochastic discrete-event systems [J].
Thorsley, D ;
Teneketzis, D .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2005, 50 (04) :476-492
[18]  
Tripakis S., 2002, LECT NOTES COMPUTER, V2469
[19]  
Viswanadham N., 1988, Proceedings of the 27th IEEE Conference on Decision and Control (IEEE Cat. No.88CH2531-2), P2301, DOI 10.1109/CDC.1988.194747
[20]   Diagnosis of discrete event systems using decentralized architectures [J].
Wang, Yin ;
Yoo, Tae-Sic ;
Lafortune, Stephane .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2007, 17 (02) :233-263
123