Оценки длины и вычислительной сложности синхронизации конечных автоматов

• Автор: Мартюгин, Павел Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 123 с. : ил.

Содержание
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 Случай истинной формулы F
3.3.7 Случай ложной формулы F
3.3.8 Основной результат
4 Заключение
Список литературы

1 Введение
1.1 Определения и мотивация
1.1.1 Детерминированные автоматы
Детерминировалтым конечным автоматом (ДКА) мы будем называть тройку = (<2- 2, (5), где <5 — конечное множество состояний, Е — конечный алфавит и 5 — всюду определенная функция переходов, действующая из <3 х Е в <3. Пусть Е* — множество всех слов над алфавитом
ДКА я/ = (<3,П,<5) называется синхронизируемым, если существует слово ШЄЕ*, под действием которого все состояния автомата отображаются в какое-то одно, или, говоря формально, найдется такое состояние уо Є (, что для любого состояния д Є <5, д(у,и>) = у0- Такое слово -ш мы будем называть словом, синхронизирующим автомат .с/ в состояние уо.
На Рис.1 приведен пример синхронизируемого автомата. Несложно проверить, что слово аЬ3аЬ3а синхронизирует изображенный автомат в состояние 2. Немного сложнее проверить, что слово аЪ3аЬ3а является кратчайшим среди всех слов, синхронизирующих этот автомат.
Почему слова называются синхронизирующими? Для ответа на этот вопрос представим себе, что есть некоторое количество одинаково устроенных автоматов, работающих независимо. Пусть в какой-то момент времени каждый из автоматов находится в определенном состоянии, и эти состояния могут быть различными для разных автоматов. Если ко всем автоматам одновременно применить синхронизирующее слово, то они окажутся в одном и том же состоянии. Тем самым, их дальнейшая работа будет синхронизирована. Поэтому слова и называются синхронизирующими.
Для математиков понятие синхронизируемости автоматов само по себе является естественным и интересным, однако оно также находит свое применение в различных практических приложениях. Например, синхронизация

Рис. 1: Автомат Черни для /г
Предложение 2.4. Задача БУ N (топ) может, быть решена за время 0(пк), где к — разліер алфавита, п — количество состояний автомата.
Доказательство. Автомат &У — монотонный, поэтому на множестве его состояний может быть введен линейный порядок <, сохраняемый действием букв. Пусть С) = {1
Доказательство использует идею доказательства верхней оценки величины штоп(п) — п — 1 из [11]. Пусть р = тах{д Є <51 Это Є Е*, 1.то = д}. Пусть V Є Е* такое, что 1-й = р. Если найдется слово и Є Е* такое, что п.и < р, то слово иу будет синхронизировать автомат в состояние р, так как для любого q Є Q, дми < п.ш < р.у < р, и д.иу > 1 .иу > 1-у = р. Алгоритм поиска синхронизирующего слова будет состоять из поиска слова V и состояния д с последующим поиском слова и. Приведем формальное описание алгоритма:
£=1,у =
Пока существует буква а Є Е такая, что £.а > £ у = уа £ — £.а
р = £
г ~п, и
Пока г > р и существует буква а € Е такая, что і.а > £ у = иа г — г.а
Если г > р то
Автомат не синхронизируем
Иначе
Автомат л/ синхронизируем, и слово иу является синхронизирующим
Оба цикла в алгоритме проделают вместе не более чем ті — 1 итерацию. Каждая проверка на существование подходящей буквы а может быть осуществлена перебором всех букв из Е, то есть за время не превосходящее О (к). Поэтому время работы алгоритма не превосходит 0(пк). Предложение доказано. _ □
Заметим, что алгоритм, описанный в доказательстве предложения, позволяет найти слово длины не превосходящей п — 1, синхронизирующее заданный монотонный ДКА, и работает за время 0(пк). Однако, найденное слово может не быть кратчайшим синхронизирующим для автомата л/.