Title :
NP-completeness of sensor selection problems arising in partially observed discrete-event systems
Author :
Yoo, Tae-Sic ; Lafortune, Stéphane
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI, USA
fDate :
9/1/2002 12:00:00 AM
Abstract :
We consider the three properties of diagnosability, normality, and observability of discrete-event systems. In each case, we consider the problem of finding an observable event set with minimum cardinality such that the property under consideration holds. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete.
Keywords :
computational complexity; decision theory; discrete event simulation; observability; stability; NP-completeness; decision problems; diagnosability; minimum cardinality; normality; observability; partially observed discrete-event systems; sensor selection problems; Automatic control; Computational complexity; Control systems; Discrete event systems; Gold; Observability; Polynomials; Search problems; Sensor phenomena and characterization; Sensor systems;
Journal_Title :
Automatic Control, IEEE Transactions on
DOI :
10.1109/TAC.2002.802762
