Синхронизируемость конечных автоматов в экстремальном и среднем случаях

• Автор: Закс, Юлия Иосифовна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Екатеринбург
• Количество страниц: 89 с. : ил.

Оглавление
Введение

0.1 Синхронизируемые автоматы.

0.2 Синхронизируемость автоматов в экстремальном случае, гипотеза Черни.

0.3 Синхронизируемость автоматов в среднем случае

0.4 Апробация результатов

1 Синхронизируемые автоматы с буквой дефекта 2

1.1 Формулировка и обсуждение результатов

1.2 п серия автоматов с буквойбактрианом

1.3 п серия автоматов с буквойдромадером

2 Синхронизируемые автоматы с буквой большого дефекта

2.1 Постановка задачи и основные определения
2.2 Медленно синхронизируемые автоматы с буквой большого
дефекта.
2.3 Экспериментальная проверка экстремальности серий при небольших п
3 Синхронизируемость случайных автоматов
3.1 Предварительные сведения.
3.2 Случайные автоматы, синхронизируемые с высокой вероятностью
3.3 Случайные автоматы, для которых выполняется гипотеза
3.4 Случайные автоматы, синхронизируемые с конечной вероятностью
Литература


Заметим, что стиранием букв со стрелок автомата я/ и “склеиванием” одинаковых стрелок мы получим ориентированный граф: назовем его графом автомата. Более строго, граф автомата - это орграф, множество вершин которого совпадает с множеством состояний автомата &, а дуги соответствуют переходам автомата, т. Основное понятие, изучаемое в данной диссертации, - это понятие синхронизируемого автомата. Автомат я/ = (С2,? Е ? В символах это свойство выражается равенством ру = qw для всех р, q € С^. Любое слово с таким свойством называется синхронизирующим для автомата я/. Пример синхронизируемого автомата с четырьмя состояниями приведен на рис. Более того, IV является кратчайшим словом с таким свойством, хотя проверка этого факта уже менее тривиальна. Синхронизируемые автоматы нашли широкое практическое применение в различных областях: роботике, а точнее в производстве механизмов для сортировки, обработки и установки деталей определенной конструкции [], тестировании реагирующих систем и протоколов []. Подробнее о различных применениях синхронизируемых автоматов см. Особо хочется остановиться на мотивации, одновременно интересной теоретически и непосредственно практически применимой, а именно, на мотивации из теории кодирования. Для описания данной мотивации нам понадобится несколько определений, связанных со словами. Слово и € * называется префиксом слова \> є ? V є Г* такое, что XV = XIV. Если слово V непустое, то префикс называется собственным. Слово х Є Г* является фактором слова IV Є Iесли существуют слова и, V Є I* такие, что XV = иху. Префиксным кодом над конечным алфавитом ? X слов из I* таких, что никакое слово из X не является префиксом никакого другого слова из X. Префиксный код называется максимальным, если он не содержит другого префиксного кода над тем же алфавитом. Максимальный префиксный код X над алфавитом Ї. X* такое, что для любого слова XV Є * выполняется ххгк Є X*. Такое слово х называется синхронизирующим адовом кода X. Преимущество синхронизирующих кодов состоит в том, что в случае возникновения помех при передаче информации от передатчика к приемнику, передачу можно восстановить. Достаточно передать синхронизирующее слово, и все последующие символы будут декодироваться верно. Более того, поскольку вероятность того, что некоторое слово V є I* содержит фиксированный фактор х, с ростом длины слова стремится к 1, при передаче большого количества информации в некоторые моменты времени синхронизирующие коды синхронизируются сами. Как показано в [], это свойство синхронизирующих кодов является характеристическим. Рассмотрим пример, иллюстрирующий введенные понятия. Пусть I = {0,1}, X = {0,,,0,,,,0,1}. Слова кода - это листья бинарного дерева на рис. Легко проверить, что X является максимальным префиксным кодом и каждое из слов 0, , 1 ПО,. ООО, а приемник в силу помех в канале принимает слово 0. Тогда приемник интерпретирует слово как кодовое, и синхронизация между приемником и передатчиком будет потеряна. Однако, с высокой вероятностью1 синхронизация быстро восстановится, а именно в тот момент, когда в потоке передаваемых данных встретится одна из этих последовательностей 0, , , Некоторые примеры синхронизации потоков приведены на рис. Передано 0 | | 0 1 | . Получено |0|||. Передано 0 1 1 1 |0| |0| |0 |. Получено | [1 |0 [1 | Ц|. Передано 0|0|1 0 |. Получено |0| | | . Рис. Пусть X - максимальный конечный префиксный код над алфавитом I, тогда он может быть декодирован с помощью автомата, определенного следующим образом. В качестве возьмем множество всех собственных префиксов слов из X, включая пустое слово Л, в качестве алфавита - ? Получившийся автомат я/х полон в силу того, что X максимален. Нетрудно видеть, что я/х - синхронизируемый автомат тогда и только тогда, когда X - синхронизируемый код. Более того, слово х синхронизирует код X тогда и только тогда, когда оно переводит автомат я/х в состояние Л. Рис 0. Под высокой вероятностью мы понимаем вероятность, которая стремится к 1 при длине символьной последовательности, стремящейся к бесконечности.