Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs
Kushik, Natalia and Yevtushenko, Nina and Yenigün, Hüsnü (2016) Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. In: 1st International Workshop on domAin Specific Model-Based AppRoaches to vErificaTion and validaTiOn, Rome, Italy
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.
Repository Staff Only: item control page