Дескриптивная сложность некоторых преобразований регулярных языков

Содержание
Введение
0.1 Регулярные языки и конечные автоматы.
0.2 Дескриптивная сложность.
0.3 Содержание диссертации
0.4 Апробация результатов
1 Предварительные сведения
2 Дескриптивная сложность окрестности регулярного языка в метрике Хэмминга
2.1 Окрестность языка в метрике Хэмминга
2.2 Верхние оценки недетерминированной и детерминированной сложности
2.3 Нижняя оценка недетерминированной сложности
2.4 Нижняя оценка детерминированной сложности.
2.5 Сопоставление оценок детерминированной сложности и результатов экспериментов.
3 Дескриптивная сложность применения конечного траисдьюсера
3.1 Конечные трансдьюсеры.
3.2 Недетерминированная сложность применения конечного трансдыоссра.
3.3 Детерминированная сложность применения конечного трансдыоссра
4 Дескриптивная сложность динамической окрестности регулярного языка
4.1 Динамическая окрестность языка
4.2 Регулярность динамической окрестности регулярного языка .
4.3 Верхняя оценка недетерминированной сложности
Список литературы