The effect of partiality and adaptivity on the complexity of FSM state identification problems

Yenigün, Hüsnü and Yevtushenko, Nina and Kushik, Natalia and Lopez, Jorge (2018) The effect of partiality and adaptivity on the complexity of FSM state identification problems. Proceedings of the Institute for System Programming, 30 (1). pp. 7-24. ISSN 2079-8156 (Print) 2220-6426 (Online)

Full text not available from this repository. (Request a copy)


State identification is a long standing problem in the area of Finite State Machine (FSM) based modeling and testing of discrete event systems. For the identification of the current state of the system, so-called homing and synchronizing experiments with FSMs are used whereas for the initial state identification one can perform a distinguishing experiment. The homing, synchronizing, and distinguishing experiments are known as “gedanken” experiments, and the sequences for these experiments can be derived for deterministic and nondeterministic, partial and complete specification FSMs that are used to formally represent the required behavior of systems under investigation. The problems of checking the existence and derivation of homing, synchronizing, and distinguishing sequences are known to become harder as a specification FSM turns to be nondeterministic and partial. It is also known that in some cases the complexity can be reduced through a ‘switch’ from preset to adaptive experiment derivation. In this paper, we study how the partiality and adaptivity affect the complexity of checking the existence of homing/synchronizing/distinguishing sequences for deterministic and nondeterministic FSMs and visualize the complexity issues via appropriate figures. We also mention that the existing solutions to state identification problems are widely used for verification and testing of finite state transition systems.
Item Type: Article
Uncontrolled Keywords: Finite State Machines (FSMs), state identification problems, complexity
Subjects: Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Hüsnü Yenigün
Date Deposited: 03 Aug 2018 10:39
Last Modified: 03 Aug 2018 10:39

Actions (login required)

View Item
View Item