A polynomial algorithm for testing diagnosability of discrete-eventsystems |
| |
| Authors: | Shengbing Jiang Zhongdong Huang Chandra V Kumar R |
| |
| Affiliation: | Dept. of Electr. Eng., Kentucky Univ., Lexington, KY; |
| |
| 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: | |
|
|
