Approximate Diagnosis and Opacity of Stochastic Systems

We consider information control questions in a stochastic setting where an observation function provides to an external observer a view of the states along paths and relevant paths are those visiting some state from a fixed subset. Exact disclosure occurs when the observer can deduce from a finite observation that the path is relevant, the approximate disclosure variant corresponding to the execution being identified as relevant with arbitrarily high accuracy. We consider the problems of diagnosability and opacity, which corresponds, in spirit, to the cases where one wants to disclose all the information or hide as much of it as possible. While these problems have already been studied for the exact disclosure notion, there are very few works using the approximate disclosure. We establish that opacity of Markov chains is in EXPTIME and PSPACE-hard while nearly every opacity question is undecidable in an active setting. Moreover, we show that diagnosability is EXPTIME-complete for controllable systems