Аппроксимация длин синхронизирующих слов для конечных автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

4846759

На правах рукописи

Берлипков Михаил Владимирович

АППРОКСИМАЦИЯ ДЛИН СИНХРОНИЗИРУЮЩИХ слов ДЛЯ КОНЕЧНЫХ АВТОМАТОВ

01.01.09 —дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

Екатеринбург, 2011

1 9 МАЙ 2011

4846759

Работа выполнена па кафедре алгебры и дискретной математики Уральского государственного университета им. A.M. Горького.

Научный руководитель:

доктор физико-математических наук, профессор М. В. Волков

Официальные оппоненты:

доктор технических наук, профессор Д. В. Сперанский

кандидат физико-математических наук, доцент Р. Г. Мубаракзянов

Ведущая организация:

Сапкт-Петербургскнй академический университет - научно-образовательный центр иалотехнологий РАН

Защита диссертации состоится 34 ьШХД, ЮЦ на засе-

дании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 13 2011 г.

Учёный секретарь диссертационного совета, кандидат физ.-мат. наук, ст.н.с.

В. Д. Скарин

Общая характеристика работы

Актуальность темы. Одной из самых простых и в то же время эффективных моделей дискретных систем являются конечные автоматы. Детерминированнъш конечным автоматом называется тройка объектов ¿г/ = Е, 6), где <5 - множество состояний, Е - входной алфавит,, 5 :С} х Е <2 - функция переходов автомата. В работе рассматривается только этот вид автоматов.

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

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

Если автомат обладает хотя бы одним синхронизирующим словом, то он называется синхронизируемъш, а длина кратчайшего синхронизирующего слова для обозначается через £(.с/). Само отображение С, ставящее в соответствие автомату число будем называть

функцией Черни. В качестве примера рассмотрим изображенный на рис. 1 автомат Нетрудно проверить, что автомат ^ синхронизируем и что кратчайшим синхронизирующим словом этого автомата является Ьа?Ьа3Ь. Следовательно, £(^4) — 9- Этот пример принадлежит к серии автоматов, построенной в 1964 году словацким математиком Яном Черни [7]. В [7] впервые явно появилось понятие синхронизируемого автома-

та и построена серия п-автоматов1 ^ с кратчайшим синхронизирующим словом дайны (п — I)2.

Черни предположил, что серия Чоп реализует наихудший в смысле скорости синхронизации случай, т.е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п -1)2. Это предположение получило название гипотезы Черни. Несмотря на простоту формулировки и многочисленные попытки доказать или опровергнуть эту гипотезу, в общем случае она остается открытой и доказана лишь в некоторых частных случаях. Наилучшая известная на момент написания диссертации оценка сверху на число для п-автомата ¿г/ равна(Эта оценка была доказана около 30 лет назад Пэном |14] при помощи комбинаторного результата Франкля [10].) Так как предполагаемая верхняя оценка на функцию Черни для п-автоматов есть квадратичная функция от п, то принципиальной задачей является получение квадратичной оценки для как можно более широкого класса п-автоматов.

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

1 Для краткости здесь и ниже под п-автоматом понимается автомат с п состояни-

I

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

ями.

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

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

Заметим, что доказательство квадратичных оценок легко сводится к случаю силыю-связных автоматов (см., напр., [19, предл. 3]). Пусть я/ = Е, 6} - сильно-связный синхронизируемый п-автомат. Через Я.и будем обозначать образ подмножества состояний 5 СЦ под действием слова V € Е*. Идея метода расширения заключается, в том, чтобы построить последовательность относительно коротких расширяющих слов 1)1, г>2,. • •, Ук и выбрать состояние ц так, чтобы последовательность множеств Бх, ¿>2,..., Би таких, что

{д} = 51, Я^г = 8к.ик = возрастала по мощности и достигала <3, т. е.

1=1&|<|$2|<---<|&ыд| = п.

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

На практике часто встречаются системы, для которых необходима быстрая перезагрузка. Один раз найдя кратчайшее синхронизирующее слово автомата, соответствующего такой системе, можно применять его многократно, экономя время и ресурсы при перезагрузке. Таким образом, задача поиска относительно короткого синхронизирующего слова или его длины является одной из основных не только с теоретической, но и с практической точки зрения. К сожалению, точный вариант этой задачи является труднорешаемъш. А именно, известно, что вопрос о том, существует ли для данного синхронизируемого автомата <£/ синхронизирующее слово, длина которого не превосходит данного числа £, является АТ-полной задачей (см., напр., [9]). Из этого, однако, не следует, что синхронизирующее слово на один символ длиннее кратчайшего не может быть найдено эффективным алгоритмом. Следовательно, ключевым становится вопрос о возможности приближенного вычисления длины кратчайшего синхронизирующего слова. Этот вопрос, поставленный в недавнем обзоре М.В.Волкова [20], рассматривается во второй главе диссертации.

При моделировании систем конечными автоматами иногда встречаются такие системы, в которых определены возможные переходы между состояниями и набор допустимых операций, но не определено соответствие («раскраска») между операциями и переходами, либо соответствие задано, но его можно переопределить («перераскрасить»). При этом рассматриваются тс же вопросы, что и для автоматов, по с учетом возможности перераскраски: задача перераскраски заданного автомата в синхронизируемый и задача перераскраски автомата в синхронизируемый с как можно более коротким синхронизирующим словом. Например, на рис. 2 слева изображен граф автомата ^4, в центре изображен сам автомат а справа еще одна синхронизирующая раскраска ОрЬ4 этого графа с кратчайшим синхронизирующим словом а3. Заметим, что раскраска Ори является оптимальной, т. е. обладает кратчайшим синхронизирующим словом среди всех возможных раскрасок графа автомата

Значение функции Черни для оптимальной синхронизируемой раскраски заданного графа б называется значением оптимальной раскраски и обозначается ОРТ (С).

Задача о возможности раскраски орграфа в синхронизируемый автомат первоначально возникла в символической динамике, см. [2]. Для исключения из рассмотрения тривиальных случаев достаточно рассматривать только сильно-связные графы, у которых степени исхода всех вер-

шин одинаковы и длины циклов взаимно просты в совокупности. Такие графы называются АС\Ч-графами, поскольку гипотеза о существовании синхронизирующей раскраски для любого такого графа была сформулирована в статье Адлера, ГуДвина и Вэйса [3] в 1977 году. Эта гипотеза, получившая название гипотезы о раскраске дорог, привлекала внимание многих исследователей на протяжении более 30 лет и только недавно была подтверждена Трахтманом [18]. Основной открытой задачей является точный или приближенный поиск оптимальной раскраски или ее значения для заданного АС\У-графа. Этот вопрос, который также был поставлен в обзоре М. В. Волкова [20], рассматривается в третьей главе диссертации.

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

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории конечных автоматов, теории формальных языков и теории сложности вычислений.

Рис. 2: Граф автомата и две его раскраски

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

Ссылки на результаты диссертации присутствуют в работах других авторов: [11,13,16,17].

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 86 страниц. Библиографический список содержит 47 наименований.

Краткое содержание работы

Во введении обсуждается история решения задач, приводятся основные определения и формулируются основные результаты диссертации.

В первой главе диссертации изучается главная теоретическая проблема теории синхронизируемых автоматов - доказательство квадратичных оценок сверху на функцию Черни для сильно-связных автоматов. В §1.1 приведен алгоритм расширения в обобщенном виде. Через Б. гг1 обозначим полный прообраз подмножества состояний Б С <5 под действием слова V € Е*. Предполагается, что в п-автоматс есть два непустых подмножества состояний С5, Се такие, что С, С Се, а также заданы два слова связанные соотношениями С}:ис — Се и = 1.

Следующий алгоритм возвращает синхронизирующее слово путем построения расширяющей последовательности слов.

Алгоритм расширения (ЕА) Дано: л/, Св,Се,у3>уе инициализация Б С3

пока П Сс| < |Се|, найдем кратчайшее слово и € £* такое, что |5.и-1 П Се\ > |5 П Се|; если такого слова нет, то Ошибка у иу, 5 Б.и'1 Вернуть

Доказывается, что для любого синхронизируемого автомата алгоритм ЕА возвращает синхронизирующее слово, длина которого не превосходит |г>е| + [и4| + (|Се| - |С,|) тахясСе |м(5)|. Таким образом, для доказательства квадратичной оценки при помощи алгоритма ЕА необходимо оценивать сверху максимально возможную длину расширяющих слов. Подмножество 3 С С] называется т-расширяемым в подмножестве Се С. если существует некоторое расширяющее слово V длины не больше ш такое, что \S.v~1 П Се| > ¡5 П Се|. Для заданного числа к скажем, что п-автомат ¿г/ к -расширяемый, если любое собственное подмножество состояний /сп-расширяемо. Аналогично, п-автомат назовем строго к-расширяемым, если любое собственное подмножество состояний к(п — 1)-расширяемо. Ясно, что для [строго] ^-расширяемого п-автомата алгоритм ЕА вернет синхронизирующее слово длины не больше к(п — 2)(п — 1) + 1 или к(п — 2)п +1 соответственно. Таким образом, получается квадратичная верхняя оценка на функцию Черни для [строго] ¿-расширяемых автоматов.

Для доказательства того, что те или иные автоматы обладают приведенными выше свойствами расширения, различными авторами были предложены некоторые более сильные свойства, которые проще проверять. Одно из таких свойств было введено Карпи и Д'Алессандро [5] (см. также [6]). Скажем, что я-автомат «с/ удовлетворяет свойству к-независимости для некоторого числа к, если существует множество слов Цг С £* мощности п такое, что для любых двух состояний « и 4 найдется слово из IV, переводящее б1 в и длина каждого слова из IV не превосходит к(п — 1). В [6] доказано, что свойство &~независимости влечет свойство строгого (к + 1)-распгарения. Карпи и Д'Алессандро также предположили, что этот подход применим в общем случае, т. е. что справедлива

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

Справедливость этой гипотезы влекла бы квадратичную верхнюю оценку на функцию Черни для всех синхронизируемых п-автоматов.

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

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

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

В §1.1 вводится свойство к-баланса и доказывается, что это свойство является обобщением свойств ^-независимости и регулярности Рысцова (при к = 1). Далее доказывается, что свойство (к — 1)-баланса влечет свойство строгого ^-расширения для синхронизируемых автоматов.

В §1.2 строится двупараметрическая серия однокластерных автоматов ¿г/{т, к) (т > 2, к > 1) над двухбуквенным алфавитом. Из этой

серии выделяются две подсерии бёп — я/(п - 2,1) и 3)к — si(к2, к), для которых доказываются две основные теоремы первой главы.

Теорема 5. Для любого с <2 автомат ёёп не удовлетворяет свойству с-расгииреиия при тг >

Теорема 6. Автомат %>к не удовлетворяет свойству (к — 1)-баланса и, следовательно, серия опровергает как гипот.езу Карпи и Д'Алесса-ндро так и гипотезу Рысцова.

Из теоремы 5, в частности, следует, что алгоритм расширения не может быть применен напрямую при Се — Q для доказательства гипотезы Черни в общем случае, а из теоремы 6 следует, что как подход Карпи и Д'Алессандро из [5], так и подход И. К. Рысцова из [15] неприменимы напрямую для доказательства квадратичной оценки на функцию Черни в общем случае. Это наталкивает на мысль ослабить свойство строгого к-расширения (к-расширения аналогично) до следующего свойства строгого к-локалъного расширения: существуют подмножества Cs, Се С Q и слова vs,ve £ £* такие, что

\Cs.vs\ = 1, Ce.v~] =Q, Ca С Ce,

и каждое собственное подмножество S множества Се является k(n — 1)-расширяемым в Се, т.е. \S.v~1 Г) Се\ > |5 П Се| для некоторого слова v длины не больше к(п — 1). Если n-автомат удовлетворяет1 свойству строгого ¿-локального расширения, то он обладает синхронизирующим словом длины не больше |us| + |ие| + ([Се| - |Cs|)fc(n — 1). Ясно, что при подходящих ограничениях на длины слов vs и ve получаются соответствующие квадратичные оценки. Аналогичным образом, свойство к-баланса может быть ослаблено до свойства к-локалъного баланса. Легко показать, что свойство ¿-локального баланса влечет свойство строгого (к + 1)-локалыгого расширения для тех же параметров.

Заметим, что свойства 1-локального баланса и строгого 1-локального расширения выполняются для автоматов ßf(m, к) из построенной серии для подходящих Cs, va, Се и ve и алгоритм ЕА на таких исходных данных возвращает синхронизирующее слово квадратичной длины т2 + 2 < п2 - 4п + 6. Таким образом, примеры, построенные для опровержения «глобальных» версий некоторых свойств, удовлетворяют ослабленным версиям тех же самых свойств. Вполне возможно, что эти обновленные версии рассмотренных свойств могут быть эффективны для

доказательства квадратичных оценок для произвольных автоматов. В качестве косвенного подтверждения этого предложения, в §1.3 при помощи указанной идеи устанавливается квадратичная оценка 2п2 — 7п + 7 для однокластерных автоматов.

Теорема 7. Любой однокластерный синхронизируемый п-автомат имеет синхронизирующее слово длины не более 2п2 — 7п н- 7.

Справедливость теоремы следует из того, что однокластериые автоматы удовлетворяют свойству 1-локального баланса для подходящих подмножеств С3,Се и слов у3,ье.

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

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

В доказательстве этой теоремы используется сведение задачи ВЫПОЛНИМОСТЬ к рассматриваемой задаче. Второй этап состоит в доказательстве основной теоремы второй главы.

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

Доказательство происходит по индукции, причем теорема 8 используется как дня доказательства базы индукции, так и в качестве основы для построения на шаге индукции. В §2.3 также показано, как перенести доказанный результат на случай автоматов с двумя входными буквами.

Третья глава посвящена задаче поиска значения оптимальной раскраски и самой оптимальной раскраски. Показано, что эти задачи не

могут быть приближенно решены полиномиальными алгоритмами с относительной погрешностью меньше 2 в предположении Р ф ЫР. Основным утверждением третьей главы является следующая

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

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

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

Стоит отметить, что задачи вычисления значения оптимальной раскраски и вычисления самой оптимальной раскраски также не сводятся друг к другу. Тем не менее, при помощи анализа доказательства теоремы 10 в третьей главе в качестве следствия доказана полиномиальная неаппроксимируемость поиска оптимальной раскраски с относительной погрешностью меньше 2 в предположении Р Ф №. В конце третьей главы также показано как перенести результаты на АС\У-графы со степенью исхода 2.

Основные результаты диссертации

• Опровергнута гипотеза Рысцова (1995) о том, что любой сильносвязный автомат является регулярным и гипотеза Карпи и Д'Алессандро (2008) о том, что любой сильно-связный синхронизируемый автомат обладает независимым множеством слов линейной длины. Обе гипотезы использовались указанными авторами для доказательства квадратичных оценок на длину кратчайшего синхронизирующего слова в частных случаях. Опровергнуто так называемое свойство е-расширения (для

с<2), также используемое во многих частных случаях для доказательства квадратичных оценок. Указано ослабление опровергнутых гипотез, не опровергаемое тем же способом, но по-прежиему обеспечивающее квадратичные оценки.

• На основе идей, связанных с ослаблением опровергнутых гипотез, доказана квадратичная оценка для класса однокластерных автоматов, являющихся естественным обобщением класса циклических автоматов.

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

• Аналогичный результат получен для задачи поиска оптимальной раскраски АС\У-графа, т. е. раскраски с кратчайшим синхронизирующим словом среди всех синхронизируемых раскрасок данного графа. Для этой задачи доказано отсутствие полиномиального алгоритма с относительной погрешностью меньше 2.

Благодарности

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

Список литературы

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

[2] Adler R., Weiss В. Similarity of automorphisms о} the torus // Memoirs Amer. Math. Soc. 1970. No.98.

[3] Adler R., Weiss В., Goodwyn L. W. Equivalence of topological Markov shifts Il Israel J.'Math. 1977. V.27. P.49-63.

[4] Béai M., Perrin D. A quadratic upper bound on the size of a synchronizing word in one-cluster automata // Lect. Notes Сотр. Sci. Springer, Heidelberg. 2009. V.5583. P.81-90.

[5] Carpi A., D'Alessandro F. The synchronization problem for strongly transitive automata // Lect. Notes Сотр. Sci. Springer, Heidelberg. 2008. V.5257. P.240-251.

[6] Carpi A., D'Alessandro P. Strongly transitive automata and the Cerny conjecture // Acta Informatica. 2009. V.46. P.591-607.

[7] Cerny J. Poznamka к homogennym eksperimentom s konecnymi automatami // Mat.-Pyz. Cas. Slovensk. Akad. Vied. 1964. V.14. P.208-216.

[8] Dubuc L. Sur les automates circulaires eta la conjecture de Cerny // RAIRO Theor. Inform, and Appl. 1998. V.32. P.21-34.

[9] Eppstein D. Reset sequences for monotonic automata // SIAM J. Comput. 1990. V.19. P.500-510.

[10] Frankl P. An extremal problem for two families of sets// Eur. J. Comb. 1982. V.3. P.125-127.

[11] Gerbush M., Heeringa B. Approximating minimum reset eequences// Lect. Notes Сотр. Sci. 2010. V.6482. P. 154-162.

[12] Kari J. Synchronizing finite automata on eulerian digraphs / j Theor. Comput. Sci. 2003. V.295. P.223-232.

[13] Olschewski J., Ummels M. The complexity of finding reset words in finite automata // Lect. Notes Сотр. Sci. 2010. V.6281. P.568-579.

[14] Pin J. On two combinatorial problems arising from automata theory// Ann. Discrete Math. 1983. V.17. P.535-548.

[15] Rystsov I. K. Quasioptimal bound for the length of reset words for regular ■ automata // Acta Cybernetica. 1995. V.12. P.145-152.

[16] Steinberg B. The averaging trick and the Cerny conjecture // Lect. Notes Сотр. Sci. 2010. V.6224. P.423-431

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

[18] Trahtman A. The road coloring problem// Israel J. of Math. 2009. V.172. No.l. P.51-60.

[19] Volkov M. V. Synchronizing automata preserving a chain of partial orders// Lect. Notes Сотр. Sci. 2007. V.4783. P.27-37.

[20] Volkov M. V. Synchronizing automata and the бету conjecture// Lect. Notes Сотр. Sci. 2008. V.5196. P. 11-27.

Работы автора по теме диссертации

[21] Béai 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.

[22] 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.

[23] 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.

Подписано в печать 26.04.2011. Формат 60*84 1/16. Усл. печ. л. 30 Тираж 100 экз. Заказ № 18051

Центр оперативной полиграфии «Копирус», г. Екатеринбург, ул. Мамина-Сибиряка, 137

Тел.: (343) 350-44-12

Введение

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

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

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

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

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

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

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

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

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

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

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

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

1 Метод расширения и гипотеза Черни

1.1' Алгоритм расширения и связанные свойства.

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

1.3 Локальные версии свойств.

1.4 Однокластерные автоматы.

2 Поиск кратчайших синхронизирующих слов

2.1 Неаппроксимируемость с погрешностью меньше 2.

2.2 Основной результат.

2.3 Случай двухбуквенного алфавита.

3 Поиск оптимальной раскраски

3.1 Вспомогательные определения и формулировка результата

3.2 Случай трехбуквенного алфавита.

3.3 Случай двухбуквенного алфавита.

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 году. Так как автоматы также являются циклическими и €(Сп) = (п — 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. Любой допустимый граф имеет синхронизирующую раскраску.

13

Задача вызвала большой интерес среди специалистов теории графов, конечных автоматов и символической динамики. Несмотря на простоту формулировки, задача оставалась нерешенной более 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.

15

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

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

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

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

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

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

16

Возможность построения расширяющей последовательности линейной длины можно формализовать следующим образом. Подмножество состояний 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] справедливость этой гипотезы также влечет квадратичную верхнюю оценку на на функцию Черни для всех синхронизируемых автоматов.

18

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

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

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

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

19

Рис. 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 напрямую не следует невозможность точного или приближенного вычисления самой оптимальной раскраски. Такой вывод нельзя сделать, так как для поиска оптимальной раскраски не требуется находить значение оптимальной раскраски, равное значению функции Черни для этой раскраски.

23

Если бы задача вычисления значения функции Черни для автомата была полиномиально разрешимой, то любой полиномиальный алгоритм, находящий оптимальную раскраску, можно было бы достроить до полиномиального алгоритма, находящего значение оптимальной раскраски и, таким образом, получить противоречие. Однако, ввиду теоремы 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].

24

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. Béai M., Perrin D. A quadratic algorithm for road coloring // Электронная публикация]. 2008. arXiv:0803.0726.

11. Béai 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 Informática. 2009. V. 46. P. 591-607.

15. Cerny J. Poznámka k homogénnym eksperimentom s konecnymi automatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. 1964. V. 14. P. 208-216.

16. Culik K., Karhumáki 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. 201209.

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. Béai 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.