Deciding Coobservability is PSPACE-complete

In this paper we reduce the deterministic finite-state automata intersection problem to the problem of deciding coobservability of regular languages using a polynomial-time many-one mapping. This demonstrates that the problem of deciding coobservability 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 coobservability introduced in [Yoo,Lafortune,2002]. These results imply that coobservability of regular languages most likely cannot be decided in polynomial time unless we make further restrictions on the 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.