On Length of an Adaptive Distinguishing Sequence for a Family of Observable Finite State Machines
https://doi.org/10.15514/ISPRAS-2025-37(6)-1
Abstract
In the paper, the length of an adaptive distinguishing sequence for a family of initialized complete observable, possibly nondeterministic Finite State Machines (FSM) is studied. The upper bound for the length of such a sequence is established and its reachability is shown. It is also discussed how the obtained results can be applied for constructing adaptive diagnostic test suites based on a FSM model.
About the Authors
Igor Borisovich BURDONOV
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Dr. Sci. (Phys.-Math.), a Leading Researcher of ISP RAS. Research interests: formal specifications, test generation, compilation technology, real-time systems, operating systems, object-oriented programming, network protocols, software development processes.
Nina Vladimirovna YEVTUSHENKO
Institute for System Programming of the Russian Academy of Sciences,
National Research University Higher School of Economics
Russian Federation
Russian Federation
Dr. Sci. (Tech.), Professor, a Leading Researcher of ISP RAS, worked at the Siberian Scientific Institute of Physics and Technology as a researcher up to 1991. In 1991, she joined Tomsk State University as a professor and then worked as the chair head and the head of Computer Science laboratory. Her research interests include formal methods, automata theory, distributed systems, protocol and software testing.
Alexander Sergeevitch KOSSATCHEV
Institute for System Programming of the Russian Academy of Sciences
Russian Federation
Russian Federation
Cand. Sci. (Phys.-Math.), a Leading Researcher of ISP RAS. Research interests: formal specifications, test generation, compilation technology, real-time systems, operating systems, object-oriented programming, network protocols, software development processes.
References
1. Khaled El-Fakih, Nina Yevtushenko, Natalia Kushik. Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation. Formal Aspects Comput., 2018, 30(2), pp. 319-332.
2. Tiziano Villa, Timothy Kam, Robert K. Brayton, and Alberto Sangiovanni-Vincentelli. Synthesis of Finite State Machines. Springer, 1997.
3. Villa T, Yevtushenko N, Brayton R, Mishchenko A, Petrenko A, Sangiovanni-Vincentelli A. The Unknown Component Problem: Theory and Applications, 2012. Springer.
4. P. Starke, Abstract Automata. American Elsevier, 1972.
5. Spitsyna N. Studying the separability relation between finite state machines. Softw. Test., Verif. Reliab., 2007, (17(4), pp. 227-241.
6. Alexandre Petrenko, Nina Yevtushenko. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM. International Workshop on Formal Approaches to Software Testing (FATES), 2005, pp. 118-133.
7. Moore E. F. Gedanken-experiments on sequential machines. In Automata Studies (Annals of Mathematical Studies), 1956, 1, pp. 129-153.
8. Гилл А. Введение в теорию конечных автоматов. Наука, 1966.
9. Chow T. S. Testing software Design Modelled by Finite State Machines. IEEE Trans. Software Eng., 1978, 4(3), pp. 178-187.
10. D. Lee, M. Yannakakis. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 1994, 43(3), pp. 306-320.
11. R. Alur, C. Courcoubetis, M. Yannakakis. Distinguishing tests for nondeterministic and probabilistic machines. Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, 1995, pp. 363-372.
12. H.Yenigun, N. Yevtushenko, N. Kushik, J. López. The effect of partiality and adaptivity on the complexity of FSM state identification problems. Труды ИСП РАН, 2018, 30(1), с. 7-24.
13. N.Yevtushenko, I.Burdonov, A.Kossachev. Deriving Distinguishing Sequences for Input/Output Automata. Proceedings of the 2020 IEEE East-West Design & Test Symposium, 2020, pp. 1-5.
Review
For citations:
BURDONOV I.B., YEVTUSHENKO N.V., KOSSATCHEV A.S. On Length of an Adaptive Distinguishing Sequence for a Family of Observable Finite State Machines. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(6):7-20. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(6)-1
Email this article 