О разделимости входо-выходных полуавтоматов с недетерминированным поведением

Main Article Content

Игорь Борисович Бурдонов
Нина Владимировна Евтушенко
Александр Сергеевич Косачев

Аннотация

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

Article Details

Как цитировать
Бурдонов, И. Б., Евтушенко, Н. В., & Косачев, А. С. (2020). О разделимости входо-выходных полуавтоматов с недетерминированным поведением . Электронные библиотеки, 23(4), 634-655. https://doi.org/10.26907/1562-5419-2020-23-4-634-655
Биографии авторов

Игорь Борисович Бурдонов

Ведущий научный сотрудник Института системного программирования им. В.П. Иванникова РАН. Сфера научных интересов – моделирование и верификация программных систем, теория графов, теория автоматов.

Нина Владимировна Евтушенко

Ведущий научный сотрудник Института системного программирования им. В.П. Иванникова РАН. Сфера научных интересов – теория автоматов, моделирование, верификация и верификация программных систем, телекоммуникационные протоколы и сервисы.

Александр Сергеевич Косачев

Ведущий научный сотрудник Института системного программирования им. В.П. Иванникова РАН. Сфера научных интересов – моделирование и верификация программных систем, теория графов, теория автоматов.

Библиографические ссылки

Kam T., Villa T., Brayton K.R., Sangiovanni-Vincentelli A. Synthesis of FSMs: Functional Optimization. Springer. 1997. 282 p.

Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. Наука. Глав. ред. физ.-мат. лит., 2008. 412 c.

Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.

Starke P. Abstract Automata. American Elsevier, 1972. 419 p.

Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.

Kushik N., Yevtushenko N., Cavalli A.R. On Testing against partial nondeterministic machines // Intern. Conf. on the Quality of information and Communications Technology. 2014. P. 230–233.

Евтушенко Н., Кушик Н. Некоторые задачи идентификации состояний для недетерминированных автоматов. СTT, 2018. 190 с.

Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. V. 3997. P. 118–133.

Kushik N., Yevtushenko N., Burdonov I., Kossachev A. Synchronizing and Homing Experiments for Input/output Automata // System Informatics. 2017. No 10. P. 1–10.