The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs
Yenigün, Hüsnü and Yevtushenko, Nina and Kushik, Natali (2017) The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 127 . pp. 49-53. ISSN 0020-0190 (Print) 1872-6119 (Online)
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ipl.2017.07.001
In this paper, we address the problem of setting a deterministic Finite State Machine (FSM) to a designated initial state. Differently from other papers, we propose to use adaptive synchronizing sequences (test cases) for this purpose and show that for weakly-connected deterministic complete reduced FSMs the problem of checking the existence of an adaptive synchronizing sequence is in P. For partial deterministic reduced FSMs the problem is PSPACE-complete.
Repository Staff Only: item control page