Универсальные синхронизирующие и универсальные сжимающие слова

Содержание
1 Введение
1.1 Синхронизируемость и сжимаемость.
1.2 Универсальные синхронизирующие слова
1.3 Универсальные сжимающие слова.
1.4 Апробация результатов.
2 Разрешимость задачи распознавания сжимающих слов
3 Алгоритм распознавания сжимающих слов
3.1 Предварительные сведения и определения
3.1.1 Фишки и дырки
3.1.2 Послойное представление
3.1.3 Строение слоя
3.1.4 Строение слоя псобственного автомата
3.1.5 Метки состояний и роли букв .
3.1.6 Основа
3.1.7 Операции по изменению основы.
3.1.8 Вычисления по основе.
3.2 Алгоритм
3.2.1 Общее описание алгоритма.
3.2.2 Проверка слова на пполноту.
3.2.3 Генерация ролей букв.
3.2.4 Распределение ролей и начало рекурсии
3.2.5 Шаг рекурсии разбиение на подклассы
3.2.6 Классы автоматов, не требующие разбиения.
3.2.7 Корректность.
3.3 Неизоморфность рассматриваемых автоматов
3.4 Время работы алгоритма
4 Алгоритмы поиска и построения синхронизирующих и сжимающих слов
4.1 Переборный алгоритм поиска кратчайших синхронизирующих
4.2 Поиск сжимающих слов
4.3 Распознаватель слов, синхронизирующих автомат.
4.4 Алгоритм построения синхронизирующих слов через пересечение языков
4.5 Результаты
5 Зеркальный образ 2синхронизирующих слов
6 Заключение
Список литературы