  The state inference problem and fault diagnosis/prediction problem are
fundamental topics in many areas. In this paper, we consider discrete-event
systems (DESs) modeled by finite-state automata (FSAs). There exist results for
decentralized versions of the latter problem but there is almost no result for
a decentralized version of the former problem. We propose a decentralized
version of strong detectability called co-detectability which implies that once
a system satisfies this property, for each generated infinite-length event
sequence, at least one local observer can determine the current and subsequent
states after a common observation time delay. We prove that the problem of
verifying co-detectability of FSAs is coNP-hard. Moreover, we use a unified
concurrent-composition method to give PSPACE verification algorithms for
co-detectability, co-diagnosability, and co-predictability of FSAs, without any
assumption or modifying the FSAs under consideration, where co-diagnosability
is firstly studied by [Debouk & Lafortune & Teneketzis 2000], while
co-predictability is firstly studied by [Kumar \& Takai 2010]. By our proposed
unified method, one can see that in order to verify co-detectability, more
technical difficulties will be met compared to verifying the other two
properties, because in co-detectability, generated outputs are counted, but in
the latter two properties, only occurrences of events are counted. For example,
when one output was generated, any number of unobservable events could have
occurred. The PSPACE-hardness of verifying co-diagnosability is already known
in the literature. In this paper, we prove the PSPACE-hardness of verifying
co-predictability.
