Введение к работе
Актуальность темы. Одной из самых простых и в то же время эффективных моделей дискретных систем являются конечные автоматы. Детерминированным конечным автоматом называется тройка объектов «й/ = (Q, Е, 8), где Q - множество состояний, Е - входной алфавит,, 8 : Q х Е —> Q - функция переходов автомата. В работе рассматривается только этот вид автоматов.
При моделировании систем конечными автоматами состояния автомата соответствуют возможным состояниям системы, а буквы входного алфавита соответствуют допустимым операциям системы. В силу внешних воздействий или внутренних причин в таких системах могут происходить некорректные переходы. Для того чтобы можно было вернуть контроль над системой после некорректных переходов, не прибегая к ее анализу, целесообразно проектировать систему таким образом, чтобы она обладала некоторой «перезагрузочной» последовательностью операций. Таким образом, вопрос существования перезагрузочной последовательности и вопрос о том, насколько короткой ее можно выбрать, являются существенными для рассматриваемых систем.
Введем теперь формальное определение синхронизирующих слов, играющих роль перезагрузочных последовательностей при моделировании систем конечными автоматами. Слово w Є Е* в автомате «й/ называется синхронизирующим, если его действие «перезагружает» автомат «г/, т. е. переводит автомат в некоторое состояние вне зависимости от того состояния, в котором автомат находился до применения этого слова. Иначе говоря, слово w синхронизирующее, если 8{q, w) = 8{р, w) для всех q,pe Q.
Если автомат «г/ обладает хотя бы одним синхронизирующим словом, то он называется синхронизируемым, а длина кратчайшего синхронизирующего слова для «й/ обозначается через ((«й/). Само отображение , ставящее в соответствие автомату «й/ число ((«й/), будем называть функцией Черни. В качестве примера рассмотрим изображенный на рис. 1 автомат Чо±. Нетрудно проверить, что автомат ^4 синхронизируем и что кратчайшим синхронизирующим словом этого автомата является Ъо?Ъо?Ъ. Следовательно, () = 9. Этот пример принадлежит к серии автоматов, построенной в 1964 году словацким математиком Яном Черни [7]. В [7] впервые явно появилось понятие синхронизируемого автома-
та и построена серия п-автоматов1 ^ с кратчайшим синхронизирующим словом длины (п — I)2.
Рис. 1: Автомат Черни ^4
Черни предположил, что серия Чоп реализует наихудший в смысле скорости синхронизации случай, т. е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — I)2. Это предположение получило название гипотезы Черни. Несмотря на простоту формулировки и многочисленные попытки доказать или опровергнуть эту гипотезу, в общем случае она остается открытой и доказана лишь в некоторых частных случаях. Наилучшая известная на момент написания диссертации оценка сверху на число ((«g/) для гг-автомата «й/ равна п ~п. (Эта оценка была доказана около 30 лет назад Пэном [14] при помощи комбинаторного результата Франкля [10].) Так как предполагаемая верхняя оценка на функцию Черни для гг-автоматов есть квадратичная функция от п, то принципиальной задачей является получение квадратичной оценки для как можно более широкого класса гг-автоматов.
Дюбук [8] в 1998 году доказал гипотезу Черни для циклических автоматов, т. е. автоматов, у которых некоторая буква действует как циклическая перестановка на всем множестве состояний. Естественным обобщением циклических автоматов являются одпокластерпые автоматы, т. е. автоматы, в которых некоторой буквой помечен ровно один простой цикл. Однокластерными автоматами являются декодеры полных префиксных кодов и свойство синхронизации для таких декодеров равносильно свойству самокоррекции для соответствующих кодов. Поэтому получение оценок кратчайшей длины синхронизирующих слов
хДля краткости здесь и ниже под n-автоматом понимается автомат с п состояни-
для однокластерных автоматов представляет большой интерес как с практической точки зрения, так и с точки зрения продвижения на пути доказательства квадратичной оценки в общем случае. Эта задача рассматривается в первой главе диссертации.
Одним из основных методов доказательства квадратичных верхних оценок на функцию Черни является метод расширения. Этот метод получил широкое применение в последние 15 лет и стал основой нескольких впечатляющих результатов. Кроме уже упомянутого результата Дюбу-ка [8], можно отметить работу Кари [12], в которой гипотеза Черни была подтверждена для автоматов с эйлеровым графом. И. К. Рысцов, используя метод расширения, доказал квадратичную верхнюю оценку для автоматов, в которых каждая буква либо переставляет состояния, либо фиксирует все состояния, кроме одного [1], а также для так называемых регулярных автоматов [15].
Заметим, что доказательство квадратичных оценок легко сводится к случаю сильно-связных автоматов (см., напр., [19, предл. 3]). Пусть <й/ = {Q,T.,8) - сильно-связный синхронизируемый п-автомат. Через S.v будем обозначать образ подмножества состояний S С Q под действием слова v Є Е*. Идея метода расширения заключается в том, чтобы построить последовательность относительно коротких расширяющих слов г>і, г>2, , ^k и выбрать состояние q так, чтобы последовательность множеств Si,S2,...,Sk таких, что
{q} = Si, S2.vi = Si,... Sk-Vk = Sk-i,
возрастала по мощности и достигала Q, т.е.
1 = {Sil < \S2\ < < \Sk\ = \Q\ = п.
Ясно, что для любой такой последовательности слово VkVk-i f і синхронизирует автомат. Легко видеть, что описанный метод позволяет построить синхронизирующее слово для любого сильно-связного синхронизируемого автомата. Заметим, что длина цепочки к не больше п—1, так как мощности множеств Si строго возрастают. Следовательно, для получения квадратичных оценок сверху на функцию Черни для гг-автоматов достаточно, чтобы длины слов 1 были линейно ограничены от п. Ввиду этого аргумента принципиально важной задачей является доказательство или опровержение гипотез, позволяющих получать линейные оценки на длину расширяющих слов. Эта задача также рассматривается в первой главе диссертации.
На практике часто встречаются системы, для которых необходима быстрая перезагрузка. Один раз найдя кратчайшее синхронизирующее слово автомата, соответствующего такой системе, можно применять его многократно, экономя время и ресурсы при перезагрузке. Таким образом, задача поиска относительно короткого синхронизирующего слова или его длины является одной из основных не только с теоретической, но и с практической точки зрения. К сожалению, точный вариант этой задачи является труднорешаемым. А именно, известно, что вопрос о том, существует ли для данного синхронизируемого автомата «й/ синхронизирующее слово, длина которого не превосходит данного числа , является iVP-полной задачей (см., напр., [9]). Из этого, однако, не следует, что синхронизирующее слово на один символ длиннее кратчайшего не может быть найдено эффективным алгоритмом. Следовательно, ключевым становится вопрос о возможности приближенного вычисления длины кратчайшего синхронизирующего слова. Этот вопрос, поставленный в недавнем обзоре М.В.Волкова [20], рассматривается во второй главе диссертации.
При моделировании систем конечными автоматами иногда встречаются такие системы, в которых определены возможные переходы между состояниями и набор допустимых операций, но не определено соответствие («раскраска») между операциями и переходами, либо соответствие задано, но его можно переопределить («перераскрасить»). При этом рассматриваются те же вопросы, что и для автоматов, но с учетом возможности перераскраски: задача перераскраски заданного автомата в синхронизируемый и задача перераскраски автомата в синхронизируемый с как можно более коротким синхронизирующим словом. Например, на рис. 2 слева изображен граф автомата Чо±, в центре изображен сам автомат ^4, а справа еще одна синхронизирующая раскраска Opt^ этого графа с кратчайшим синхронизирующим словом о?. Заметим, что раскраска Opt4 является оптимальной, т. е. обладает кратчайшим синхронизирующим словом среди всех возможных раскрасок графа автомата ^4- Значение функции Черни для оптимальной синхронизируемой раскраски заданного графа G называется значением оптимальной раскраски и обозначается OPT{G).
Задача о возможности раскраски орграфа в синхронизируемый автомат первоначально возникла в символической динамике, см. [2]. Для исключения из рассмотрения тривиальных случаев достаточно рассматривать только сильно-связные графы, у которых степени исхода всех вер-
b a
b ^b
Рис. 2: Граф автомата ^4 и две его раскраски
шин одинаковы и длины циклов взаимно просты в совокупности. Такие графы называются AGW-графами, поскольку гипотеза о существовании синхронизирующей раскраски для любого такого графа была сформулирована в статье Адлера, Гудвина и Вэйса [3] в 1977 году. Эта гипотеза, получившая название гипотезы о раскраске дорог, привлекала внимание многих исследователей на протяжении более 30 лет и только недавно была подтверждена Трахтманом [18]. Основной открытой задачей является точный или приближенный поиск оптимальной раскраски или ее значения для заданного AGW-графа. Этот вопрос, который также был поставлен в обзоре М. В. Волкова [20], рассматривается в третьей главе диссертации.
Перечислим основные цели работы: опровержение гипотез различных авторов, справедливость которых обеспечивает линейные оценки на длины расширяющих слов; модернизация опровергнутых подходов и доказательство на основе этих модернизированных подходов квадратичной оценки сверху на функцию Черни для класса однокластерных автоматов; доказательство полиномиальной неаппроксимируемости значения функции Черни; доказательство полиномиальной неаппроксимируемости значения оптимальной раскраски и самой оптимальной раскраски с относительной погрешностью меньше 2.
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории конечных автоматов, теории формальных языков и теории сложности вычислений.
Апробация результатов работы. Основные результаты диссертации докладывались на Российско-индийском семинаре по алгебре, комбинаторике и сложности (Екатеринбург, 2008), международной конференции "Симпозиум по компьютерным наукам в России" CSR 2010 (Казань, Россия, 2010), 14-ой международной конференции по теории формальных языков DLT 2010 (Лондон, Канада, 2010), международном семинаре по автоматам DAAST (Вена, Австрия, 2010) и заседаниях семинара "Компьютерные науки" (УрГУ).
Ссылки на результаты диссертации присутствуют в работах других авторов: [11,13,16,17].
Публикации. Основные результаты диссертации опубликованы в [21-23]. Результаты из [21] были независимо доказаны автором диссертации и французскими математиками Беал и Перрэном, а совместная работа [21] возникла в результате слияния в один статью текстов, подготовленных автором и французскими коллегами. При этом результат, полученный автором диссертации, был несколько точнее, чем результат Беал и Перрэна, и в тексте совместной статьи приведен именно он. Работа [21] опубликована в издании, входящем в перечень утвержденных ВАК.
Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 86 страниц. Библиографический список содержит 47 наименований.