Deciding Co-observability is PSPACE-Complete

Kurt Rohloff, Tae Sic Yoo, Stéphane Lafortune

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

In this note, we reduce the deterministic finite-state automata intersection problem to the problem of deciding co-observability for 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.

Original languageEnglish (US)
Pages (from-to)1995-1999
Number of pages5
JournalIEEE Transactions on Automatic Control
Volume48
Issue number11
DOIs
StatePublished - Nov 2003
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Keywords

  • Co-observability
  • Computational complexity
  • Discrete event systems

Fingerprint Dive into the research topics of 'Deciding Co-observability is PSPACE-Complete'. Together they form a unique fingerprint.

Cite this