О длине адаптивной различающей последовательности для семейства наблюдаемых автоматов
https://doi.org/10.15514/ISPRAS-2025-37(6)-1
Аннотация
В статье исследуется длина адаптивной различающей последовательности для семейства инициальных полностью определенных наблюдаемых, возможно, недетерминированных автоматов. Приводится верхняя оценка длины такой последовательности и показывается ее достижимость. Обсуждается, каким образом полученные результаты можно применить при построении адаптивных диагностических тестов на основе конечно-автоматной модели.
Об авторах
Игорь Борисович БУРДОНОВ
Институт системного программирования РАН им. В.П. Иванникова
Россия
Россия
Доктор физико-математических наук, главный научный сотрудник ИСП РАН. Научные интересы: формальные спецификации, генерация тестов, технология компиляции, системы реального времени, операционные системы, объектно-ориентированное программирование, сетевые протоколы, процессы разработки программного обеспечения.
Нина Владимировна ЕВТУШЕНКО
Институт системного программирования РАН им. В.П. Иванникова,
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Доктор технических наук, профессор, главный научный сотрудник ИСП РАН, до 1991 года работала научным сотрудником в Сибирском физико-техническом институте. С 1991 г. работала в ТГУ профессором, зав. кафедрой, зав. лабораторией по компьютерным наукам. Её исследовательские интересы включают формальные методы, теорию автоматов, распределённые системы, протоколы и тестирование программного обеспечения.
Александр Сергеевич КОСАЧЕВ
Институт системного программирования РАН им. В.П. Иванникова
Россия
Россия
Кандидат физико-математических наук, ведущий научный сотрудник ИСП РАН. Научные интересы: формальные спецификации, генерация тестов, технология компиляции, системы реального времени, операционные системы, объектно-ориентированное программирование, сетевые протоколы, процессы разработки программного обеспечения.
Список литературы
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.
Рецензия
Для цитирования:
БУРДОНОВ И.Б., ЕВТУШЕНКО Н.В., КОСАЧЕВ А.С. О длине адаптивной различающей последовательности для семейства наблюдаемых автоматов. Труды Института системного программирования РАН. 2025;37(6):7-20. https://doi.org/10.15514/ISPRAS-2025-37(6)-1
For citation:
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
Послать статью по эл. почте 