О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | ПДМ. 2011. № 2(12).

О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат

Сильносвязный орграф называется допустимым, если исходящие степени всех вершин в нём одинаковы и длины циклов взаимно просты в совокупности. Раскраской допустимого графа G назовем произвольный автомат A, граф которого совпадает с G. Слово называется синхронизирующим автомат A, если оно переводит его в одно и то же состояние вне зависимости от исходного состояния автомата A. Оптимальная раскраска допустимого графа -это раскраска с кратчайшим синхронизирующим словом среди всех синхронизирующих раскрасок. Длину соответствующего синхронизирующего слова назовем значением оптимальной раскраски. Доказано, что любой приближенный полиномиальный алгоритм для вычисления оптимальной раскраски или ее значения имеет относительную погрешность не меньше 2 в случае трехбуквенного алфавита при предположении P = NP. Также показано, как результат можно перенести на случай двухбуквенного алфавита.

A note on polynomial approximation of synchronizing optimal coloring.pdf Введение и история задачиВведём определения синхронизируемого автомата и оптимальной раскраски. ПустьA = (Q, Е, 8) -полный детерминированный конечный автомат, где Q - множество со-стояний; Е - входной алфавит автомата; 8 : Q х Е ^ Q - функция переходов. Функ-ция 8 продолжается единственным образом на множество Q х Е *, где Е * обозначаетсвободный моноид над Е. Таким образом, каждое слово из Е действует на множе-стве Q в соответствии с функцией переходов 8. Через S.v будем обозначать образподмножества S С Q под действием слова v, т. е. S.v = {8(q, v) : q G S}.Автомат A называется синхронизируемым, если существует слово w G Е *, действиекоторого «перезагружает» автомат A, т. е. переводит автомат в некоторое состояниевне зависимости от исходного состояния автомата: q.w = p.w для всех q,p G Q, что эк-вивалентно равенству |Q.w| = 1. Произвольное слово w с таким свойством называетсясинхронизирующим автомат A, а длина кратчайшего синхронизирующего слова для Aназывается значением функцией Черни и обозначается через C(A). На рис. 1 в центренарисован автомат Черни C4 с кратчайшим синхронизирующим словом ba3ba3b дли-ны 9 и, следовательно, C(C4) = 9.Рис. 1. Автомат Черни, его граф и оптимальная раскраскаЗадачи, возникающие в теории синхронизируемых автоматов, являются не про-сто алгебраическими головоломками, но и имеют приложения в различных областяхкомпьютерных наук, таких, как кодирование или построение вычислительных систем.Вычислительные системы зачастую могут быть смоделированы как конечные автома-ты. Под действием шума или внутренних причин в системе могут происходить некор-ректные переходы. Системы, соответствующие синхронизируемым автоматам, болееустойчивы к таким ошибкам, так как могут быть возвращены в корректное состоя-ние применением перезагрузочной последовательности операций (синхронизирующегослова). Ясно, что важно не только наличие такой последовательности, но и то, насколь-ко короткой ее можно выбрать. Таким образом, две ключевые задачи этой теории -это задача проверки заданного автомата на синхронизируемость и задача поиска крат-чайшего синхронизирующего слова или его длины для заданного синхронизируемогоавтомата.При моделировании систем конечными автоматами иногда встречаются такие, в ко-торых определены возможные переходы между состояниями и набор допустимых опе-раций, но не определено соответствие («раскраска») между операциями и переходами,либо соответствие задано, но его можно переопределить («перераскрасить»). При этомключевые задачи остаются теми же, но ставятся с учетом возможности перераскраски:задача проверки возможности перераскраски в синхронизируемый автомат и задачапоиска перераскраски с кратчайшим синхронизирующим словом среди всех синхрони-зируемых перераскрасок. Для перехода к этим задачам нам понадобится определениеграфа автомата.Орграф G = UG(A) называется графом автомата A, если его множество вер-шин совпадает с множеством состояний автомата A, а дуги соответствуют переходамавтомата, т. е. из вершины q есть стрелка в вершину q' тогда и только тогда, когда$(q,a) = q' для некоторой буквы a Е Е. Тогда G - орграф с одинаковыми степенямиисхода вершин, и автомат A называется раскраской графа G. Сильносвязный орграф Gназывается допустимым, если исходящие степени всех вершин в нём одинаковы и дли-ны циклов взаимно просты в совокупности. Условие одинаковых исходящих степенейвершин необходимо для возможности раскраски, а условия взаимной простоты длинциклов и сильной связности необходимы для разрешимости и неприводимости задачинахождения синхронизирующей раскраски [1-3]. Очевидно, что любой допустимыйорграф может быть получен как граф подходящего автомата и любая перераскраскаавтомата - это раскраска его графа.Пусть G - допустимый орграф. Раскраску A назовем оптимальной раскраской G иположим OPT(G) = C(A), если для любой другой раскраски B графа G выполняетсяC(A) ^ C(B); в этом случае OPT(G) называется значением оптимальной раскраски.Другими словами, раскраска графа G оптимальна, если она есть раскраска с кратчай-шим синхронизирующим словом среди всех возможных синхронизируемых раскрасокграфа G. На рис. 1 показаны один четырёхвершинный орграф и две его синхронизи-руемые раскраски. В центре нарисован автомат Черни с кратчайшим синхронизиру-ющим словом ba3ba3b длины 9, а справа - оптимальная раскраска заданного орграфас синхронизирующим словом а3 длины 3.Вопрос проверки автомата на синхронизируемость полиномиально разрешим (см.для примера [4]). Гораздо более интересным является вопрос о том, можно ли перерас-красить любой автомат так, чтобы он стал синхронизируемым. Этот вопрос известенкак проблема раскраски дорог. Задачу впервые поставили в 1970 г. Р. Л. Адлер и Б. Вэйсв работе [5], окончательно сформулировав её в следующем виде для допустимых гра-фов в [1] (1977 г.).Гипотеза. Любой допустимый граф имеет синхронизирующую раскраску.Несмотря на многочисленные исследования, эта гипотеза оставалась открытой бо-лее 30 лет и была положительно решена А. Н. Трахтманом [2] только в 2008 г. До-казательство в [2] конструктивно и дает кубический (от числа состояний) алгоритмдля нахождения синхронизирующей раскраски любого допустимого графа. В [6] былопоказано, как можно решать эту задачу квадратичным алгоритмом.Рассмотрим теперь задачу минимизации длины синхронизирующего слова. Дляавтоматов ее можно поставить следующим образом.Задача Min-Synch-Length. Дан синхронизируемый автомат A, найти C(A).Д. Эпштейн [7] показал, что эта задача NP- и TO-NP-трудна, и, следовательно, даженедетерминированный полиномиальный алгоритм не может решать эту задачу в пред-положении P = c°-N P . Из этого результата, однако, не следует, что не существуетполиномиального алгоритма, находящего синхронизирующее слово на один символдлиннее кратчайшего. Тем не менее в [8] показано, что в предположении P = NPне существует полиномиального алгоритма, решающего последнюю задачу даже длякласса двухбуквенных автоматов.Заметим, что длядопустимых графов можно поставить две задачи, связанные с ми-нимизацией длины синхронизирующего слова:1) задачу вычисления значения оптимальной раскраски:Задача OCV (Optimal C°l°ring Value). Дан допустимый граф G, найти OPT(G);2) задачу построения оптимальной раскраски:Задача OC (Optimal C°l°ring). Дан допустимый граф G, найти его оптимальнуюраскраску.Заметим, что хотя задача Min-Synch-Length соответствует задаче OCV с зафик-сированной раскраской, из её полиномиальной неаппроксимируемости не следует та-кой же результат для задачи вычисления значения оптимальной раскраски OCV, таккак для нахождения OPT(G) не требуется искать значения C(A(G)) для всех раскра-сок A(G) графа G.Далее докажем, что в предположении P = NP любой приближенный полиноми-альный алгоритм решения задачи OCV в трёхбуквенном алфавите имеет относитель-ную погрешность не меньше 2, и покажем, как этот результат перенести на двухбук-венный случай и применить к задаче OC.В п. 1 вводятся вспомогательные понятия и обозначения. В п. 2 доказано, чтов предположении P = NP любой полиномиальный алгоритм для вычисления значе-ния оптимальной раскраски имеет относительную погрешность не меньше 2 в случаетрехбуквенного алфавита, и показано, как перенести результат на задачу поиска опти-мальной раскраски. В п. 3 показано, что при помощи некоторых изменений в структуреграфа можно доказать такой же результат для раскраски в двухбуквенном алфавите.Из этого, в частности, следует, что задача поиска оптимальной раскраски NP-труднадаже в случае двухбуквенного алфавита.1. Вспомогательные определенияПусть A - сильносвязный синхронизируемый автомат, Q - множество его состоя-ний. Назовем подмножество S С Q занятым после применения некоторого слова v,если S С Q.v. Будем обозначать v ( i . . . j) подслово слова v c i-го по j-й символ вклю-чительно; v(i) - i-й символ слова.Пусть S, T - два непустых множества состояний автомата A. Через LRadiusA(S, T)обозначим минимальное число r, такое, что найдется t Е T и для каждого элемента sиз S есть путь из s в t с длиной, в точности равной r. В роли множества T обычно будетвыступать Q, поэтому для краткости обозначим LRadius^S, Q) через LRadius^S).Например, на рис. 1 для автомата Черни LRadiusC4({1, 2}, {2}) = 1. Через LSynchA(S)для непустого множества состояний S обозначим длину кратчайшего слова v, синхро-низирующего множество S в автомате A, т.е. такого v, что |S.v| = 1. Заметим, что нарис. 1 для автомата Черни LSynchC4({1, 2}) = 4, и LSynchA(Q) совпадает с C(A) длялюбого автомата A.Пусть r - натуральное число; тогда через Image^S, r) (соответственно черезPreimageA(S, r)) обозначим множество состояний q Е Q, таких, что в UG(A) естьпуть длины не больше r из множества S в q (соответственно в множество S из q).Другими словами, ImageA(S, r) (соответственно PreimageA(S, r)) - это полный образ(соответственно прообраз) S под действием слов длины не более r в автомате A. От-метим несколько простых свойств введенных выше функций.Лемма 1.1) Функция LRadius везде определена.2) LSynchA(S) ^ LRadiusA(S).3) Пусть T - объединение двух непустых множеств и T2; тогдаLRadiusA(S, T) = min(LRadiusA(S, Ti), LRadiusA(S, T2)).4) Пусть S1 -непустое подмножество S; тогда LRadiusA(S1, T) ^ LRadiusA(S, T).5) Функции LRadius, Image и Preimage зависят только от графа автомата.6) Пусть S ^ Preimage(T, r) для некоторого r > 0; тогда LRadiusA(S, T) > r.Доказательство. Пусть w есть кратчайшее слово, синхронизирующее S в ав-томате A; тогда S.w = qo для некоторого qo Е Q. Так как автомат сильносвязный,то существует слово v, такое, что q0.v Е T. Тогда S.wv - это одноэлементное множе-ство в T, поэтому LRadiusA(S,T) определен и не превосходит |wv|. Таким образом,п. 1 леммы 1 доказан. Если в качестве T выбрать множество всех состояний, то сло-во v можно выбрать пустым. Следовательно, LRadius^S) ^ |w| = LSynch^(S), и п. 2также доказан. Пункты 3-7 непосредственно следуют из определений. Действительно,проверим для примера п. 3. Заметим, что для функции LRadius справедливо соотно-шение LRadiusA(S, T) = mmLRadiusA(S, t). Следовательно, п. 3 следует из свойстваминимума и условия T = T1 U T2. Поскольку все автоматы, рассматриваемые далее в доказательстве теоремы, имеютодин и тот же граф, то ввиду п. 5 леммы 1 можно не указывать автомат в записифункций LRadius, Image и Preimage.Используемые в работе определения из теории сложности вычислений можно най-ти в [9]. Приведем понятие аппроксимирующего алгоритма для нашей задачи. ПустьK - некоторый класс допустимых графов. Следуя определению погрешности алгорит-ма из [9], скажем, что алгоритм A/g приближенно находит значение оптимальнойраскраски в классе K, если для любого допустимого графа G G K алгоритм возвра-щает натуральное число A/g(G) ^ OPT(G). Тогда говорят, что алгоритм A/g решаетOCV с относительной погрешностью к G R для класса K, еслиsup { OPTG) : G G K } = к.2. Случай трехбуквенного алфавитаТеорема 1. В предположении P = NP любой полиномиальный алгоритм, реша-ющий OCV для класса трехбуквенных автоматов, имеет относительную погрешностьне меньше 2.Доказательство. План доказательства следующий. Покажем, что полиноми-альный алгоритм A/g, решающий OCV с относительной погрешностью меньше 2, мо-жет быть использован для полиномиального алгоритма, решающего NP-полную за-дачу ВЫПОЛНИМОСТЬ (SAT). Таким образом, получим противоречие с предполо-жением P = N P. Более точно, пусть полиномиальный алгоритм A/g решает OCVс относительной погрешностью 2 - е, где 0 < е < 2. Возьмем произвольный экземплярзадачи SAT - формулу ф с n переменными и m дизъюнктами (дизъюнкциями перемен-ных и их отрицаний). Построим допустимый граф G(^), имеющий полиномиальныйразмер от m, n, и полином p(m, n), такие, что:- если ф выполнима, то OPT(G(^)) ^ p(m, n) (этот случай назовем GOODCASE);- если ф невыполнима, то OPT(G^)) ^ (2 - 0,5e)p(m, n) (случай BADCASE).Из построения следует, что ф выполнима тогда и только тогда, когда A/g возвращаетзначение, меньшее чем (2 - 0,5e)p(m,n). Следовательно, найдем решение NP-полнойзадачи SAT, используя полиномиальный алгоритм A/g.Выполним теперь описанное сведение формально. Рассмотрим некоторый экзем-пляр ф задачи SAT с набором переменных Xi, X2,... , Xn и набором дизъюнктов от нихCi, C2,... , cm. Будем писать Xj G Cj или - Xj G Cj, если дизъюнкт Cj содержит в своейзаписи переменную Xj или ее отрицание соответственно. Без ограничения общностиможно предполагать, что m > 3, n > 3 и задача ф нормализована, т. е. выполняютсяследующие условия:(C1) Для любой переменной Xj есть дизъюнкт Cj, состоящий из переменной и ееотрицания, т. е. Cj = (xj V -Xj).(C2) Переменная Xn равна 0 в любом наборе, выполняющем ф.(C3) Для любой переменной Xj и дизъюнкта Cj если (Xj G Cj и -Xj G Cj), то Cj =^^j V '^^j.Для того чтобы выполнялись условия (C1), (C3), нужно добавить дизъюнкты видаCj = (Xj V -Xj), если их еще нет в формуле, и исключить все дизъюнкты, содержащиеXj, - Xj и еще какие-то переменные. Если (C2) не выполняется, то можно добавитьпеременную Xn+i, дизъюнкт Cm+i = (-Xn+i), а также дизъюнкт Cm+2 = (Xn+i V- Xn+i),чтобы удовлетворять (C1). Ясно, что такие преобразования формулы - не влияют наее выполнимость.Вместо определения дуг графа G(-) будем сразу определять переходы автомата Aэтого графа так, что если - выполнима, то C(A) ^ p(m, n). Из этого следует коррект-ность сведения для случая GOODCASE. Для случая BADCASE, т. е. когда - невыпол-нима, сделаем предположение от противного о том, что есть некоторая раскраска Bграфа G(-), такая, чтоC(B) < (2 - 0 , 5 ф ( т , n). (Ev)Получив противоречие с этим предположением, докажем корректность сведения дляслучая BADCASE.Таким образом, для случая GOODCASE достаточно показать, как можно за поли-номиальное от n,m время построить автомат A графа G(-), для которого есть син-хронизирующее слово u длины не больше p(m,n). Для BADCASE нужно получитьпротиворечие с тем, что найдется слово v длины не больше (2 - 0,5e)p(m,n), син-хронизирующее автомат B. Заметим также, что из доказательства будет видно, чтограф G(-) строится за полиномиальное от размера - время.Схема автомата A показана на рис. 2. Множество состояний Q автомата A явля-ется объединением шести компонент (подмножеств состояний автомата, играющихопределенную роль в доказательстве): Rinit, Rsat, Tsat, R/i x , Ra c c , Qs pec. Алфавит Е ав-томата A состоит из трех букв a,b,c, а функция переходов будет определена по ходудоказательства. Заметим, что компонента Q s p e c состоит из подмножеств C0, C1, C2, R0и состояния z и не окружена рамкой. Компонента Racc состоит из набора подмножествD1, D2 , . . . , D n - 1 и подкомпоненты Rowacc, также явно на рисунке не обозначенной.Компоненты Rinit и Tsat являются трехмерными, а компоненты Rsat и Rowacc - дву-мерными массивами состояний, т. е. каждое состояние из этих компонент может бытьзаписано как K(i1, i2, i3), где K - одна из компонент Rinit, Rs«t, Tsat, Rowacc (индекс i3имеет смысл только для Rinit и Tsat). Строкой и столбцом этих компонент автоматабудем называть подмножество состояний массива компоненты с фиксированным пер-вым и вторым индексом соответственно. Например, на рис. 2 отмечены 1-я и 2-я строкиRinit (Rinit(1, *, *) и Rinit(2, *, *)); 1-я и (n + 1)-я строки Rsat ( R s a t ( 1 , *) и Rsat(n +1, *));4-й, 6-й и (4n + 2)-й столбцы Rowacc (Rowacc(*, 4), Rowacc(*, 6), Rowacc(*, 4n + 2)) и др.Одномерные массивы состояний C0, C1, C2, R f i x назовем столбцами, а R0 - строкой.Заметим, что строкам и столбцам компонент на рис. 2 соответствуют горизонтальныеи вертикальные наборы состояний соответственно.Введем теперьполиномы, требующиеся для определения компонент:Р1 = Р1 (m, n) = m + 3 - число столбцов в Rinit и Rsat;p2 = p2(m, n) = 15n2 + m - вспомогательный полином;p3 = p3(m, n) = 4(p1 + p2) - количество значений, которые может принимать третийиндекс в Ri„it;p = p(m, n) = ((kn- 1)p3 + 2) + (n+1) + (18+(4n+13)(n-2)) -полином, участвующийв оценках на OPT(G);p«dd = p«dd(m, n) = p3(kn - 1) = 4(15n2 + 2m + 2)(kn - 1) -высота столбцов C0, C1, C2компоненты Qs p e c.Константа k выбрана так, чтобы выполнялось неравенство 2padd ^ (2 - 0,5e)p длявсех m > 3, n > 3. Заметим, что k не зависит от задачи, т. е. от -, m или n.Перед тем как переходить к формальному определению компонент автомата и рас-смотрению их свойств, объясним, для чего необходима каждая из компонент на соот-ветствующем шаге доказательства.Рис. 2. Схема автомата A1) При помощи свойств компоненты построим слово uirait длины (kn - 1)p3 ++2 для автомата A, отображающее Q \ Q s p e c в первую строку Rsat (Rsat(1, *)).Таким образом, фактически после этого шага потребуется отслеживать об-раз только одной строки. Для случая BADCASE докажем, что можно найтипрефикс vinit слова v со свойством Rsat(1, *) С Rirait.virait и длиной не меньше(kn - 1)рз.2) Компоненты Rsat и Tsat построены для определения выполнимости -. В случаеGOODCASE для автомата A найдется слово usat длины n + 1, такое, что ровно nсостояний заняты в строке Rowacc(1, *) после применения этого слова к первойстроке Rsat, полученной после шага 1. В случае BADCASE для автомата Bдокажем, что в Rowacc(1, *) занято более n состояний после применения любогослова длины n +1 к первой строке Rsat, полученной после шага 1.3) Компоненты R f i x и Racc требуются для подсчета числа занятых состоянийв строке Rowacc(1, *) после предыдущего шага. Компонента R f i x нужна для«фиксации» (наложения ограничений на структуру) слова, используемого наэтом шаге для BADCASE.4) Компонента Qspec играет специальную роль; в частности, с её помощью прове-ряется, что после предыдущего шага нет занятых состояний в Q \ Qspec. Крометого, компонента Qspec помогает сделать граф сильносвязным.Определим формально множества состояний компонент автомата A:Rinit = { R i n i t ( i r , i c , i f ) : ir G [1,kn],ic G [-2 , m ] , f G [0,рз - 1]},где ir -номер строки Rinit; ic - номер столбца Rinit, при ic > 0 соответствующий но-меру дизъюнкта; if - номер элемента в Ri n i t(ir, ic, *).Следующие компоненты:Tsat {Tsat( i r , iv , ivv) ir G [2,n + 1],iv G [1, ir] , ivv G { 0 , 1 } },где ir - номер строки Tsat, при ir ^ n соответствующий номеру переменной плюс 1, аiv (при iv = n + 1) и ivv соответствуют номеру переменной и ее значению.Компонента Rsat состоит из подкомпонент R+a и R_at, гдеR-at = {Rsat (iv ,ic) : iv G [1,П + 1], ic G [ - 2 , 0]},R+at = {Rsat(iv,ic) : iv G [1, n], ic G [1,m],iv = max(i G [1,n] : Xi G qc или - X i G qc ) }.В этом определении iv - это номер строки Rsat, при iv = n +1 соответствующий номерупеременной, а ic - номер столбца Rsat, при ic > 0 соответствующий номеру дизъюнкта.Пусть h = (4n + 13)(n - 2) + 20, тогда R f i x = {R/i x ( i r ) : ir G [1, h]}, т. е. компонен-та R f i x состоит из одного столбца высоты h.Компонента Racc состоит из n - 1 строки Rowacc(i, *), и любой путь в Racc междудвумя последовательными строками будет проходить через подкомпоненту Di . Фор-мально:RoWacc = {RoWacc(iv, ic) : iv G [1, n - 1], ic G [4, 4n + 2]},Viv G [1, n - 1] Div = {Div (ie) : ie G [1, 35]},где iv -номер строки Rowacc, ic - номер столбца Rowacc и ie - номер элемента в Di.Для i G [1, n - 2] положим Di(35) = Rowacc(i + 1, 4),Racc = Rowacc U Di U D2 U . . . U D „ _ i ,hs = padd и определим Qspec следующим образом: Qspec = {z} U Ro U C0 U C1 U C2,где Ci = {Ci(i r) : ir G [1, hs]} для i G {0,1, 2} это столбец Qspec из hs элементови R0 = {R0(ic ) : ic G [-2,m]} - строка Qspec из m + 3 элементов. Для i из {0,1, 2}обозначим si = Ci (1).При определении переходов в автомате A будем использовать метки LDXY, гдеX - метка компоненты, а Y - порядковый номер метки. Каждое такое определениепереходов в автомате A однозначно задает определение дуг графа С(^), которое будемобозначать, заменяя первую букву L на E (например, LDinit1 и EDinit1). Будем гово-рить, что слово w перемещает/отображает состояние q в состояние q', если q.w = q',и слово w «сжимает», или «синхронизирует» множество S, если |S.w| = 1. Терми-ны направления перемещения следует понимать в соответствии с рис. 2, и они будутиспользоваться только для визуального представления.Переходы из состояний Rinit в автомате определены следующим образом: буква aперемещает состояния Rinit внутри столбцов по «спирали» относительно номера стро-ки и третьего индекса. Формально:R i n i t ( i r , / ) - aRinit (ir, ic, (i/ + 1) mod рз), если if + 1 < рз, TAnit1Rinit(ir + 1, ic, (i/ + 1) mod рз), если i/ + 1 = рз и ir < kn, LAnit2. Rinit(1,ic, ( i / + 1) mod рз), если i/ + 1 = рз и ir = kn. LAnit3Буква b отображает состояния последней строки Rinit в первую строку Rsat (т. е.Rinit(kn, *, *).b С Rsat(1, *)). Более того, состояния нулевого столбца последней стро-ки компоненты Rinit отображаются на первую строку Rsat (т.е. Rinit(kn, 0, *).b == Rsat(1, *)). Другие строки перемещаются в первую строку Rinit по этой букве:Rinit ( i r , i c , i / ) . bRinit(1, ic, (i/ + 1) mod рз), если ir < kn,Rsat(1, ic), если ir = kn, ic = 0,Rsat(1, ((i/ + 1) mod р:) - 1),если ir kn, icБуква c перемещает все состояния Rinit вверх, в первую строку Rinit:Rinit ( i r , i c , i / ) . c = Rinit ( 1 , i c , ( i / + 1) m o d р з ) .L D i n i t 4L D i n i t 5L D i n i t 6L D i n i t 7Следующее замечание следует из определений дуг в Rinit.Замечание 1.(A) Все буквы в автоматах A и B сохраняют «полное» множество остатков от де-ления третьего индекса в Rinit на рз, пока состояния находятся в Rinit, т. е. еслидля x Е Е, S С Rinit выполняется S.x С Rinit и Vi Е [0,рз - 1]3q Е SПRi n i t(*, *, i),то также выполняется Vi Е [0,рз - 1]3q Е S.x П Rinit(*, *, i).(B) 7mage(Rinit(1, *, 0 ) , р ^ ) С Rinit; другими словами, кратчайший путь, ведущийиз Rinit(1, *, 0) вне Rinit, имеет длину больше = р з ( ^ - 1).Рассмотрим теперь компоненты Rsat и Tsat, которые «кодируют» -. Заметим, чтообраз множества { - 2, -1, 0} под действием функции 1,x = c, L D s p e c 2z, если q = R0(1) и ic > 1,x = c, L D s p e c 3s0, если q = z и x = c, L D s p e c 4Cj(ir + 1), если q = Ci(ir), ir < L D s p e c 5iR0 (m), если q = Ci(hs). L D s p e c 6Заметим, что граф G(^) теперь полностью определен, хотя раскраска A еще заданане до конца (не определены 6j(1),6j(2)).Для доказательства сильной связности графа рассмотрим рис. 4. Здесь верши-ны графа соответствуют подмножествам графа G(^), а переход из подмножества S1в подмножество S2, помеченный некоторым числом k (если не указано, то предпо-лагается 1) и, возможно, некоторым условием (в круглых скобках) на индексы вер-шин множеств S1,S2, соответствует тому, что Image (S1, k) D S2 и из любой верши-ны множества S1 можно перейти в вершину из S2, где множества S1 и S2 полученыиз S1 и S2 соответственно наложением указанного на переходе условия (если мно-жество содержит индекс, на который накладывается условие). Например, переход изRs«t(*,ic) в множество Tsat, помеченный числом n +1 и условием ic > 0, означает,что Image(R+t ,n + 1) D Tsat и из любой вершины из R+t можно перейти в некото-рое состояние Tsat. Достижимость Tsat для этого перехода следует из условий (C1)и EDsat4, 5,9, а существование перехода из R+,t в Tsat следует из определения R+tи EDsat4, 5. Остальные переходы в графе подмножеств следуют непосредственно изопределений переходов графа С(-0).Заметим также, что любая вершина q графа G(^) принадлежит, по крайней ме-ре, одному подмножеству S на рис.4, причем множество Image({q}, 1) содержитсяв объединении множеств, в которые ведут переходы из множества S, и самого мно-жества S (кроме вершин, окруженных пунктирной линией - s0,si,s2). Таким обра-зом, по рисунку для любой вершины можно найти множество, в котором содержитсяPreimage({q}, 1).Сильная связность графа G(^) следует из того, что граф подмножеств на рис. 4является сильносвязным, так как из z есть путь в любую вершину графа подмножестви из любой вершины графа подмножеств есть путь в z.Рис. 4. Граф подмножеств С(ф)В следующем замечании показаны основные свойства Qspec.Замечание 6.(A) Для i . {0,1, 2} любой путь, начинающийся вне Ci и проходящий через Cj,содержит Sj (так как только переходы из EDspec4 оканчиваются в Cj(j) дляj > 1).(B) Для r . [0, hs - 1] и i . {0,1, 2} любой путь длины r из sj оканчивается в Cj(r + 1)и любой путь длины r, оканчивающийся в Cj (r + 1), начинается в sj (по (A) иE D s p e c 4 ) .(C.1) Preimage(Ro, hs) = Qspec \ { z }.(C.2) Preimage(Rjnjt(*, i, *), 1) С R n i t ( * , i, *) U R s a t ( * , i) U Ro для i = 0.(C.3) Preimage(Rjr a j t ( * , 0, * ) , 1) С R jmt ( * , 0, *) U Rsat(*, 0) U Ro U R ^ .( C . 4 ) P r e i m a g e ( R s a t ( * , i ) , 1 ) С R j m t ( * , { 0 , i } , * ) U R s a t ( * , { 0 , i } ) .(D) Preimage(Rjrajt(*, i, * ) , h s ) С Rinit(*, { 0 , i } , *) U Rsat(*, { 0 , i } ) U R/ix U Qspec дляi . [-2, m] по пунктам (C.1 ... 4).(E.1) Image(Rjnit(*, ic, *), 1) С Rinit(*, ic, *) U Rsat(*, ic) для ic > 0 в силу ЕДы*5.(E.2) Image (Rsat (*,ic), 1) С Rinit (*,ic, *) U Rsat(*,ic) U Tsat для ic > 0 в силуEDsat1, 4 . . . 7.(E.3) Image (Tsat, 1) С Tsat U Racc U {So, Si, S2} в силу EDsat8, 9, 10.(E.4) Image (Racc, 1) С Racc U {So, Si, S2} в силу EDacc5, 6, 7.(E.5) Image({so, S1, S2}, hs) С Co U C1 U C2 в силу EDspec4.(F) Image(Rinit(*,ic, * ) , h s ) С Rinit(*,ic, *) U Rsat(*,ic) U Tsat U Racc U Co U Ci U C2 дляic > 0 в силу (E.1... 5).Доказательство оценок для длин синхронизирующих слов u и v автоматов A и Bсоответственно проведем следующим образом: для GOODCASE пошагово построимсинхронизирующее слово. При этом на каждом шаге будем отслеживать образ множе-ства состояний автомата после применения уже построенного слова. Для BADCASEтакже пошагово докажем, что синхронизирующее слово v должно перемещать состоя-ния аналогично тому, как перемещаются состояния в GOODCASE под действием сло-ва u, либо можно выбрать несколько состояний в образе соответствующего префикса v,для которых значение LRadius по следующей лемме будет достаточно большим дляполучения требуемой оценки длины оставшегося суффикса v (по п. 2 леммы 1).Лемма 3. Справедливы следующие неравенства для функции LRadius:(A) LRadiuS({qi, q2}) ^ Рз(кп - 1), где qi . {SO, Si, S2}, q2 = qi.(B) LRadius({qi,q2}) ^ Рз(кп- 1),где qi = Rnit(1,ici,i/i), ici = 0 , q2 . Rinit(*,ic2, * )UURsat(*, ic2) U Tsat U R/ix U Racc, 0 = ic2 = ici.(C) LRadius({qi,q2} ) ^ рз(кп- 1), где qi = Rinit(1,ici , i / i ) , ici = 0 , q2 . Rinit(*,ic2, * )UU Rsat ( *, ic2 ) U Tsat U R acc 0 < ic2.(D) LRadius({q/, q2,q3}) ^ Рз(кп - 1), где q/ = Rsat(1,ici ), q2 Rinit( ir2 , 0, i/2),q3 . Rinit(*,ic3, *) U Rsat(1,ic3), ir2 < kn, 0 < ic3 = ici и (i/2 ^ 3p2 + 1 илиir2 = 1).(E) LRadius({qi , q2}) ^ p3(kn - 1)

Ключевые слова

synchronizing automata, optimal coloring, road coloring problem, синхронизируемые автоматы, кратчайшее синхронизирующее слово, поиск оптимальной раскраски, проблема раскраски дорог

Авторы

ФИООрганизацияДополнительноE-mail
Берлинков Михаил ВладимировичУральский государственный университет, г. Екатеринбургаспирант кафедры алгебры и дискретной математикиberlm@mail.ru
Всего: 1

Ссылки

Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Eppstein D. Reset sequences for monotonic automata // SIAM J. Comput. 1990. V. 19. P. 500-510.
Berlinkov M. Approximating the Minimum Length of Synchronizing Words is Hard // LNCS. 2010. V. 6072. P. 37-47.
Adler R. L. and Weiss B. Similarity of automorphisms of the torus // Mem. Amer. Math. Soc. 1970. V. 98. P. 1-43.
Beal M. and Perrin D. A quadratic algorithm for road coloring // arXiv:0803.0726. 2008.
Volkov M. Synchronizing Automata and the Cerny conjecture // LNCS. 2008. V. 5196. P. 11-27.
Cerny J. Poznamka k homogennym eksperimentom s konecnymi automatami // Matematickofyzikalny Casopis Slovensk. Akad. Vied (in Slovak). 1964. V. 14. No.3. P.208-216.
Trahtman A. N. The Road Coloring Problem // arxiv:0709.0099. 2007.
Adler R. L., Weiss B., and Goodwyn L. W. Equivalents of topological Markov shifts // Isr. J. Math. 1977. No. 27. P. 49-63.
 О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | ПДМ. 2011. № 2(12).

О погрешности полиномиального вычисления оптимальной раскраски графа в синхронизируемый автомат | ПДМ. 2011. № 2(12).

Полнотекстовая версия