On the computational complexity of some problems arising in partially-observed discrete-event systems

We study some problems arising in partially-observed discrete-event systems and examine the computational effort required for their solution. First, the problem of verifying the property of diagnosability is considered. In current works, the verification of diagnosability relies on the construction of the diagnoser, a step that requires exponential time in the worst case. We present a new polynomial time algorithm for deciding diagnosability. We also consider the problem of finding an observable event set with minimum cardinality with respect to three properties: diagnosability, normality, and observability. We prove that these search problems are computationally hard by showing that the corresponding decision problems are NP-complete.