NP-completeness of sensor selection problems arising in partially observed discrete-event systems

被引：63

作者：

Yoo, TS ^{[1
]}

Lafortune, S ^{[1
]}

机构：

[1] Univ Michigan, Dept Elect Engn & Comp Sci, Ann Arbor, MI 48109 USA

来源：

IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 2002年 / 47卷 / 09期

关键词：

computational complexity; discrete-event systems; NP-completeness; sensor selection problems;

D O I：

10.1109/TAC.2002.802762

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1495 / 1499

页数：5