Институт системного программирования Роcсийской академии наук


Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами

Н. Кушик (аспирантка Томского Университета). Начало семинара - 20 ноября 2012 г.

Методы синтеза умозрительных экспериментов развиваются с 1956 г., когда Э. Мур определил понятие эксперимента с конечным автоматом в одноименной статье. Тем не менее, большая часть известных результатов по синтезу различающих (диагностических) и установочных экспериментов получена для детерминированных автоматов. Исследования, посвященные синтезу таких экспериментов для недетерминированных (неинициальных) автоматов, только начинают развиваться, и известные результаты по синтезу условных и безусловных различающих экспериментов покрывают только класс автоматов с двумя начальными состояниями.

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

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

С презентацией доклада можно ознакомиться здесь.

Семинар группы

Технологии программирования

Перейти к списку семинаров ИСП РАН