Оценки длины и вычислительной сложности синхронизации конечных автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Мартюгин, Павел Владимирович

• Мартюгин, Павел Владимирович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Мартюгин, Павел Владимирович

1 Введение

1.1 Определения и мотивация.

1.1.1 Детерминированные автоматы.

1.1.2 Частичные автоматы.

1.2 Постановка задач.

1.2.1 Общая постановка задач.

1.2.2 Классы автоматов и основные результаты.

1.2.3 Таблица результатов полученных ранее.

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

2 Детерминированные автоматы

2.1 Нижняя оценка для автоматов с нулем.

2.1.1 Пример для четных п.

2.1.2 Пример для нечетных п

2.1.3 Результаты компьютерных экспериментов.

2.2 Проверка автоматов на синхронизируемость.

2.3 Сложность поиска длин кратчайших синхронизирующих слов

2.3.1 Класс всех ДКА.

2.3.2 Автоматы с нулем, апериодические, ^-тривиальные и частично монотонные автоматы. Сжимаемость.

2.3.3 Коммутативные автоматы.

2.3.4 Автоматы с простыми идемпотентами

2.3.5 Монотонные п циклически монотонные автоматы

2.3.6 Автоматы, содержащие цикл по всем состояниям

3 Частичные автоматы

3.1 Нижние оценки длины бережно синхронизирующих слов

3.1.1 Пример для числа состояний кратного трем.

3.1.2 Пример для числа состояний равного степени тройки

3.1.3 Трехбуквенный алфавит.

3.1.4 Двухбуквенный алфавит.„.

3.2 Проверка на бережную синхронизируемость. Принадлежность к Р БРАСЕ.

3.2.1 Постановка задач. Общие факты.

3.2.2 Принадлежность к РБРАСЕ.

3.3 Проверка на бережную синхронизируемость. Р Б РЛС Е- т руд но сть

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

3.3.2 Построение множества состояний автомата.

3.3.3 Задание функции переходов.

3.3.4 Описание обнуления счетчика.

3.3.5 Описание шага синхронизации.

3.3.6 Случай истинной формулы F.

3.3.7 Случай ложной формулы F.

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

Введение диссертации (часть автореферата) на тему «Оценки длины и вычислительной сложности синхронизации конечных автоматов»

1.1 Определения и мотивация 1.1.1 Детерминированные автоматыДетерминирован1)шм конечным автоматом (ДКА) мы будем называть тройку = {О, Е, 8), где С) — конечное мноэюество состояний, Е — конечный алфавит и 5 — всюду определенная функция переходов, действующая из С} х Е в С}. Пусть Е* — множество всех слов над алфавитом Е.

ДКА = ((¿,£,6) называется синхронизируемым, если существует слово ги € Е*, под действием которого все состояния автомата отображаются в какое-то одно, или, говоря формально, найдется такое состояние (¡о € О, что для любого состояния q € <3, гч) = д0- Такое слово ги мы будем называть словом, синхронизирующим автомат в состояние доРис. 1: Автомат Черни для п—АНа Рис.1 приведен пример синхронизируемого автомата. Несложно проверить, что слово аЪ3аЬ3а синхронизирует изображенный автомат в состояние 2. Немного сложнее проверить, что слово аЪ3аЬ3а является кратчайшим среди всех слов, синхроиизирующих этот автомат.

Почему слова называются синхронизирующими? Для ответа на этот вопрос представим себе, что есть некоторое количество одинаково устроенных автоматов, работающих независимо. Пусть в какой-то момент времени каждый из автоматов находится в определенном состоянии, и эти состояния могут быть различными для разных автоматов. Если ко всем автоматам одновременно применить синхронизирующее слово, то они окажутся в одном и том же состоянии. Тем самым, их дальнейшая работа будет синхронизирована. Поэтому слова и называются синхронизирующими.

Для математиков понятие синхронизируемости автоматов само по себе является естественным и интересным, однако оно также находит свое применение в различных практических приложениях. Например, синхронизация*применяется при производстве некоторых механизмов для сортировки, обработки и установки деталей определенной конструкции. Рассмотрим простой пример. Пусть один из видов деталей, которые нужно обрабатывать, имеет форму, изображенную на Рис.2.

Рис. 2: ДетальПредположим, что такие детали попадают на конвейер, будучи ориентированными случайным образом, и для сборки должны быть ориентированы правильно. Предположим для простоты, что деталь может находиться только в одном из четырех положений (ориентации), изображенных на Рис.3.

Рис. 3: Возможные ориентации деталиДопустим, для правильной сборки деталь должна быть ориентирована выступом влево (вторая ориентация на Рис.3). Встает задача, как сконструировать устройство, ориентирующее детали правильно?Рассмотрим одно из возможных ориентирующих устройств. Пусть детали поступают на движущийся конвейер, на котором расположено несколько небольших неподвижных перегородок, которые деталь будет вынуждена преодолеть. Мы будем использовать перегородки двух типов: высокие и низкие. Высокая перегородка будет высокой настолько, чтобы деталь, преодолевающая эту перегородку, переворачивалась "на бок", то есть поворачивалась на 90 градусов по часовой стрелке. При преодолении маленькой перегородки, деталь будет переворачиваться, только в том случае, если она стоит выступом вниз (первая ориентация на Рис.3), в остальных случаях она будет проскакивать перегородку не перевернувшись.

Общая схема поведения детали в зависимости от ориентации и типа преодолеваемой перегородки изображена на Рис.4. Несложно заметить, что эта схема в точности реализует автомат, изображенный на Рис.1. Обозначим высокую перегородку через HIGH, низкую через low. Кратчайшему синхронизирующему слову ab3ab3a будет соответствовать следующая последовательность перегородок:1ош-НЮН-НЮН-Н1СН-1о\у-НЮН-НЮН-НЮН-1о\\'Пройдя через такую последовательность перегородок, деталь, находящаяся в начале конвейера в произвольной ориентации, в конце конвейера будет ориентирована правильно.

Существует также множество других применений синхронизирующих слов. Некоторые из них описаны в работах [32, 27].

Одним из первых понятие синхронизируемости рассматривал Черни в 1964 году, в работе [17]. Черни высказал гипотезу, что любой синхронизируемый ДКА с п состояниями может быть синхронизирован словом длины не превосходящей (п — I)2. За годы, прошедшие с тех пор, предпринималось множество попыток доказать или опровергнуть эту гипотезу, но ни одна из них не увенчалась успехом. Гипотеза доказана только для многочисленных частных случаев. Подробнее многие из этих частных случаев будут описаны в разделе 1.2.2. В общем случае получена только кубическая верхняя оценка " (см. [8]). Соответствующая нижняя оценка максимальной длины кратчайшего синхронизирующего слова получена Черни в [17].

Другой естественный вопрос состоит в том, как проверить заданный ДКА ¿г/ = Е, <)) на синхронизируемость, и как найти длину кратчайшего слова, синхронизирующего заданный автомат? Алгоритмическая разрешимость этих задач очевидна, однако встает вопрос об их сложности. Оказывается, что проверка заданного ДКА ¿г/ = (О, Е, 5) на синхронизируемость может быть осуществлена за время 0(|Е| • |(?|2) (см.[19]), то есть за полиномиальное время. Задача поиска длины кратчайшего синхронизирующего слова для заданного ДКА является ЫР-трудной и со-ЫР-трудной одновременно (см. [43]). Подробнее постановка алгоритмических задач связанных с ДКА будет описана в разделе 1.2.1.

1о\¥1о\\г 1о\уРис. 4: Действия перегородок1.1.2 Частичные автоматыНа практике автоматы со всюду определенной функцией переходов встречаются редко. Чаще всего возможна следующая ситуация: автомат находится в состоянии q, и если в этот момент применить некоторую букву а, то он сломается. Автомат при работе не должен ломаться, поэтом}'- можно считать, что в такой ситуации функция переходов по букве а не определена на состоянии q. и буква а к состоянию q применяться не может. Понятие таких автоматов может быть формализовано, и для таких автоматов можно рассматривать обобщение понятия синхронизации.

ЧКА «е/ = (Q, Е, <5) называется бережно синхронизируемым, если существует слово w & Е* такое, что величина d(Q, w) определена и го)| = 1. Такое слово w мы будем называть бережно синхронизирующим словом (б.с.с.) для автомата Заметим, что любой ДКА является ЧКА, и если слово бережно синхронизирует ДКА, то оно является синхронизирующим для него.

Пример бережно синхронизирующего автомата изображен на Рис.5. В этом автомате, буква а определена на всех состояниях, а буква Ъ не определена на состоянии 4. Несложно убедиться, что слово arbaba2 является бережно синхронизирующим для этого автомата. Это слово переводит любое состояние автомата в состояние 2, не ломая автомат.

Бережная синхронизация ЧКА может быть применена на практике также как и синхронизация ДКА. Пусть, как и в примере с ДКА, на некотором производстве используются детали определенного вида. Пусть деталь имеет вид, изображенный на Рис.6.

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

Рис. 7: Возможные ориентации деталиДля построения устройства, ориентирующего деталь, мы будем использовать конвейер, не котором расположено некоторое количество неподвижных перегородок. Двигаясь по конвейеру, детали будут вынуждены преодолеть эти перегородки. Мы будем использовать перегородки двух видов: высокие и низкие. Если деталь, преодолевая низкую перегородку, лежит на грани без выступа (положения 2 и 3 на рисунке), то она не переворачивается, а если лежит на грани с выступом (положения 1 и 4 на рисунке), то она переворачивается на 90 градусов по часовой стрелке. Преодолевая высокую перегородку, деталь переворачивается по часовой стрелке на 90 градусов всегда. Однако, если деталь лежит хрупкой частью вперед (положение 4 на рисунке), то высокая перегородка, ударив по детали, заденет хрупкую часть и сломает ее.

На производстве такая ситуация недопустима, поэтому деталь, находясь в положении 4, не должна встретить высокую перегородку.lowРис. 8: Действия перегородокАвтомат, описывающий поведение детали при преодолении перегородок, изображен на Рис.8. В этом автомате несложно узнать автомат с Рис.5. Если обозначить высокую перегородку через HIGH, а низкую через low, то бережно синхронизирующему слову a2baba2 будет соответствовать следующая последовательность перегородок:low-low-HIGH-low-HIGH-low—low.

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

Бережную синхронизацию ЧКА (как и синхронизацию ДКА) удобно себе представлять как передвижение фишек, стоящих на состояниях автомата. Пусть рассматривается бережно синхронизируемый ЧКА si = (Q, Е, 5), и пусть w — б.с.с. для я/. Представим себе, что автомат нарисован на листе бумаги, и в начальный момент времени на всех состояниях автомата стоит по фишке. Если на состоянии q е Q стоит фишка, то под действием буквы а эта фишка передвигается на состояние 8(q, а). Если несколько фишек оказываются на одном состоянии, то они склеиваются в одну. Если буква а € Е не определена на состоянии q € Q, и на состоянии q стоит фишка, то после действия буквы а фишка умирает. Б.с.с. w G Е* переводит фишки со всех состояний автомата на одно таким образом, что ни-одна из них не умирает, то есть "бережет" их. Это еще одно объяснение термина бережная синхронизация. Иногда в доказательствах мы для простоты будем оперировать с фишками, а иногда даже просто говорить, что состояние q\ передвигается в состояние q2, или что состояния q\ и qo склеиваются, имея в виду, что передвигаются или склеиваются, фишки, стоящие на этих состояниях.

Понятие бережной синхронизации было впервые сформулировано автором диссертации в [4]. Однако, задача оценки длины кратчайших бережно синхронизирующих слов рассматривалась в [25] в качестве вспомогательной задачи. В [25] были получены некоторые верхние и нижние оценки длины кратчайшего бережно синхронизирующего слова. Эти оценки, а также постам новка других задач, касающихся бережной синхронизируемости ЧКА, будут приведены в разделе 1.2.

1.2 Постановка задачВведем несколько обозначений. Через мы будем обозначать множество всех подмножеств множества Q. Через Е* мы будем обозначать свободный моноид над алфавитом Е. Через Л мы будем обозначать пустое слово. Пусть w — слово над алфавитом Е. Обозначим через |ги| длину слова w. Для г G 1. |ги| через w[i] обозначим г-ю букву слова w. Для i,jGl.\w\ через w[i,j] обозначим слово гф]ги[г-И]. w[j]. Нам также будет удобно положить w[i, i — 1] = Л.

1.2.1 Общая постановка задачВ работе будут рассматриваться различные классы автоматов (ДКА или ЧКА). Для каждого из рассматриваемых классов можно поставить естественные задачи, касающиеся проверки автоматов на синхронизируемость (бережную синхронизируемость) и оценки длин синхронизирующих (бережно синхронизирующих) слов. Для каждого из классов автоматов различные понятия, задачи и величины будут схожими, поэтому мы дадим несколько общих определений и обозначений, каждое из которых будет приобретать определенный смысл для конкретного класса автоматов. Каждый класс автоматов будет иметь свое обозначение. Например, класс монотонных ДКА будет обозначаться через топ (определение класса монотонных ДКА будет дано позже).

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

Введем соответствующие обозначения. Пусть class — некоторый класс ДКА или ЧКА. Обозначим через u)ciass(n) максимально возможную длину кратчайшего синхронизирующего слова для синхронизируемого автомата из класса class, множество состояний которого содержит п элементов. Величину Wdass(ji) мы будем называть длиной синхронизации класса class. Обозначим через <^ciass(n) максимально возможную длину кратчайшего синхронизирующего слова для /^-буквенного синхронизируемого автомата из класса class, множество состояний которого содержит п элементов. Например, для класса монотонных автоматов только что описанные величины будут обозначаться через ujmon{n) и и*1ст{п). Для классов ЧКА аналогичные обозначения будут рассматриваться применительно к бережной синхронизации.

Для всех классов, которые мы будем рассматривать, функции a;c/as,(n) и шciassiп) являются неубывающими по п и по к. То есть для всех к > 1, п > 1, выполняется ш%шв(п) < u%ass(n+1) и b)kdass(n) < < uiciass(n). Первоеиз неравенств обычно удается доказать, добавив одно состояние и аккуратно переопределив буквы, второе удается доказать добавив букву действующуютождественно. Всилу вышесказанного, верхние оценки обычно доказываются для величин о>dass(n), а нижние для величин uj^[ass(п) при к = 1,2 или 3. Оценки величин uj^ass(n) для других к получаются как следствия.

Другими важными задачами являются задачи проверки заданного автомата на синхронизируемость (бережную синхронизируемость) и задачи поиска длины кра тчайших синхронизирующих (бережно синхронизирующих) слов для заданного автомата. Нас будет интересовать алгоритмическая сложность этих задач. Мы будем рассматривать только задачи распознавания, т.е. задачи, ответами на которые могут быть только "да" и "нет". Если мы определим сложность таких задач, то сложность задач оптимизации также будет определена (в нашем случае задачи оптимизации это задачи поиска длины кратчайших синронизирующих слов для заданных автоматов различного вида). Пусть class —некоторый класс автоматов. Дадим формальное описание рассматриваемых задач.

Задача: SYN{class) (СИНХРОНИЗИРУЕМОСТЬ АВТОМАТОВ КЛАССА class)Дано: ДКА s/ = (Q,H,5) из класса class.

Вопрос: Существует ли слово, синхронизирующее автомат s/'?Например, для класса монотонных автоматов задача будет называться SYN(mon). Аналогичная задача определяется для класа всех ЧКА.

Задача: SYN{pfa) (БЕРЕЖНАЯ СИНХРОНИЗИРУЕМОСТЬ)Дано: ЧКА s/=(Q,E,5).

Вопрос: Существует ли слово, бережно синхронизирующее автомат sail'Задача: SYN{class, < L) (СИНХРОНИЗИРУЮЩЕЕ СЛОВО ДЛИНЫ НЕ ПРЕВОСХОДЯЩЕЙ L ДЛЯ АВТОМАТОВ КЛАССА class)Дано: ДКА s/ = (Q, Г, 6) из класса class и целое число L > 0.

Вопрос: Верно ли, что существует слово длины не превосходящей L, синхронизирующее автомат silНапример, для класса монотонных автоматов задача будет называться SYN(mon,<L).

Задача: SYN(pfa, < L) (БЕРЕЖНО СИНХРОНИЗИРУЮЩЕЕ СЛОВО ДЛИНЫ НЕ ПРЕВОСХОДЯЩЕЙ L)Дано: ЧКА si = (Q, и целое число L > 0.

Вопрос: Верно ли, что существует слово длины не превосходящей L, бережно синхронизирующее автомат silЗадача: SYN(class, = L) (КРАТЧАЙШЕЕ СИНХРОНИЗИРУЮЩЕЕ СЛОВО ДЛЯ АВТОМАТОВ КЛАССА class)Дано: ДКА srf = (Q, из класса class и целое число L > 0.

Вопрос: Верно ли, что кратчайшее слово, синхронизирующее автомат л/, имеет длину L ?Например, для класса монотонных автоматов задача будет называться SYN(rnon,=L).

Задача: SYN(pfa, = L) (КРАТЧАЙШЕЕ БЕРЕЖНО СИНХРОНИЗИРУЮЩЕЕ СЛОВО)Дано: ЧКА = (Q, Е, 5) и целое число L > 0.

Вопрос: Верно ли, что кратчайшее слово, бережно синхронизирующее автомат л/, имеет длину L?Не все ДКА являются синхронизируемыми, но для любого ДКА = (Q, Е. 5) существует некоторое число, называемое рангом автомата, равное min{|5(Q,it;)| : w £ Е*}. Слово w называется сжимающим автомат л/ до М состояний, если u>)| < М. Для сжимаемости ДКА Пеном в работе [34] была высказана гипотеза, обобщающая гипотезу Черни. Гипотеза утверждала, что любой автомат с п состояниями, сжимаемый до М состояний, может быть сжат до М состояний словом длины (п — М)2. Однако, эта гипотеза была опровергнута Кари в [28]. Был построен такой автомат с 6-ю состояниями, что кратчайшее слово, сжимающее этот автомат до 2 состояний, имеет длину 17 = (6 — 2)2 + 1. Других примеров, опровергающих данную гипотезу, пока не найдено.

Для сжимаемости ДКА естественно поставить задачи аналогичные задачам SYN:Задача: СО MP (class, М) (СЖИМАЕМОСТЬ АВТОМАТОВ КЛАССА class ДО М СОСТОЯНИЙ).

Дано: ДКА stf = (Q, E,S) из класса class, и целое число М < |Q|.

Вопрос: Существует ли слово w G £* такое, что |i(0. u>)| < MlАналогичным образом могут быть сформулированы задачи COMP(class, М, < L), COMР (class, M,=L).

Пусть Z — одна из выше перечисленных задач. Допустим, что на вход задачи могут подаваться не все автоматы, предусмотренные в задаче Z, а только те из них, которые имеют /с-буквенный алфавит. В этом случае перед названием задачи Z мы будем добавлять к-. Например:Задача: k-SYN(pfa) (А:-БЕРЕЖНАЯ СИНХРОНИЗИРУЕМОСТЬ)Дано: ЧКА л/ = (Q, Е, S), |Е| = к.

Вопрос: Существует ли слово, бережно синхронизирующее автомат silРассмотрение задач вида k-Z является естественным, так как многие автоматы, используемые на практике имеют заведомо ограниченный- алфавит. Очень часто используются 2-х или 3-х буквенные автоматы, поэтому случаям к = 2 и к = 3 мы будем уделять особое внимание.

1.2.2 Классы автоматов и основные результатыОпределим классы автоматов, которые мы будем рассматривать. Для каждого класса автоматов перечислим известные результаты, а также результаты, которые получены в данной диссертации. Для вычислительных задач (SYN и.т.п.), сложность которых будет упоминаться, мы будем полагать, что задан автомат s/ = (О, Е, S) из соответствующего класса, и \Q\ = п, |Е| = А;.

1. Класс всех детерминированных конечных автоматов {ДКА). Обозначение класса— dfa. Гипотеза Черни (см.[17]) предполагает, что u>dfa(n) = (n — I)2 для всех п > 1. Однако, на данный момент доказано лишь что LOdfa(n) < r2-=JÍ (см.[8]). В статье [17] был приведен пример такой бесконечной серии двухбуквенных автоматов с возрастающим количеством состояний, что кратчайшее синхронизирующее слово для каждого из этих автоматов имеет длину (п — I)2, где п — количество состояний. Пример такого автомата для п — 4 изображен на Рис.1. Общий вид автомата для произвольного п изображен на Рис.9. Таким образом, > (п — I)2.

Следовательно:ОП - I)2 < ш%а{п) < u>dfa{n) < ——.

Задача SYN(dfa) решается за полиномиальное время. Эпштейн в [19] описал алгоритм, который проверяет заданный ДКА на синхронизируемость и работает за время 0{n2k). Эпштейн в [19] и Саломаа в [41] показали, что задачи SYN(dfa, < L) и k-SYN(dfa, < L) для всех к > 2 являются NP-полными. Самотий в [43] установил, что задача SYN(dfa,=L) является одновременно NP-трудной и co-NP-трудной.

Мы докажем, что задачи k-SYN(dfa, —L) для всех к > 2 также являются одновременно NP-трудными и co-NP-трудными. Также мы покажем, что задачи SYN{dfa,—L) и k-SYN{dfa, =L) лежат в классе сложности Е^пЩ-Это будет означать, что для любого подкласса class класса всех ДКА задачи SYN(class, —L) и k-SYN(class, = L) для к > 1 лежат в классе сложности Еf ПЩ (раздел 2.3.1).

Кроме того, мы покажем что задачи COMP(dfa, М, < L) и k-COMP(dfa, М, <L) для к > 2 NP полны, а задачи COMP(df a, M, = L) и k-COMP(dfa,M, = L) для к > 2 лежат в классе П По, но являются NP-трудными и co-NP-трудными (раздел 2.3.2).

Слова, синхронизирующие ДКА, обладают очень удобным свойством.

Предложение 1.1. Пусть а/ = (Q,T,,5) —ДКА, и слово w £ Е* синхронизирует sä, тогда для любых слов и, v € Е* слово uwv также синхронизирует sä.

Доказательство. Q.u С Q, следовательно Q.uw С Q.w. С другой стороны, \Q.w\ = 1, следовательно \Q.uw\ = 1. Поэтому \Q.uwv\ < \Q.uw\ = 1. Следовательно, слово uwv синхронизирует автомат sä. Предложение доказано. □Слова, бережно синхронизирующие ЧКА, свойством аналогичным Предложению 1.1 не обладают.

2. Класс ДКА с нулем, обозначение — zero. Автомат sä = (Q, Е, 6) называется автоматом с нулем, если существует состояние q € Q такое, что для всех букв а € Е, 5(q,a) = q. Состояние q в этом случае называется нулем автомата sä. Несложно понять, что ДКА с нулем может быть синхронизирован только в нуль, и синхронизируемый ДКА не может иметь более одного нуля. Известно, что uzero(n) — (см. например [39]). Это значит,что гипотеза Черни верна для автоматов с нулем. Однако, для построения серии примеров, обеспечивающих длину максимальную кратчайшего синхронизирующего слова, требуются автоматы, в которых размер алфавита растет с увеличением количества состояний.

Мы докажем, что ш^его(п) >п2+6п-16 4построением соответствующейсерии двухбуквенньтх автоматов (раздел 2.1). Кроме того мы опишем алгоритм, решающий задачу SYN(zero) за время 0(пк) (раздел 2.2), и докажем, что для всех к > 2 задачи k-SYN(zero,< L), SYN(zero,< L) NP-полны, а задачи k-SYN(zero, — L) и SYN(zero,= L) NP-трудны и co-NP-трудны (раздел 2.3.2).

Мы докажем что для всех к >2 задачи к-БУ N (сус1е, <Ь) и БУ М(сус1е, < Ь) ИР-полны, а задачи к-БУ М(сус1е, = Ь) и БУЫ(сус1е,= Ь) NP-тpyдны и со-КР-трудны (раздел 2.3.6).

Для циклически монотонных автоматов гипотеза Черни верна, сОстоп (п) = ш1тоЛп) = (п — I)2 (см. [19]), т.е. нижняя оценка также совпадает с оценкой для произвольных ДКА. В [19] также доказано, что в отличие от произвольных ДКА, кратчайшее синхронизирующее слово для заданного циклически монотонного автомата з/ = (<3, д) может быть найдено за время 0(п2к). Следовательно, любая из задач БУМ (стоп), БУ N (стоп, < Ь) и БУМ (стоп, = V), а также соответствующие /г-задач и могут быть решены за время 0(п?к), то есть за полиномиальное время.

5. Класс монотонных ДКА, обзначение — топ. Автомат «с/ = ((¿,11,8) называется монотонным, если на множестве (3 можно ввести линейный порядок < такой, что для любых состояний < и любой буквы а, выполняется с)(д,а) < д(с/. а). Для монотонных автоматов шП 10П(п) = ш]поп(п) = п — 1 (см.[11]), то есть гипотеза Черни для них верна.

Любой монотонный автомат является циклически монотонным. Поэтому, любая из задач БУМ(топ), БУИ (топ, < Ь) и БУ М(топ, = Ь), а также соответствующие /с-задачи могут быть решены за время 0(п2к). Мы докажем, что задача SYN(mon) может быть решена за время 0(пк) (раздел 2.2).

Однако, можно сформулировать достаточно естественные задачи, которые будут NP-полными для монотонных и циклически монотонных автоматов. Имеются в виду задачи СОМР(топ, М, < L), СОМР(стоп, М, < L), СОМР(топ, Af, = L) и СОМР{стоп, М, = L). Мы покажем, что первые две задачи NP-полны, а последние две являются одновременно NP-трудньши и co-NP-трудными. Такую же сложность будут иметь соответствующие к-задачи для к > 2 (раздел 2.3.5).

6. Класс апериодических или Ж-тривиальных ДКА, обозначение — aper. ДКА л/ — (Q,S,S) называется апериодическим, если его моноид переходов не содержит не одноэлементных подгрупп, или что то же самое, в моноиде переходов все ^-классы тривиальны. В [46] было доказано, что шарег(п) < причем для сильносвязных синхронизируемых апериодических автоматов длина кратчайшего синхронизирующего слова не превосходит. Это означает, что гипотеза Черни верна для апериодических автоматов. С другой стороны в [13] было доказано, что ^рег(п) > п— 1+ [-^J.

Мы докажем, что для всех к >2 задачи k-SYN(aper, < L), SYN(aper, < L) NP-полны, а задачи k-SYN(aper,=L) и SYN(aper, — L) NP-трудны и co-NP-трудны (раздел 2.3.2).

7. Класс Qs-тривиальных ДКА, обозначение — dtr. ДКА s/ = (Q, Е, S) называется ^-тривиальным, если в его моноиде переходов все ^-классы содержат по одному элементу.

Несложно показать, что uJdtr(п) = Lo\tT{n) — п — 1. Мы докажем что для всех к > 2 задачи k-SY N (dtr, < L), SYN(dtr,<L) NP-полны, а задачи к-SYN(dtr, = L) и SYN(dtr, = L) NP-трудны и co-NP-трудны (раздел 2.3.2).

Тем самым мы покажем, что даже для столь узкого класса автоматов задачи поиска длин кратчайших синхронизирующих слов могут оказаться сложными. Кроме того, мы опишем алгоритм, решающий задачу SYN(dtr) за время 0{пк) (раздел 2.2).

8. Класс частично монотонных ДКА, обозначение — ртоп. ЧКА з/ = (Q, Е, 5) называется монотонным, если на множестве его состояний можно ввести линейный порядок < такой, что для любых q,p G Q таких, что р < q, и для любой буквы а € Е, определенной на состояниях р и q, выполняется р.а < q.a. Любой ЧКА можно превратить в ДКА, добавив к нему состояние err, и положив q.a — err в случаях, если величина q.a не определена в исходном ЧКА. ДКА, которые таким образом можно получить из монотонных ЧКА, называются частично монотонными.

В [13] доказано, что oj^nwn > п — 1 + L^^J • Класс частично монотонных автоматов является подклассом класса апериодических автоматов с нулем, поэтому из [46] следует, что LOpmon < . Следовательно, гипотеза Чернидля частично монотонных автоматов также верна.

Мы опишем алгоритм, решающий задачу SYN(pmon) за время 0{пк) (раздел 2.2) и докажем, что для всех к > 2 задачи k-SYN(pmon,< L), SYN(pmon,<L) NP-полны, а задачи k-SYN(pmon,=L) и SYN(pmon,=L) NP-трудны и co-NP-трудны (раздел 2.3.2).

9. Класс комльутативных ДКА, обозначение — сот. ДКА si = (Q, Е, 5) называется комлгутативным, если для любого состояния q G Q и любых букв а, Ь € Е выполняется равенство 8(q,ab) = 6(q,ba). В [39] было доказано, что шсот(гг) = ш1от(п) = п — 1, то есть и для коммутативных автоматов выполняется гипотеза Черни.

Мы докажем, что для любого фиксированного k > 1 задачи k-SYN(com, < L) и k-SYN(com, = L) решаются за полиномиальное время (0(пк Inп)), в то время как задача SYN(com, < L) — NP-полна, а задача SYN(com, = L) — NP-трудна и co-NP-трудна (раздел 2.3.3). Кроме того, мы приведем алгоритм, решающий задачу SYN(com) за время 0(кп In п) (раздел 2.2).

Мы докажем, что задачи 2-БУН^с1,<Ь) и 2-ЗУN(31(1, = Ь) решаются за полиномиальное время (0(п)), в то время как задача ЗУ1У(згс1, <Ь) ЛТР-полна, а задача БУМ^ъй, —V) МР-трудна и со-КР-трудпа (раздел 2.3.4).

Кроме того, мы докажем что (п) для всех к >2 представляет из себя функцию, растущую быстрее любого полинома от п (разделы 3.1.3 и 3.1.4).

Задача проверки заданного ЧКА на бережную синхронизируемость, оказывается значительно сложнее задачи проверки ДКА на синхронизируемость. Мы докажем, что задачи 5УЯ(р/а), SYN(pfa),< Ь и БУМ{р/а. = Ь). а также аналогичные /с-задачи для к > 2 являются РБРАСЕ-полными (в разделе 3.2 доказывается принадлежность задач к РБРАСЕ, в разделе 3.3 доказывается их РБРАСЕ-трудность). Это самый существенный результат диссертации.

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

Часть клеток таблицы являются заполненными только потому, что некоторые задачи решены для класса всех ДКА, и как следствие такие же значения получились и для частных случаев ДКА, хотя конкретно решением задач для частных случаев никто не занимался. Например, сложность задач SYN для частных случаев ДКА заполнена равной п2к только потому, что задача SYN может быть решена за время 0(п2к) для произвольного заданного ДКА. Некоторые из уже заполненных клеток по результатам данной работы изменят свои значения. Кроме того, будет заполнено большинство клеток, пустых на данный момент.

1.3 Апробация результатовОсновные результаты диссертации опубликованы в [1]-[6].

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

Основные результаты диссертации докладывались на:• Международной конференции по теоретическим компьютерным наукам, CSR 2006 WOWA (Санкт-Петербург, 2006)• Международной конференции по языкам и автоматам, LATA 2007 (Тар-рагона, Испания, 2007)• Международной конференции по языкам и автоматам, AFL 2008 (Ба-латонфюред, Венгрия, 2008)• 39-й региональной молодежной конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2008)• Заседаниях семинара "Алгебраические системы" (УрГУ).

Автор выражает глубокую благодарность своему научному руководителю Ананичеву Д.С. и профессору Волкову М.В. за помощь в подготовке текстов и внимание к работе.

2 Детерминированные автоматыВ статье [17] Черни высказал гипотезу, что любой синхронизируемый ДКА с п состояниями может быть синхронизирован словом длины (п — I)2. В случае выполнения этой гипотезы, получается Udfa(n) = — l)2. Гипотеза Черни была высказана на основе серии примеров ДКА, в которой для любого целого числа п > 1 присутствует двухбуквенный автомат с п состояниями, длина кратчайшего синхронизирующего слова для которого равна (n — I)2. Тем самым доказано, что > (п — I)2.

Автомат Черни изображен на Рис.9. Несложно проверить, что слово а(Ьп1а)п2 синхронизирует автомат sy'cer. Докажем, что это слово является кратчайшим среди синхронизирующих автомат Доказательство взято из [17].

Е £\{аьа2} Е\{а2,а3} £\{аз,а4} Е\{а^.2>«„!> Е\{а№1}Рис. 10: Автомат с нулем, обладающий кратчайшим синхронизирующим слоСущественной особенностью примера на Рис.10 (на котором фактически изображена целая серия автоматов для разных п) является тот факт, что размер алфавита в автомате растет с увеличением количества состояний. В то время, как в любом автомате из классической серии примеров, построенной Черни [17], алфавит не зависит от количества состояний и всегда содержит две буквы. Тем самым обеспечивается оценка и)^а(п) > (п — I)2. Для автоматов с нулем также можно поставить задачу: насколько длинным может быть кратчайшее синхронизирующее слово в двухбуквенном автомате с п состояниями. В наших обозначениях эта задача является задачей оценкивом длинывеличины о4го(д). Во всех примерах известных ранее длина кратчайшего синхронизирующего слова линейно зависела от п. (см. например [13]).

771+1, если г = 2т -2,, т + 2, если г = 2т -1.

Автомат £/гего(2т) изображен на Рис. 11. Состояние 0 является нулем в автомате ^его(2т.).

Для любого подмножества в С и любого слова ю € {а, 6}* обозначим:8{8,у,1) = {де<2\6(д,'ш)еЗ}. Лемма 2.1. ДКА £/гего(2т) может быть синхронизирован словом длинып2+6п-16 4Доказательство. Рассмотрим словоV = ат1Ьат1 аЪа'п1 (а2ЬаТп^1)1Докажем, что слово v синхронизирует автомат s¿/zero(2m).

Обозначим множество Q через S-i, и для всех г = 1,.m обозначим множество <5(S;i,-Uj) через S¿.

Вычислим длину слова V. Имеем:|и0| = т - 1, \иг\=т, \у2\ = т + 1, |г/3| = |г>4| =. = |ит| =т + 2.

Таким образом, |г»| = "2+64"16. Лемма доказана. □Теперь наша цель — доказать, что слово v действительно является кратчайшим синхронизирующим словом для автомата.сСего(2гп). Пусть w — произвольное кратчайшее синхронизирующее слово для автомата &?zero(2т). Положим Ql = ¿(Q, Ц1,г']). Заметим, что Q0 = Q, Q\w\ = {0}.

Лемма 2.2. Если р — номер первого вхождения буквы Ъ в слово w, то для всех i=p,.,\w\, \Qi Г) {1,., т — 1}] < 1.

Доказательство. Воспользуемся индукцией по г. Заметим, что S(Q,b) = {0,m — 1,т,., 2т — 1}. Поэтому, Qp П {1,., т — 1} С {т — 1}.

Пусть \Qi П {1,., т — 1}| < 1. Множество Qi+i может быть равным или S(Qi, а) или S(Oi} b). Ни одно из состояний, содержащихся во множестве Q\{1,., m —1}, под действием буквы а не отображается внутрь множества {1,., т — 1}. Следовательно,|<Щ,а)П{1,.,т-1}| < \Qi П {1,., m — 1}| < 1.

Кроме того, 5(Q, b) П (1,., т — 1} = {т — 1}. Поэтому, мы также получаем\ö(Qi,b) П {1,. — 1}[ < 1.

Лемма доказана. □Лемма 2.3. w[ 1, т - 1] = а™"1.

Доказательство. Рассмотрим число ко такое, что |11 > т + 1,I^a-oI <т + 1.

Для начала мы покажем, что буква b не содержится в слове ко]. Предположим от противного, tito w\p] является первым вхождением буквы Ъ в слово w[l,k0]. Из того, что 5({т,., 2т — 1},а) = {т,. 2т — 1}, следует{т,. 2т — 1} СОткуда, учитывая, что |(Qp-i| > т + 1, получаем <3P-i П {1,., т — 1} ф 0. Следовательно, Qp = 5(Qpi, b) = {0, т — 1, т,., 2т — 1}.

Таким образом, слово w[k0 — т + 1, |ш|] синхронизирует автомат sä?zero(2га). Мы получили противоречие с минимальностью | ш \.

Заметим, что число А:0 имеет то же значение, что в доказательстве Леммы 2.3. Обозначим множество Q^ через Sj и заметим, что Sm = {0}.

Лемма 2.4. Для любого j £ {0,., тп}, Sj С {0, т,., 2т — 1} и vu[kj] - а.

3, если т £ Sj, га + 1 ^ Sj.

Лемма 2.6. Если х,у € {0,2,3}, то d(x, у) > (m + 2) + (х — у).

Если = 2, тогда то ф Sj-l, и П {1,.,то} = 0. Так каккаждый элемент из Р4 имеет непустое пересечение с {1,., то}, имеем Ь > 5. Следовательно, <¿(2,0) = Ь + (то — 1) > то + 4.

Если p(Sj-■l) = 2, то т ф. 1, и П {1,. то} = 0. Все множества из и Рг имеют непустое пересечение с множеством {1,., т}. Получаем I = р — > 3. Это значит, что (1(2,2) = £ + (то — 1) > т + 2.

Кроме того, множество не может быть получено из Sj применением слова длины меньшей чем Следовательно, — к^ > d(xJ,Xj+l).

Напомним, что w — кратчайшее синхронизирующее слово для автомата <i^ero(2m). Из того, что \Sm\ = 1, следует \w\ = кт. Оценим длину слова w.

Таким образом, слово v = am lbam labam1(a2baml)m2. имеющее длину n +6n-i6 ^ на самом деле является кратчайшим синхронизирующим словом для автомата £/zero(2m). Тем самым, Теорема 2.1 доказана для четных п > 8.

Следующее слово длины 71 +64"15- синхронизирует автомат ^его(2т +1):v = aTn1bam abam (а Ьат )1\т—1Рис. 12: Автомат ¿г?гего(2т + 1)Повторив рассуждения для автомата £/гего(2т), можно доказать, что слово V является кратчайшим синхронизирующим для автомата £/гего(2т + 1). Остается лишь заметить, чтоп2 + 6п - 15п2 + 6п — 16для всех нечетных п. Теорема 2.1 доказана.

2.1.3 Результаты компьютерных экспериментовТеорема 2.1 применима только для автоматов имеющих не менее 8 состояний, поэтому был проведен полный компьютерный перебор всех двух-буквенных автоматов с нулем, число состояний в которых не превосходит 7. Результаты приведены в Таблице 2.

Этот факт не следует из Теоремы 2.1, потому что формула + 6п—16дает в результате 14 для п = 6 и 19 для п = 7, в то время как величины, приведенные в таблице 2, составляют соответственно 13 и 18.

Это означает, что нижняя оценка величины а>2его(п) может быть увели-чина, по крайней мере для автоматов с 10 состояниями. Полный перебор всех двухбуквенных автоматов с нулем, содержащих 8, 9, 11 и 12 состояний, не дал других примеров автоматов с длинной кратчайшего синхронизирующего слова, превышающей оценку из Теоремы 2.1. Однако, были найденные другие автоматы с длиной слова, совпадающей с оценкой из Теоремы 2.1.

2.2 Проверка автоматов на синхронизируемостьВ силу того, что модель вычислений, использующая память произвольного доступа (RAM), полиномиально эквивалентна машине Тьюринга (см.[22]), мы будем использовать для вычислений обычный компьютер. Для ДКА проверка на синхронизируемость не является сложной и может быть произведена за полиномиальное время. А именно, заданный ДКА «с/ = (Q, Е, 5) может быть проверен на синхронизируемость за время 0(|Q|2|£|). Более того, за время 0(]Q|2|E] + |Q|3) может быть найдено некоторое (не обязательно кратчайшее) слово, синхронизирующее автомат srf. Найденное слово будет иметь длину, порядка не большего чем 0(|Q|3) (все результаты см.[19], [42]). Таким образом, можно сформулировать следующее предложение.

Предложение 2.1. Пусть class — некоторый подкласс ДКА, задачи SYN(class) и k-SYN(class) для k > 1 могут быть решены за врелы 0(п2к).

Доказательство. Проверка на синхронизируемость осуществляется за время 0(п2к) для любого автомата, а, следовательно, и для автоматов из класса class. Предложение доказано. □Для некоторых классов автоматов существуют более быстрые алгоритмы проверки на синхронизируемость. Описанию таких алгоритмов и посвящен этот раздел.

Напомним, что zero — обозначение класса всех ДКА с нулем. Опишем быстрый алгоритм решения задачи SYN(zero).

Предложение 2.2. Задача SYN(zero) может быть решена за время 0(пк), где к — размер алфавита, п — количество состояний автомата.

Доказательство. Построим алгоритм поиска синхронизирующего слова для заданного автомата ¿г/. Пусть до — нуль в автомате «с/. Осуществим поиск в ширину из состояния до по автомату ¿г/, двигаясь по стрелкам в обратном направлении. Если после завершения поиска некоторое состояние не было посещено, то из этого состояния нельзя добраться до до, и автомат не будет синхронизируемым. Если при обходе мы посетили все состояния автомата, то автомат является синхронизируемым. Во время поиска в автомате каждая стрелка не может быть просмотрена более одного раза, поэтому сложность алгоритма — 0(пк) (автомат содержит всего пк стрелок).

Докажем, что алгоритм работает правильно. Для этого мы докажем, что если все состояния автомата были посещены, то можно построить синхронизирующее слово. Параллельно мы опишем алгоритм поиска некоторого синхронизирующего слова для автомата с нулем. Каждый раз при посещении поиском состояния автомата мы будем сохранять ссылку на состояние, непосредственно из которого мы пришли. Таким образом, при посещении любогосостояния можно будет восстановить путь из него до qo. Синхронизирующее слово может быть построено следующим образом: находим состояние gi, из которого достижимо состояние qo- Пусть w(qi, qQ) — путь из qi в q0. Применяем слово w(qi,q0) к множеству Q, получаем множество Состояние qi под действием слова w(qi,q0) переходит в состояние q0, которое в свою очередь, может перейти только само в себя. Во множестве Qi находим состояние qi и находим путь w(q?, q0) от него до состояния q0. Применяем w(q2, qo) к множеству Qi, получаем множество Q2 и т.д. Повторяем до тех пор пока не получим множество Qs = {<?о}- При поиске в ширину по автомату из состояния qo мы достигли всех вершин, поэтому на г-м шаге очередная вершина ^ всегда найдется, и по ней построится очередное слово w(qi, g0) - В качестве синхронизирующего слова можно будет взять слово w(qi,qo)w(q2, qo) ■ ■ - w{qs- qo) ■ Под действием него все состояния перейдут в qo. Откуда можно сделать вывод, что вышеописанный алгоритм проверки на синхронизируемость работает правильно. Предложение доказано. □Из доказательства предложения понятен также и алгоритм поиска некоторого синхронизирующего слова для автоматов с нулем. Несложно показать, что полученное при помощи этого алгоритма слово будет иметь длину не больше чем п(п — 1)/2, что совпадает с оценкой полученной в [39]. Такой алгоритм поиска синхронизирующего слова имеет сложность 0(пк+п3). Слово найденное алгоритмом может не являться кратчайшим синхронизирующим для автомата s?J.

Напомним, что dtr — обозначение класса всех ^-тривиальных ДКА, а ртоп — обозначение класса всех частично-монотонных ДКА.

Предложение 2.3. Задачи SYN(dtr) и SYN(pmon) могут быть решены за время 0(пк), где к — размер алфавита, п — количество состояний автомата.

В любом частично монотонном автомате есть состояние err, которое является нулем. Поэтому, любой частично монотонный автомат также является автоматом с нулем и по Предложению 2.2 может быть проверен на синхронизируемость за время 0(пк). Предложение доказано. □Аналогичное предложение можно доказать для класса монотонных автоматов автоматов (обозначение класса монотонных ДКА — топ).

Предложение 2.4. Задача БУИ (топ) моэ/сет быть решена за время 0(пк), где к — размер алфавита, п — количество состояний автомата.

Доказательство. Автомат — монотонный, поэтому на множестве его состояний может быть введен линейный порядок <, сохраняемый действием букв. Пусть О = {1,.,гг} и 1 < 2 <. < п. Из монотонности автомата я/ следует, что для любого слова ги £ Е*, 1.гу < 2.к; <. < п.ии. Следовательно, если для некоторого слова го выполняется 1.ги = п.ги, то слово го — синхронизирующее. В то же время для любого синхронизирующего слова ги выполняется 1.ги = гг.ги.

Напомним, что сот — обозначение класса всех коммутативных ДКА. Для решения задачи SYN(com) также существует алгоритм, работающий быстрее чем за время 0(кп2).

Предложение 2.5. Задача SYN(com) может быть решена за время 0(кп In п), где к — размер алфавита, п — количество состояний автомата.

Доказательство. Пусть Е = {gi,., ak}. Любой синхронизируемый коммутативный ДКА с п состояниями может быть синхронизирован словом длины п — 1 (см.[39]). Поэтому, существует слово, синхронизирующее автомат.й/, содержащее не более чем гг.—1 букву ai, не более чем п — 1 букву а^ и т.д. Если добавить к любому синхронизирующему слову в конец еще одну букву, то оно не перестанет быть синхронизируемым (см. Предложение 1.1). В слове синхронизирующем коммутативный автомат буквы можно переставлять в любом порядке, и действие слова при этом не изменится. Поэтому, сначала можно поставить все буквы а\, затем все буквы ао и т.д. Таким образом, слово w = öj'-1^"1 • • • all будет синхронизировать любой синхронизируемый коммутативный автомат с п состояниями. Это означает, что если \Q.w\ = 1, то автомат является синхронизируемым; а иначе — нет.

Вычислить величину Q.w можно за время o{kn 1п п), используя идею быстрого возведения в степень. Если известно преобразование задаваемое некоторым словом и, то для любого множества S С Q, множество S.u может быть вычислено за время 0(п). Пусть а £ Е. Преобразование, задает - ^ваемое словом а может быть вычислено как возведение преобразования а2™-1 в квадрат. Это можно сделать за время 0(п). Пусть (с]С2. ct) — двоичная запись числа п — 1. Величина t растет с ростом п как Inn. Все преобразования а, а2,., а2', вместе взятые, могут быть вычислены за время O(nlnn): сначала а, по нему а2, по нему о4 и.т.д. Преобразование а"-1 может быть вычислено как произведение преобразований вида а2% по всем г £ {1,. t} таким, что с* = 1. Это можно сделать за время 0(п Inn). Следовательно, если мы уже знаем множество Q.a'l'^ao"1. a"Zi то множество Q.a\xaо-1. может быть вычислено за время 0(п\пп). Следовательно, множество Q.iu может быть вычислено за время O(knhin). После этого остается только посчитать мощность этого множества. Если |Q.u>| = 1, то автомат sf синхронизируем, иначе — нет. Предложение доказано. □Заметим, что мы построили слово, синхронизирующее любой коммутативный автомат с п состояниями и к буквами. Такое слово называется уни-версалъныл1 синхронизирующим словом для класса коммутативных автоматов. Универсальным синхронизирующим словам для класса всех ДКА посвящено много работ (см. например [10, 12, 21]).

Следствие 2.1. Для любого фиксированного числа к > 1 задачи вида к-8УМ(гего), к-8УМ(топ), к-8УМ(сИг) могут быть решены за время 0(п), а задача к-8УМ(сот) за время 0(п1итг).

Доказательство. Алгоритмы из предудущих предложений работают и в этих случаях, однако размер алфавита к является фиксированным, и поэтому не входит в выражения для времени работы алгоритмов (0{п) и 0(п 1п п)). Следствие доказано. □Остается открытым вопрос о существовании алгоритмов, решающих задачи БУИ для остальных классов ДКА (с циклом по всем состояниям, апериодических и т.д.) быстрсе чем за время 0(п2к).

2.3 Сложность поиска длин кратчайших синхронизирующих слов2.3.1 Класс всех ДКАНайти кратчайшее синхронизирующее слово для автомата, или хотя бы установить, существует ли синхронизирующее слово заданной длины, обычно бывает значительно сложнее, чем просто проверить автомат на синхро-низируемость. Напомним, что класс всех ДКА обозначается через ¿/я. Если задача ¿"УЛ^й/а) может быть решена за полиномиальное время (см.[19]), то задача ЗУМ((1/а, < Ь) является КР-полной (см.[19, 41]), а задача ЗУАт(с1[а, = Ь) вообще КР-трудна и со-КР-трудна(см.[43]). В Предложении 2.6 мы получим верхнюю оценку сложности задач 5УАг(г//а, = Ь) и к-вУ М(с1/а,= Ь) для к > 1.

Нам понадобятся некоторые факты из теории сложности вычислений. Все используемые нами понятия из теории сложности вычислений подробнее описаны в книгах [7] и [15]. Любая задача из класса ЛТР может быть решена при помощи машины Тьюринга с использованием простого оракула, который может угадать ответ и выписать его па ленту. Алгоритм решения задачи состоит в угадывании ответа при помощи оракула и последующей проверки угаданного ответа на правильность при помощи машины Тьюринга. Если для любых входных данных правильность угаданного оракулом ответа может быть проверена за полиномиальное время, то задача принадлежит классу ЫР. Аналогичным образом класс со-КР состоит из задач, которые могут быть решены при помощи оракула, угадывающего контрпример, благодаря которому утверждение задачи может быть опровергнуто за полиномиальное время.

Не все задачи принадлежат классам КР или со^Р и могут быть решены при помощи машины Тьюринга с простым оракулом, поэтому также рассматриваются более широкие классы задач. Класс состоит из задач, каждая из которых разрешима на машине Тьюринга М, использующей оракул 0+, который представляет собой машину Тьюринга, которая умеет вызывать оракул О-, который умеет отгадывать контрпример к задаче решаемой оракулом 0+. Используя оракул О- и проверяя угаданные им контрпримеры на правильность, оракул 0+ постепенно угадывает и записывает на ленту машины М некоторую информацию (ответ). Ответ будет записан только в том случае, если все контрпримеры прошли проверку на правильность. Машина М может за полиномиальное время проверить информацию, записанную оракулом 0+- на ленту. Задача имеет положительный ответ, если оракул 0+- записал на ленту ответ, и этот ответ оказался правильным.

Аналогичным образом определяется класс Щ. Класс Щ состоит из задач, каждая из которых разрешима на машине Тьюринга М, использующей оракул 0-+, который представляет собой машину Тьюринга, которая умеетвызывать оракул 0+, который умеет возвращать некоторый ответ на задачу решаемую оракулом 0+. Оракул 0+ может проверять ответы, возвращаемые оракулом 0+, и постепенно выписывать на ленту машины М контрпример к исходной задаче. Машина М может за полиномиальное время проверить контрпример, записанный оракулом 0+ на ленту. Задача имеет отрицательный ответ, если оракул 0+ записал на ленту контрпример, и этот контрпример оказался правильным.

Другие определения и свойства классов Е? и Щ описаны в [7] (раздел 7.2) и [15] (раздел 5.2). Мы докажем, что задача ЗУМ(с!/а, =Ь) лежит в каждом из классов Ез и Щ.

Предложение 2.6. Задачи ЗУЫ(й$а,—Ь) и к-ЗУМ(с1/а, — Ь) для всех к > 1 принадлежат классу сложности Щп Е?.

Доказательство. На вход любой из задач, содержащейся в формулировке теоремы, подаются автомат ^ и число Ь. Пусть 0+ — оракул, возвращающий для автомата некоторое синхронизирующее слово длины Ь. Пусть 0 — оракул, возвращающий синхронизирующее слово длины не превосходящей Ь — 1 для автомата.с/. Пусть 0+ — оракул, который, используя оракул О-, проверяет для автомата <й/, существует ли слово длины < Ь — 1, синхронизирующее автомат и если такого слова не найдено, то угадывает слово длины Ь и возвращает его, иначе ничего не возвращает. Пусть 0+ — оракул, который угадывает синхронизирующее слово длины Ь—1, если такого не найдено, то просит оракула 0+ найти синхронизирующее слово длины Ь, и затем проверяет, является ли найденное слово синхронизирующим для автомата.

Задачи 5"УЛг((//а, = Ь)и к-ЗУМ(с1/а, = Ь) для к > 1 могут быть решены при помощи следующего алгоритма. Производится запуск оракула 0+. Если оракул вернул нам слово, то мы проверяем, является ли оно синхронизирующим. Если слово является синхронизирующим, то кратчайшее синхронизирующее слово для автомата имеет длину Ь. Иначе, кратчайшее слово имеет длину отличную от Ь (больше Ь). Если оракул 0+ не вернул слова (это значит, что О- нашел контрпример), то кратчайшее синхронизирующее слово также имеет длину отличную от Ь (меньше Ь). Длина кратчайшего слова не превосходит (п3 — п)/6 (см. [8]), поэтому все проверки могут быть сделаны за полиномиальное время, и алгоритм также работает за полиномиальное время. Следовательно, задачи ЗУМ((1/а, = Ь) и к-ЗУН(с1/а, = Ь) принадлежат классу сложности Е^.

В то же время, задачи SУN(dfa, = Ь) и к-ЗУК(й}а, —Ь) также могут быть решены при помощи другого алгоритма. Производится запуск оракула 0+. Если оракул 0+ не возвращает контрпримера и запускаемый им оракул (9+ нашел синхронизирующее слово длины Ь, то длина кратчайшего синхронизирующего слова для автомата равна Ь. Иначе, длина кратчайшего синхронизирующего слова отлична от Ь. Этот алгоритм также работает за полиномиальное время. Следовательно, задачи SYN(dfa, = Ь) и к-£№N((1/(1, = Ь) принадлежат классу сложности Щ. Предложение доказано. □Следствие 2.2. Для любого класса class, содержащегося в классе всех ДКА, задачи SYN (class, =L) и k-SYAT (class, = L) для k>l принадлеокат классу сложности Щ П Е1^.

В работах [19], [41] и [43] была описана сложность задач SYN(dfa, < L) и SYN(dfa, = L). В Предложении 2.7 мы приведем эти результаты вместе с доказательством (доказательство взято из [19]). При доказательстве NP-полноты задач будет использоваться классическая NP-полная задача ВЫПОЛНИМОСТЬ. Значения булевых переменных мы везде будем обозначать через 0 (ложь) и 1 (истина).

Задача: ВЫПОЛНИМОСТЬДано: Набор булевых переменных xi,. хп и набор из р булевых выра-, жений (эти выражения мы будем называть клозами) вида Ci(xi,. хп) = V. V г G {1.,р} где у* G {xt\l € {1,., п}} U {-пхе\£ € {1,., п}}.

Вопрос: Существует ли такой набор значений переменных Xi,. хп е {0,1}, что значения все клозы с подстановкой этих значений истинны, то есть для всех г Е {1,. р], Ci(xi,., хп) = 1 ?Предложение 2.7. 1. Задачи SYN(dfa, < L) и к-SYN(dfa,< L) для всех к > 2 NP-полны.

2. Задачи SYN(dfa,=L) и k-SYN(dfa, = L) для всех к>2 NP-трудны и co-NP-трудны.

Доказательство. 1. Длина кратчайшего синхронизирующего слова для синхронизируемого ДКА с п состояниями не может превосходить (п3 — п)/6 (см. [8]). Следовательно, если число L > (п3 — тг)/6, то задача SYN(dfa, < L) может быть решена при помощи проверки автомата на синхронизируемость, что может быть сделано за полиномиальное время. Пусть L < (п3 — п)/6. В этом случае, если для данного ДКА, дано некоторое слово длины L, то можно за полиномиальное время проверить, является ли это слово синхронизирующим для данного автомата. Проверка осуществляется простым последовательным применением букв слова. Поэтому задачи SYN(dfa, <L) и k-SYN(dfa, < L) лежат в классе NP, как задачи с полиномиальной проверкой.

Докажем, что задача 2-SYN(dfa, <L) NP-полна сведением к ней задачи ВЫПОЛНИМОСТЬ. Пусть на вход дан набор клозовci(x 1,., хп),., Ср(х 1,., хп) над переменными х\,. хп. Построим по ним2-х буквенный автомат = (Q, Е, S) и число L такие, что слово длины L, синхронизирующее автомат существует, тогда и только тогда, когда переменным х\,.,хр могут быть присвоены значения, обращающие все клозы с\,., Ср в истину. В противном случае кратчайшее синхронизирующее слово будет иметь длину большую чем L.

Доказательство. Задачи SYN(class,<L) и k-SYN(class,<L) являются частными случаями задач SYN(dfa,< L) и k-SYN(dfa,< L) соответственно, а они в свою очередь лежат в классе NP. Следствие доказано. □любого; ;. Имеем Q.w = end, следо-w\m\ = аполны.

Принимая в силу только что доказанное следствие, мы в дальнейшем будем предполагать, что принадлежность задач SYN(class, <L) и k-SYN(class, < L) к классу NP для классов автоматов, которые будут рассматриваться нами, уже доказана.

2.3.2 Автоматы с нулем, апериодические, ^-тривиальные и частично монотонные автоматы. СжимаемостьПредложение 2.8. 1. Задачи SYN(zero,<L), SYN(aper,<L), SYN(dtr, <L), SYN(pmon, <L), а также соответствующие k-задачи для k > 2 NP-полны.

2. Задачи SYN(zero,=L), SYN(aper,=L), SYN{dtr,=L), SYN(pmon,= L), а также соответствующие k-задачи для k > 2 NP-трудны и co-NP-трудны.

Доказательство. Утверждение предложения следует из того факта, что построенный в предыдущем предложении автомат является ^-тривиальным (и как следствие апериодическим), частично монотонным автоматом с нулем. То что s/dfa — автомат с нулем понять несложно, так как нулем является состояние end.

Для того, чтобы доказать, что автомат ¿г/dfa является частично-монотонным, достаточно ввести порядок <. Порядок < на множестве состояний без элемента end, играющего роль состояния err, можно ввести следующим образом: q{jni,ii) < q(jn2,i2), если г\ < г2, или ?'L = г2 и mi < т2. Можно убедиться, что если для любых q, q' G Q\{end}, q < q' и a 6 {a, b} таких, что q.a Ф end и q'.a ф end, следует q.a < q'.a. Потому, — частично монотонный ДКА.

Предложение 2.9. 1. Для любого класса class С dfa задает COMP(class, М, < L) и COMP(class, AI, < L) для k > 1 лежат в классе NP.

2. Для любого класса class С dfa задачи COMP (class, М,= L) и k-СОM P { class, М, = L) для k > 1 принадлежат классу П Щ?.

Доказательство. 1. Если L > (п3 — тг)/6, то задача COMP{class, М,< L) может быть решена при помощи проверки автомата на сжимаемость до М состояний, что может быть сделано за полиномиальное время. Пусть L < (п3 — п)/6. В этом случае, если для заданного ДКА дано некоторое слово длины L, то можно полиномиально проверить: будет ли это слово сжимать данный автомат до М состояний? Проверка осуществляется простым последовательным применением букв слова. Таким образом, задачи COMP(class, М, < L) и k-COMP(class, М, < L) лежат в классе NP.

2. Доказывается аналогично Предложению 2.6. □2.3.3 Коммутативные автоматыЕсли для какой-то из выше рассматриваемых задач доказывалась, что она NP-трудна, то соответствующие fc-задачи для к > 2 оказывались также NP-трудными. Однако в случае коммутативных автоматов это не так. Задачи SYN(com, <L) и SYN(com, =L) являются трудными, в то время как задачи k-SYN(com, < L) и k-SYN(com, — L) для любого фиксированного к > 1 могут быть решены за полиномиальное время. Этот факт демонстрируется следующими двумя предложениями. Основные результаты разделов 2.3.3 и2.3.4 опубликованы в [5].

Предложение 2.10. Пусть к > 1, тогда задачи k-SYN(com,< L) и k-SYN(com,=L) могут быть решены за время 0(пк\пп).

Доказательство. Любой коммутативный синхронизируемый ДКА может быть синхронизирован словом длины не превосходящей n—1 (см.[39]). Определим на множестве слов S* отношение эквивалентности Положим для w,u £ £*, и w, если слово w может быть получено из слова и перестановкой букв. Обозначим через N(n, к) количество классов эквивалентности по отношению для множества всех слов длины не превосходящей п — 1 над /с-буквепным алфавитом. Число N(n. к) равно количеству сочетаний с повторениями из к+1 по тт,—1. Из известной формулы имеем N(n, к) = . Следовательно, величина N(n, к) имеет порядок 0(пк) при фиксированном к.

Доказательство. Рассмотрим доказательство NP-пoлнoты задачи SYN(dfa, < Ь) из [43] и покажем, что используемый в нем автомат является коммутативным. Сведем задачу ВЫПОЛНИМОСТЬ к задаче 5УN{00171, < Ь). Пусть на вход дан набор клозов сх(я;х,., хп),., ср(хь., хп) над переменными х1,.,хп. Построим по ним автомат.с/слт = (С). Е, 6) и число Ь такие, что слово длины Ь, синхронизирующее автомат существует тогда и только тогда, когда переменным х±,. хп могут быть присвоены значения, обращающие все клозы сх,., Ср в истину.

Пусть существуют такие значения переменных Xi,., хп, что все кло-зы С\ j • • • } ср обращаются в истину. Тогда рассмотрим слово w длины п.

С{(хi,.,.t„) = 1, поэтому существует такое т. что хт содержится в q и хт = 1, а следовательно w[m] = om; или ->хт содержится в q и хт = 0, а следовательно w[m] =Ьт. В обоих случаях получаем qt.w[m] = end. Следовательно Q.w = {end}.

Предположим, что существует слово w длины п, синхронизирующее автомат ¿/сот- Для любого 77? G {1,., п} в слове w содержится ровно одна из букв ат и Ьт. Присвоим значения переменным xi,. хп. Положимсостояние qi в end, то значение хт = 1 обеспечит истинность клоза Cj, если буква Ьт переводила состояние в end, то значение хт = 0 обеспечит истинность клоза с-,. Таким образом, все клозы будут истинными.

Предложение 2.12. Задача SYN(sid,<L) является NP-полной, а задача SYN(sid,=L) является NP-трудной и co-NP трудной.

Доказательство. Сведем задачу ВЫПОЛНИМОСТЬ к задаче SYN(sid, < L). Пусть на вход дан набор клозов С\ (xj,., хп),. Ср(х ь., хп) над переменными., хп. Построим по ним такой ДКА ¿¡/sid — (Q, Е, 5) и такое число L, что слово длины L, синхронизирующее автомат &/sla, существует тогда и только тогда, когда переменным xi,. хп могут быть присвоены значения, обращающие все клозы с\,., Ср в истину.

Состояние end не может перейти в другое состояние, поэтому автомат s^sid может быть синхронизирован только в состояние end. Всего в автомате srfsid содержится п + 2р + 2 состояния. Применение одной буквы может перевести в end не более одного состояния отличного от end. В end переводят только буквы z,yi,. ур, поэтому эти буквы вместе взятые, должны быть применены не менее чем п + 2р + 1 раз. Кроме того, для перевода в end состояний vi,. vn необходимо применить хотя бы одну из букв каждой пары ат,Ьт для т Е {1,. п}. Следовательно, автомат не может быть синхронизирован словом длины меньшей, чем 2п + 2р + 1.

Доказательство. Если а и b — перестановки, то для п > 1 автомат szf не является синхронизируемым. Если а и Ъ — простые идемпотенты, то для п > 3 автомат ¿г/ также не является синхронизируемым, а для п < 3 легко рассмотреть все возможные варианты. Поэтому можно считать, что а — простой идемпотент, а Ъ — перестановка.

Пусть qi.a — q? ф qi для qx, qo Е Q. Перестановка b разлагается в произведение простых циклов. Если циклов больше чем два, то автомат, очевидно, не будет синхронизируемым, так как буква а может склеивать либо состояния одного цикла, либо состояния двух конкретных циклов. Пусть циклов два, в этом случае для синхронизируемости необходимо, чтобы состояния qi и 52 принадлежали разным циклам С\ и С12- При этом, если цикл Со содержит более одного состояния, то автомат не будет синхронизируемым, так как различные состояния из цикла Сг не смогут быть склеены. В таком случае, автомат se/ имеет вид. изображенный на Рис.17.

Кратчайшим синхронизирующим словом для автомата ¿г/ в этом случае будет слово а{Ъа)п2, это несложно показать.

При q2 = п, автомат si представляет собой автомат Черни с п состояниями, изображенный на Рис.9. Проведя рассуждения аналогичные тем, что были в начале раздела 2, можно показать, что если НОД(п,р) = 1, то слово а(№1а)п2 будет кратчайшим синхронизирующим для автомата srf.

Проверить, имеет ли автомат si один из видов, изображенных на Рис.17 или Рис.18 можно за время О(п). Для этого достаточно найти состояния q± и (j21 посчитать длины циклов перестановки Ь, в которых содержатся эти состояния, и если они лежат в одном цикле, найти расстояние между ними по циклу. После этого достаточно сравнить одну из величин а{Ьа)п2 (для случая двух циклов) и а(6р-1а)п2 (для случая одного цикла) с числом L. Предложение доказано. □Таким образом, задачи 2-SYN(sid, <L) и 2-SYN(sid, = L) решаются за полиномиальное время, а задачи SYN(sid, < L) и SYN(sid, — L) трудны. Вопрос об оценке сложности задач k-SYN(sid, <L) и k-SYN(sid, = L) для к > 2 остается открытым.

2.3.5 Монотонные и циклически монотонные автоматыСуществуют классы class С dfa для которых задачи SYN(class, < L) и SYN(class, = L) решаются за полиномиальное время. Примерами могут служить классы монотонных и циклически монотонных автоматов. В [19] приведен алгоритм поиска кратчайшего синхронизирующего слова для заданного циклически монотонного автомата si = (Q, S, 6), работающий за время 0(|<5|2|2|). Если такой алгоритм находит слово, то оно имеет длину не превосходящую (|Q| — I)2. Любой монотонный автомат является циклически монотонным, поэтому кратчайшее синхронизирующее слово для заданного монотонного автомата si = (Q, Е, 5) также может быть найдено за время0(М2|£|).

Предложение 2.14. 1. Задачи БУИ (топ, <Ь) и к-БУN(171011, <Ь) могут быть решены за врелия 0(п2к).

2. Задачи БУК(стоп, <Ь) и к-БУИ(стоп, <Ь) могут быть решены за время 0(п2к).

Однако не все задачи, связанные с синхронизацией, решаются для монотонных ДКА за полиномиальное время. Для класса монотонных ДКА нами также сформулирована задача СОМР(топ, М, < Ь). Входными данными этой задачи являются автомат ¿г/ и числа Ь и М. Решением этой задачи является ответ на вопрос, существует ли для заданного монотонного автомата слово длины не превосходящей Ь, переводящее множество состояний автомата в не более чем М-элементное множество? Такое слово называется сжимающим автомат до М состояний. В следующем предложении мы покажем, что эта задача, аналогичная задача для циклически монотонных автоматов и задачи поиска длины кратчайшего слова, сжимающего данный монотонный или циклически монотонный автомат до А/ состояний, являются трудными даже для двухбуквенных автоматов.

Предложение 2.15. 1. Задачи СОМР(топ, М, <Ь), СОМР(стоп, М, < Ь), а также задачи к-СОМР(тотг, М,<Ь) и к-СОМР(стоп,М,<Ь) для к >2 ЫР-полны.

2. Задачи СОМР(топ,М, = Ь), СОМР(топ,М, = Ь), а также задачи к-СОМР(топ,М, = Ь) и к-СОМР(топ,М, = Ь) для к > 2 ИР-трудны и со-ИР- трудны.

Доказательство. Мы докажем КР-полноту задачи 2-СОМР(топ,М,— Ь). Утверждения относительно других задач, сформулированные в предложении, могут быть получены из КР-полноты задачи 2- СОМР(топ. М, = Ь) аналогично доказательству Предложения 2.7, и учитывая тот факт, что монотонные автоматы являются циклически монотонными.

Пример автомата.я^поп изображен на Рис.19. Действие буквы а изображено сплошными линиями, действие буквы Ъ — пунктирными. Состояния нарисованы в три колонки, в каждой находятся состояния вида д{т, г) для фиксированного г. В каждом горизонтальном ряду расположены состояния вида q(m,i) для фиксированного т.

Порядок на состояниях автомата можно ввести следующим образом:<7(7711, ¿1) < я(т2,г2), если < г2, или ¿1 = г2 и гпг < т2.q(2m+l,i), иначеГ q(2m + 2, г), ->хт присутствует в с* q(2m + 1, г), иначеm + 2, г), хт присутствует в с,- безq(2m, г).а = q(2m, г).Ъ = q(2m + 2,г).

Несложно убедиться, что автомат ¿&топ с порядком ^ является монотонным. Также несложно заметить, что размер автомата £/топ полиномиально зависит от размера входных данных задачи ВЫПОЛНИМОСТЬ. Число М мы возьмем равным р, число Ь мы возьмем равным п.

2.3.6 Автоматы, содержащие цикл по всем состояниямНапомним, что через dcZe мы обозначаем класс всех ДКА, содержащих букву, действующую как цикл по всему множеству состояний.

Предложение 2.16. Задача 2-SYN(cycle, <L) — NP-полна.

Доказательство. Из определения функции переходов автомата £&сус1е можно заметить, что в независимости от того, какой буквой а или Ъ является ги[1], множество 1), • • •, содержится во множестве С^.ги[1\.

2. Задачи SY N {cycle, = L) и k-SYN{cycle,= L) для к >2 являются NP-трудными и co-NP-трудными.

Доказательство. 1. Задача 2-SYN{cycle, <L) является частным случаем задачи SYN {cycle, < L), и сводится к задаче k-SYN {cycle, <L) для k > 2 добавлением k — 2-х букв, действующих тожественно.

2. NP-трудность задач SYN {cycle, = L) и k-SYN {cycle,= L) для всех к > 2 доказывается построением такого же автомата, как в Предложении 2.16. co-NP-трудность доказывается при помощи того же автомата srfCydc, но в этом случае число L надо взять равным п + 3. Кратчайшее слово, синхронизирующее автомат s/cyxie, имеет длину L тогда и только тогда, когда не существует таких значений переменных. х„. что с\{х\,., хп) =. = Cp{xi,.,./'„) = 1. Поэтому задачи co-NP-трудны. Следствие доказано. □Таким образом, задачи поиска длины кратчайшего синхронизирующего слова для автоматов, содержащих перестановку порядка не являются существенно более простыми, чем те же задачи для произвольных ДКА.

3 Частичные автоматыНапомним, что частичным конечным автоматом (ЧКА) называется тройка = (Q, Е, 6), где Q — конечное множество состояний, Е — конечный алфавит и 5 — частичная функция переходов, действующая из Q х Е в Q. ЧКА.¡г/ — (Q, Е, 5) называется бережно синхронизируемым, если существует слово w € Е* такое, что величина S(Q,w) определена и w)\ = 1.

Заметим, что 2§ < 3§ для всех п> 0. Поэтому, наша нижняя оценка величины ujpfa(n) превосходит оценки известные раннее. Результаты разделов 3.1.1 и 3.1.2 опубликованы в [4]. Результаты разделов 3.1.3 и 3.1.4 опубликованы в [2]. Результаты разделов 3.2 и 3.3 опубликованы в [3]. Результаты всего раздела 3 анонсированы в [1].

3.1.1 Пример для числа состояний кратного тремВ этом и следующем разделах мы получим нижние оценки величины и)р}а{п). Для этого мы приведем две бесконечных серии автоматов. В обеих сериях найдутся автоматы со сколь угодно большим числом состояний. Вторая серия будет модификацией первой. Автоматы во второй серии гораздо более сложные по своей конструкции, но они дают большую нижнюю оценку величины и'р/а(п).

В этом автомате (¿(С^т^д™}) = 6. Соответствующий автомат на подмножествах (автомат с множеством состояний и функцией переходов 8, естественным образом продолженной на подмножества множества состояний) представлен на Рис.23.

Построим кратчайшее слово, бережно синхронизирующее автомат &р/а. Рассмотрим слова гУо, и>1,.,. VI,., у^ определенные следующим образом:-Шо = \,Шг = ад^бда-хЬг'Шг-!, г € {1,., к},Рис. 21: Автомат ёёр}а для к = 3Рис. 22: Действие букв ат и Ът на множествеVI = а»(«;г1Ьг)2и;г1аг(г(;г1бг)2^1, г € {1,., к}. Индукцией по т непосредственно проверяется, что8((Э, VI. ут) = Як и и. и фт+1 и., д]} для т £ {1,., к}.

Следствие 3.1. Если п3к для к > 1, то (¿р/а(п) > 3 • 3§ — 2.

3.1.2 Пример для числа состояний равного степени тройкиЦелью этого раздела является доказатеьство оценки uJPfa(n) >= 5 • 3? — о(З^) для п = Зг. Эта оценка превосходит оценку, полученную в предыдцщем разделе. Для ее доказательства мы построим автомат ^,/а(гг) такой, что длина кратчайшего б.с.с. для него имеет вид 5 • Зз — о(Зз).

ЧКА я/ назовем однородно синхронизируемым словом у, если у — кратчайшее б.с.с. для ¿г/, и для любого подмножества Б С найдетсятакой префикс т слова у, что ги) = Б.

Пусть я/ — ЧКА, однородно синхронизируемый словом у. Построим слово у', однородно синхронизирующее автомат «с/ • 3. Допустим также, что для всех с Е Е и 5 С <5 таких, что значение с) определено, выполняется неравенство с)| > |5| — 1. Легко проверить, что в этом случае в автомате.с/ • 3 для всех с £ Е и £' и 5' С таких, что значение 5'(5", с) определено, выполняется неравенство |<5'(5/,с)| > |5"| — 1.

Докажем, что автомат л/ • 3 является бережно синхронизируемым и построим кратчайшее б.с.с. для него. Пусть — последовательность различных натуральных чисел из множества Определим слово ги(1г 1,., кг) следующим образом: положим яи^х) = Ь\х, для г € {2,., г} положимии(}11,.,1ц) = ги(Лх,. -., Ы^Ън-ы^х,.,., }цх).

Кроме того, \Sr\ = 1 и |Sr-i| = 2. Следовательно, |5'(5ri • 3, г/[|г/|])| = 1 и слово v' бережно синхронизирует автомат sé • 3.

Следовательно, \¿'(Q', гг[1, Шо])| > к. Получаем, что S'(Q', ¿¿[1, /л0]) = Q • 3. Рассуждая аналогично примеру 1, можно получить, что v\. ик — кратчайшее слово, переводящее множество Q' во множество Q ■ 3. Следовательно, m0 = \vi.vk\.

Определим весовую функцию р : 2® —Z. Для каждого одноэлементного подмножества Т С Q положим р(Т ■ 3) = —2.

Пусть TCg',T = {¿., qj1}, ¿!,., í\t\ E{ 0,1,2}, ju., jm E {1,., к},и ji ф jm для £ ф тп. Положим тг(Г) = {4\ ■ ■ ■, Р(Т) = р(тг(Т)) + ¿i +3 • ¿2 +. + З'т'-1 • í\t\ ■ Таким образом, мы определили функцию р для всех подмножеств Т С Q' таких, что \Т П Qi\ < 1 для г Е {1,., к}.

Пусть с G S. Если значение 8'(Т,с) определено, то Т = S ■ 3 для некоторого S С Q. Заметим, что 8'{Т,с) С., ir{ô'(T, с)) = ô(S,c) -3. Обозначим 8(S, с) через S' и |5| через р.

Следовательно, р(8'(Т,с)) > р(Т) — 1.

Получается, что ¿'(Q, ^[1, то]) = Q • 3. Проверим по определению слова г/, что для всех m > то имеет место равенство p(8'(Q, ?/[!, m])) = p(8'(Q, v'\l, m— 1])) — 1. Это означает, что на каждом шаге синхронизации значение функции р уменьшается на максимально возможную величину. Следовательно, v' — кратчайшее б.с.с. для автомта • 3.

Докажем, что автомат srf • 3 однородно синхронизируется словом v'. Опишем все множества, достижимые из Q', и докажем, что для любого множества Т Ç Q' достижимого из Q', найдется число t 6 {1,., |г>'|} такое, что 8'(Q', t/[l,£]) = Т. Пусть T € DÇ&'). Это означает, что существует слово щ € (Е U S')* такое, что S'(Q',u0) = Т.

Из определения слова v' получаем, что существуютhi,h2 е {1,.>'|} такие, что S'(Q', v'[l, /ц]) = 5fi и 5'{Q',v'[l,h2}) = Si.

Пусть |5i| = р. Существует Зр различных множеств Т' таких, что тг(Т') =Кроме того, ho — hi = Зр для всех j £ {/ii + 1,., ho}, ir(5'(Q', г/[1, j])) = Si,и S'(Q', г;'[1, j]) различны для различных j. Следовательно, найдется i G{/я + 1,.,/г2} С {1,.>'|} такое, что d'(Q',v'[l,t}) = Т.

1=Ш2Обозначим через г; • 3 слово г/, построенное из слова V при помощи выше описанной процедуры.

Используя только что описанную конструкцию автомата «й^-З, мы построим автомат, обеспечивающий нижнюю оценку величины ш(п) для п = 3Г.

Пример 2. Пусть п = Зг. Построим автомат = ((3,1!,, 8) с Зг состояниями. Пусть ^о = ({9}, ¡2- 0) — ЧКА с пустым алфавитом. Построим автоматы — ■ 3, £/2 — • 3, • ■., = ■ 3 и положим =.

Для каждого тп € {1,., г} определим — (<Зт, Их и. и Ет, ¿т), где <2ТО — множество из Зт элементов и Ет =., а™^^,., при этом имеем |Ет| = 2 • 3т1.

Пример автомата для г = 2 изображен на Рис.24. Буквы а и Ь играют роли букв а\ и Ь\, буквы а\, аг, Ь2, аз, Ьз играют роли букв а2, б2, а2, &>> аз>Легко заметить, что А — б.с.с. для и автомат однородно синхронизируется словом щ = А. Для всех т Е {1,. г} можно построить слово ит = ит-1 • 3. Слово ит однородно синхронизирует автомат. Следовательно, слово и — иг — кратчайшее б.с.с. для автоматаВычислим длину слова и. Пусть т € {1,., г}, г Е {1,., т — 1}. Обозначим Ят • Зг = дт • 3 •. • Имеем<ьр,м <5о • 3) = Яг-X • 3) +. + СЦ^СО! ■ З'--1, д0 ■ Зг).

Заметим, что и),()0 • 3) = и — 1. Следовательно,М = <5о • 3) - гг + 1.

Следствие 3.2. Если п = Зг, тог-1 / нт. (ш+1)п \ I Опт Ч зт+1 \^р/а(п) > 3 ■ 3« + X) ((Зт + 1)- 32^-1-! 1 -п-5-3«-о(3«).

3.1.3 Трехбуквенный алфавитВ сериях автоматов, построенных в предыдущих разделах, размер алфавита рос с увеличением количества состояний в автоматах. Но кроме этого интересен вопрос, какая нижняя оценка длины кратчайшего бережно синхронизирующего слова может быть получена для ЧКА с фиксированным размером алфавита? В наших обозначениях эта вопрос соответствует задачам оценки снизу величин ш^а(п) для фиксированных к.

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

Теорема 3.1. Существует бесконечная последовательность ЧКА{^а(п)\я/р%{п) = {а, Ь, с}, 6п}, Ш = гг}такая, что длина кратчайшего б. с. с. для автоматов растет быстрее чем любой полином от п.

Доказательство. Обозначим г-е простое число через р%, т.е. р\ = 2,р2 =г3 и т.д. Построим автоматы ^¡а{р) для п = Определим ЧКА1=1= {С}п,{а,Ь,с},5п}. Далее мы будем считать, что число п зафиксировано, и обозначать С}п через <5, а Зп через 6. ПоложимЯ = {г;(г, А;)|г е {1,. г}, к е {0,pi - 1}}.

Действие буквы а изображено сплошными линиями, действие буквы Ь — пунктирными с короткими черточками, действие буквы с — пунктирными с длинными черточками.

Действие буквы а — это перестановка всего множества Q, которая распадается на циклы Ci, г £ {1,., г}, длины которых являются последовательными простыми числами. Буква Ъ переводит множество Q в состояния вида v(i, 0), то есть в "нулевые" состояния циклов. Буква с определена только на состояниях вида v(i,pi — 1), т.е. на "последних" состояниях циклов.

Поэтому, из минимальности длины и следует, что буква b в слове и присутствует только на первом месте. Следовательно, и = Ьаьс для некоторого натурального t.

После применения буквы b в каждом из циклов C¿ остается по одному состоянию v(i, 0). Заметим, что и(г,0).ах = v(i,pt — 1) тогда и только тогда, когда х = pi — l(modp¿), и это для всех г £ {1,. г}. Мы получили систему из г сравнений. Минимальным положительным решением этой системы является х — PiPi.pr — 1. Следовательно, t = pip-j.pr 1, и слово w — baPl'-'Prlc является кратчайшим б.с.с. для автомата -с//а(п).

Оценим скорость роста длины слова w в зависимости от количества состояний автомата ¿2^а(п), равного pi +. +рг. Из теоремы Чебышева о распределении простых чисел получаем а ■ ¿1п(г) < pi < /3 ■ г1п(г), где 0,9 < а < Р < 1,2 — некоторые константы. Имеем]im (fl Pi)1/Pr = е, см. [20].г=ггСледовательно, для достаточно болыцих г получаем \и\ > \\рг > earlnr.¿=iгС другой стороны ^Рг 1пг, см.[16]. Следовательно, п = <г=1 г=11г2+£ дДЯ любого £ > 0 и достаточно больших г. Откуда получаем г > 2+у/2п. Таким образомПоэтому, длина слова го растет быстрее любого многочлена от п. Теорема доказана. □Из только что доказанной теоремы следует, что величина (п) растет быстрее любого многочлена от п. Аналогичный автомат можно построить для произвольного п, не обязательно равного сумме простых чисел, добавив несколько новых состояний, которые под действием буквы Ь переходят в состояние г>(1,0). Точную формулу для оценки величины и>^а(п) написать затруднительно.

3-1.4 Двухбуквенный алфавитСерия двухбуквенных автоматов, обеспечивающая нижнюю оценку величины ojpfa{n), строится аналогично серии sé^а(п), но конструкция является более сложной.

Теорема 3.2. Существует бесконечная последовательность ЧКА(Ч/аИК/аН = {Qn, {а, Ь}, 5п}, IQ„¡ = п}такая, что длина кратчайшего б.с.с. для автоматов растет быстрее любого многочлена от п.

Доказательство. Обозначим i-e простое число через Pi. Построим автогматы £/pfa(n) для п = 2 • Определим ЧКА.з^fa(n) = {Qn, {a,6},ón}.¿=iДалее мы будем считать, что число п зафиксировано и обозначать Qn через Q, a Sn через 6. ПоложимQ = {v(m, i, k)\m € {0,1}, i в {1,., г}, к е {0,pt - 1}}.

Лемма 3.2. Слово и имеет вид Ь2(аЬ)га2 для некоторого натуральногоЬ.

Доказательство. Буква а определена не на всем множестве <2, поэтому и[1] = Ь. Если и[2] = а, то на множестве 1,2] определена только буква Ъ, поэтому гг[3] = Ь. В этом случае С}.и[1.3] = С^.ЬаЬ = С^.Ъ и из слова и можно безболезненно выкинуть первые две буквы, что противоречит минимальности длины и. Следовательно, м[1,2] = Ь.

Пусть в начале синхронизации на каждом состоянии автомата стояло по фишке. После применения слова м[1,2] — Ъ2 все фишки оказываются на состояниях ряда До. Заметим, что И^.а С. Е^.Ь С До, Я^.Ь С Д0, и если все фишки находятся в ряду Н\ так, что буква а определена на всех состояниях с фишками, то под действием буквы а все фишки перейдут на состояниег;(1,1,1). Следовательно, для к > 2 множество Q.u[l,k] содержится либо в До, либо в Ri. Фишки из разных колонок JQ могут быть склеены только под действием буквы а. При этом они все должны находиться в некотором подмножестве Р ряда Ri. В этом случае Р.а = {г>(1,1,1)}, то есть Р переходит в одноэлементное множество. Следовательно, Q.u[ 1, |u| — 1] = Р и последняя буква слова и — это а.

После применения слова Ъ2 в каждой колонке Ki, г & {1, • • • г} находится одна фишка, и при применении букв слова и кроме последней эта фишка так и останется в колонке К"г. Поэтому, если для некоторого 2 < к < |it| множество Q.u[ 1, к — 1] содержится в ряду R0 и и[к] — Ь, то Q.u\l, = Q.b2. В этом случае слово u[l,fc] может быть заменено на б2, что противоречит минимальности длины и. Поэтому, если после применения и[1, к — 1] фишки стоят в ряд\г i?o, то = а. Если для некоторого 2 < к < \и\, множество Q.u[ 1, к — 1] содержится в ряду Ri, то буква а не определена на этом множестве и и[к] = Ь. Следовательно, начиная с третей буквы слова и, буквы а и b применяются но очереди, до тех пор, пока не появится возможность применить букву а в момент, когда фишки находятся в ряду R\. Следовательно, слово и имеет вид ¡г (ab)1 а1 для некоторого t. Лемма доказана. □Лемма 3.3. и = ft2(ab)pi-"p,-2a2 = w.

Мы уже знаем, что задача SYN(dfa) может быть решена за полиномиальное время, задача SYN(dfa, <L) является NP-полной, а задача SYN(dfa, = L) является NP-трудной и co-NP-трудноп, но лежит в классе £2 П По. Какова же сложность аналогичных задач для бережной синхрони-зируемости заданного ЧКА? Мы докажем, что задача проверки заданного ЧКА на бережную синхронизируемость (SYN(pfa)) PSPACE!-полна, даже в случае автоматов с 2-мя буквами. Также мы докажем, что PSPACE-полны: задача проверки заданного автомата на бережную синхронизируемость словом заданной длины (SYN{pfa, < L)) и задача поиска длины кратчайшего б.с.с. для заданного ЧКА (SYN(pfa, —L)). Эти результаты являются самыми значительными в данной диссертации. Им будут полностью посвящены разделы 3.2 и 3.3.

Приступаем к доказательству PSPACE-полноты всех вышеперечисленных задач, а также соответствующих А--задач, рассмотренных для любых к > 2. Для этого мы найдем алгоритм, позволяющий решить задачи SYN(pfa), SYN(pfa, < L) и SYN(pfa, = L), используя дополнительную память полиномиального размера (Предложение 3.2). Кроме того, мы сведем известную PSPACE-полную задачу 3-ВЫПОЛНИМОСТЬ С КВАНТОРАМИ к задачам 2-SYN(pfa), 2-SYN(pfa,<L) и SYN(pja, = L) (Предложение 3.3). Таким образом, благодаря Предложению 3.1, получим PSPACE-полноту задач SYN(pfa), SYN(pfa, < L), SYN{pfa, = L), k-SYN(pfa), kSYN(pfa,<L) и k-SYN(pfa,=L) для всех к > 2.

Пусть задача А полиномиально сводима к задаче В. В этом случае мы будем писать А <р В.

Пусть слово w G (EU {a})* кратчайшее б.с.с. для автомата si' и |ш| = L. Из того что |5'(<Э,7г(г(;))| = \5'{Q,w)\ — 1, получаем 7r(u>) = го. Следовательно иёЕ*,п поэтому w является б.с.с. для автомата si. Если и — б.с.с. для автомата si и |u| < \w\, то и также является б.с.с. для автомата si', и u; не будет кратчайшим б.с.с. для si'. Поэтому кратчайшее б.с.с. для автомата si имеет длину L. Таким образом k-SYN(pfa,= L) <р (k + l)-SYNipfa,=L).

2, 4, 6. Получаются очевидным образом, так как автоматы с к буквами являются частными случаями произвольных автоматов.□3.2.2 Принадлежность к РSPACEВ силу того, что модель вычислении, использующая память произвольного доступа (RAM), полиномиально эквивалентна машине Тьюринга (см.[22]), мы будем использовать для вычислений обычный компьютер. Построим алгоритм проверки автомата srf на бережную синхронизируемость, использующий п2 + 0(п) дополнительной памяти. Идея взята из алгоритма поиска пути между двумя вершинами в заданном графе, который использует дополнительную память логарифмического размера (см. [35]).

Основную идею алгоритма проверки ЧКА на бережную синхронизируемость проще всего понять на примере решения более простой задачи.

Задача: ПУТЬ МЕЖДУ ДВУМЯ МНОЖЕСТВАМИДано: ЧКА si — (Q, Е,<")), множества То, Ту С Q и целое число к > 0.

Вопрос: Верно ли, что существует слово wGE* длины не большей чем 2к такое, что Tq.w = Ту.

Задача SYN(pfa, < L) отличается от задачи ПУТЬ МЕЖДУ ДВУМЯ МНОЖЕСТВАМИ тем, что начальное множество То всегда является всем множеством состояний Q, конечное множество Ту может быть любым из одноэлементных подмножеств множества Q, и длина слова w ограничена числом L, которое может не быть степенью двойки. Поэтому, для решения задачи SYN(pfa, < L) мы опишем чуть более сложный алгоритм.

Предложение 3.2. Существует, алгоритм, позволяющий решить задачи SYN(pfa), SYN(pfa, <L) и SYN(pfa, = L) используя дополнительную память полиномиального размера.

Доказательство. Построим функцию, которая реализует алгоритм, решающий задачу ЗУМ(р/а, < Ь). Алгоритмы решения задач БУМ(р/а) и 5УЛ^(р/а, = Ь) будут использовать эту функцию в качестве подпрограммы. Пусть на вход нам дан ЧКА — £, 6), = {1,., п}, £ = {<21,., ат} и целое число Ь > 0. Построим алгоритм, отвечающий на вопрос: существует ли слово го € £* длины не большей чем Ь, бережно синхронизирующее автомат.

Каждое множество £>[/'] может быть закодировано при помощи п битментами которого будут n-битные записи множеств из {5"[г]|г = 1. п}. Элемент B[j] служит для хранения подмножеств множества Q, претендующих на то, чтобы быть множествами S[p ■ 2J] для различных нечетных р.

В начале работы алгоритма присваивается Б[3] = {1,2,3}. Вызывается InPath(2,4,4). Перебираются различные варианты множества В[2]. Пусть В[2] = {1}, это будет S^""1] = S[4].

Затем вызывается InPath( 1,2,4). Перебираются различные варианты множества В[ 1]. Пусть В[1] = {2,3}, это будет S[2n2] = S[2].

Докажем, что алгоритм СheckLength(^/, L) работает правильно. Рассмотрим дерево вызовов Тг функции InPath. Вершинами в этом дереве являются вызовы InPath(k, с, L), будем их для краткости обозначать через 1Р(к, с) (т.к. L одно и то же для всех вызовов InPath). Ребро из вершины 1Р(кх,сх) в вершину /Р(&2, со) существует тогда и только тогда, когда функция InPath(k2, С2, L) рекурсивно вызывается при выполнении функции InPath{kx,Cx, L). Вершины вида 1Р(к,с) будем называть вершинами к-ого уровня. Если к > 0, то при выполнении функции InPath(k,c,L) происходит не более чем два рекурсивных вызова функции InPath: InPath(k-l,c — 2kl,L) и InPath(k — l,c + 2fe-1, L). Поэтому дерево Тг получится двоичным. Будем называть ребра вида (1Р(к, с), 1Р(к — 1, с — 2к л)) левылш, а ребра вида (1Р(к, с),1Р(к — 1,с + 2к1)) правыми. Если к = 0, то функция InPath далее рекурсивно не вызывается, поэтому в дерево Тг состоит из уровней {тг — 1,. 0}. Как и в любом дереве, в Тг существуетединственный путь из корня 1Р(п — 1,2" до любой вершины.

Лемма 3.4. Пусть 1Р{к,с) — вершина в дереве Тг, (спх,., со) — двоичная запись числа с и еп-\,., — ребра, составляющие путь из вершины 1Р(п — 1,2й"1) в вершину 1Р(к,с), тогдаск- 1 =. = со = 0.

Доказательство. К различным вершинам дерева Тг ведут различные пути из корня. Поэтому, из Леммы 3.4 следует, что для различных вершин IP(k, с), числа с различны. Вершина IP(k, с) содержится на к-м уровне, поэтому по Лемме 3.4 двоичная запись числа с имеет вид с = (cn-i,., Cfc-ii, 1,0,. 0). Следовательно, номер младшего ненулевого разряда в записи числа с равен к. В двоичной записи числа с содержится п разрядов, поэтому 1 < с < 2п — 1. Лемма доказана. □Лемма 3.6. Пусть 1Р(0,с) — вершина 0-го уровня в дереве Тг, eni,., &i — ребра, составляющие путь из вершины 1Р(п — 1, 2п1) в вершину /Р(0,с);£ = Номер младшего ненулевого разряда в двоичной записи числа с + 1, г = Номер младшего ненулевого разряда в двоичной записи числа с — 1,Для г € {п — 1,., к + 1}

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Мартюгин, Павел Владимирович

4 Заключение

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

Был проведен обзор почти всех классов ДКА, которые ранее описывались кем-либо в связи с понятием синхронизируемости и гипотезой Черни. Для двухбуквенных автоматов с нулем была получена нижняя оценка максимальной длины кратчайшего синхронизирующего слова (раздел 2.1). Для некоторых из рассматриваемых подклассов ДКА были найдены быстрые алгоритмы проверки на синхронизируемость (раздел 2.2). Для большинства из рассматриваемых классов была определена сложность задач проверки на синхронизируемость словом заданной длины и задач поиска длины кратчайшего синхронизирующего слова (раздел 2.3). Отдельно была рассмотрена сложность тех же задач для автоматов с фиксированным размером алфавита. Сложность оказались различной для различных классов автоматов. Кроме того, для некоторых классов ДКА была также рассмотрена сжимаемость до заданного числа состояний и сложность ответствующих задач.

Результаты, касающиеся ДКА, приведены в верхней части Таблицы 4. В первой колонке указан подкласс ДКА. Если перед названием подкласса стоит цифра 2, то задачи рассматриваются для двухбуквенных автоматов. Если после названия стоит "до М" то рассматривается сжимаемость ДКА до М состояний. Пусть п — количество состояний, к — размер алфавита автомата соответствующего конкретной строчки таблицы. Во второй колонке приведена сложность самого быстрого из имеющихся на данный момент алгоритмов проверки заданного автомата на синхронизируемость. Если задача проверки на синхронизируемость заданного ДКА словом заданной длины решается полиномиально, то в третьей колонке приведена сложность соответствующего алгоритма, если доказано, что эта задача ЫР-полна, то в третьей колонке написано NP. Если задача поиска длины кратчайшего синхронизирующего слова для заданного ДКА решается полиномиально, то в четвертой колонке приведена сложность соответствующего алгоритма. В четвертой колонке написано Е2 П П2, если задача принадлежит классу £2 П П2, но является КР-трудной и со-ЫР-трудной. В пятой и шестой колонках приведены лучшие на данный момент нижние и верхние оценки длин кратчайших синхронизирующих слов для рассматриваемых подклассов автоматов. Результаты, полученные в данной диссертации, выделены жирным шрифтом.

Было определено понятие бережной синхронизируемости ЧКА. Были получены нижние оценки длин кратчайших бережно синхронизирующих слов для ЧКА как с произвольным, так и с двух и трехбуквенным алфавитом (раздел 3.1). Была доказана РвРАСЕ-полнота задач проверки заданного ЧКА на бережную синхронизируемость и поиска длины кратчайшего бережно синхронизирующего слова для заданного ЧКА (разделы 3.2 и 3.3). Задачи оказались PSPACE-полными даже для автоматов с двумя буквами.

Результаты, касающиеся бережной синхронизации ЧКА, приведены в последних двух строчках Таблицы 4. В первой колонке указан класс: все ЧКА или только двухбуквепные ЧКА. Во второй колонке приведена сложность задач проверки на бережную синхронизируемость, в третей — сложность задач проверки на бережную синхронизируемость словом заданной длины, в четвертой — сложность поиска длины кратчайшего бережно синхронизирующего слова (все задачи PSPACE-полны). В пятой и шестой колонках приведены лучшие на данный момент нижние и верхние оценки длин кратчайших бережно синхронизирующих слов для рассматриваемых ЧКА. Запись > POL означает, что величина w2fa{n) растет быстрее любого полинома от п. Результаты, полученные в данной диссертации, выделены жирным шрифтом.

Список литературы диссертационного исследования кандидат физико-математических наук Мартюгин, Павел Владимирович, 2008 год

1. Мартюгин П.В. Бережная синхронизируемость частичных автоматов // Труды 39-й региональной молодежной конференции "Проблемы теоретической и прикладной математики", Екатеринбург, 2008. С. 336-341.

2. Мартюгин П.В. Нижние оценки длины кратчайших бережно синхронизирующих слов для двух- и трёхбуквенных частичных автоматов // Дискретн. анализ и исслед. опер., 2008, 15:4, С. 44-56.

3. Мартюгин П.В. PSPACE-полнота задачи проверки частичных автоматов на бережную инхроиизируемость // Известия Уральского Государственного Университета, №62, 2008, С. 106-150.

4. Martyugin P.V. Lower bounds for length of shortest carefully synchronizing words // Proc. Int. Conf. Workshop on Words and Automata, St.Petersburg, 2006.

5. Martyugin P.V. Complexity of problems concerning reset words for commutative automata and automata with simple idempotents // Proc. 12th Int. Conf. Automata and Formal Languages, 2008, pp. 314-324.

6. Martyugin, P.V. A series of slowly synchronizable automata with a zero state over a small alphabet // Information and Computation, 206 (2008), pp. 1197-1203.

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

8. Клячко А.А., Рысцов И.К., Спивак М.А. Экстремальная комбинаторная задача связанная с длиной синхронизирующего слова в автомате // Кибернетика, №2, 1987, С. 16-20.

9. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир, 1985. 439 с.

10. Ananichev D. S., Volkov М. V. Collapsing words vs. synchronizing words // Lecture Notes in Computer Science, 2295, 2002, pp. 166-174.

11. Ananichev D. S., Volkov M. V. Synchronizing monotonic automata // Lecture Notes in Computer Science, 2710, 2003, pp. 111-121.

12. Ananichev D. S., Petrov I. V. Quest for short synchronizing words and short collapsing words // 4th International Conference on Combinatorics on Words, Turku, 2003, pp. 411-418.

13. Ananichev D. S. The mortality threshold for partially monotonie automata // Lecture Notes in Computer Science, 3572, 2005, pp. 112-121.

14. Ananichev D. S., Volkov M. V. Synchronizing generalized monotonie automata // Theoretical Computer Science, 330, 2005, pp. 3-13.

15. Arora S., Barak B. Complexity Theory: A Modern Approach, Web Draft, 2007.

16. Bach. E., Shallit. J., Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, 1996.

17. Cerny J. Poznâmka k hornogénnym eksperimentom s konecnymi avtomatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. 14, 1964, pp. 208-216.

18. Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Inform. Theor. Appl. 32, 1998, pp. 21-34.

19. Eppstein D. Reset sequences for monotonie automata // SIAM J. Comput. 19, 1990, pp. 500-510.

20. Finch S.R., Mathematical Constants. Cambridge, England: Cambridge University Press, 2003.

21. Gawrychowski P., Kisielewicz A. Synchronizing words // Proc. Int. Conf. AUTOMATA, Palermo, 2007.

22. Hopcroft J, Ulman J. Formal Languages and their Relation to Automata. Addison-Wesley, Reading, MA, 1967.

23. B. Imreh, M. Steinby, Directable nondeterministic automata // Acta Cybernetica 14, 1999, pp. 105-115

24. B. Imreh, M. Ito, M. Steinby, On commutative directable nondeterministic automata // Grammars and Automata for Strings: From Mathematics and Computer Science to Biology, and Back, Taylor and Francis, London, 2003, pp. 141-150

25. Ito M., Shikishima-Tsuji K. Some results on directable automata // Lecture Notes in Computer Science, 3113, 2004, pp. 125-133.

26. Ito M. Algebraic Theory of Automata and Languages // World Scientific, Singapore, 2004.

27. Jurgensen Hi Synchronization // Proc. Int. Conf. LATA, 2007, pp. 27-49.

28. Kari J. A counter example to a conjecture concerning synchronizing words in finite automata // EATCS Bull. 73, 2001, p. 146.

29. Kohavi Z., Winograd J // Bounds on the length of synchronizing sequences and the order of information losslessness // Theory of Machines and Computations, Academic Press, New York and London, 1971, pp. 197-206.

30. Markovsky G. Bounds on the index and period of a binary relation on a finite set // Semigroup Forum 13, 1977, pp. 253-259.

31. Mateescu A., Salomaa A. Many-valued truth functions, Cerny's conjecture and road coloring // EATCS Bull. 68, 1999, pp. 134-150.

32. Natarajan B. K. An algorithmic approach to the automated design of parts orienters // Foundations of Computer Science (27th Annual Symposium), IEEE, 1986, pp. 132-142.

33. Natarajan B. K. Some paradigms for the automated design of parts feeders // International Journal of Robotics Research 8, 1989, No.6, pp. 89-109.

34. Pin J.-E. On two combinatorial problems arising from automata theory // Ann. Discrete Math. 17, 1983, pp. 535-548.

35. Reingold. O. Undirected st-connectivity in log-space // Proc. 37th Symposium on Foundations of Computer Science, 2005, pp. 376-385.

36. Roman A., Forys W. Lower bound for the length of synchronizing words in partially-synchronizing automata // Proc. Int. Conf. SOFSEM, 2008.

37. Rystsov I. K. Polynomial complete problems in automata theory // Information Processing Letters, 16(3), April 1983, pp. 147—151.

38. Rystsov I. K. Quasioptimal bound for the length of reset words for regular automata // Acta Cybernetica, 12, 1995, pp. 145-152.

39. Rystsov I. K. Reset words for commutative and solvable automata // Theoretical Computer Science, 172, 1997, pp. 273-279.

40. Rystsov I. K. Reset words for automata with simple idenipotents // Cybernetics and System Analysis, 36, 2000, pp. 339-344.

41. Salomaa A. Composition sequences for functions over a finite domain // Theoretical Computer Science, 292, 2003, pp. 263-281.

42. Sandberg S. Homing and synchronizing sequences // Lecture Notes in Computer Science, 3472, 2005, pp. 5-33.

43. Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // Proc. Int. Conf. AUTOMATA, Palermo, 2007.

44. Stockmeyer L.J., Meyer A.R. Word Problems Requiring Exponential Time // Proc. 5th Ann. ACM Symp on theory of computing, Assotiating for Computing Machinery, New York, 1973, pp. 1-9.

45. Trahtman A.N. An efficient algorithm finds noticeable trends and examples concerning the Cerny conjecture // Lecture Notes in Computer Science, 4162, 2006, pp. 789-800.

46. Trahtman A. N. The Cerny conjecture for aperiodic automata // Discr. Math, and Theoret. Comput. Sei. v. 9 2, 2007, pp. 3-10.