О разделимости входо-выходных полуавтоматов с недетерминированным поведением
https://doi.org/10.26907/1562-5419-2020-23-4-634-655
Аннотация
При синтезе тестов для проверки функциональных и нефункциональных требований для компонентов различных управляющих систем особое значение имеет понятие различимости, поскольку должна быть возможность отличить правильно функционирующий компонент от неправильно функционирующего, и при активном тестировании для этого используются специальные различающие последовательности. Такие последовательности хорошо исследованы для детерминированных и полностью определенных автоматов, однако компоненты управляющих систем часто могут быть описаны только частично и имеют недетерминированное поведение. В настоящей работе мы рассматриваем модель входо-выходного полуавтомата, вводим понятие разделяющей последовательности для двух таких полуавтоматов, при однократной подаче которой можно однозначно распознать, какой из двух полуавтоматов представлен для эксперимента, и предлагаем алгоритм построения таких последовательностей для специального класса полуавтоматов.
Об авторах
И. Б. Бурдонов
Институт системного программирования им. В.П. Иванникова Российской академии наук
Россия
Россия
Н. В. Евтушенко
Институт системного программирования им. В.П. Иванникова Российской академии наук
Россия
Россия
А. С. Косачев
Институт системного программирования им. В.П. Иванникова Российской академии наук
Россия
Россия
Список литературы
1. Kam T., Villa T., Brayton K.R., Sangiovanni-Vincentelli A. Synthesis of FSMs: Functional Optimization. Springer. 1997. 282 p.
2. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Теория соответствия для систем с блокировками и разрушением. Наука. Глав. ред. физ.-мат. лит., 2008. 412 c.
3. Tretmans J. A formal approach to conformance testing // The Intern. Workshop on Protocol Test Systems. 1993. P. 257–276.
4. Starke P. Abstract Automata. American Elsevier, 1972. 419 p.
5. Гилл А. Введение в теорию конечных автоматов. Наука, 1966. 272 с.
6. 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.
7. Евтушенко Н., Кушик Н. Некоторые задачи идентификации состояний для недетерминированных автоматов. СTT, 2018. 190 с.
8. Petrenko A., Yevtushenko N. Conformance Tests as Checking Experiments for Partial Nondeterministic FSM // Lecture Notes in Computer Science. 2005. V. 3997. P. 118–133.
9. Kushik N., Yevtushenko N., Burdonov I., Kossachev A. Synchronizing and Homing Experiments for Input/output Automata // System Informatics. 2017. No 10. P. 1–10.
Рецензия
Для цитирования:
Бурдонов И.Б., Евтушенко Н.В., Косачев А.С. О разделимости входо-выходных полуавтоматов с недетерминированным поведением . Электронные библиотеки. 2020;23(4):634-655. https://doi.org/10.26907/1562-5419-2020-23-4-634-655
For citation:
Burdonov I.B., Yevtushenko N.V., Kossachev A.S. Separating Input/Output Automata With Nondeterministic Behavior. Russian Digital Libraries Journal. 2020;23(4):634-655. (In Russ.) https://doi.org/10.26907/1562-5419-2020-23-4-634-655
Просмотров:
19
Послать статью по эл. почте 