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

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.

Finite State Machines (FSMs), state identification problems, complexity, Finite State Machines (FSMs), state identification problems, complexity

1. Moore E.F. Gedanken-experiments on sequential machines. Automata Studies (Annals of Mathematical Studies), 1956, 1, pp. 129-153.

2. Gill A. State-identification experiments in finite automata. Information and Control, 1961, pp. 132-154.

3. Gill A. Introduction to the Theory of Finite-State Machines. 1962, 207 p.

4. Kohavi Z. Switching and Finite Automata Theory. 1979, 658 p.

5. Sandberg S. Homing and Synchronization Sequences. Lecture Notes in Computer Science, 2005, 3472, pp. 5–33.

6. Lee D., Yannakakis M. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 1994, 43 (3), pp. 306-320.

7. Alur R., Courcoubetis C., Yannakakis, M. Distinguishing tests for nondeterministic and probabilistic machines. Proc. of the 27th ACM Symposium on Theory of Computing, 1995, pp. 363-372.

8. Kushik N., El-Fakih K., Yevtushenko, N. Adaptive homing and distinguishing experiments for nondeterministic finite state machines. Lecture Notes in Computer Science, 2013, 8254, pp. 33-48.

9. Kushik N., Yevtushenko N. On the Length of Homing Sequences for Nondeterministic Finite State Machines. Lecture Notes in Computer Science, 2013, 7982, pp. 220-231.

10. Hierons R.M., Türker U.C. Distinguishing Sequences for Partially Specified FSMs. Lecture Notes in Computer Science, 2014, 8430, pp. 62-76.

11. Yenigün H., Yevtushenko N., Kushik N. Some classes of finite state machines with polynomial length of distinguishing test cases. Proc, of International Symposium on Applied Computing (SAC’2016), 2016, pp. 1680-1685.

12. Kushik N., Yevtushenko N., Yenigun H. Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic FSMs. Proc. of Intern. Workshop on Domain Specific Model-based Approaches to Verification and Validation (AMARETTO’2016), 2016, pp. 83-90.

13. Kushik N., El-Fakih K., Yevtushenko N., Cavalli A.R. On adaptive experiments for nondeterministic finite state machines. Software Tools for Technology Transfer, Springer, 2016, 18 (3), pp. 251-264.

14. Yenigun H., Yevtushenko N., Kushik N. The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs. Information Processing Letters, 2017, 127, pp. 49-53.

15. Kushik N. G., Kulyamin V. V., Evtushenko N. V. On the complexity of existence of homing sequences for nondeterministic finite state machines. Programming and Computer Software, 2014, 40(6), pp. 333-336.

16. El-Fakih K., Yevtushenko N., Kushik N. Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation. Formal Asp. Comput., 2018, 30(2), pp. 319-332.

17. N. Kushik, J. López, A. Cavalli, N. Yevtushenko. Improving Protocol Passive Testing through "Gedanken" Experiments with Finite State Machines. In Proceedings of Intern. Conf. on Software Quality, Reliability & Security (QRS’2016), 2016, pp. 315-322.

18. Yenigün H., Kushik N., López J., Yevtushenko N., Cavalli A.R. Decreasing the complexity of deriving tests against nondeterministic finite state machines. Proc. of East-West Design & Test Symposium (EWDTS), 2017, IEEE Xplore, IEEE, pp. 1-4.

19. Hopcroft, J.E., Ullman, J.D. Introduction to Automata Theory, Languages, and Computation (1st ed.), 1979, 521 p.

20. Volkov, M.V. Synchronizing automata preserving a chain of partial orders. Lecture Notes in Computer Science, Vol. 4783, pp. 27–37 (2007)

21. Hibbard T.N. Least Upper Bounds on Minimal Terminal State Experiments for Two Classes of Sequential Machines. J. ACM, 1961, 8(4), pp. 601-612.

22. Pavel V. Martyugin. Careful Synchronization of Partial Automata with Restricted Alphabets. Proceedings of the Intern. Conf. Computer Science in Russia (CSR’2013), 2013, pp. 76-87.

23. Kushik N., Yevtushenko N. Describing Homing and Distinguishing Sequences for Nondeterministic Finite State Machines via Synchronizing Automata. Lecture Notes in Computer Science, 2015, 9223, pp. 188-198.