Deciding co-observability is PSIPACE-complete

被引：13

作者：

Rohloff, K ^{[1
]}

Yoo, TS ^{[1
]}

Lafortune, S ^{[1
]}

机构：

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

来源：

IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 2003年 / 48卷 / 11期

基金：

美国国家科学基金会;

关键词：

computational complexity; co-observability; discrete event systems;

D O I：

10.1109/TAC.2003.819285

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this note, we reduce the deterministic finite-state automata intersection problem to the problem of deciding co-observability or regular languages using a polynomial-time many-one mapping. This demonstrates that the problem of deciding co-observability for languages marked by deterministic finite-state automata is PSPACE-complete. We use a similar reduction to reduce the deterministic' finite-state automata intersection problem to deciding other versions of co-observability introduced in a previous paper. These results imply that the co-observability of regular languages most likely cannot be decided in polynomial time unless we make further restrictions on the languages. These results also show that deciding decentralized supervisor existence is PSPACE-complete and therefore probably intractable.

引用

页码：1995 / 1999

页数：5

共 17 条

[1]

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

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