Введение
1 Языки синхронизирующих слов медленно синхронизируемых автоматов 31
1.1 Верхняя оценка синхронизационной сложности идеального языка 32
1.2 Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов 34
1.3 Вопрос о единственности МСА 49
2 Главные идеальные языки и синхронизируемые автоматы 52
2.1 Вопрос о единственности МСА в классе сильно связных автоматов 53
2.2 Алгоритм построения сильно связного МСА для главного идеального языка 56
2.3 Доказательство корректности алгоритма 61
2.4 Синхронизационная сложность главного идеального языка 64
2.5 Синтаксическая полугруппа главного идеального языка 66
3 Конечно порожденные идеальные языки и синхронизиру емые автоматы 75
3.1 Идеальный язык, порожденный ТІ1 75
3.2 Идеальный язык, порожденный множеством слов постоянной длины
3.3 Идеальный язык, порожденный конечным множеством слов 81
3.4 Идеальный язык, порожденный двумя словами 83
4 Вычисление синхронизационной сложности идеальных языков 90
4.1 Принадлежность классу PSPACE 91
4.2 PSPACE-полнота 93
5 Представление регулярных языков синхронизируемыми автоматами 108
5.1 Левые факторы главных левых идеальных языков 109
5.2 Регулярные языки и синхронизируемые автоматы 114
Список литературы
