Введение
Глава 1. Сложность условного установочного эксперимента для различных классов автоматов 21
1. Введение 21
2, Основные определения и результаты 21
3. Вспомогательные утверждения 23
4. Доказательство теорем 1 и 2 38
5. Доказательство теорем 3 и 4 41
6. Доказательство теорем 5 и б 47
7. Связь длины установочного эксперимента с разбиениями Rk 50
Глава 2. Сложность установочного эксперимента для автоматов без выхода 53
1. Введение 53
2, Основные понятия и результаты 53
3. Доказательство теорем 1,2 и 3 54
4. Доказательство теоремы 4 58
5. Вспомогательные определения и леммы .60
6. Доказательство теоремы 5 66
7. Случай автоматов над термами. Вспомогательные определения и леммы 70
8. Доказательство теоремы о времени склейки г состояний автомата для почти всех автоматов над термами 74
9. Некоторые оценки для времени склейки г состояний в автоматах над термами 77
Глава 3. Соотношение сложностей условного и безусловного экспериментов 79
1. Введение 79
2. Основные определения и формулировка результатов 79
3. Доказательство теоремы 1 80
4. Доказательство теоремы 2 81
Глава 4. Установочный эксперимент для частично-определённых автоматов 87
1, Введение 87
2. Основные определения и результаты 87
3. Понятия и результаты 88
4. Доказательство теорем 1 и 2 91
5. Оценки длины условного установочного эксперимента для частичных автоматов 97
Глава 5. Установочные эксперименты для автоматов с изменяемой логикой поведения 99
1. Введение 99
2. Основные определения и результаты 100
3. Понятия и результаты. 102
4. Связи степени отличимости автомата с длиной установочного эксперимента 105
5. Теорема об условной степени отличимости 107
6. Доказательство теоремы 1
7. Доказательство теоремы 2
8. Доказательство теорем 3 и 4 113
Заключение 115
Список литературы 117
