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

Article Sidebar

PDF
Опубликован: 28.05.2020
УДК 519.713
DOI: https://doi.org/10.26907/1562-5419-2020-23-4-634-655
Выпуск
Том 23 № 4 (2020): Тематический выпуск «Научный сервис в сети Интернет». Часть 2

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.



Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.

Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.

Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.

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

При использовании материалов из журнала обязательна ссылка на URL: http://elbib.kpfu.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается только для научных исследований и персонального использования, но не для коммерческого использования, перепродажи или передачи другому лицу.

Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: [email protected]

Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.

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