Polynomial Time Verification of Decentralized Diagnosability of Discrete Event Systems

被引：131
作者：
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 条
[1]   Maximum Likelihood Failure Diagnosis in Finite State Machines Under Unreliable Observations [J].
Athanasopoulou, Eleftheria ;
Li, Lingxi ;
Hadjicostis, Christoforos N. .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2010, 55 (03) :579-593
[2]   Robust codiagnosability of discrete event systems [J].
Basilio, Joao Carlos ;
Lafortune, Stephane .
2009 AMERICAN CONTROL CONFERENCE, VOLS 1-9, 2009, :2202-+
[3]  
Boel RK, 2002, WODES'02: SIXTH INTERNATIONAL WORKSHOP ON DISCRETE EVENT SYSTEMS, PROCEEDINGS, P175, DOI 10.1109/WODES.2002.1167685
[4]  
Cassandras C. G., 2008, INTRO DISCRETE EVENT
[5]   Diagnosability of discrete event systems with modular structure [J].
Contant, O ;
Lafortune, S ;
Teneketzis, D .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2006, 16 (01) :9-37
[6]  
Cormen T H, 2007, Introduction to algorithms
[7]   Coordinated decentralized protocols for failure diagnosis of discrete event systems [J].
Debouk, R ;
Lafortune, S ;
Teneketzis, D .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2000, 10 (1-2) :33-86
[8]   FAULT-DIAGNOSIS IN DYNAMIC-SYSTEMS USING ANALYTICAL AND KNOWLEDGE-BASED REDUNDANCY - A SURVEY AND SOME NEW RESULTS [J].
FRANK, PM .
AUTOMATICA, 1990, 26 (03) :459-474
[9]  
Hopcroft J.E., 2006, Introduction to Automata Theory, Languages, and Computation, V3rd
[10]   A polynomial algorithm for testing diagnosability of discrete-event systems [J].
Jiang, SB ;
Huang, ZD ;
Chandra, V ;
Kumar, R .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2001, 46 (08) :1318-1321
123