Автоматный анализ детерминированных графов

• Автор: Тихончев, Михаил Юрьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Димитровград
• Количество страниц: 113 с.

Глава 1. Свойства контрольных экспериментов для

детерминированных графов

1.1 Основные определения и обозначения

1.2 Безреверсный базис и его свойства

1.3 Существование и некоторые общие свойства

контрольных экспериментов для детерминированных графов

Глава 2. Контроль детерминированных деревьев

2.1 Контрольный эксперимент для детерминированных деревьев

2.2 Контроль изоморфной вложимости

Глава 3. Контроль маркированных графов

3.1 Структура класса маркированных графов

3.2 Контрольные эксперименты для маркированных графов
Глава 4. Реализация контрольного эксперимента
конечным автоматом
4.1 Автоматы, реализующие контрольный эксперимент
4.2 Автоматы с красками
4.2.1 Автомат с одной краской
4.2.2 Автомат с к(С) красками
Заключение
Список литературы
Бурное развитие кибернетики и информатики стимулирует интенсивное развитие теории управляющих и вычислительных процессов, а также моделей (систем), реализующих эти процессы. Одной из основных моделей при этом является модель взаимодействия управляющей и управляемой систем (управляющего автомата и операционной среды) [1,2]. Взаимодействие этих систем зачастую представляется как процесс перемещения управляющего автомата по графу (“лабиринту”) управляемой системы [2], что привело к возникновению обширной и интенсивно развивающейся области исследований поведения автоматов в лабиринтах [3-11]. Одним из направлений этих исследований является анализ с помощью автомата изображений, формальных языков, рабочих пространств робота и других дискретных систем.
Одна из центральных и актуальных проблем такого анализа известна как “проблема проверки правильности карты” [7,8]. Эта проблема состоит в следующем: задан конечный граф-эталон (карта) и определен класс
исследуемых графов рабочих пространств. Требуется построить автомат, который, передвигаясь по произвольному графу из этого класса и воспринимая некоторую локальную информацию о вершинах пройденных путей, проверяет, изоморфен исследуемый граф эталону или нет. Процесс прохождения путей по графу, восприятия локальной информации о вершинах путей и вывода заключений о свойствах графа называется контрольным экспериментом над графом. При этом вершины и ребра исследуемого графа могут нести отметки, которые автомат во время эксперимента может изменять.
При исследовании проблемы проверки правильности карты наметилось несколько подходов. Один из них основан на том, что исследуемые графы являются конечными инициальными автоматами без выхода [3-5,12,13], т.е. конечными ориентированными графами с постоянными отметками на дугах. В рамках этого подхода найдены точные верхние оценки наименьшего времени,
за которое различаются два графа, предложен метод построения контрольных экспериментов относительно класса всех таких графов, число вершин которых не превосходит числа вершин эталона. Второй подход заключается в рассмотрении лабиринтов, являющихся неориентированными конечными графами, и в процессе эксперимента на ребрах графа управляющий автомат расставляет отметки [6-11]. Предложен ряд методов проведения контрольных экспериментов относительно конечных классов исследуемых графов. Третий подход исходит из предположения, что лабиринты являются неориентированными графами с отмеченными вершинами [14-18]. Предложены методы различения таких графов и методы проведения контрольных экспериментов для конечных классов графов.
Результаты, полученные в рамках этих подходов, не образуют цельной картины и, в отличие от “классической” теории экспериментов с автоматами, заложенной Э.Муром и С.В.Яблонским и созданной трудами многих исследователей [2,19-22], исследования в этой области находятся в зачаточном состоянии. Поэтому разработка этой тематики чрезвычайно актуальна.
Данная диссертационная работа посвящена проблематике, связанной с автоматным анализом графов (лабиринтов) с отмеченными вершинами, а именно вопросам исследования условий существования и методам построения контрольных экспериментов над этими графами.
Описание управляемых систем такими графами используется в системах распознавания зрительных образов [23,24], в системах навигации роботов [6-11,23,24], в моделях представления знаний в интеллектуальных системах принятия решений [25], в системах поиска в сетях ЭВМ и в мультиагентных системах [26], при разработке операционных сред вычислительных систем [1]. Поэтому тематика диссертации актуальна как в теоретическом, так и в прикладном плане.
Целью работы является нахождение условий существования контрольных экспериментов для потенциально бесконечных классов исследуемых графов; исследование свойств таких экспериментов; разработка методов построения

Теорема 2.1.3. Конечное множество слов РсМ+ является контрольным экспериментом для эталона Тє ДМ) относительно класса Л'(М) тогда и только 9 тогда, когда ІДРпС^є УГ(1) и в КГ(Т) найдется такой свободный базис
достижимости УР(Т), что/т(Р—/,т) содержит (УР(Т)М)-Д.
Доказательство теоремы следует непосредственно из лемм 2.1.2 и 2.1.3.
Рассмотрим способы построения контрольного эксперимента. Следующая теорема предлагает один из способов построения контрольного эксперимента для дерева Те ДМ) относительно класса ЛГ(М).
Теорема 2.1.4. Множество слов Сі(Т)=Б[У(Т)Мі] является контрольным экспериментом для эталона Тє ДМ) относительно класса ЛГ(М).
* Доказательство. Пусть Т - произвольное дерево из ДМ) и У(Т) - его базис достижимости. Поскольку У(Т) состоит только из безреверсных слов, то У(Т)сСі(Т). В тоже время, по лемме 1.2.4, У(Т) содержит все безреверсные слова языка Ь и, очевидно, что К(У(Т))=У(Т). Следовательно, С1(Т)гіТІ=У(Т). С другой стороны, как нетрудно видеть, С і (Т)-Тт=/) (С і (Т)-/,т)=( V (Т)М)-Тт.
Поскольку базис достижимости У(Т), очевидно, является также и свободным базисом достижимости дерева Т (т.е. У(Т)е РТ^Т)), то по теореме
• 2.1.3 Сі(Т) является контрольным экспериментом для дерева Т относительно класса ЛГ(М). Теорема доказана.
Сделаем ряд полезных оценок сложности полученного контрольного эксперимента С|(Т)=Б[У(Т)Мі].
Пусть п - число вершин дерева Т. Поскольку У(Т) содержит ровно п слов,
♦ то множество У(Т)Мі состоит из п|М|+1 слов. Ровно (п— 1) слово из них не являются безреверсными, причем, безреверсный базис кажщого из них состоит из единственного слова, очевидно входящего в У(Т)Мі. Следовательно, кратность эксперимента Сі(Т) составляет
| С і (Т)|=п| М |+1 -(п-1 )=п( |М|—1 )+2 . (2.1.1)