Содержание
Введение
0.1 Синхронизируемые автоматы и гипотеза Черни.
0.2 Синхронизируемые автоматы с нулем
0.3 Конечно порожденные синхронизируемые автоматы
0.4 Универсальные синхронизирующие и сжимающие слова
0.5 Предварительные сведения.
0.6 Апробация результатов
1 Медленно синхронизируемые автоматы с нулем и непокрывающие множества
1.1 Неиокрывающие множества
1.2 Полуцвегочный автомат для конечного множества слов . .
1.3 Непокрывающие множества и синхронизируемые автоматы
2 Конечно порожденные синхронизируемые автоматы
2.1 Характеризация конечно порожденных синхронизируемых
автоматов.
2.2 Алгоритм проверки конечности языка минимальных синхронизирующих слов
2.3 Время работы алгоритма.
2.4 Гипотеза Черни для класса конечно порожденных синхронизируемых автоматов
2.5 Верхняя оценка длины минимального синхронизирующего
2.6 Вычислительная сложность задачи проверки конечности
языка минимальных синхронизирующих слов.
2.7 Вычислительная сложность в случае постоянного алфавита
3 Некоторые свойства 1сжимающих и 2синхронизирующих слов
3.1 Характеризация 2сжимающих слов.
3.1.1 Классификация 2сжимаемых автоматов
3.1.2 Критерий 2сжимаемости слова.
3.1.3 Критерий в случае одной почти перестановочной буквы
3.1.4 Критерий в случае двухбуквеиного алфавита
3.2 Нижняя оценка длины кратчайшего
2сжимающего слова
3.3 Место языка 2сжимаклцих слов в иерархии Хомского .
3.4 Характеризация 2сиихронизирующих слов
3.5 Реконструкция 2сжимаклцих и 2синхронизи
рующпх слов по внутренним отрезкам
3.6 Модификация алгоритма распознавания
2сжимающих слов
Список литературы
- Київ+380960830922