THE COMPUTATIONAL-COMPLEXITY OF DECENTRALIZED DISCRETE-EVENT CONTROL-PROBLEMS

被引：89

作者：

RUDIE, K ^{[1
]}

WILLEMS, JC ^{[1
]}

机构：

[1] UNIV GRONINGEN,INST MATH,9700 AV GRONINGEN,NETHERLANDS

来源：

IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 1995年 / 40卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1109/9.400469

中图分类号：

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

学科分类号：

0812 ;

摘要：

Computational complexity results are obtained for decentralized discrete-event control problems. These results generalize the earlier work of Tsitsiklis, who showed that for a special class of centralized supervisory control problems under partial observation, there is an algorithm for determining in polynomial time whether or not a solution exists. The negative complexity results associated with Tsitsiklis' work also carry over to the decentralized case, so that solution existence for the more general class is not decidable in polynomial time, nor does there exist a polynomial-time algorithm for producing supervisor solutions when such solutions exist.

引用

页码：1313 / 1319

页数：7

共 18 条

[1]

BALEMI S, 1993, IEEE T AUTOMAT CONTR, V38

[2] SUPERVISORY CONTROL OF DISCRETE-EVENT PROCESSES WITH PARTIAL OBSERVATIONS [J].