$\mathbf{N}-(k_{1}, k_{2})$-detectability of Discrete Event Systems Under Nondeterministic Observations
Lei Zhou, Shaolong Shu, Feng Lin · 2018
In practical systems, due to some reasons such as sensor limitations, sensor faults and packet losses in networks, the observations of events become nondeterministic. It is necessary to re-consider detectability which says, for any string, we can distinguish state pairs in a given specification from the observation, which is unique. In this paper, we extend detectability into N-(k1, k2)-detectability which requires, for any string, we can distinguish state pairs in the specification for all the observations of the string. For N-(k1, k2)-detectability, we construct an augmented automaton and then translate N- (k1, k2)-detectability into traditional detectability of which the verification problem has been solved and the computational complexity is polynomial. N-(k1, k2)-detectability is very useful in deterministic supervisory control. Our results show that N- (k1, k2)-detectability and controllability are the necessary and sufficient conditions under which the deterministic supervisory control is solvable.