Установочные эксперименты с автоматами

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

§1. Основные понятия и обозначения

§2. Результаты работы

§3. Предыстория вопроса

Глава 1. Сложность условного установочного эксперимента для различных

классов автоматов

§1. Введение

§2. Основные определения и результаты

§3. Вспомогательные утверждения

§4. Доказательство теорем 1 и

§5. Доказательство теорем 3 и

§6. Доказательство теорем 5 и

§7. Связь длины установочного эксперимента с разбиениями Ик
Глава 2. Сложность установочного эксперимента для автоматов без выхода
§1. Введение
§2. Основные понятия и результаты
§3. Доказательство теорем 1,2 и
§4. Доказательство теоремы
§5. Вспомогательные определения и леммы
§6. Доказательство теоремы
§7. Случай автоматов над термами. Вспомогательные определения и леммы
§8. Доказательство теоремы о времени склейки г состояний автомата для почти всех
автоматов над термами
§9. Некоторые оценки для времени склейки г состояний в автоматах над термами
Глава 3. Соотношение сложностей условного и безусловного экспериментов
§1. Введение
§2. Основные определения и формулировка результатов
§3. Доказательство теоремы
§4. Доказательство теоремы
Глава 4. Установочный эксперимент для частично-определённых автоматов
§1. Введение
§2. Основные определения и результаты
§3. Понятия и результаты
§4. Доказательство теорем 1 и
§5,Оценки длины условного установочного эксперимента для частичных автоматов
Глава 5. Установочные эксперименты для автоматов с изменяемой
логикой поведения
§1. Введение
§2. Основные определения и результаты
§3. Понятия и результаты
§4. Связи степени отличимости автомата с длиной установочного
эксперимента

§5. Теорема об условной степени отличимости
§6. Доказательство теоремы
§7. Доказательство теоремы
§8. Доказательство теорем Зи4
Заключение
Список литературы

§1. Основные понятия и обозначения.
Настоящая работа посвящена исследованию свойств установочного эксперимента с автоматами.
Договоримся о следующих используемых в работе обозначениях и понятиях.
Пусть X и У конечные множества. Через |Х| обозначаем число элементов множества X, X х У - множество упорядоченных пар {(х,у),х Є Х,у Є У}, Хк - множество упорядоченных к—элементных наборов {(х1,Х2, ...,Хк),Хі Є Х,1 < і < к}.
Словом в алфавите X будем называть любую конечную последовательность элементов из множества X. Элементы последовательности, образующей слово, называем буквами слова. Длиной слова называем число его букв.
Пусть а = аіа2...ак — некоторое слово. Для каждого г такого, что 1 < г < к, префиксом слова а длины г будем называть слово аа.2... а,- , которое будем обозначать аг. Суффиксом слова а длины і будем называть слово щ_г+іщ._г+2... а*,. Через а (г) будем обозначать г—ую букву слова
а. Через 1(а) будем обозначать длину слова а. Множество всех слов в алфавите X обозначаем X*.
Пусть а = Х1Х2 ...ж,-,,/? = уіу2 ••-2/га—Два слова в алфавите X.
Конкатенацией слов а и /? называем слово ХХ2... х,- хуУ2... Уіг. Для операции конкатенации будем использовать знак *.
Натуральный ряд обозначаем К, множество натуральных чисел с нулем обозначаем N0. Множество действительных чисел обозначаем Е. Если х Є Е, то через [ж] обозначаем целую часть числа х. Начальный отрезок натурального ряда из г > 1 элементов обозначим Ег, таким образом, Ег — {1,2 г). Обозначим далее Е® = {0,1 г — 1}. Для п Є К, т Є М, т < п обозначим через Ет>п множество Еп ЕтПусть р — предикат на множестве X. Множество элементов х из X таких, что р{х) = 1, будем обозначать {х Є X р(х) = 1}. Пусть также И - конечное подмножество натуральных чисел яр — некоторый предикат на £>. Для обозначения минимального и максимального элементов из обладающих свойством, определяемым предикатом р, будем использовать запись: тіп{х Є -О | р{х) = 1}, тах{т Є 1? | р{х) = 1}.
Пусть X - множество и / : X -» N - некоторое отображение. Минимальное из натуральных чисел п со свойством п > /(л) для всех х из X, если такое существует, обозначим тах/(х). Если такого п не существует, то полагаем
ІЄЛ'

Для доказательства нижней оценки достаточно рассмотреть следующий автомат 210 = (А,С2,В,ір0,фо), А = {1,2}, <2 = {0,1,... ,п}, В - {0,1}, для которого
1)р(1,1) = 1, (р(г, 1) = п — і + 2, если і ф 1,
2)у>(1,0) = п, ср(г, 0) = і — 1, если г ф 1.
Можно убедиться в том, что для автомата 21о выполнено огД21о) = 2,1(210) = Зп - 6.
Так как, очевидно, 21о € ©п, то теорема 6 доказана.
§7. Связь длины установочного эксперимента с разбиениями Д*.
С каждым автоматом 21 = {А, С},В,ір, ф) свяжем последовательность = £о£і • • • £п—і, где £г есть мощность максимальной компоненты эквивалентности отношения Дг неотличимости словами длины 1. Считаем,
что £о = |<5|- Как известно [1], £г- ^ £і+і,£„_і = 1. Выделим
из последовательности £ монотонную подпоследовательность По
определению положим г'о = 0 и если > 1, то і}+ = тіп{г : £Г < ^.}. Эту последовательность назовем Д— последовательностью для автомата 21.
Теорема 8. Если 21 - приведенный автомат и - его II — последовательность, то
/(21) ^ ^і(£і0 Сії) "К г'2(Сіі — Сг'2) + • • • + їр+і(Сір Сір+і), г^е Сір+1
Доказательство. Построим дерево условного установочного эксперимента для автомата 21. Напомним, что это ориентированное от корня дерево такое, что для любой вершины и определены подмножество Б,, и слово ау, а для каждого ребра гйЙ определено слово так, что выполнены следующие условия:
1)5ц, = <5, где го- корень дерева,
2) Если е = (пщ) - ребро, выходящее из вершины и и <3е = {<7 Є
| ф{д,ау) = /?е}, то С^е ф 0 и С}щ = Тр{С^е,ау) и, кроме того, для любого
состояния д Є найдётся ребро е, выходящее из вершины и такое, что
ф{д,ау) = Д.
При этом, кроме того, листьям дерева соответствуют одноэлементные множества и им приписываются пустые слова из А*.
Предположим, что мы уже построили некоторую часть дерева установочного эксперимента для автомата 21 такую, что выполнены требования 1) и 2), но еще остаются некоторые листья этого дерева, которым соответствуют множества, содержащие более одного элемента. Пусть и - один из таких листьев. Тогда |5„| > 1. Найдем минимальный индекс ц такой, что |Д„| > Непосредственно из определения