Аппроксимация длин синхронизирующих слов для конечных автоматов

Содержание
Сведение
0.1 Синхронизируемые автоматы и гипотеза Черни
0.1.1 Синхронизируемость автоматов
0.1.2 Оценки длин кратчайших синхронизирующих слов .
0.1.3 Доказанные квадратичные оценки
0.1.4 Метод расширения и однокластерные автоматы . . .
0.1.5 Алгоритмы поиска кратчайших синхронизирующих
0.2 Допустимые графы и проблема раскраски дорог
0.2.1 Синхронизируемые раскраски.
0.2.2 Алгоритмы поиска оптимальной раскраски.
0.3 Обзор полученных результатов
0.3.1 Квадратичные оценки на функцию Черни.
0.3.2 Алгоритмы вычисления функции Черни
0.4 Апробация результатов.
1 Метод расширения и гипотеза Черни
1.1 Алгоритм расширения и связанные свойства
1.2 Медленно расширяемые множества
1.3 Локальные версии свойств
1.4 Однокластерные автоматы.
2 Поиск кратчайших
синхронизирующих слов
2.1 Неанпроксимирусмость с погрешностью
меньше 2
2.2 Основной результат
2.3 Случай двухбуквенного алфавита
3 Поиск оптимальной раскраски
3.1 Вспомогательные определения
и формулировка результата
3.2 Случай трехбуквенноо алфавита.
3.3 Случай двухбуквенного алфавита
Список литературы