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

共 11 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Cassandras C. G., 2009, Introduction to discrete event systems, V2nd, DOI 10.1007/978-3-030-72274-6

[3]

Cormen T. H., 1990, INTRO ALGORITHMS

[4]

Debouk R., 1999, Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No.99CH36304), P4990, DOI 10.1109/CDC.1999.833338

[5] Minimizing the cardinality of an events set for supervisors of discrete-event dynamical systems [J].

HajiValizadeh, A ;

Loparo, KA .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1996, 41 (11) :1579-1593

[6] A polynomial algorithm for testing diagnosability of discrete-event systems [J].

Jiang, SB ;

Huang, ZD ;

Chandra, V ;

Kumar, R .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2001, 46 (08) :1318-1321

[7] THE COMPUTATIONAL-COMPLEXITY OF DECENTRALIZED DISCRETE-EVENT CONTROL-PROBLEMS [J].

RUDIE, K ;

WILLEMS, JC .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1995, 40 (07) :1313-1319

[8] DIAGNOSABILITY OF DISCRETE-EVENT SYSTEMS [J].

SAMPATH, M ;

SENGUPTA, R ;

LAFORTUNE, S ;

SINNAMOHIDEEN, K ;

TENEKETZIS, D .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1995, 40 (09) :1555-1575

[9] A general architecture for decentralized supervisory control of discrete-event systems [J].

Yoo, TS ;

Lafortune, S .

DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2002, 12 (03) :335-377

[10] Polynomial-time verification of diagnosability of partially observed discrete-event systems [J].

Yoo, TS ;

Lafortune, S .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2002, 47 (09) :1491-1495

← 1 2 →