Detectability in stochastic discrete event systems

A discrete event system possesses the property of detectability if it allows an observer to perfectly estimate the current state of the system after a finite number of observed symbols, i.e., detectability captures the ability of an observer to eventually perfectly estimate the system state. In this paper we analyze detectability in stochastic discrete event systems (SDES) that can be modeled as probabilistic finite automata. More specifically, we define the notion of A-detectability, which characterizes our ability to estimate the current state of a given SDES with increasing certainty as we observe more output symbols. The notion of A-detectability is differentiated from previous notions for detectability in SDES because it takes into account the probability of problematic observation sequences (that do not allow us to perfectly deduce the system state), whereas previous notions for detectability in SDES considered each observation sequence that can be generated by the underlying system. We discuss observer-based techniques that can be used to verify A-detectability, and provide associated necessary and sufficient conditions. We also prove that A-detectability is a PSPACE-hard problem.