Title :
A polynomial algorithm for testing diagnosability of discrete-event systems
Author :
Jiang, Shengbing ; Huang, Zhongdong ; Chandra, Vigyan ; Kumar, Ratnesh
Author_Institution :
Dept. of Electr. Eng., Kentucky Univ., Lexington, KY, USA
fDate :
8/1/2001 12:00:00 AM
Abstract :
Failure diagnosis in large and complex systems is a critical task. In the realm of discrete-event systems, Sampath et al. (1995) proposed a language based failure diagnosis approach. They introduced the diagnosability for discrete-event systems and gave a method for testing the diagnosability by first constructing a diagnoser for the system. The complexity of this method of testing diagnosability is exponential in the number of states of the system and doubly exponential in the number of failure types. We give an algorithm for testing diagnosability that does not construct a diagnoser for the system, and its complexity is of fourth order in the number of states of the system and linear in the number of the failure types
Keywords :
computational complexity; discrete event systems; fault diagnosis; finite state machines; large-scale systems; diagnosability testing; diagnoser; discrete-event systems; failure diagnosis; polynomial algorithm; Automata; Discrete event systems; Polynomials; Sufficient conditions; System testing;
Journal_Title :
Automatic Control, IEEE Transactions on
