NP-completeness of sensor selection problems arising in partially observed discrete-event systems
Tóm tắt
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.
Từ khóa
#Sensor systems #Discrete event systems #Sensor phenomena and characterization #Automatic control #Observability #Polynomials #Control systems #Computational complexity #Search problems #GoldTài liệu tham khảo
debouk, 1999, on an optimization problem in sensor selection, IEEE Conf Decision and Control, 4990
10.1109/9.543996
10.1109/9.400469
cormen, 1990, Introduction to Algorithms
10.1023/A:1015625600613
young, 1993, optimal sensor and actuator choices for discrete event systems, 31st Allerton Conf Communication Control Computing
10.1109/TAC.2002.802763
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
10.1109/9.412626
10.1109/9.940942
10.1007/978-1-4757-4070-7