Title: Complexity of Deciding Detectability in Discrete Event Systems,
Abstract: Detectability of discrete event systems (DESs) is a question whether the
current and subsequent states can be determined based on observations. Shu and
Lin designed a polynomial-time algorithm to check strong (periodic)
detectability and an exponential-time (polynomial-space) algorithm to check
weak (periodic) detectability. Zhang showed that checking weak (periodic)
detectability is PSpace-complete. This intractable complexity opens a question
whether there are structurally simpler DESs for which the problem is tractable.
In this paper, we show that it is not the case by considering DESs represented
as deterministic finite automata without non-trivial cycles, which are
structurally the simplest deadlock-free DESs. We show that even for such very
simple DESs, checking weak (periodic) detectability remains intractable. On the
contrary, we show that strong (periodic) detectability of DESs can be
efficiently verified on a parallel computer.