Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs

Official URL: http://dx.doi.org/10.5220/0005854500830090

In this paper, we address the problem of setting a discrete system specified as a Finite State Machine (FSM) to a known initial state. As the system behavior can be nondeterministic, we discuss the complexity of problems related to deriving synchronizing sequences for nondeterministic FSMs and propose a way for decreasing such complexity. In fact, we suggest to use adaptive synchronizing experiments instead of preset ones, and prove that for non-initialized nondeterministic FSMs the problem of checking the existence of an adaptive synchronizing experiment is in P.