logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Deciding co-observability is PSIPACE-complete

delete2003-11-01
delete13
PRE
AI
K
Kurt Rohloff
T
Tae-Sic Yoo
S
Stéphane Lafortune
DOI：10.1109/TAC.2003.819285delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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.
Keywords:
computational complexity
co-observability
discrete event systems

Journal

IEEE Transactions on Automatic Control cover
IEEE Transactions on Automatic Control
IF:
7
Papers:
1.3W
Citations:
6.7W

Organization

No organization information available