|
Оглавление
 Введение 5 1. Обозначения и термины 15 Алфавиты и буквы 15 Слова 17 Обращения слов 20 Удвоения слов 21 Вхождения слов 21 Замены в словах 23 Формулы 26 Простые формулы 26 Заключительные формулы 26 Одноразовые формулы 27 Пополняющие формулы с простыми пополнениями 28 Пополняющие формулы с заключительными пополнениями 29 Пополняющие формулы с одноразовыми пополнениями 30 Пополняющие формулы с групповыми пополнениями 31 Функции для обработки формул 32 Схемы алгорифмов 38 Преобразования схем алгорифмов и слов 42 Самопополняемые слева алгорифмы 46 Определение самопополняемого слева алгорифма 46 Правила применения схемы самопополняемого слева алгорифма 47 1.12. Методы правой и левой индукции 51 Метод правой индукции 51 Метод левой индукции 52 Обращающие и удваивающие алгорифмы 52 Вспомогательные обозначения 53 Область действия обозначений и терминов 54 2. Обращающий самопополняемый слева алгорифм с простым пополнением с двухбуквенным дополнительным алфавитом 55 2.1. Описание алгорифма 55 Схемы алгорифма 55 Преобразование исходного слова алгорифмом 57 Вспомогательные утверждения 58 Основное утверждение 70 Характеристики алгорифма 72 Длины схем 72 Число шагов преобразования исходного слова 73 Мощности алфавитов схем 83 2.5. Пример 84 3. Обращающий самопополняемый слева алгорифм с простым и заключительным пополнениями с однобуквенным дополнительным алфавитом 86 3.1. Описание алгорифма 86 Схемы алгорифма 86 Преобразование исходного слова алгорифмом 89 Вспомогательные утверждения 90 Основное утверждение 104 Характеристики алгорифма 105 Длины схем 105 Число шагов преобразования исходного слова 107 3.4.3. Мощности алфавитов схем 117 3.5. Пример 118 4. Обращающий самопополняемый слева алгорифм с групповым пополнением с однобуквенным дополнительным алфавитом 121 4.1. Описание алгорифма 121 Схемы алгорифма 121 Преобразование исходного слова алгорифмом 123 Вспомогательные утверждения 124 Основное утверждение 136 Характеристики алгорифма 137 Длины схем 137 Число шагов преобразования исходного слова 139 Мощности алфавитов схем 148 4.5. Пример 149 5. Обращающий самопополняемый слева алгорифм с одноразовыми пополнениями с двухбуквенным дополнительным алфавитом 152 5.1. Описание алгорифма 152 Схемы алгорифма 152 Преобразование исходного слова алгорифмом 155 Вспомогательные утверждения 156 Основное утверждение 165 Характеристики алгорифма 166 Длины схем 166 Число шагов преобразования исходного слова 168 Мощности алфавитов схем 173 5.5. Пример 174 6. Обращающий самопополняемый слева алгорифм с одноразовыми пополнениями с однобуквенным дополнительным алфавитом 177 6.1. Описание алгорифма 177 Схемы алгорифма 177 Преобразование исходного слова алгорифмом 179 Вспомогательные утверждения 180 Основное утверждение 186 Характеристики алгорифма 187 Длины схем 187 Число шагов преобразования исходного слова 189 Мощности алфавитов схем 192 6.5. Пример 193 7. Удваивающий самопополняемый слева алгорифм с простым пополнением с двухбуквенным дополнительным алфавитом 196 7.1. Описание алгорифма 196 Схемы алгорифма 196 Преобразование исходного слова алгорифмом 198 Вспомогательные утверждения 199 Основное утверждение 213 Характеристики алгорифма 214 Длины схем 214 Число шагов преобразования исходного слова 216 Мощности алфавитов схем 227 7.5. Пример 228 8. Удваивающий самопополняемый слева алгорифм с заключительным и одноразовыми пополнениями с двухбуквенным дополнительным алфавитом 231 8.1. Описание алгорифма 231 Схемы алгорифма 231 Преобразование исходного слова алгорифмом 234 Вспомогательные утверждения 235 Основное утверждение 242 Характеристики алгорифма 243 Длины схем 243 Число шагов преобразования исходного слова 245 Мощности алфавитов схем 248 8.5. Пример 249 Обращающие и удваивающий нормальные алгорифмы 252 А.1. Обращающий нормальный алгорифм с двухбуквенным дополнительным алфавитом . . . 252 А. 1.1. Схема алгорифма 252 А.1.2. Характеристики алгорифма 253 А.2. Обращающий нормальный алгорифм с однобуквенным дополнительным алфавитом ... 254 А.2.1. Схема алгорифма 254 А.2.2. Характеристики алгорифма 255 А.З. Удваивающий нормальный алгорифм с трехбуквенным дополнительным алфавитом . . . 256 А.3.1. Схема алгорифма 256 А.3.2. Характеристики алгорифма 258 Б. Основные обозначения 259 Связи лемм и теорем 266 Библиографический список 274 Предметный указатель 278 Об авторах
|