Эксперименты в финитно-определенных метрических пространствах автоматов

Актуальность темы

.

Данная работа посвящена изучению одной из классических и актуальных проблем теории конечных автоматов — задаче сравнения поведения автоматов с помощью экспериментов. При этом под экспериментом [15,17,42] понимается процесс подачи входных слов на неизвестный автомат — «черный ящик», принадлежащий априорно заданному классу I*1, получение его реакций и вывод заключений о функциях автомата. Для конечных классов Р теория экспериментов разработана достаточно хорошо [4,12,13,14,42,48].

Для бесконечных классов Р изучение экспериментов находится в зачаточном состоянии. Принципиальными трудностями таких исследований являются отсутствие общих конструктивных средств представления априорных классов и общих алгоритмов вывода заключений. В последнее время в задачах контроля и диагностики дискретных устройств возникают потенциально бесконечные классы автоматов, задаваемые конечными средствами — спецификациями на заданное поведение. Другими источниками бесконечных классов заданных конечными средствами, являются задачи контроля протоколов сети ЭВМ, компонент сети автоматов и др. [5,24,25,35,36].

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

Связь работы с научными программами, планами, темами.

Диссертационная работа выполнена в соответствии с планами научно-исследовательских работ лаборатории прикладных проблем дискретной математики ИПММ HAH Украины (г. Донецк):

НИР 1 900 012 554 — Представление конечных автоматов фрагментами поведения (1989 — 1993).

НИР 0194U022564 — Исследование обратных задач теории автоматов применительно к идентификации и распознаванию дискретных систем (1994 — 1998).

НИР — Исследование актуальных проблем моделирования, управления и идентификаций дискретных систем (1999).

Цель работы и задачи исследования.

Главная цель исследований состоит в:

— разработке подхода к изучению экспериментов с бесконечными классами автоматов на основе представления процесса вывода заключений как процесса анализа убывающей последовательности некоторых классов (окрестностей в метрических пространствах) автоматов безотносительно к способу подачи входных и наблюдения выходных слов при эксперименте с черным ящиком;

— нахождении условий существования контрольных и распознающих экспериментов как для произвольных, так и финитно-определенных бесконечных классов автоматов;

— построении методов проведения контрольных и распознающих экспериментов с финитно-определенными классами автоматов.

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

Научная новизна полученных результатов.

В работе введен и обоснован подход к исследованию контрольных и распознающих экспериментов на основе их представления сходящимися последовательностями окрестностей в метрических пространствах автоматов. Для произвольных автомата-эталона А, класса автоматов Р и метрики р найдены точные (неконструктивные в общем случае) критерии существования и получены нормальные формы контрольных и распознающих экспериментов. Для контрольных экспериментов этот критерий является новым, а для распознающих — обобщением критерия из [9].

Введено и обосновано задание потенциально бесконечного класса инициальных автоматов конечным слабоинициальным недетерминированным автоматом, обобщающее [35]. Рассмотрена совокупность всех таких классов. Показано, что она является дистрибутивной решеткой с нулем и единицей, но не булевой алгеброй.

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

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

Для специальной бэровской метрики (3, отражающей близость автоматов по поведению, найдены конструктивные условия существования контрольного эксперимента относительно произвольных, А и класса Е З^и^- Показано, что для любого такого Р всегда существует распознающий эксперимент относительно его подкласса, не содержащего предельных автоматов класса Р. Для случая Р У эт0 утверждение в общем случае не выполняется.

Найдены конструктивные критерии бесконечности, конечности и одноэлементности класса F Е |J $ 2? подкласса его предельных автоматов UmF и открывания ]F[= F — limF. Показана замкнутость относительно оператора lim.

Для бэровской метрики? найден ряд конструктивных критериев существования контрольных экспериментов относительно класса G и автомата-эталона А, выбираемых из совокупности классов F, UmF и ]F[ для некоторого F Е Приведены оценки сложности таких экспериментов.

Показано, что существует разбиение {]UmkF[}k> 1 любого F G Уь где для каждого ]limkF[ есть распознающий эксперимент в бэровской метрике ?.

Для любого F е $ 2 найдена структура максимального по включению подкласса, для которого существует распознающий эксперимент в бэровской метрике ?.

Практическое значение полученных результатов.

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

Личный вклад соискателя.

Личный вклад соискателя состоит из: математической постановки задач контроля и распознавания автоматов в виде соответствующих задач в метрических пространствах автоматовобщих критериев существования контрольных и распознающих экспериментов и их частных случаев для #1. В статьях [18,19,20,21], опубликованных в соавторстве, личный вклад соискателя состоит в критериях существования и алгоритмах построения контрольных и распознающих экспериментов относительно Общее направление исследований принадлежит научному руководителю И. С. Грунскому.

Апробация результатов диссертации.

Основные положения и результаты работы докладывались и обсуждались на 3-й Международной конференции «Дискретные модели в теории управляющих систем» (Красновидово, 1998), 12-й Международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 1999), областном семинаре «Актуальные проблемы компьютерных наук» (Донецк, 1999), научных семинарах «Дискретные системы и формальные языки» (ИПММ HAH Украины, Донецк) и семинарах кафедры Компьютерных технологий (ДонГУ, Донецк).

Публикации.

Публикации по теме диссертации составляют три статьи [18,19,39] в журналах, одну в сборнике научных трудов [38], один препринт [21] и 2 тезиса докладов на международных конференциях [20,37].

Структура и объем работы.

Диссертация содержит 130 машинописных страниц и состоит из введения, четырех основных разделов, заключения и списка литературы из 55 источников.

Основные результаты работы состоят в следующем :

1. Создан метод исследования контрольных и распознающих экспериментов на основе их представления сходящимися множествами окрестностей в метрических пространствах автоматов. Для произвольных автомата-эталона А, класса автоматов F и метрики р найдены точные (неконструктивные в общем случае) критерии существования и нормальные формы контрольных и распознающих экспериментов.

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

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

4. Введены операторы аппроксимации 0р, ставящие в соответствие каждому классу автоматов F другой класс G Е, F С G. Показано, что эти операторы относительно выбранного класса автоматов F образуют дистрибутивную решетку. В терминах операторов найден критерий существования контрольного эксперимента относительно произвольных автомата, А, класса F и метрики р.

5. Для бэровской метрики? найдены конструктивные условия существования контрольного эксперимента относительно произвольных, А и класса F Е Показано, что для открывания любого такого F всегда существует распознающий эксперимент.

6. Найдены конструктивные критерии конечности F Е SiU^j подкласса его предельных автоматов UmF и открывания Показана замкнутость относительно оператора lim.

7. Для бэровской метрики? найдены конструктивные критерии существования контрольных экспериментов относительно класса G и автомата-эталона А, выбираемых из множества классов F, UmF и ]F[ для некоторого F Е (J • Приведены оценки сложности таких экспериментов.

8. Показано, что существует разбиение вида {]ИткР[}к>1 любого Р 6 Зъ где каждый }ИткР[ является финитно-распознаваемым классом.

9. Для любого найдена структура максимального по включению финитно-распознаваемого подкласса.

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

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

ЗАКЛЮЧЕНИЕ

.

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