title   
  

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

Abstract

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.

Item Type:Article
Uncontrolled Keywords:Adaptive sequences; Deterministic finite state machines; Formal methods; Synchronizing experiments
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:32767
Deposited By:Hüsnü Yenigün
Deposited On:20 Aug 2017 20:30
Last Modified:20 Aug 2017 20:30

Repository Staff Only: item control page