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

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

СОДЕРЖАНИЕ ВВЕДЕНИЕ
1. ТОПОЛОГИЧЕСКИЕ СВОЙСТВА ЭКСПЕРИМЕНТОВ С АВТОМАТАМИ
1.1. Основные понятия и определения
1.2. Обобщенные контрольные эксперименты
1.3. Обобщенные распознающие эксперименты
1.4. Выводы
2. КЛАССЫ АВТОМАТОВ, ЗАДАННЫЕ ФИНИТНЫМИ СРЕДСТВАМИ
... >*
2.1. Введение
#!» ч 'ЛУ
2.2. Основные понятия и определения
2.3. Алгебраическая структура множества финитно-определенных классов
2.4. Операторы алгебраического замыкания и аппроксимации
2.5. Выводы
3. ЭКСПЕРИМЕНТЫ В ФИНИТНО-ОПРЕДЕЛЕННЫХ КЛАССАХ 1-ГО РОДА
3.1. Основные понятия и определения
3.2. Топологические свойства финитно-определенных классов 1-го рода
3.3. Контрольные эксперименты в финитно-определенных классах 1 -го рода
3.4. Распознающие эксперименты в финитно-определенных классах 1 -го рода
3.5. Выводы
4. ЭКСПЕРИМЕНТЫ В ФИНИТНО-ОПРЕДЕЛЕННЫХ
КЛАССАХ 2-ГО РОДА
4.1. Структура финитно-определенных классов 2-го рода
4.2. Контрольные эксперименты в финитно-определенных классах
2-города
4.3. Простые контрольные эксперименты в финитно-определенных классах 2-го рода
4.4. Распознающие эксперименты в финитно-определенных
классах 2-го рода
4.5. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВВЕДЕНИЕ
Актуальность темы.
Данная работа посвящена изучению одной из классических и актуальных проблем теории конечных автоматов - задаче сравнения поведения автоматов с помощью экспериментов. При этом иод экспериментом [15,17,42] понимается процесс подачи входных слов на неизвестный автомат - ’’черный ящик”, принадлежащий априорно заданному классу Е, получение его реакций и вывод заключений о функциях автомата. Для конечных классов Е теория экспериментов разработана достаточно хорошо [4,12.13,14,42,48].
Для бесконечных классов Е изучение экспериментов находится в зачаточном состоянии. Принципиальными трудностями таких исследований являются отсутствие общих конструктивных средств представления априорных классов и общих алгоритмов вывода заключений. В последнее время в задачах контроля и диагностики дискретных устройств возникают потенциально бесконечные классы автоматов, задаваемые конечными средствами - спецификациями на заданное поведение. Другими источниками бесконечных классов Е, заданных конечными средствами, являются задачи контроля протоколов сети ЭВМ, компонент сети автоматов и др. [5,24,25,35,36].
Исходя их сказанного задачи исследования процессов вывода заключений, получения условий существования и алгоритмов проведения экспериментов для бесконечных классов Е являются актуальными в прикладном плане. Нетривиальность и важность задач делает их актуальными и в теоретическом плане.
Связь работы с научными программами, планами, темами.
Диссертационная работа выполнена в соответствии с планами нау-
и пространство (21(17),(3) - бэровским пространством автоматов.
1.2. Обобщенные контрольные эксперименты.
Распространим понятие контрольных экспериментов на любые метрические пространства автоматов, которые для метрики /3 равносильны классическим контрольным экспериментам. Пусть даны автомат А и класс Е.
В теории экспериментов содержательно под контрольным экспериментом с автоматом-эталоном А относительно класса Е понимают [ 32,48 ] процесс подачи на автомат, называемый ’’черным ящиком”, из Р и {А}, входных слов, наблюдения выходных реакций черного ящика и вывода заключения на основе полученного в эксперименте множества вход-выходных слов : черный ящик эквивалентен А или нет.
Существует несколько по существу равнозначных подходов к уточнению понятия ’’контрольный эксперимент”. В [ 17 ] контрольным экспериментом с автоматом относительно автомата-эталона А и класса Е ’’неисправных” автоматов называется такое конечное множество IV вход-выходных слов, что IV С Ьа и если ТЕ С Ьв, где В £ Е, то А= В.
Для бэровской метрики /3 и такого определения контрольных экспериментов справедлив следующий критерий существования контрольных экспериментов относительно А и Е :
Предложение 1.2.1. Равносильны утверждения:
1. существует контрольный эксперимент относительно А и Е;
2. множество ЬкА является контрольным экспериментом относительно А и Е для некоторого к
3. класс 01/к(А) ПЕС {А} для некоторого к-
4. класс 0/к{А) ПЕ конечен для некоторого к;