О длине адаптивной различающей последовательности для семейства наблюдаемых автоматов

И. Б. Бурдонов^a, Н. В. Евтушенко^ab, А. С. Косачев<sup>a

a</sup> Институт системного программирования им. В.П. Иванникова РАН
^b Национальный исследовательский университет "Высшая школа экономики"

Аннотация: В статье исследуется длина адаптивной различающей последовательности для семейства инициальных полностью определенных наблюдаемых, возможно, недетерминированных автоматов. Приводится верхняя оценка длины такой последовательности и показывается ее достижимость. Обсуждается, каким образом полученные результаты можно применить при построении адаптивных диагностических тестов на основе конечно-автоматной модели.

Ключевые слова: недетерминированные автоматы, адаптивная различающая последовательность, диагностические тесты

DOI: 10.15514/ISPRAS-2025-37(6)-1