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

Volume

46

Issue

8

fYear

2001

fDate

8/1/2001 12:00:00 AM

Firstpage

1318

Lastpage

1321

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;

fLanguage

English

Journal_Title

Automatic Control, IEEE Transactions on

Publisher

ieee

ISSN

0018-9286

Type

jour

DOI

10.1109/9.940942

Filename

940942