Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures

Initial-state estimation is an important problem in discrete-event systems. In this problem, the initial-state of the system is unknown and one wants to determine the initial-state of the system based on its observation. In this paper, we investigate the problem of initial-state detection of partially-observed discrete-event systems in the stochastic setting. We consider two sources of randomness in this problem: stochastic dynamic of the system and probabilistic sensor failures. Specifically, we model a stochastic discrete-event system by a probabilistic finite-state automaton and we use a probabilistic projection function as the observation model. The notion of stochastic initial-state detectability (SI-detectability) is introduced in order to capture whether or not the probability of detecting the initial-state converges to one even in the presence of potential sensor failures. An approach for the verification of SI-detectability is proposed. We also investigate the complexity of the SI-detectability verification problem and we show that this problem is PSPACE-complete.