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

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

Как известно, все системы, возникающие па практике, рассматриваются в науке в виде непрерывных или дискретных моделей. Одной из самых простых и в то же время эффективных моделей дискретных систем являются конечные автоматы. Детерминированным конечным автоматом называется тройка объектов = (ф, Х,<5), где С} - множество состояний, X — входной алфавит, и 5: ф х X —>• ф — всюду определенная функция переходов автомата. В работе рассматривается только этот вид автоматов. Функция 5 продолжается единственным образом на множество <5 х X*, где X* обозначает свободный моноид над X, элементы которого называются словами. Таким образом, каждое слово из X* действует на множестве С) в соответствии с функцией переходов 6.

Несмотря на простоту определения, автоматы являются естественной и широко используемой конструкцией для моделирования дискретно работающих устройств. В частности, при помощи них моделируются различные вычислительные системы (компьютеры), получающие все более широкое применение. При таком моделировании состояния автомата соответствуют возможным состояниям системы, а буквы соответствуют допустимым операциям системы. В силу внешних воздействий или внутренних причин в таких системах могут происходить некорректные переходы. Для того чтобы можно было вернуть контроль над системой после некорректных переходов, не прибегая к ее анализу, целесообразно проектировать систему таким образом, чтобы она обладала некоторой «перезагрузочной» последовательностью операций. Таким образом, вопрос существования перезагрузочной последовательности и вопрос о том, насколько короткой ее можно выбрать являются существенными для рассматриваемых систем.

Введем теперь формальное определение синхронизирующих слов, играющих роль перезагрузочных последовательностей при моделировании систем конечными автоматами. Слово ги 6 X* в автомате, е/ называется синхронизирующим, если его действие «перезагружает» автомат, т. е. переводит автомат в некоторое состояние вне зависимости от того состояния, в котором автомат находился до применения этого слова. Иначе говоря, слово и> синхронизирующее, если 5(д, га) = 5{р, ги) для всех д, р е Я3.

История возникновения идеи синхронизируемости подробно освещена в недавнем обзоре М. В. Волкова [44]. Там отмечено, что истоки понятия синхронизируемости можно найти уже в рамках классических «умозрительных экспериментов» Мура [30]. Мур и его последователи использовали конечные автоматы для моделирования дискретно работающих устройств (компьютеров). При этом возникал следующий естественный вопрос: как восстановить контроль над устройством, не зная его текущего состояния, но наблюдая его поведение в ответ на различные посылаемые ему входные сигналы? В 1956 году Мур [30] показал, что при некоторых условиях можно однозначно определить состояние, в которое автомат приходит под действием подходящей последовательности сигналов. В его работе такая последовательность называлась экспериментом. Отметим, что эксперименты Мура были адаптивными, т. е. каждое следующее действие выбиралось на основе реакции устройства на предыдущие действия. В 1958 году Гинзбург [22] рассмотрел особый тип экспериментов, которые он назвал однородными. Такой эксперимент — это просто фиксированная последовательность сигналов, т. е. подходящее слово над входным алфавитомособенностью однородных экспериментов являлось то, что ответные сигналы нужны были только для определения состояния устройства в конце эксперимента. Отсюда понадобился всего один шаг, чтобы прийти к понятию синхронизирующего слова — эксперимента, в котором вообще не учитываются ответные сигналы устройства. Отметим, что это понятие является довольно естественным с точки зрения практики, поскольку далеко не всегда можно наблюдать ответные сигналы устройства: например, при движении спутника вокруг Луны он не может контролироваться с Земли в момент, когда он находится «позади» Луны. С середины 60-х годов прошлого века теория синхронизируемых автоматов начинает активно развиваться ввиду многочисленных приложений таких автоматов в различных областях: тестировании систем, роботике, символической динамике и др., см. обзоры [28,37,44].

Если автомат .е/ обладает хотя бы одним синхронизирующим словом, то он называется синхронизируемым, а длина кратчайшего синхронизирующего слова для обозначается через. Само отображение ставящее в соответствие автомату число ?(."/), будем называть функцией Черни. В качестве примера рассмотрим изображенный на рпс. 1 автомат Нетрудно проверить, что автомат синхронизируем и что кратчайшим синхронизирующим словом этого автомата является ЪагЪа6Ъ. Следовательно, ?(^4) = 9. Этот пример принадлежит к се4 рии автоматов, построенной в 1964 году словацким математиком Яном Черни [15]. В [15] впервые явно появилось понятие синхронизируемого автомата и построена серия п-автоматов1 гй? п с кратчайшим синхронизирующим словом длины (п — I)2.

Ъ^ ^Ъ.

Рис. 1: Автомат Черни.

В оставшейся части введения будем считать, что = Е, 5} это автомат с п состояниями. Как уже было сказано выше, основными задачами рассматриваемой области является проверка автомата на син-хронизируемость и вычисление или оценка длины кратчайшего синхронизирующего слова для автомата ¿-г/, если автомат синхронизируемый. Обсудим вначале задачу проверки автомата на синхронизируемость.

0.1.1 Синхронизируемость автоматов.

Вопрос проверки автомата ?2/ на синхронизируемость разрешим полиномиальным алгоритмом. Алгоритм строится на основе следующего несложного критерия сипхронизируемости, полученного Черни [15].

Критерий 0.1. Автомат я/ является синхронизируемым тогда и только тогда, когда для любой пары состояний 671,(72? Я существует слово V такое, что <5(дь^) = 6{д2, у).

Из этого утверждения Эпштейн [18] получил квадратичный от п алгоритм, проверяющий автомат ¿-г/ на синхронизируемость. Обсудим вкратце конструкцию, используемую в этом алгоритме, так как она будет использоваться и при обсуждении других результатов. Для этого рассмотгДля краткости здесь и ниже под^{-автоматом} понимается автомат с п состояниями. 5 рим квадрат автомата — автомат .с/2 = (<2 х (3,Е,<52), где функция переходов 52 определяется покомпонентно в соответствии с ?, т. е.

Из такого определения следует, что ?(<71, у) = = д тогда и только тогда, когда ?2((г/ь г/2), ?-) — (д, д). Таким образом, у синхронизирует пару 92} в автомате ¿-г/ тогда и только тогда, когда V помечает некоторый путь из состояния (д1, д2) в диагональное множество Игад — {(<7, q) q? С в автомате ¿-г/2. Следовательно, для проверки критерия спнхронизируе-мости нам достаточно проверить, что множество Пгад достижимо из любого состояния множества (Я х С}) И га д. Это можно сделать поиском в ширину (см. [3]) в графе автомата ¿-г/2 за линейное время от числа состояний автомата .в/2. Следовательно, можно получить квадратичный от п алгоритм проверки автомата на синхронизпруемость, так как количество состояний автомата .е/2 равно п2. Ввиду существования этого алгоритма, вопрос синхронизируемости для автомата можно считать решенным.

0.1.2 Оценки длин кратчайших синхронизирующих слов.

Так как функция переходов в большинстве случаев однозначно определяется контекстом, то для сокращения обозначений через д. у будем обозначать ?-) для произвольного слова у? Е* и состояния д € <3-Через Б. у и Б. у-1 обозначим соответственно образ и прообраз множества <5 под действием слова у, т. е.

Б.У = {я-у qeSj, Б. у-1 = {д е я | д. у е ?}.

Заметим, что алгоритм, предложенный Эпштейном для проверки син-хронизируемости, не возвращает никакого синхронизирующего слова. Однако на основе аналогичных рассуждений, можно построить кубический от числа состояний алгоритм, возвращающий некоторое синхронизирующее слово для данного синхронизируемого автомата = (<5, Е, 5). Такой алгоритм последовательно «сжимает» множество состояний <3 ДО одноэлементного множества, т. е. строит следующую цепочку й = д, 52 = й. иф),., = пока множество не одноэлементное. При этом слова у (Яг) можно найти в автомате ?/2 поиском в ширину за время 0(п2) из множества 6.

Игад во множество (>5гх 5, г-) Пгад. Следовательно, длина каждого слова из цепочки не больше п2, а длина цепочки не больше п ~ 1, так как мощности множеств в цепочке строго убывают. Следовательно, мы получаем кубический от п алгоритм, возвращающий синхронизирующее слово и (5,1)г>(5,2). длины не больше п3. Этот алгоритм называется жадным алгоритмом синхронизации.

Аккуратный анализ этого алгоритма позволяет получить более точную оценку В 1983 году Пэн [34] с использованием изящного комбинаторного результата Франкля [19] улучшил эту оценку в два раза, т. е. 3 показал, что длина слова и не больше п ~п. Так была получена лучшая на момент написания диссертации верхняя оценка длины кратчайшего синхронизирующего слова в автомате.

Наилучшая нижняя оценка, известная на сегодняшний день, равна (п — I)2 и достигается на серии автоматов предложенной Черни [15] в 1964 году. Позднее Черни предположил, что эта серия реализует наихудший в смысле скорости синхронизации случай, т. е. что любой синхронизируемый п-аетомат обладает синхронизирующим словом, длины не более (п — I)2. Впоследствии эта гипотеза стала очень популярной и получила название гипотезы Черни. Несмотря на простоту постановки и многочисленные попытки решения, гипотеза Черни остается открытой уже более 45 лет. За эти годы гипотеза была доказана для нескольких частных классов автоматов, см. [9,17,26,36,39,40,43].

По аналогии с определением функции Черни для автоматов введем ее для класса синхронизируемых автоматов, как функцию от числа состояний автомата. Для натурального числа п и класса синхронизируемых автоматов <�Ж через обозначим наибольшую длину кратчайших синхронизирующих слов среди всех синхронизируемых п-автоматов из класса Ж, т. е. шах ?(?0.

Эту функцию называют функцией Черни, ограниченной на класс Ж. Пусть а11 это класс всех синхронизируемых автоматов. Тогда гипотеза Черни может быть записана в виде? ац (п) < (п — I)2, а существующая верхняя и нижняя оценки в виде гг-1)2<�Сагг (п)<^^. (1).

Так как предполагаемая верхняя оценка на функцию Черни для п-ав7 томатов есть квадратичная функция от п, а доказанная верхняя оценка кубическая от п, то принципиальной задачей является получение квадратичной оценки для как можно более широкого класса п-автоматов. Рассмотрим вкратце существующие оценки на функцию Черни для различных классов автоматов.

0.1.3 Доказанные квадратичные оценки.

Для начала, рассмотрим класс автоматов с нулем, т. е. автоматов, обладающим выделенным состоянием 0, таким что О. а = 0 для любой буквы а. Обозначим этот класс через zero. Ясно, что если автомат с 0 синхронизируемый, то 0 достижим из любого другого состояния автомата и, поэтому, длина синхронизирующего слова не больше суммы длин кратчайших путей из вершин автомата в 0. Следовательно, легко получается оценка сверху €zero (n) < (см. напр. [36]). Более того, для каждого п несложно построить синхронизируемый n-автомат с нулем, имеющий п — 1 букв, для которого кратчайшее синхронизирующие слово имеет длину п<-п~1″ >. Следовательно, ?zcrn (n) = п<-п~г Гораздо более интересной задачей является построение серий синхронизируемых автоматов с нулем, с постоянным количеством букв и квадратичной длиной синхронизирующего слова, т. е. рассмотрение класса автоматов с нулем с к символами (обозначим через zeroДля этого класса, с учетом оценки сверху, в [4,27] доказано неравенство для функции Черни п2 п ^ / ч п (п — 1).

Т + «» 1 < СгегоЛп) < ^ 2.

Ввиду квадратичной оценки сверху на значение функции Черни для класса автоматов с нулем, получение оценок сверху для любого автомата, можно свести к случаю, когда граф автомата сильно-связен (см. напр. [43, предложение 3]). Поэтому, в оставшейся части этого параграфа мы будем рассматривать только сильно-связные синхронизируемые автоматы.

В 2003 году Кари [26] доказал гипотезу Черни для класса синхронизируемых автоматов, чей граф является эйлеровым, т. е. входящая степень равна исходящей и равна размеру алфавита. В действительности, он доказал более сильное неравенство: €euier (n) < п2 — Зп + 3.

В 2007 году Трахтман [40] показал, что €apcr (n) <. где aper обозначает класс апериодических автоматов, т. е. автоматов, у которых 8 для любого слова v найдется степень к такая, что действие слова vk+1 совпадает с действием слова vk. Лучшая известная нижняя оценка для этого класса принадлежит Ананичеву [1]: €арсг (п) > п + J — 2.

Важным шагом на пути решения гипотезы Черни стало доказательство гипотезы Черни для класса циклических автоматов, т. е. автоматов, у которых некоторая буква действует как циклическая перестановка на всем множестве состояний. Этот результат получил Дюбук [17] в 1998 году. Так как автоматы также являются циклическими и &euro-(Сп) = (п — I)2, то нижняя оценка для этого класса совпадает с верхней. Если класс циклических автоматов обозначить через cycle, то в наших терминах это утверждение можно записать в виде Ccijcic (n) = (п — I)2.

0.1.4 Метод расширения и однокластерные автоматы.

Мы рассмотрим одно из естественных обобщений циклических автоматов — однокластерные автоматы в главе 1. Автомат называется одно-кластерным, если некоторой буквой помечен ровно один простой цикл. Ясно, что каждый циклический автомат является однокластерным, и легко привести пример синхронизируемого однокластерного автомата, не являющегося циклическим. Одпокластерпыми автоматами являются декодеры полных префиксных кодов и свойство синхронизации для таких декодеров равносильно свойству самокоррекции для соответствующих кодов. Поэтому получение оценок кратчайшей длины синхронизирующих слов для однокластерных автоматов представляет большой интерес как с практической точки зрения, так и с точки зрения продвижения на пути доказательства квадратичной оценки в общем случае. Эта задача рассматривается в главе 1 диссертации.

Оценки, полученные для циклических и эйлеровых автоматов, интересны еще и тем, что они получены с неявным использованием метода расширения. Этот метод является одним из основных для получения оценок сверху на функцию Черни. Метод расширения получил широкое применение в последние 15 лет и стал основой нескольких впечатляющих результатов. Кроме уже упомянутых результатов Дюбука [17] и Кари [26], И. К. Рысцов, используя метод расширения, доказал квадратичную верхнюю оценку для автоматов, в которых каждая буква либо переставляет состояния либо фиксирует все кроме одного [5], а также для так называемых регулярных автоматов [35], определение которых 9 мы дадим позже.

Идея метода расширения заключается в том, чтобы построить последовательность относительно коротких расширяющих слов VI,., г>/- и выбрать состояние д так, чтобы последовательность множеств Бг,., таких, что =^ъ 52.^1 =51,. БьЛк =^-ь возрастала по мощности и достигала (3, е.

Ясно, что для любой такой последовательности слово. г^ синхронизирует автомат. Легко видеть, что описанный метод позволяет построить синхронизирующее слово для любого сильно-связного синхронизируемого автомата. Заметим, что этот метод является, в некотором смысле, противоположным к методу сжатия, используемому в жадном алгоритме синхронизации. Заметим также, что длина цепочки к не больше п — 1, так как мощности множеств Бг строго возрастают. Следовательно, для получения квадратичных оценок сверху на функцию Черни для п-автоматов достаточно, чтобы длины слов ьг были линейно ограничены от п. Ввиду этого аргумента принципиально важной задачей является доказательство или опровержение гипотез, позволяющих получать линейные оценки на длину расширяющих слов. Эта задача также рассматривается в главе 1 диссертации.

После статьи Дюбука 1998 года [17] надежды на доказательство гипотезы Черни были связаны со следующим свойством расширения. Скажем, что подмножество 51 является т-расширяемым в автомате, если существует слово V длины не больше т такое, что ^.г?" 1! > |5'|.

Свойство 0.2 (Расширения). Любое собственное подмножество Б множества состояний <5 синхронизируемого п-автомата является п-расширяемым.

Используя свойства метода расширения и то, что любой синхронизируемый автомат обладает буквой, сжимающей какую-то пару состояний, легко доказать, что в синхронизируемых автоматах со свойством расширения выполнена гипотеза Черни. Однако существуют синхронизируемые автоматы, не удовлетворяющие этому свойству. В частности, можно проверить, что 6-автомат построенный Кари [24] и изображенный на рис. 2, содержит собственное подмножество, которое не является 7.

10 а.

Рис. 2: Автомат Кари расширяемым (хотя в самой работе [24] этот факт не отмечался). Мы рассмотрим свойство расширения и его обобщения в главе 1.

0.1.5 Алгоритмы поиска кратчайших синхронизирующих слов.

Безусловно, получение эффективного алгоритма, возвращающего кратчайшее синхронизирующее слово, важно не только с теоретической, но и с практической точки зрения. Действительно, на практике, зачастую встречаются системы, для которых необходима быстрая перезагрузка системы (применение синхронизирующего слова), поэтому, один раз найдя кратчайшее синхронизирующее слово автомата соответствующего системе, можно применять его многократно, экономя время и ресурсы системы при перезагрузке.

В теории сложности общепринято считать задачу эффективно разрешимой, если для нее существует (детерминированный) полиномиальный алгоритм и для этого есть существенные аргументы. Принято также считать, что класс задач ЫР, разрешимых недетерминированными полиномиальными алгоритмами, шире класса задач Р, разрешимых детерминированными полиномиальными алгоритмами, т. е. делать предположение Рт^Р.

В предыдущем параграфе уже был описан эффективный кубический алгоритм, возвращающий для каждого синхронизируемого п-автомата я/ некоторое синхронизирующее слово V. Однако длина слова у потенциально может быть кубической от п, в то время как нижняя оценка длины синхронизирующего слова квадратичная. К сожалению, эта неоптимальность не случайна и эффективного алгоритма, находящего кратчайшее синхронизирующее слово или даже только его длину, не существует (в.

11 предположении Р ф КР). Формально, для заданного синхронизируемого автомата ¿-г/ и натурального числа? ответ на вопрос о существовании синхронизирующего слова длины не больше? является ЫР-полной задачей (см. напр. [18]). Из этого, однако, не следует, что синхронизирующее слово, на один символ длиннее кратчайшего, не может быть найдено эффективным алгоритмом. Следовательно, ключевым становится вопрос о возможности приближенного вычисления длины кратчайшего синхронизирующего слова. Этот вопрос, поднятый в недавнем обзоре М. В. Волкова [44], будет рассмотрен в главе 2.

0.2 Допустимые графы и проблема раскраски дорог.

При моделировании систем конечными автоматами, иногда встречаются такие, в которых определены возможные переходы между состояниями и набор допустимых операций, но не определено соответствие («раскраска») между операциями и переходами, либо соответствие задано, но его можно переопределить («перераскрасить»). При этом рассматриваются те же вопросы, что и для автоматов, но с учетом, возможности перераскраски: задача перераскраски заданного автомата в синхронизируемый и задача перераскраски автомата в синхронизируемый с как можно более коротким синхронизирующим словом.

Орграф С называется графом автомата и обозначается и С? (.я/), если его множество вершин совпадает с множеством состояний автомата я/, а дуги соответствуют переходам автомата, т. е. из вершины д есть стрелка в вершину д' тогда и только тогда, когда 5(д, а) = д' для некоторой буквы, а € Е. Другими словами, граф автомата получается «стиранием» букв с переходов автомата. Например, на рис. 3 слева нарисован граф автомата Черни, в центре сам автомат Черни, а справа еще один автомат с таким же графом.

Автомат назовем раскраской графа С, если граф автомата ¿-г/ равен заданному, т. е. С = 1/С (.с/). Другими словами, раскраска получается из орграфа приписыванием букв дугам графа таким образом, чтобы из каждой вершины исходило ровно по одной дуге для каждой буквы. Очевидно, что орграф должен иметь одинаковую степень исхода вершин для того, чтобы хотя бы одна раскраска существовала.

Перераскраской автомата ¿-г? называется произвольная раскраска его графа IIС (я/). Таким образом, задача перераскраски автомата эквивалентна задаче раскраски его графа. Например, автомат, изображенный.

12 на рис. 3 справа является перекраской автомата Черни, изображенного на том же рисунке в центре. Заметим, что эта перекраска является синхронизируемым автоматом с кратчайшим синхронизирующим словом а3. Более того, можно проверить, что эта перекраска является оптимальной в том смысле, что она обладает кратчайшим синхронизирующим словом среди всех возможных нерераскрасок автомата,.

Основными задачами, связанными с раскрасками графов, являются задача о раскраске графа в синхронизируемый автомат и задача о том, как найти синхронизирующую раскраску с коротким синхронизирующим словом. Рассмотрим вначале задачу о синхронизируемой раскраске.

0.2.1 Синхронизируемые раскраски.

Задача о возможности раскраски орграфа в синхронизируемый автомат первоначально возникла в символической динамике, см. [7]. Для исключения из рассмотрения тривиальных случаев достаточно рассматривать только сильно-связные графы с одинаковой степень исхода вершин и длины циклов должны быть взаимно просты в совокупности. Такие графы называются, А С УУ-графами, поскольку гипотеза о существовании синхронизирующей раскраски для любого такого графа была сформулирована в статье Адлера, Гудвина и Вэйса [6] в 1977 году. Вопрос состоит в том, любой ли допустимый граф является графом некоторого сильносвязного синхронизируемого автомата? Задача получила название проблемы раскраски дорог и формулируется в виде гипотезы следующим образом.

Гипотеза 0.3. Любой допустимый граф имеет синхронизирующую раскраску.

Задача вызвала большой интерес среди специалистов теории графов, конечных автоматов и символической динамики. Несмотря на простоту формулировки, задача оставалась нерешенной более 30 лет. С 1977 по 2000 год гипотеза была подтверждена для некоторых частных случаев [12,20,23,31,33] без существенного продвижения в общем случае.

В 2001 году Кулик, Кархумяки и Кари [16] предложили концепцию стабильных пар, ставшую существенной частью для решения задачи в общем случае. Пара состояний в,? € <3 автомата называется стабильной, если для любого слова и е Е* найдется слово иЕ Е* такое, что 6(з, ии)) = 8(1, ит). Смысл определения в том, что пара состояний является стабильной, если эту пару можно сжать в одно состояние и это свойство стабильно относительно применения слов к исходной паре состояний. Ввиду критерия 0.1 автомат является синхронизируемым тогда и только тогда, когда все его пары состояний стабильны, и, следовательно, существование стабильной пары более слабое свойство, чем син-хронизируемость. В [16] было доказано, что проблема раскраски дорог эквивалентна гипотезе о том, что для любого допустимого графа существует раскраска со стабильной парой. В 2002 Кари [25] развил технику стабильных пар и с ее использованием подтвердил гипотезу для класса графов, имеющих ровно одну вершину со степенью захода больше, чем общая степень исхода вершин. Таким образом, была дополнительно подтверждена эффективность использования концепции стабильных пар.

Одним из самых выдающихся результатов в теории синхронизируемых автоматов можно считать результат Трахтмана [42], где с использованием концепции стабильных пар и искусного анализа структуры графов была положительно решена проблема раскраски дорог, т. е. доказана следующая.

Теорема 1. Любой допустимый граф имеет синхронизирующую раскраску.

Таким образом, была решена одна из двух основных проблем теории синхронизируемых автоматов. Заметим, что доказательство в [42] конструктивно и дает некоторый полиномиальный алгоритм для нахождения синхронизирующей раскраски. В последующих работах [10,41] были получены такие алгоритмы с кубической и квадратичной сложностью, соответственно. Таким образом, как и для автоматов, вопрос синхро-низируемости для графов, т. е. вопрос существования синхронизируемой.

14 раскраски, можно считать решенным. В следующем разделе мы рассмотрим вопрос о длине синхронизирующих слов в получающихся синхронизируемых раскрасках.

0.2.2 Алгоритмы поиска оптимальной раскраски.

Назовем синхронизируемую раскраску лг/ допустимого графа О оптимальной, если это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок графа С?. Длину кратчайшего синхронизирующего слова оптимальной раскраски я/ графа С назовем значением оптимальной раскраски и обозначим 0РТ{О). Ясно, что тогда = ОРТ © и для любой другой синхронизирующей раскраски графа С выполняется >

Важность получения эффективных алгоритмов, находящих оптимальную раскраску или значение оптимальной раскраски по заданному допустимому графу, объясняется теми же причинами, что и для задачи поиска кратчайшего синхронизирующего слова для заданного синхронизируемого автомата в параграфе 0.1.5. Один раз найдя оптимальную или «почти оптимальную» раскраску графа, соответствующего системе, и кратчайшее синхронизирующее слово в ней, можно многократно использовать то, что эта раскраска имеет короткое синхронизирующее слово относительно других раскрасок для экономии ресурсов при восстановлении контроля над системой. Важно также заметить, что задачи поиска оптимальной раскраски и кратчайшего синхронизирующего слова оптимальной раскраски не являются эквивалентными.

Из предыдущего раздела мы знаем, что существует эффективный квадратичный алгоритм, находящий некоторую синхронизирующую раскраску и естественным образом встает вопрос о том, насколько оптимальную раскраску возвращают эти алгоритмы относительно оптимальной раскраски. Таким образом, задачи точного или приближенного вычисления значения оптимальной раскраски или самой оптимальной раскраски являются основными открытыми задачами в этой области. Эти задачи, также рассмотренные в обзоре М. В. Волкова [44], будут обсуждаться в главе 3.

0.3 Обзор полученных результатов.

0.3.1 Квадратичные оценки на функцию Черни.

В главе 1 представлены полученные результаты по задачам, рассмотренным в разделе 0.1.2: расширение класса автоматов с доказанной квадратичной оценкой сверху на функцию Черни и анализ гипотез, связанных с доказательством таких оценок.

Как уже было сказано выше, одной из основных теоретических проблем в рассматриваемой области является доказательство квадратичной оценки сверху на функцию Черни для как можно более широкого класса синхронизируемых автоматов. Большинство методов получения квадратичных оценок сверху могут быть разделены на два типа: методы сжатия и расширения. Методы обоих типов строят конечную последовательность слов V = (г>1, г>2, • • •, Ут), конкатенация которых является синхронизирующим словом для автомата. Назовем т = размером последовательности V, а максимальную длину слов из V назовем длиной последовательности V. Методы отличаются тем, что метод сжатия последовательно ссисимает множество <3 до некоторого состояния р, т. е. т1 = |<2| > q. vi] > q. vv2 > .> q. viv2 ¦¦¦ут = |{р}| = 1, в то время как метод расширения последовательно расширяет некоторое состояние р до множества всех состояний <3, т. е.

1 = |{р}| < р-уТ1 < < <. .V" 1! = М = П.

Так как размер последовательностей т не больше п — 1, то получение квадратичных оценок может быть сведено к поиску последовательностей линейной длины от количества состояний автомата п. Однако, легко привести серию примеров автоматов и соответствующих подмножеств, для которых кратчайшее сжимающее слово будет иметь квадратичную длину от п. Например для автоматов Черни с? п несложно проверить, что кратчайшее сжимающее слово для 2-элементного множества состояний {!>[§]} имеет Длину порядка (c)(%-)¦ Поэтому гораздо более перспективным кажется метод расширения, для которого таких примеров еще не найдено. Более того, не найдено примеров, когда кратчайшее расширяющее слово для некоторого собственного подмножества имеет длину больше 2п.

Возможность построения расширяющей последовательности линейной длины можно формализовать следующим образом. Подмножество состояний S назовем т-расширяелтм в автомате если найдется расширяющее слово v длины т такое, что > Скажем, что п-автомат .о/ удовлетворяет свойству к-расширения, если любое собственное подмножество состояний S является А-п-расширяемым. По аналогии, скажем что n-автомат удовлетворяет свойству строгого к-расширения, если любое собственное подмножество состояний к (п — 1)-расширяемое.

Предположим, что сильно-связный синхронизируемый n-автомат удовлетворяет свойству /г-расширения или строгого^{-расширениятогда} из метода расширения легко следует оценка < к (п — 2) п 4- 1 или £(.е/) < к (п — 2)(п — 1) + 1 соответственно. В частности, автоматы, удовлетворяющие свойству 1-расширения, удовлетворяют и гипотезе Черни. Такие рассуждения использовал Дюбук [17] и Кари [26] для доказательства гипотезы Черни для циклических и квадратичной оценки (п — 2)(п —1) + 1 для эйлеровых автоматов соответственно. В главе 1 мы продемонстрируем серию автоматов, не обладающих свойством с-расширения ни для какого для с < 2. Ввиду этого результата естественным образом возникает открытый вопрос о справедливости в общем случае свойства 2-расширепия или строгого 2-расширения, из которых следуют квадратичные оценки порядка 2(n — I)2. Заметим, что эти свойства уже использовались для доказательства квадратичных оценок для различных классов автоматов [5,11,35,45].

Рассмотрим теперь подходы, использующиеся для доказательства свойства с-расширения для с > 2. На конференции «Developments in Language Theory 2008″ Карпи и Д’Алессандро [13] (см. также журнальную версию их статьи [14]) представили новую идею для построения расширяющей последовательности линейной длины в общем случае. Идея основана на понятии независимого множества слов. Множество из п слов W С Е* называется независимым для некоторого п-автомата если для любых двух состояний автомата s и t найдется слово из W, переводящее sat. Автомат srf называется сильно-транзитивным, если он обладает некоторым независимым множеством слов. В качестве примера сильнотранзитивного автомата можно рассмотреть произвольный циклический автомат. Действительно, пусть с — циклическая буква в произвольном тг-автомате, тогда легко понять, что множество слов {1, с, с2,., с» -1} является независимым для этого автомата.

Карпи и Д’Алессандро [14] доказали, что любой сильно-связный син.

17 хронизируемый автомат является сильно-транзитивным и если слово и синхронизирует автомат .с/, то автомат имеет независимое множество длины не более |и| + п — 1, причем эта оценка точна. Основным утверждением из [14] является теорема о том, что если n-автомат si сильно-транзитивный для некоторого независимого множества W, то он обладает синхронизирующим словом длины (п — 2)(n + Lw — 1) + 1, где Lw = тахг wi. Как следствие, для циклических автоматов получается оценка 2п2 — 6п + 5, так как любой циклический автомат обладает независимым множеством длины п — 1.

Карпи и Д’Алессандро также предположили, что произвольный синхронизируемый автомат, обладает независимым множеством линейной длины и, следовательно, справедлива квадратичная оценка в общем случае. Формально: скажем, что n-автомат я/ удовлетворяет свойству к-независимости для некоторого числа к, если он обладает независимым множеством длины не больше к (п — 1). Тогда гипотеза Карпи и Д’Алессандро может быть сформулирована следующим образом.

Гипотеза 0.4 (Карпи и Д’Алессандро). Существует некоторое число к, для которого любой сильно-связный синхронизируемый автомат удовлетворяет свойству к-независимости.

Так как к это константа, то ввиду упомянутого результата из [14], справедливость гипотезы влечет квадратичную верхнюю оценку на функцию Черни для всех синхронизируемых автоматов.

Похожие идеи были выдвинуты ранее И. К. Рысцовым [35]. Он называл конечное множество слов W регулярным для n-автомата, если W содержит пустое слово, длина каждого слова из W не больше (п—1) и для некоторого натурального г и любой пары состояний s, t найдется ровно г слов из W, переводящих s в t. Автомат называется регулярным, если он обладает некоторым регулярным множеством слов. И. К. Рысцов [35] доказал верхнюю оценку 2(га — I)2 для минимальной длины синхронизирующих с лов регулярного гг-автомата и предложил следующую гипотезу:

Гипотеза 0.5 (И. К. Рысцов). Као/сдый сильно-связный автомат является регулярным.

Ввиду упомянутого результата из [35] справедливость этой гипотезы также влечет квадратичную верхнюю оценку на на функцию Черни для всех синхронизируемых автоматов.

В параграфе 1.1 главы 1 мы представим алгоритм расширения в общем виде, введем свойство к-баланса и докажем, что оно является обобщением как свойства^{-независимости} Карпи и Д’Алессандро, так и свойства регулярности Рысцова. Далее мы покажем, что это свойство к-баланса влечет свойство строгого к + 1-расширения. Все связи между рассмотренными свойствами изображены на рис. 0.3.1 в виде графа, вершины которого соответствуют свойствам автомата, а дуги соответствуют логической связи между соответствующими свойствами, с учетом указанного на некоторых дугах условия.

Рис. 4: Связи между свойствами.

В параграфе 1.2 главы 1 мы построим двупараметрическую серию сильно-связных синхронизируемых автоматов, включающую в себя серию контрпримеров к свойству /с-расширения для к < 2 и серию контрпримеров к свойству /г-баланса при любом к > 0. Таким образом, мы опровергнем две связанные с методом расширения гипотезы: гипотезу Карпи и Д’Алессандро и гипотезу Рысцова и, тем самым, покажем что эти гипотезы неприменимы для доказательства квадратичных оценок на функцию Черни. Опровергнутые гипотезы обозначены пунктирной линией на рис. 0.3.1.

В параграфе 1.3 мы ослабим рассмотренные свойства до их «локальных» версий и при помощи этих версий и алгоритма расширения представим доказательство квадратичной верхней оценки 2п2 — 7п + 7 для обобщения класса циклических автоматов — класса одно-кластерных автоматов [11,45] — и, тем самым, расширим класс.

Рис. 5: Оставшиеся связи между свойствами автоматов, для которых доказана квадратичная оценка сверху.

0.3.2 Алгоритмы вычисления функции Черни.

В главе 2 представлен ответ на вопрос о существовании эффективного приближенного алгоритма, вычисляющего значение функции Черни, поставленный в разделе 0.1.5. Основным результатом главы 2 является доказательство отсутствия полиномиального алгоритма, вычисляющего длину кратчайшего синхронизируемого слова с любой конечной относительной погрешностью (в предположении Р ф NP). Мы также докажем, что этот результат остается верен для класса автоматов с ¿—буквенным алфавитом для любого? > 1.

Формально задача вычисления длины кратчайшего синхронизирующего слова (значения функции Черни) ставитсяследующим образом. Задача Мш-ЗупсЬ-Ьеп^Ь. Дано: Синхронизируемый автомат Найти: €(?/).

Доказательство данного результата происходит в два этапа. Сначала доказывается следующая теорема об полиномиальной неаппроксимируемости задачи Mш-Synch-Lengt, h для класса трехбуквенных автоматов с относительной погрешностью меньше 2.

Теорема 2. В предположении Р ф ЫР любой полиномиальный алгоритм, приближенно вычисляющий значение функции Черни для клас.

20 са трехбуквенных автоматов, имеет относительную погрешность не меньше 2.

В доказательстве этой теоремы используется сведение задачи ВЫПОЛНИМОСТЬ к заданной задаче аппроксимации, т. е. для каждой формулы КНФ (конъюнкции дизъюнкций переменных и их отрицаний) ф с п переменными строится синхронизируемый трехбуквенный автомат .с/2(Ф), такой что если ф выполнима, то (¿-(^(Ф)) — п + 2, а если ф невыполнима, то £(^2(ф)) > 2(п — 1). Ясно, что при таком построении формула ф выполнима тогда и только тогда, когда (¿-{^{Ф)) < 2(п — 1). Следовательно любой алгоритм, вычисляющий значение функции Черни для класса трехбуквенных автоматов с относительную погрешность не меньше 2, может быть использован для определения выполнимости ф и, следовательно, такой алгоритм не может быть полиномиальным (при условии Р ф так как ВЫПОЛНИМОСТЬ является^{-полной} задачей.

Второй этап состоит в доказательстве основной теоремы.

Теорема 3. В предположении Р ф NP не существует приближенных полиномиальных алгоритмов, вычисляющих значение функции Черни для класса трехбуквенных автоматов с конечной относительной погрешностью.

Для каждой КНФ формулы ф с п переменными по индукции строится серия синхронизируемых автоматов ^(Ф), ^{Ф)-, ¦ ¦ ¦, г (Ф) таких, что ?(.е/г (ф)) < п + г и синхронизирующее слово имеет определенный вид, если ф выиолнима и ?(?/г (ф)) > г (п — 1), если ф не выполнима. При этом автомат ^¿-(Ф) из теоремы 2 используется как для доказательства базы индукции, так и в качестве основы для построения автомата ?^г (Ф) на шаге индукции. Таким образом, доказательство шага индукции практически повторяет доказательство теоремы 2.

Ясно, что для класса автоматов с одной буквой задача разрешима за линейное время, так как для каждого п существует только один синхронизируемый гг-автомат и он имеет синхронизирующее слово длины тт. — 1. Если же рассмотреть автоматы с количеством букв больше трех, то добавив необходимое количество тождественно действующих букв в конструкцию, используемую при доказательстве теоремы 3 результат будет верен и в этом случае. Остается разобрать двухбуквепный случай. В этом случае аналогичный результат доказывается при помощи универсальной.

21 конструкции, позволяющей для любого ¿—буквенного синхронизируемого n-автомата ffJ построить двухбуквенный синхронизируемый? п-автомат S8 со значением функции Черни не меньше ?(&/) и не больше В автомате ??3 одна буква имитирует выбор буквы в исходном автомате ?</, а вторая буква имитирует действие выбранной буквы.

Несмотря на то, что мы доказали неаппроксимируемость эффективным алгоритмом значения функции Черни с любой конечной относительной погрешностью, нельзя считать вопрос о существовании эффективного алгоритма для этой задачи полностью решенным. Действительно, ввиду невозможности эффективной аппроксимации значения функции Черни с конечной относительной погрешностью в классе всех синхронизируемых автоматов, естественным образом возникает вопрос о существовании эффективного алгоритма с логарифмической погрешностью, т. е. алгоритма, возвращающего для некоторой константы d, > 1 значение между и d?(.t-/) log для любого синхронизируемого автомата с/. Частичный ответ на этот вопрос представлен в [21]. Более того, исходя из некоторых компьютерных экспериментов, можно сделать предположение о том, что жадный алгоритм синхронизации, рассмотренный в разделе 0.1.2, может обладать таким свойством. Также может оказаться интересным и важным вопрос о возможности эффективной аппроксимации задачи для некоторых классов синхронизируемых автоматов.

Алгоритмы поиска оптимальной раскраски.

В главе 3 мы докажем результат аналогичный результату из главы 2. Основным результатом главы 3 будет доказательство того, что задача поиска значения оптимальной раскраски и самой оптимальной раскраски не может быть решена полиномиальным алгоритмом с погрешностью меньше 2 в предположении Р ф NP. Таким образом, мы дадим частичный ответ на вопрос из параграфа 0.2.2. Более того, будет показано как перенести результаты на класс автоматов с ¿—буквенным алфавитом, для любого? > 1.

Формально задачу вычисления значения оптимальной раскраски можно записать в следующем виде. Задача OCV (Optimal Coloring Value). Дано: Допустимый орграф G. Найти: OPT{G).

Заметим, что значение оптимальной раскраски по определению совпада.

22 ет со значением функции Черни для оптимальной раскраски. Следовательно, задача состоит в том, чтобы вычислить минимально возможное значение функции Черни среди всех синхронизируемых раскрасок заданного графа. Однако несмотря на аналогию с задачами для автоматов, из отсутствия эффективного алгоритма, вычисляющего значение функции Черни для заданного автомата, напрямую не следует отсутствие такого алгоритма для вычисления значения оптимальной раскраски, так как само вычисление значения оптимальной раскраски, т. е. значения функции Черни для оптимальной раскраски, может оказаться простой задачей. Заметим также, что если проводить аналогию с задачей аппроксимации значения функции Черни для автоматов, то для этой задачи мы доказываем более слабый результат, а именно, эффективную неаппроксимируемость с относительной погрешностью меньше 2. Доказательство этого результата оказалось гораздо технически более сложной задачей, ввиду того, что необходимо учитывать возможность различных раскрасок заданного графа.

Основным утверждением главы 3 является следующая теорема:

Теорема 4. Если Р ф NP, то любой полиномиальный алгоритм, вычисляющий значение оптимальной раскраски для AGW-графов со степенью исхода 3, имеет относительную погрешность не меньше 2.

Мы также докажем, что такой же результат можно доказать для задачи поиска самой оптимальной раскраски. Задача поиска оптимальной раскраски записывается в следующем виде. Задача ОС (Optimal Coloring). Дано: Допустимый орграф G. Найти: Оптимальную раскраску графа G.

Под приближенным вычислением оптимальной раскраски с относительной погрешностью с > 1 надо понимать поиск синхронизирующей раскраски со значением функции Черни не больше чем в с раз больше значения оптимальной раскраски заданного графа.

Заметим, что из полиномиальной неаппроксимируемости значения оптимальной раскраски с относительной погрешностью меньше 2 напрямую не следует невозможность точного или приближенного вычисления самой оптимальной раскраски. Такой вывод нельзя сделать, так как для поиска оптимальной раскраски не требуется находить значение оптимальной раскраски, равное значению функции Черни для этой раскраски.

Если бы задача вычисления значения функции Черни для автомата была полиномиально разрешимой, то любой полиномиальный алгоритм, находящий оптимальную раскраску, можно было бы достроить до полиномиального алгоритма, находящего значение оптимальной раскраски и, таким образом, получить противоречие. Однако, ввиду теоремы 3 для задачи вычисления значения функции Черни не существует даже приближенного полиномиального алгоритма с любой конечной относительной погрешностью.

Тем не менее, при помощи обратного анализа доказательства теоремы 4 в главе 3 доказывается полиномиальная неаппроксимируемость поиска оптимальной раскраски с относительной погрешностью меньше 2 в предположении Р ф МР.

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

Основные результаты диссертации опубликованы в [45−47]. Результаты из [45] были независимо доказаны автором диссертации и французскими математиками Беал и Перрэн, а совместная работа [45] возникла в результате слияния в один текст обеих статей. При этом результат, полученный автором диссертации несколько точнее, чем результат Беал и Перрэна, и в тексте совместной статьи приведен именно он. Работа [45] опубликована в издании, входящем в перечень утвержденных ВАК.

Ссылки на результаты диссертации присутствуют в работах других авторов: [21,32,38,39].

Основные результаты диссертации докладывались на Российско-индийском семинаре по алгебре, комбинаторике и сложности (Екатеринбург, 2008), международной конференции «Симпозиум по компьютерным наукам в России» СЭЯ 2010 (Казань, Россия, 2010), 14-ой международной конференции по теории формальных языков БЬТ 2010 (Лондон, Канада, 2010), международном семинаре по автоматам БААЭТ (Вена, Австрия, 2010) и заседаниях семинара «Компьютерные пауки» (УрГУ).

Автор выражает глубокую благодарность своему научному руководителю профессору М. В. Волкову за постановки задач и постоянное внимание к работе. В частности, результаты глав 2 и 3 явились попыткой ответить на вопросы, поставленные в его обзоре [44].

1. Ананичев Д. С. Порог аннуляции для частично монотонных автоматов // Изв. вузов. Матем. 2010. No. 1. С. 3−13.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. СПб: Вильяме, 2011.

4. Прибавкина Е. В. Вопросы оптимальности в теории синхронизируемых автоматов. Диссертация на соискание ученой степени кандидата физ.-мат. наук. Институт математики м механики УрО РАН. Екатеринбург, 2009.

5. Рысцов И. К. О длине возвратных слов для автоматов с простыми идемпотентами // Кибернетика и системный анализ. 2000. Т. 3. С. 32−39.

6. Adler R., Goodwyn L. W., Weiss В. Equivalence of topological Markov shifts 11 Israel J. Math. 1977. V. 27. P. 49−63.

7. Adler R., Weiss B. Similarity of automorphisms of the torus // Memoirs Amer. Math. Soc. 1970. No. 98.

8. Ananichev D., Gusev V., Volkov M. Slowly synchronizing automata and digraphs // Lect. Notes Сотр. Sci. 2010. V. 6281. P. 55−65.

9. Ananichev D., Volkov M. Synchronizing generalized monotonie automata Ц Theor. Comput. Sci. 2005. V. 330. P. 3−13.

10. Beai M., Perrin D. A quadratic algorithm for road coloring // Электронная публикация]. 2008. arXiv:0803.0726.

11. Beai M., Perrin D. A quadratic upper bound on the size of a synchronizing word in one-cluster automata // Lect. Notes Сотр. Sci. 2009. V. 5583. P. 81−90.

12. Carbone A. Cycles of relatively prime length and the Road Coloring Problem 11 Israel J. Math. 2001. V. 123. P. 303−316.82.

13. Carpi A., D’Alessandro F. The synchronization problem for strongly transitive automata // Lect. Notes Comp. Sci. 2008. V. 5257. P. 240−251.

14. Carpi A., D’Alessandro F. Strongly transitive automata and the Cerny conjecture // Acta Informatica. 2009. V. 46. P. 591−607.

15. Cerny J. Poznamka k homogennym eksperimentom s konecnymi automatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. 1964. V. 14. P. 208−216.

16. Culik K., Karhumaki J., Kari J. A note on synchronized automata and Road Coloring Problem // Int. J. Found. Comput. Sci. 2002. V. 13. P. 459−471.

17. Dubuc L. Sur les automates circulaircs eta la conjecture de Cerny // RAIRO Theor. Inform, and Appl. 1998. V. 32. P. 21−34.

18. Eppstein D. Reset sequences for monotonic automata // SIAM J. Comput. 1990. V. 19. P. 500 510.

19. Frankl P. An extremal problem for two families of sets // Eur. J. Comb. 1982. V. 3. P. 125−127.

20. Friedman J. On the colorability problem // Proc. Amer. Math. Soc. 1990. V. 110. P. 1133−1135.

21. Gerbush M., Heeringa B. Approximating minimum reset sequences // Lect. Notes Comp. Sci. 2011. V. 6482. P. 154−162.

22. Ginsburg S. On the length of the smallest uniform experiment which distinguishes the terminal states of a machine //J. Assoc. Comput. Mach. 1958. V. 5. P. 266−280.

23. Jonoska N., Suen S. Monocyclic decomposition of graphs and the road coloring problem // Congressum Numerantium. 1995. V. 110. P. 201 209.

24. Kari J. A counter example to a conjecture concerning synchronizing words infinite automata // EATCS Bull. 2001. V. 73. P. 146.

25. Steinberg В. The averaging trick and the Cerny conjecture // Lect. Notes Сотр. Sci. 2010. V. 6224. P. 423−431.

26. Steinberg B. The Cerny conjecture for one-cluster automata with prime length cycle // Электронная публикация]. 2010. arXiv:1005.1835.

27. Trahtman A. The Cerny conjecture for aperiodic automata // Discrete Math. Theor. Comput. Sci. 2007. V. 9. No. 2. P. 3−10.

28. Trahtman A. An algorithm for road coloring // Электронная публикация]. 2008. arXiv:0801.2838.

29. Trahtman A. The road coloring problem // Israel J. Math. 2009. V. 172. No. 1. P. 51−60.

30. Volkov M. V. Synchronizing automata preserving a chain of partial orders // Theor. Comput. Sci. 2009. V. 410. No. 37. P. 3513−3519.

31. Volkov M. V. Synchronizing automata and the Cerny conjecture // Lect. Notes Сотр. Sci. 2008. V. 5196. P. 11−27.85Работы автора по теме диссертации.

32. Beai M., Berlinkov M., Perrin D. A quadratic upper bound on the size of a synchronizing word in one-cluster automata // International Journal of Foundations of Computer Science. 2011. V. 22. No. 2. P. 277−288.

33. Berlinkov M. Approximating the minimum length of synchronizing words is hard // B kh.: 5th International Symposium «Computer Science in Russia». Lecture Notes in Computer Science. 2010. V. 6072. P. 37−47.

34. Berlinkov M. On a conjecture by Carpi and D’Alessandro // B kh.: 14th Internaional Conference «Developments in Language Theory». Lecture Notes in Computer Science. 2010. V. 6224. P. 66−75.