Содержание
1 Введение
1.1 Определения и мотивация.
1.1.1 Детерминированные автоматы.
1.1.2 Частичные автоматы.
1.2 Постановка задач.
1.2.1 Общая постановка задач
1.2.2 Классы автоматов и основные результаты
1.2.3 Таблица результатов полученных раиее
1.3 Апробация результатов
2 Детерминированные автоматы
2.1 Нижняя оценка для автоматов с нулем
2.1.1 Пример для четных п.
2.1.2 Пример для нечетных п.
2.1.3 Результаты компьютерных экспериментов.
2.2 Проверка автоматов на синхронизируемость.
2.3 Сложность поиска длин кратчайших синхронизирующих слов
2.3.1 Класс всех ДКА
2.3.2 Автоматы с нулем, апериодические, тривиальные и
частично монотонные автоматы. Сжимаемость.
2.3.3 Коммутативные автоматы
2.3.4 Автоматы с простыми ндемпотентами.
2.3.5 Монотонные тт циклически монотонные автоматы
2.3.6 Автоматы, содержащие цикл по всем состояниям
3 Частичные автоматы
3.1 Нижние оценки длины бережно синхронизирующих слов .
3.1.1 Пример для числа состояний кратного трем
3.1.2 Пример для числа состояний равного степени тройки .
3.1.3 Трехбуквенный алфавит.
3.1.4 Двухбуквенный алфавит
3.2 Проверка на бережную синхронизируемость. Принадлежность
к
3.2.1 Постановка задач. Общие факты.
3.2.2 Принадлежность к .
3.3 Проверка на бережную синхронизируемость. трудность
3.3.1 Алгоритм проверки на выполнимость.
3.3.2 Построение множества состояний автомата.
3.3.3 Задание функции переходов.
3.3.4 Описание обнуления счетчика.
3.3.5 Описание шага синхронизации.
3.3.6 Случай истинной формулы
3.3.7 Случай ложной формулы Р
3.3.8 Основной результат.
4 Заключение
Список литературы
- Киев+380960830922