Аппроксимация длин синхронизирующих слов для конечных автоматов

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

Содержание
Введение
0.1 Синхронизируемые автоматы и гипотеза Черни
0.1.1 Синхронизируемость автоматов
0.1.2 Оценки длин кратчайших синхронизирующих слов .
0.1.3 Доказанные квадратичные оценки
0.1.4 Метод расширения и однокластерные автоматы
0.1.5 Алгоритмы поиска кратчайших синхронизирующих

0.2 Допустимые графы и проблема раскраски дорог
0.2.1 Синхронизируемые раскраски
0.2.2 Алгоритмы поиска оптимальной раскраски
0.3 Обзор полученных результатов
0.3.1 Квадратичные оценки на функцию Черни
0.3.2 Алгоритмы вычисления функции Черни
0.4 Апробация результатов
1 Метод расширения и гипотеза Черни
ГГ Алгоритм расширения и связанные свойства
1.2 Медленно расширяемые множества
1.3 Локальные версии свойств
1.4 Однокластерные автоматы
2 Поиск кратчайших
синхронизирующих слов
2.1 Неаппроксимируемость с погрешностью
меньше
2.2 Основной результат
2.3 Случай двухбуквенного алфавита
3 Поиск оптимальной раскраски
3.1 Вспомогательные определения
и формулировка результата
3.2 Случай трехбуквенного алфавита
3.3 Случай двухбуквенного алфавита
Список литературы

Введение
0.1 Синхронизируемые автоматы и гипотеза Черни
Как известно, все системы, возникающие па практике, рассматриваются в науке в виде непрерывных пли дискретных моделей. Одной из самых простых и в то же время эффективных моделей дискретных систем являются конечные автоматы. Детерминированным конечным автоматом называется тройка объектов .с/ = (С}Д,6), где <3 - множество состояний, Е - входной алфавит, и 5 : (^ х Т; —>■ (^) - всюду определенная функция переходов автомата. В работе рассматривается только этот вид автоматов. Функция 5 продолжается единственным образом на множество ф х Е где Е* обозначает свободный моноид над Е, элементы которого называются словами. Таким образом, каждое слово из Е* действует на множестве <3 в соответствии с функцией переходов
Несмотря на простоту определения, автоматы являются естественной и широко используемой конструкцией для моделирования дискретно работающих устройств. В частности, при помощи них моделируются различные вычислительные системы (компьютеры), получающие все более широкое применение. При таком моделировании состояния автомата соответствуют возможным состояниям системы, а буквы соответствуют допустимым операциям системы. В силу внешних воздействий или внутренних причин в таких системах могут происходить некорректные переходы. Для того чтобы можно было вернуть контроль над системой после некорректных переходов, не прибегая к ее анализу, целесообразно проектировать систему таким образом, чтобы она обладала некоторой «перезагрузочной» последовательностью операций. Таким образом, вопрос существования перезагрузочной последовательности и вопрос о том, насколько короткой ее можно выбрать являются существенными для рассматриваемых систем.
Введем теперь формальное определение синхронизирующих слов, играющих роль перезагрузочных последовательностей при моделировании систем конечными автоматами. Слово гг 6 Е* в автомате .е/ называется синхронизирующим, если его действие «перезагружает» автомат , т. е. переводит автомат в некоторое состояние вне зависимости от того состояния, в котором автомат находился до применения этого слова. Иначе говоря, слово гг синхронизирующее, если й(с/, гг) = 5(р, щ) для всех д,р є <

История возникновения идеи синхронизируемости подробно освещена в недавнем обзоре М. В. Волкова [44]. Там отмечено, что истоки понятия еннхронизируемости можно найти уже в рамках классических «умозрительных экспериментов» Мура [30]. Мур и его последователи использовали конечные автоматы для моделирования дискретно работающих устройств (компьютеров). При этом возникал следующий естественный вопрос: как восстановить контроль над устройством, не зная его текущего состояния, но наблюдая его поведение в ответ на различные посылаемые ему входные сигналы? В 1956 году Мур [30] показал, что при некоторых условиях можно однозначно определить состояние, в которое автомат приходит под действием подходящей последовательности сигналов. В сто работе такая последовательность называлась экспериментом. Отметим, что эксперименты Мура были адаптивными, т. е. каждое следующее действие выбиралось на основе реакции устройства на предыдущие действия. В 1958 году Гинзбург [22] рассмотрел особый тип экспериментов, которые он назвал однородными. Такой эксперимент - это просто фиксированная последовательность сигналов, т. е. подходящее слово над входным алфавитом; особенностью однородных экспериментов являлось то, что ответные сигналы нужны были только для определения состояния устройства в конце эксперимента. Отсюда понадобился всего один шаг, чтобы прийти к понятию синхронизирующего слова - эксперимента, в котором вообще не учитываются ответные сигналы устройства. Отметим, что это понятие является довольно естественным с точки зрения практики, поскольку далеко не всегда можно наблюдать ответные сигналы устройства: например, при движении спутника вокруг Луны он не может контролироваться с Земли в момент, когда он находится «позади» Луны. С середины 60-х годов прошлого века теория синхронизируемых автоматов начинает активно развиваться ввиду многочисленных приложений таких автоматов в различных областях: тестировании систем, роботике, символической динамике и др., см. обзоры [28,37,44].
Если автомат .е/ обладает хотя бы одним синхронизирующим словом, то он называется синхронизируемым, а длина кратчайшего синхронизирующего слова для обозначается через £(л/). Само отображение £, ставящее в соответствие автомату 8/ число €.(8/), будем называть функцией Черни. В качестве примера рассмотрим изображенный на рис. 1 автомат ‘йф Нетрудно проверить, что автомат ^ синхронизируем и что кратчайшим синхронизирующим словом этого автомата является Ъа?ЪаАЬ. Следовательно, £(%ч) = 9. Этот пример принадлежит к се-

Это наталкивает на мысль ослабить свойство строгого /с-расширения (^-расширения аналогично) до следующего свойства строгого к-локаль-ного расширения: существуют подмножества Cs, Се Ç Q и слова vs,ve Є Е* такие, что
Cs.va = 1, Ce.v~l =Q, Cs С CE,
и каждое собственное подмножество S множества Се является k(n — 1)-расширяемым в С„, т. е.
IS.u"1 П Се| > |5 П Се
для некоторого слова v длины не больше /с (гг — 1).
Если n-автомат srf удовлетворяет свойству строгого fc-локального расширения, то он обладает синхронизирующим словом длины не больше |'д| + |г>е| + (|С-в| — |С5|)А:(?г — 1). Ясно, что при подходящих ограничениях на длины слов vs и ve, получаются соответствующие квадратичные оценки. Аналогичным образом, свойство fc-баланса может быть ослаблено до следующего свойства к-локалъного баланса: каждое собственное подмножество S множества Се допускает набор слов vi,v2... vr длины не больше k(n — 1) таких, что
2—1 1°ЄІ
Свойство к-локального баланса влечет свойство строгого (к + ^-локального расширения для тех же параметров. Это утверждение доказывается аналогично лемме 1.1, где роль множества Q в большинстве мест играет Се. Такого рода доказательства можно найти также в статьях [11,45].
Легко проверить, что свойство строгого 1-локального расширения выполняется для автомата srf (к2, к) для
Cs = {<1о,4і}, vs = ba
Ce Qit • • ' і Чт}з ve a.
Более того, алгоритм расширения ЕА на таких исходных данных вернет синхронизирующее слово a(bam)m_16a длины к2 + 2 = (п(к) — к — I)2 + 2. По лемме 1.3 это слово является кратчайшим синхронизирующим словом для этого автомата. Также легко проворить, что автомат srf(k2,k)