Вопросы оптимальности в теории синхронизируемых автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Прибавкина, Елена Владимировна

• Прибавкина, Елена Владимировна
• кандидат физико-математических наук
• 2009

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

Введение

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

0.2 Синхронизируемые автоматы с нулем.

0.3 Конечно порожденные синхронизируемые автоматы . 12 0.4 Универсальные синхронизирующие и сжимающие слова.

0.5 Предварительные сведения.

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

1 Медленно синхронизируемые автоматы с нулем и непо-крывающие множества

1.1 Непокрывающие множества.

1.2 Полуцветочный автомат для конечного множества слов

1.3 Непокрывающие множества и синхронизируемые автоматы

2 Конечно порожденные синхронизируемые автоматы

2.1 Характеризация конечно порожденных синхронизируемых автоматов.

2.2 Алгоритм проверки конечности языка минимальных синхронизирующих слов.

2.3 Время работы алгоритма.

2.4 Гипотеза Черни для класса конечно порожденных синхронизируемых автоматов.

2.5 Верхняя оценка длины минимального синхронизирующего слова.

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

2.7 Вычислительная сложность в случае постоянного алфавита

3 Некоторые свойства 1-сжимающих и 2-синхронизирующих слов

3.1 Характеризация 2-сжимающих слов.

3.1.1 Классификация 2-сжимаемых автоматов.

3.1.2 Критерий 2-сжимаемости слова.

3.1.3 Критерий в случае одной почти перестановочной буквы.

3.1.4 Критерий в случае двухбуквенного алфавита

3.2 Нижняя оценка длины кратчайшего

2-сжимающего слова.

3.3 Место языка 2-сжимающих слов в иерархии Хомского

3.4 Характеризация 2-синхронизирующих слов.

3.5 Реконструкция 2-сжимающих и 2-синхронизирующих слов по внутренним отрезкам.

3.6 Модификация алгоритма распознавания

2-сжимающих слов.

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

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

В данной работе под словом «язык» понимается формальный язык над фиксированным конечным алфавитом Е, т.е. подмножество свободного моноида Е* над Е, а под словом «автомат» - конечный детерминированный автомат с входным алфавитом Е. Такой автомат л/ = (С^, Е, 5} определяется заданием конечного множества состояний <3 и функции перехода 6 : <3 х Е —> С}. (Отметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние до € <5 и множество Р заключительных состояний. Мы также будем пользоваться этим вариантом определения, когда речь будет идти о языках, распознаваемых автоматами.) Функция 6 естественным образом продолжается на свободный моноид Е*, это продолжение мы также будем обозначать через 5. Таким образом, каждое слово из 6 Е* (в частности каждая буква алфавита Е) порождает преобразование 6(—,ги) : <3 —> ф множества

Имея дело с конечными детерминированными автоматами, мы будем отождествлять слово и) с этим преобразованием. Для слова ги € Е* и подмножества 5 С через 5. ги обозначим образ слова ги, т.е. множество {%,«;) \де Б}.

Автомат я/ — {<3, А, 5) называется синхронизируемым, если существует слово и) € А*, переводящее его в одно выделенное состояние, независимо от текущего состояния автомата, т.е. д. ги — д'. ги для всех <7,д' € С^. Любое слово с таким свойством называется синхронизирующим для автомата '. Пример синхронизируемого автомата с четырьмя состояниями приведен на рис. 1. Нетрудно проверить, что слово ги — Ъа?Ъа?Ь синхронизирует этот автомат (более того, ги является кратчайшим синхронизирующим для этого автомата). Данный пример принадлежит словацкому математику Яну Черни, который в 1964 году в работе [21] впервые формально ввел понятие синхронизируемого автомата. Это понятие возникло в рамках классического подхода «умозрительных экспериментов» Мура [46]. Мур и его последователи использовали конечные автоматы для моделирования дискретно работающих устройств (компьютеров). Естественный вопрос в связи с этим следующий: как мы можем восстановить контроль над устройством, не зная его текущего состояния, но наблюдая его поведение в ответ на различные посылаемые ему входь ь а

Ь а а й а Ь

Рис. 1: Автомат Черни иые сигналы? Мур в 1956 году в работе [46] показал, что при некоторых условиях можно однозначно определить состояние, в которое автомат приходит под действием подходящей последовательности сигналов. В его работе такая последовательность называлась экспериментом. Отметим, что эксперименты Мура были адаптивными, т.е. каждое следующее действие выбиралось на основе реакции устройства на предыдущие действия. Гинзбург в 1958 году в работе [36] рассмотрел особый тип экспериментов, которые он назвал однородными. Такой эксперимент - это просто фиксированная последовательность сигналов, т.е. подходящее слово над входным алфавитом; особенностью однородных экспериментов являлось то, что ответные сигналы нужны были только для определения состояния устройства в конце эксперимента. Отсюда понадобился всего один шаг, чтобы прийти к понятию синхронизирующего слова - эксперимента, в котором вообще не учитываются ответные сигналы устройства. Отметим, что это понятие является довольно естественным с точки зрения практики, поскольку далеко не всегда можно наблюдать ответные сигналы устройства: например, при движении спутника вокруг Луны он не может контролироваться с Земли в момент, когда он находится «позади» Луны.

С середины 60х годов прошлого века теория синхронизируемых автоматов начинает активно развиваться ввиду многочисленных приложений таких автоматов в различных областях: тестировании реактивных систем, роботике, символической динамике и др., см. обзоры [43,59,64]. Остановимся чуть подробней на одном из возможных будущих приложений - области молекулярных вычислений. В недавних экспериментах [19] Бененсон и др. использовали ДНК одновременно в качестве компьютера 5 и программного обеспечения, построив конечный автомат наноскопиче-ского размера. Был создан «бульон» из автоматов, т.е. раствор, содержащий 3 х 1012 копий одного и того же автомата на микролитр. Все эти копии могут работать параллельно на разных входах и, следовательно, заканчивать вычисления в разных и непредсказуемых состояниях. В отличие от электронного компьютера, мы не можем перезапустить систему, просто нажав кнопку. Вместо этого, чтобы одновременно перевести все автоматы в исходное состояние, нужно «заправить» бульон достаточным количеством ДНК молекул, чья последовательность нуклеотидов кодирует синхронизирующее слово для данного автомата.

С другой стороны, для математиков синхронизируемые автоматы сами по себе представляют интересный комбинаторный объект, и их изучению уделяется большое внимание, прежде всего, в связи с гипотезой Черни. Для удобства в дальнейшем автомат с п состояниями будем называть п-автоматом. Черни в своей работе [21] построил серию га-автоматов над двухбуквенным алфавитом, для которых кратчайшие синхронизирующие слова имеют длину (п — I)2 (автомат на рис. 1 является автоматом Черни для п = 4). Позднее он предположил, что эта конструкция реализует наихудший случай, т.е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — I)2. За годы, прошедшие с тех пор, было предпринято множество попыток доказать или опровергнуть эту гипотезу, но ни одна из них не увенчалась успехом - гипотеза доказана лишь для многих частных классов автоматов, и простота ее формулировки до сих пор продолжает привлекать внимание многочисленных исследователей, см. [17,18,31,32,40,57,62,63].

Первый естественный вопрос, связанный с синхронизируемыми автоматами, следующий: как по данному автомату проверить, является ли он синхронизируемым? Алгоритм проверки данного автомата = (<5, Е, 6) на синхронизируемость получается непосредственно из классической конструкции автомата подмножеств Множество состояний этого автомата определяется как множество 'Р'(ф) всех непустых подмножеств множества <5, а функция переходов - как естественное продолжение функции (У на множество 7?'((5) х Е (это продолжение также обозначается через 5). На рис. 2 приведен автомат подмножеств для автомата ^4, представленного на рис. 1. Ясно, что некоторое слово ги € ХГ синхронизирует автомат я/ тогда и только тогда, когда оно читается вдоль пути в автомате из состояния <3 в некоторое одноэлементное 6 а Ь подмножество. Таким образом, задача проверки синхронизируемости автомата сводится к задаче достижимости в графе, которая легко решается поиском в ширину. Несмотря на концептуальную простоту, описанный алгоритм не является эффективным, поскольку число состояний в автомате подмножеств экспоненциально зависит от числа состояний исходного автомата. Однако существует и полиномиальный алгоритм проверки автомата на синхронизируемость. Он основан на следующем наблюдении из [21].

Предложение 0.1. Автомат я/ = ((¿¡Т,^) является синхронизируемым тогда и только тогда, когда для любой пары состояний q,q' ^ Q существует слово и) € Е* такое, что д. и) = д'. ю.

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

- подавтомате автомата подмножеств, в котором присутствуют лишь двух- и одноэлементные подмножества. Поскольку этот автомат имеет IQKlQl+i) состояний, то такой алгоритм работает за время 0(|<5|2)- Отметим, что он не дает на выходе никакого синхронизирующего слова, в отличие от первого алгоритма, на выходе которого получаются кратчайшие синхронизирующие слова. Лучший известный алгоритм, выдающий в случае синхронизируемости автомата некоторое синхронизирующее его слово, был найден Эпштейном в [32]. Он работает за время 0(|Q|3) и находит синхронизирующее слово длины 0(|<2|3). Вообще задача, в которой для заданного автомата srf и заданного натурального числа Z требуется определить, имеет ли автомат si синхронизирующее слово длины не больше £, является NP-полной [32]. Самотий в работе [58] показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат si имеет длину ровно £, является NP-трудной и co-NP-трудной. Таким образом, если co-NP^NP, эта задача не может принадлежать NP. Значит, даже недетерминированные алгоритмы не могут найти кратчайшее синхронизирующее слово для данного автомата за полиномиальное время.

Что касается верхних оценок длины кратчайших синхронизирующих слов, то лучшая оценка, известная на сегодняшний день, принадлежит Пэну [53]. Он показал, что для любого синхронизируемого п-автомата существует синхронизирующее слово длины не более T±-fJi- Введем в рассмотрение функцию Черни £(п) как наибольшую длину кратчайших синхронизирующих слов для синхронизируемых n-автоматов. Тогда автоматы Черни из [21] дают нижнюю оценку €(п) > (п — 1)2, а гипотезу Черни можно переформулировать как €(п) = (п—1)2. С учетом верхней оценки справедливо следующее неравенство: п-1)2<ед<^. (1)

В дальнейшем усилия математиков были направлены на получение оценок функции Черни для различных частных классов автоматов. Было получено много интересных результатов, в качестве примера приведем некоторые из них. Пусть X - некоторый класс синхронизируемых автоматов. Обозначим через €х(п) ограничение функции Черни на X.

1. В 1998 году Дюбук рассмотрел в работе [31] класс циклических синхронизируемых автоматов (обозначение - cycle), т.е. автоматов, для которых существует буква, действующая на множестве состояний как 8 циклическая перестановка и показал, что £cycie(n-) < (та — I)2. Отметим, что автоматы Черни попадают в этот класс, следовательно, верно £cyde(n) >(п- I)2. В итоге, cycle{n) = {П- if.

2. В 2003 году Кари в своей работе [40] доказал гипотезу Черни для класса euler синхронизируемых автоматов, чей граф является эйлеровым. В действительности он доказал более сильное неравенство: feuler < (п- 1)(тг-2) + 1.

Однако до сих пор не известно, является ли эта оценка точной.

3. Моноидом переходов М(з/) автомата sä = (Q, Е, 6} называется моноид (полугруппа с единицей, где в роли единицы выступает пустое слово Л) преобразований множества состояний Q, порожденный действием букв алфавита Е на этом множестве. Моноид называется апериодическим, если все его подгруппы тривиальны; автомат называется апериодическим, если его моноид переходов является апериодическим. Класс таких автоматов обозначим через aper. Апериодические автоматы играют важную роль во многих аспектах теории формальных языков, и изучение синхронизирующих слов для этого класса автоматов вполне оправданно. В 2007 году в работе [62] Трахтман показал, что <£арег (п) < "К-1). Тем не менее для всех известных на сегодняшний день нетривиальных примеров апериодических автоматов длина кратчайшего синхронизирующего слова является линейной функцией от числа состояний. Лучшая известная нижняя оценка для этого класса принадлежит Ананичеву [10]: £oper(n) > п + Lf J — 2, тем самым,

Стоит отметить, что при получении нижних оценок функции Черни для различных классов ситуация осложняется еще и тем, что известно мало примеров «медленно» синхронизируемых автоматов, т.е. п-автоматов с кратчайшим синхронизирующим словом длины (п — I)2 или близкой к этому значению. Автоматы Черни - единственная бесконечная серия таких «экстремальных» автоматов. Кроме того, существует несколько отдельных примеров автоматов с небольшим числом состояний над двух- и трехбуквенным алфавитом, на которых достигается

2 < taper (п) < щп — I ) 9 оценка Черни. Вообще, вычислительные эксперименты показывают, что медленно синхронизируемые автоматы встречаются довольно редко. В пользу этого наблюдения говорят и вероятностные аргументы. Например, известно, что если <3 - п-элементное множество, то (для достаточно большого п) произведение 2п случайно выбранных преобразований множества ф в среднем является константным преобразованием [38]. В терминах теории автоматов это означает, что произвольно выбранный п-автомат над алфавитом с достаточно большим количеством букв с большой вероятностью является синхронизируемым, причем словом длины, не превосходящей 2п. Поэтому поиск серий наиболее медленно синхронизируемых автоматов в каждом классе представляет интересную и нетривиальную задачу. В главе 1 диссертации рассматривается эта задача для класса синхронизируемых автоматов с нулем, т.е. автоматов, обладающих выделенным состоянием 0, для которого 0. а = 0 для любой буквы о € Е. Отметим, что этот класс является особенно важным в связи с гипотезой Черни, так как известно, см., например, [63, предложение 3] что ее доказательство в общем случае сводится к доказательству в двух частных случаях: когда автомат обладает нулем, и когда граф автомата является сильно-связным, т. е. каждое состояние достижимо из любого другого.

0.2 Синхронизируемые автоматы с нулем

Легко видеть, что любой синхронизируемый автомат с нулем обладает ровно одним нулем и любое синхронизирующее слово переводит такой автомат в нулевое состояние. Относительно несложные рассуждения показывают, что длина синхронизирующего слова для произвольного синхронизируемого п-автомата с нулем не превосходит см. напр. [57]. Кроме того, для каждого п существует синхронизируемый п-автомат с нулем, имеющий п — 1 входной символ, для которого кратчайшее синхронизирующие слово имеет длину (рис. 3). Особенность этого примера состоит в том, что число букв растет вместе с числом состояний, что контрастирует с примером Черни, где число букв не зависит от числа состояний. Таким образом, вопрос об определении нижней границы функции Черни для класса автоматов с нулем над фиксированным алфавитом остается открытым.

В 2007 году Мартюгин в работе [42] с помощью компьютерных экспериментов для каждого натурального п> 8 построил синхронизируемый

10

Е Е\{аъа2} £\{а2,а3} £\{а3,а4} Е \ {о„2, а„1> Е\{а„1}

Рис. 3: Синхронизируемый п-автомат с нулем над алфавитом Е = {а!, а2,., Оп-г}) Для которого кратчайшее синхронизирующее слово п(п—1) имеет длину —'-. п-автомат с нулем над двухбуквенным алфавитом, для которого крат

Отметим, что до этого результата ситуация с оценками для класса автоматов с нулем была такой же, как и для рассмотренных выше апериодических автоматов: в известных примерах длина кратчайших синхронизирующих слов являлась линейной функцией от числа состояний, и предполагалось, что в действительности функция Черни для этого класса линейна. Отметим, что конструкция из [42] весьма нетривиальна и, кроме того, не обобщается на случай больших алфавитов. Чтобы придать точный смысл последнему утверждению, назовем синхронизируемый автомат д/ = (ф, Е, 6) существенным, если каждая буква алфавита Е входит в каждое синхронизирующее данный автомат слово. Иначе говоря, каждая буква является существенной для синхронизации такого автомата. Ясно, что задачу об оценке функции Черни уместно ставить именно для существенных автоматов, а добавление новых букв к автоматам из конструкции Мартюгина приводит к тому, что они перестают быть существенными.

Основным результатом главы 1 является следующая

Теорема 1. Пусть Е - произвольный алфавит, |Е| > 2. Для любого к > |Е| существует существенный синхронизируемый автомат с нулем и п = 2к состояниями над алфавитом Е, кратчайшее синхронизирующее слово для которого имеет длину чайшее синхронизирующее слово имеет длину

11

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

0.3 Конечно порожденные синхронизируемые автоматы

В главе 2 мы вводим в рассмотрение новый класс синхронизируемых автоматов. Этот класс определяется следующим образом. Пусть - язык всех слов, синхронизирующих данный синхронизируемый автомат . Отметим, что этот язык является бесконечным, поскольку если ги & то и ичм 6 для любых слов и, V € £*. Таким образом, вполне естественно рассмотреть минимальные синхронизирующие слова, т.е. слова, синхронизирующие автомат ¿¡/, но такие, что ни один их собственный префикс или суффикс не является синхронизирующим. Язык всех таких минимальных синхронизирующих слов обозначим через -^тт(^). Легко видеть, что язык является двусторонним идеалом, порожденным языком

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

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

12 проверки конечной порожденное™ данного синхронизируемого автомата со множеством состояний С} является экспоненциальным: он работает за время О(26101) (подробнее этот алгоритм приведен в главе 2). В связи с этим, интересен вопрос о существовании более эффективных алгоритмов проверки языка минимальных синхронизирующих слов на конечность и о вычислительной сложности этой задачи. В главе 2 диссертации дан ответ на этот вопрос, а именно, в §2.1 найдена характеризация этого класса, которая дает несколько лучший алгоритм, работающий за время 0(12^1), проверки принадлежности автомата классу ЕС. Кроме того, в §2.6 с помощью характеризации доказывается, что задача проверки языка минимальных синхронизирующих слов на конечность является со-МР-трудпой, следовательно, вряд ли можно надеяться на существование значительно более эффективных алгоритмов для этой задачи.

Приведем пример конечно порожденного автомата. Пусть Е = {а, £>}, рассмотрим минимальный автомат л/, распознающий язык Ь = Е*айаЕ* (рис. 4). Легко видеть, что автомат синхронизируем, обладает нулем

Ь а а,Ь

Рис. 4: Минимальный автомат ¿г/, распознающий L = Е*аЬаЕ* и что выполняется равенство = L. Следовательно, Л?тгп№) — aba}, т.е. G FG. Вообще, для любого слова w € Е* минимальный автомат, распознающий язык Е*гиЕ*, является конечно порожденным. Более того, из теории формальных языков хорошо известно, что такой автомат имеет п = |w| + l состояний (через |го| мы обозначаем длину слова w), следовательно, минимальное синхронизирующее его слово имеет длину n — 1. Отсюда, в частности, имеем £fg (п) > п — 1. В общем случае конечно порожденным будет и минимальный автомат языка Е*МЕ*, где М - конечный язык. Такие автоматы возникают в теории формальных языков в связи с изучением языков с конечными антисловарями (такой язык определяется как теоретико-множественное дополнение к языку вида Е*МЕ*, где М - конечное множество, называемое антисловарем, см. напр. [29]).

13

В параграфе §2.4, используя найденную характеризацию класса Ев, мы доказываем, что верхняя оценка функции Черни для данного класса также линейна, а именно, Срс(п) < Зп—5. Таким образом, в диссертации получено неравенство п - 1 < Срв(п) < Зп - 5.

В случае конечно порожденных синхронизируемых автоматов наряду с естественным вопросом о возможной длине кратчайших синхронизирующих слов уместно ставить вопрос о наибольшей возможной длине минимальных синхронизирующих слов. В §2.5 доказывается экспоненциальная верхняя оценка длины минимальных синхронизирующих слов для п-автоматов из класса ЕС.

0.4 Универсальные синхронизирующие и сжимающие слова

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

Пусть п - натуральное число. Слово № 6 Е* называется универсальным п-синхронизирующим или кратко п-синхронизирующим, если оно синхронизирует все синхронизируемые автоматы с п + 1 состоянием над фиксированным алфавитом. В явном виде это понятие впервые возникло в работе [16]. Очевидно, что п-синхронизирующие слова существуют для любого п. В самом деле, существует лишь конечное число синхронизируемых п-автоматов над фиксированным алфавитом, поэтому конкатенация всех слов, синхронизирующих каждый из этих автоматов, и будет п-синхронизирующим словом. Согласно оценке Пэна (1), длина каждого синхронизирующего слова не превосходит

14

6 > значит> построенное таким образом слово будет иметь длину

6 (та С другой стороны, поскольку каждый синхронизируемый (п + 1)-автомат синхронизируется словом длины, не превосходящей (п+1) -(»+1) ? т0 Слово, содержащее в качестве факторов все слова такой длины, будет п-синхронизирующим и будет иметь длину пЛ |(т»+1)3-(>.+ 1). су¿-<1 в ). хогда возникает естественный вопрос о существовании более коротких п-синхронизирующих слов. Задача об оценках длины универсальных синхронизирующих слов рассматривается вместе с аналогичной задачей для универсальных сжимающих слов. Дадим формальное определение. Для слова т е Е* и автомата разность с^^го) = |<2| — |<5.гу| будем называть дефектом слова т по отношению к автомату <й/. Автомат я? = (<3,2,5) (не обязательно синхронизируемый) называется п-сжимаемым, если существует слово ш € Е* такое, что ё^(гу) > п (при этом говорят, что слово 'ш сжимает автомат на п состояний). Слово и) € Е* называется п-сжимающим, если оно сжимает на п состояний все п-сжимаемые автоматы с входным алфавитом Е. Таким образом, такое слово является «универсальным тестером», чье действие на множество состояний произвольного автомата с фиксированным входным алфавитом определяет, является ли данный автомат п-сжимаемым. Отметим в частности, что любой синхронизируемый (п+1)-автомат является п-сжимаемым, поэтому любое п-сжимающее слово является также п-синхронизирующим.

Понятие п-сжимаемости является вполне естественным обобщением понятия синхронизируемости, тем не менее впервые это понятие (под другим названием) возникло в начале 1990х в связи с задачами комбинаторики и абстрактной алгебры [48,60]. Первый естественный вопрос, связанный с понятием п-сжимающих слов, - это вопрос их существования для каждого натурального п и произвольного алфавита Е. Для однобук-венного алфавита ответ очевиден: слово ги является п-сжимающим тогда и только тогда, когда |ги| > п, поэтому в дальнейшем будем считать, что алфавит содержит по меньшей мере две буквы. В этом случае существование п-сжимающих слов, а также конструкция их в явном виде совсем не очевидны (в отличие от ситуации с п-синхронизирующими словами). В самом деле, согласно данному выше определению п-сжимающего слова, алфавит Е фиксирован, но не предполагается абсолютно никаких ограничений на число состояний п-сжимаемых автоматов, которые должны «обслуживаться» данным словом. Доказательство существования п-сжимающих слов было получено Зауэром и Стоуном в [60], где, по-видимому, впервые было введено понятие л-сжимающих слов, и где они именовались словами со свойством Д„. Ими была предложена следующая индуктивная конструкция. Заметим сначала, что если автомат sí = {Q, S, 5) является 1-сжимаемым, то существует буква а 6 S такая, что df¿/(a) > 1. (Иначе каждая буква действует как перестановка на множестве состояний, а значит, автомат я/ не может быть 1-сжимаемым.) Поэтому ясно, что слово, содержащее все буквы алфавита Е = {ai,. , at}, является 1-сжимающим. Используя это наблюдение в качестве базы индукции, полагаем w\ = ai • • • aj и определяем

Wn+i = wn П (vwn). (2)

0<М<3-2»-2+1

В правой части стоит произведение по всем словам из £*, длины не более 3 ■ 2n2 + 1 (упорядоченным определенным образом, например, лексикографически, относительно порядка букв ai < • • • < at алфавита Е), умноженным на соответствующее число копий wn. Построенное таким образом слово wn для каждого п является п-сжимающим [60, теорема 3.3J.

За последние несколько лет был достигнут заметный прогресс в изучении п-сжимающих слов и их связи с теорией автоматов и формальных языков, см. [12-14,16, 41], были найдены и новые алгебраические приложения, в частности, в теории свободных проконечных полугрупп, см. [8,9,55].

Оценки длины кратчайших n-сжимающих и п-синхронизирующих слов

Обе рассмотренные выше конструкции (п-синхронизирующих слов и конструкция (2) Зауэра и Стоуна п-сжимающих слов) дают слова, длина которых растет очень быстро с ростом п. Ввиду возможных приложений, возникает вопрос о существовании более коротких п-сжимающих и п-синхронизирующих слов. Обозначим через s(n, t) и с(п, í) длины кратчайших п-синхронизирующих и п-сжимающих слов над ¿-буквенным алфавитом соответственно. Очевидно, что s(n,t) < с(п, í). Лучшие известные на сегодняшний день оценки функций s(n, t) и с(п, t) были найдены в работе [41]: n+n-l < s(n,t) < c(n,í) < íl"("+1) + (n+l)íH«+1)-1 + - • -+(n-l)t. (3)

16

Нижняя оценка следует из следующего наблюдения. Рассмотрим произвольное слово ги длины п над ¿-буквенным алфавитом Е. Тогда минимальный автомат языка £*ш£* (см. пример на рис. 3), как уже отмечалось выше в §0.3, имеет п + 1 состояние и является синхронизируемым. При этом все синхронизирующие его слова должны содержать слово V) в качестве фактора. Поскольку любое п-синхронизирующее слово должно синхронизировать все автоматы такого вида, оно должно содержать все слова длины п в качестве факторов. Слова с таким свойством называются п-полными. Известно, что кратчайшее п-полное слово (слово де Брэйна [30]) имеет длину ¿п + п — 1.

Верхняя оценка была получена с использованием тех же идей, что и в доказательстве Зауэра и Стоуна: Марголис, Пэн и Волков показали [41, теорема 3.5], что в правой части (2) можно ограничиться произведением слов длины, не больше п +1. Более точно, теорема утверждает, что если 141 = Ь)\ — • • • и

1 = ип Д (уип) (4)

0<М<п+1 здесь снова все слова из Е* длины не более п + 1 появляются в лексикографическом порядке), то для каждого п > 1 слово ип является п-сжимающим. Для £ > 5 слова ип - кратчайшие известные на сегодняшний день примеры п-сжимающих слов.

В первом нетривиальном случае п = 2 удалось улучшить верхнюю и нижнюю оценки функции с(2, ¿). В работе [23] Керубини, Гаврихов-ски, Кисилевича и Пьоки найдена комбинаторная характеризация 2-сжимающих слов. А именно, с каждым словом связывается определенная система уравнений, которая имеет лишь тривиальное решение тогда и только тогда, когда слово является 2-сжимающим. Используя этот подход, в работе [27] Керубини, Кисилевич и Пьоки показывают, что с(2,£) < Используемая конструкция схожа с конструкцией (4): пусть и = 0,10,2 • • ■ тогда авторы доказывают, что слово

10 = и П(ии)> где X = {х,х2,хух | х,у & Е,у > ж}, является 2-сжимающим. Нетрудно видеть, что длина этого слова равна *3+6^2+5.

Автором улучшена нижняя оценка функции с(2, ¿) на основе теоретико-групповой характеризации 2-сжимающих слов, найденной в работе

17

13]. Более точно, нижняя оценка (3) при п = 2 дает с(2, ¿) > ¿2 + 1, в §3.2 диссертации доказывается, что с(2, £) > 2Ь2.

Что же касается точных значений функций в(п, £) и с(п, £) для п > 1, то их пока найдено немного. Значение .ч(2,2) = с(2,2) = 8 было найдено еще в самой первой работе о сжимающих словах [60]. Остальные известные значения с(2,3) = 21, в(2,3) = 20, я(3,2) = 33 были найдены [14] с помощью компьютерного перебора. Слова $ = аЬа2Ь2аЬ и = аЬа2 с2ЬаЬ2 асЬаЬсасЬсЪ (6) представляют собой два примера кратчайших 2-сжимающих слов над алфавитом из двух и трех букв соответственно. Слово

И-20 = аЬа2с2ЬаЬ2асЬаЬсасЬсЬ (7) является одним из кратчайших 2-синхронизирующих слов над трехбуквенным алфавитом, слово

И^зз = аЪ2аЬа3Ь2а2ЬаЬаЬ2а2Ь3аЬа2Ъа2Ь2а (8) является единственным (с точностью до переименования букв) кратчайшим 3-синхронизирующим словом над бинарным алфавитом. В [5] Петров с помощью предложенного им алгоритма распознавания п-сжимаю-щих слов проверил, что слово Н^з не является 3-сжимающим, и построил самое короткое известное на данный момент 3-сжимающее слово над бинарным алфавитом:

И-эт = а2Ь3аЬа3Ь2аЬа2Ь2а • ЬаЬаЬа2Ъа2Ь2а2ЪаЪа2 ■ ЪаЪаЪ2аЪ2 ■ аЪаЪ2а2Ъ2а (9)

Таким образом, 33 < с(3,2) < 57. Вручную с проверкой на списке автоматов в [5] было также найдено 2-синхронизирующее слово над четырехбуквенным алфавитом длины 42, которое является самым коротким известным словом с этим свойством:

Ж}2 = аЪса • йсйЪсйс ■ ЪаЬсйЪ • с1а2с2с12а • сйсЪйаса • ЬсЪ(1аЪ2(1а (10)

Заметим, что слова из (6) можно использовать для улучшения верхних оценок для с(п, 2) и с(п, 3): в (4) можно получить более короткие п-сжимающие слова над алфавитом с двумя (тремя) буквами, начиная

18 рекурсию сп = 2и выбирая слово (соответственно И^) в качестве и2. Это дает, например, оценку с(3,3) < 963. Известны также примеры коротких 2-сжимающих слов над 4- и 5-буквенным алфавитом [27], длины 56 и 119 соответственно, так что с(2,4) < 56 и с(2,5) < 119. Используя эти слова в (4), снова можно получить более короткие серии п-сжимающих слов над алфавитом из четырех и пяти букв. Отметим, что 2-сжимающее слово над алфавитом из пяти букв длины 119 было найдено с использованием подхода автора, описанного в §3.6 (первоначально в [26] было найдено пятибуквенное 2-сжимающее слово длины 120).

Алгоритмы распознавания п-сжимающих, п-синхронизирующих слов

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

Для <5>п такой алгоритм распознавания следует из регулярности этого языка. Действительно, как уже отмечалось выше, все синхронизирующие данный синхронизируемый автомат $4 — (<2,5) слова служат метками всевозможных путей в автомате подмножеств из состояния <3 в одноэлементные подмножества. Следовательно, распознает язык всех слов, синхронизирующих автомат я/, если выбрать состояние в качестве начального, а все одноэлементные подмножества в качестве заключительных. Таким образом, язык является регулярным как пересечение (конечного числа) языков синхронизирующих слов для всех синхронизируемых (п + 1)-автоматов над алфавитом Е. Стоит отметить, однако, что такой алгоритм распознавания не является эффективным, поскольку число состояний автомата подмножеств экспоненциально относительно числа состояний исходного автомата.

Что касается языка С„, то для случая п = 2 алгоритм распознавания был найден в работе Ананичева, Керубини и Волкова [13] на основании теоретико-групповой характеризации 2-сжимающих слов. Более наглядная интерпретация этого результата представлена в [12], где по данному слову ш £ Е* строится конечное семейство неполных (т.е. с частичной функцией переходов) автоматов, таких; что и> не является 2-сжимающим словом тогда и только тогда, когда по крайней мере один из этих автоматов можно дополнить до 2-сжимаемого детерминированного автомата Е, 6) с числом состояний < |ги| и (^(ги) = 1. Алгоритм использует полный перебор всех подмножеств некоторых множеств факторов слова т и, следовательно, не является полиномиальным; тем не менее, он допускает реализацию, достаточно эффективную для проверки 2-сжимаемости достаточно длинных слов, см. [14]. Например, слово И^х в (6) - первое (в лексикографическом порядке) в списке 2-сжимающих слов над алфавитом {о, 6, с}, найденное с использованием программы, реализующей алгоритм Ананичева, Керубини и Волкова из [12] (всего таких слов 80 с точностью до переименования букв алфавита).

В случае тг > 2 долгое время не удавалось найти подобного алгоритм ма, и исследования были сосредоточены на доказательстве принципиальной разрешимости проблемы принадлежности слова языку Сп. Для этого достаточно было найти для каждого п вычислимую функцию /п : N —> N такую, что слово ю £ £* является п-сжимающим, если > п для всех п-сжимаемых автоматов = с |<3| < /„(|го|). Действительно, если такая функция существует, то по данному слову V) можно вычислить значение функции т = /П(|Н)> а затем проверить условие на дефект слова ги по отношению ко всем автоматам с числом состояний, не превосходящим т. Поскольку таких автоматов лишь конечное число, этот процесс остановится через конечное число шагов. Если в результате работы будет найден п-сжимаемый автомат с <Нл,/(и!) < п, тогда слово V) не 2-сжимающее по определению, если же такого автомата не будет найдено, то слово ги является 2-сжимаемым по выбору функции /„. Из алгоритма [12]' следует, что для п = 2 в качестве такой функции /2 можно взять /2ОН) = шах{3, |ги| — 1}. Для п > 2 в обзорной статье Ананичева, Петрова и Волкова [15] была предложена функция /П(М) = 3|ги|(п — 1) + п + 1, удовлетворяющая требуемому свойству (отметим, что в [15] приведена лишь схема доказательства). Петров улучшил этот результат, показав, что в качестве функции /„ можно выбрать функцию /П(М) = 2|ги|(п — 1) + 2 [51]. Таким образом, язык Сп является рекурсивным; более того, линейная зависимость функции /Т1 от длины слова влечет существование недетерминированного алгоритма, полиномиального по времени и требующего линейной памяти, распознающего дополнение к Сп: алгоритм просто угадывает автомат я? = с |<3| < 2|ш|(п — 1) + 2, а затем проверяет, что автомат является п-сжимаемым (такую проверку можно осуществить за полиномиальное время) и что слово ш не сжимает на п состояний автомат . С точки зрения вычислительной сложности, из существования такого алгоритма следует, что задача распознавания п-сжимающих слов принадлежит классу со-ЫР. Недавно Керубини и Киселевич [24,25] дали положительный ответ на поставленный в [15] вопрос о со-МР-трудности этой проблемы. Из этих двух результатов следует, что задача распознавания п-сжимающих слов со-КР-полна, следовательно, не стоит ожидать полиномиального алгоритма ее решения. С другой стороны, наличие такого алгоритма, согласно классическому результату теории формальных языков ([44, разделы 2.4 и 2.5]), позволяет сделать вывод о том, что язык Сп является контекстно зависимым. В то же время при |Е| > 1 и п > 1 этот язык не является регулярным [16, предложение 3]. (Подробное доказательство этого утверждения приведено в [16] только для случая п — 2.) Тем самым, для окончательного выяснения положения языка Сп относительно классической иерархии. Хомского,, остается ответить на вопрос, является ли этот язык контекстно свободным. В §3.3 диссертации показано, что для первого нетривиального случая п = 2 язык 2-сжимающих слов.над двухбуквенным алфавитом не является контекстно свободным. Интуитивно, 2-сжимающие слова над бблыдими алфавитами имеют более сложную структуру, а язык Сп сложнее языка Сг, поэтому стоит ожидать, что и в общем случае язык Сп не является контекстно свободным.

Оптимизация алгоритмов

Описанный выше алгоритм распознавания п-сжимающих слов так же, как и. алгоритм распознавания п-синхронизирующих слов, не является практически пригодным, так как он должен просмотреть ш"1'2' автоматов для тп = 2|ги|(п — 1) + 2. В [51] было предложено улучшение алгоритма распознавания п-сжимающих слов, учитывающее структуру входного слова. В §3.5 диссертации мы модифицируем существующие алгоритмы распознавания языков Сг и ¿>2 на основе комбинаторных свойств 2-сжимающих и 2-синхронизирующих слов. Эта модификация использует идею реконструкции данного слова по некоторому специальному множеству его факторов. Подобная задача возникает в биоинформатике при реконструкции полного генома по известным его фрагментам. В некоторых случаях наша модификация позволяет ускорить процесс проверки данного слова на 2-сжимаемость и 2-синхронизируемость. Кроме того, такой подход позволяет находить более короткие 2-сжимающие и 2-синхронизирующие слова по существующим примерам. Так, именно этот подход для 2-сжимающих слов из работы [26] позволил уменьшить длину 2-сжимающего слова над пятибуквенным алфавитом, а для четырехбуквенного алфавита построить еще несколько примеров 2-сжимающих слов.

0.5 Предварительные сведения

Чтобы зафиксировать используемые в работе терминологию и обозначения, приведем основные определения из теории формальных языков и автоматов. Через |го| будем обозначать длину слова ги, т.е. число входящих в него букв; длину пустого слова А будем считать равной нулю: |А| = 0. Через Е+ будем обозначать множество всех непустых слов над алфавитом Е, а через - множество всех слов длины к над Е. Слово и е Е+ называется фактором слова т (соответственно префиксом, суффиксом), если ги представимо в виде V) = хиу (соответственно т = иу, гп = хи) для некоторых х,у Е Е*. Фактор (префикс, суффикс) и слова ги называется собственным, если ифиз.

В теории формальных языков конечные детерминированные автоматы обычно рассматриваются как устройства, распознающие языки. Для этого во множестве состояний автомата выделяется начальное состояние до и множество заключительных состояний Р. Говорят, что автомат А, 5, до> Р) распознает язык Ь С А*, если т.е. все слова языка Ь читаются вдоль всевозможных путей, ведущих из начального состояния в заключительные. Язык называется регулярным, если он распознается некоторым конечным детерминированным автоматом. Автомат с минимальным числом состояний, распознающий данный регулярный язык Ь, называетсяминимальным автоматом языка Ь.

Кроме распознающих устройств, языки могут задаваться порождающими устройствами. Такими устройствами являются порождающие грамматики. Порождающей грамматикой С? называется четверка объектов О = (У,Е, Р, 5), где V - вспомогательный алфавит (алфавит нетерминальных символов), Е - основной алфавит (алфавит терминальных символов), 5 € V - аксиома (начальный вспомогательный символ), Р - конечное множество правил вывода, т.е. выражений вида а —> ¡3, где а,/3 € (V и Е)*. Пусть 7,6 € (V и Е)*. Слово 5 непосредственно выводимо из 7 (обозначение 7 6), если 7 = хау, 5 = х(5у, и о —> /3 6 Р. Через 7 =>+ 5 обозначим транзитивное замыкание отношения

22

Языком, порождаемым грамматикой G, называется множество всех слов над Е, выводимых из аксиомы:

C(G) = {w € Е* | S w}.

Грамматики можно классифицировать по виду их правил вывода. Общепринятой классификацией грамматик и порождаемых ими языков является иерархия Хомского.

Грамматика типа 0 (рекурсивно-перечислимая грамматика) - грамматика произвольного вида, без ограничений на правила вывода. Такие грамматики порождают класс рекурсивно перечислимых языков, т.е. языков, принимаемых машинами Тьюринга.

Грамматика типа 1 (контекстно зависимая грамматика) - это грамматика, все правила вывода которой имеют вид а^Лаг —> схх/Зсхч, А € V, ai,аг,е (FUE)*. Класс языков, порождаемых контекстно зависимыми грамматиками, совпадает с классом языков, распознаваемых машинами,Тьюринга, использующими линейную память.

Грамматика типа 2 (контекстно свободная грамматика) - грамматика, все правила вывода которой имеют вид А —>■ /?, А Е V, /? € (V- U £)*.

Грамматика типа 3 (регулярная грамматика) - все правила вывода имеют вид А —► аВ или А Ь, А, В Е V, a, b € Е*. Класс языков, порождаемых регулярными грамматиками, совпадает с классом регулярных языков.

Предварительные сведения из теории сложности вычислений

Рассматриваемые в теории сложности вычислений задачи являются массовыми задачами распознавания, объединяющими в себе множество конкретных задач. Стандартная форма описания таких задач состоит из УСЛОВИЯ и ВОПРОСА, предполагающего один из двух ответов - «да» или «нет». Каждая конкретизация массовой задачи получается фиксированием УСЛОВИЯ. Размером задачи называется длина ее записи на ленте машине Тьюринга. Задача принадлежит классу сложности Р, если она решается за полиномиальное время от ее размера на детерминированной машине Тьюринга (см. [2,49]). Задача принадлежит классу сложности NP, если существует недерминироватшя машина Тьюринга, решающая ее за полиномиальное время. Если угадав каким-то образом ответ задачи, мы можем его проверить за полиномиальное время на детерминированной машине Тьюринга, то такая задача называется задачей полиномиальной проверкой. Все такие задачи, очевидно, принадлежат классу КР. Задача принадлежит классу со-^7Р, если ее.отрицание принадлежит NP. Нетрудно видеть, что если задача принадлежит классу КР, то для нее существует экспоненциальный по времени алгоритм решения. При естественном (с практической точки зрения) предположении, что Р^Р, задачи из класса Р считаются «легкими», а задачи из класса ИР, для которых не известен полиномиальный алгоритм решения, - «труд-норешаемыми». Конечно, поскольку до сих пор не доказано, что Р7ШР, нет никакой надежды показать, что некоторая задача А принадлежит NP\P. По этой причине в теории сложности вычислений доказываются более слабые результаты вида: «если Р,<^Р, то А еИР\Р». Подобные доказательства основаны на идее полиномиальной сводимости. Задача А полиномиально сводится к задаче В, если существует полиномиальный от размера задачи А алгоритм /, который по каждой конкретизации а задачи А строит конкретизацию /(а) задачи В так, что размер построенной задачи /(а) полиномиально зависит от размера задачи а; ответ на задачу а положителен тогда и только тогда, когда ответ на задачу /(а) также положителен.

Задача называется КтР[со-КР]-трудной, если к ней полиномиально сводится любая задача из класса ИР[со-КР]. Если ИР[со-КР]-трудная задача принадлежит классу КР[со-КР], то она называется КР[со-ЫР]-полной. Честь быть «первой» ИР-полной задачей выпала на долю задачи ВЫПОЛНИМОСТЬ. Результат о ее ИР-полноте, независимо полученный Куком [28] и Левиным [3], позволил с тех пор доказать вычислительную трудность широкого класса алгоритмических задач. Напомним, что под задачей ВЫПОЛНИМОСТЬ понимается следующая задача распознавания:

УСЛОВИЕ: набор булевых переменных Х\,., Хп и клозов сх,., ст (дизъюнкций переменных или их отрицаний);

ВОПРОС: существует ли приписывание значений истинности переменным так, что булева формула А^с, становится истиной?

24

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

Основные результаты диссертации опубликованы в [65-72]. Совместные работы [71,72] с Э. Родаро выполнены в нераздельном соавторстве. Работа [69] опубликована в издании, входящем в перечень утвержденных ВАК.

Ссылки на результаты диссертации присутствуют в работах других авторов: [15,22-27,51].

Основные результаты диссертации докладывались на Международной конференции по формальным языкам DLT 2005 (Палермо, Италия, 2005), спутниковом семинаре по полугруппам и автоматам к Международному коллоквиуму по автоматам, языкам и программировнию ICALP 2005 и Международной конференции по полугруппам и языкам (Лиссабон, Португалия, 2005), Международной алгебраической конференции, посвященной 100-летию со дня рождения П.Г. Конторовича и 70-летию Л.Н. Шеврина (Екатеринбург, 2005), Международной конференции Автоматы: от математики к приложениям (Палермо, Италия, 2007), Российско-индийском семинаре по алгебре, комбинаторике и сложности (Екатеринбург, 2008), Международной конференции по языкам и автоматам LATA 2009 (Таррагона, Испания, 2009).

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

25

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

1. Гинзбург С. Математическая теория контекстно свободных языков// М.: Мир. 1970.

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

3. Левин JI. А. Универсальные задачи перебора// Пробл. передачи ин-форм. 1973. Т.9. №3 С.115-116.

4. Линдон Р., Шупп П. Комбинаторная теория групп// М: Мир. 1980.

5. Петров И. В. Универсальные синхронизирующие и универсальные сжимающие слова// Диссертация на соискание ученой степени кандидата физ.-мат. наук. 2009.

6. Рысцов И. К. Возвратные слова для разрешимых автоматов// Кибернетика и системный анализ. 1994. Т.ЗО. №6. С.21-26.

7. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений// Москва-С.-Петербург-Киев: Вильяме. 2002.

8. Almeida J., Volkov М. V. Subword complexity of profinite words and subgroups of free profinite semigroups// Int. J. Algebra Comput. 2006. V.16. P.221-258.

9. Almeida J., Volkov M. V. Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety// J. Algebra Appl. 2003. V.2. P.137-163.

10. Ananichev D. S. The mortality threshold for partially monotonic automata// В кн. С. De Felice, A. Restivo (eds.) Developments in Language Theory, Lect. Notes Сотр. Sci., Springer-Verlag, Berlin-Heidelberg-New York. V.3572. 2005. P.112-121.

11. Ananichev D. S. The problem of the shortest SBH reconstruction is in P. Manuscript.83

12. Ananichev D. S., Cherubini A., Volkov M. V. Image reducing words and subgroups of free groups// Theor. Comput. Sei. 2003. V.307. P.77-92.

13. Ananichev D. S., Petrov I. V. Quest for short synchronizing words and short collapsing words// Proc. 4th Int. Conf. on WORDS. Univ. of Turku. 2003. P.411-418.

14. Ananichev D. S., Petrov I. V., Volkov M. V. Collapsing words: a progress report// Int. J. Found. Comput. Sei. V.17. No.3. 2006. P.507-518.

15. Ananichev D. S., Volkov M. V. Collapsing words vs. synchronizing words// B kh. W. Kuich, G. Rozenberg, A. Salomaa (eds.) Developments in Language Theory, Lect. Notes Comp. Sei., SpringerVerlag, Berlin-Heidelberg-New York. V.2295. 2002. P.166-174.

16. Ananichev D. S., Volkov M. V. Synchronizing generalized monotonic automata// Theor. Comput. Sei. 2005. V.330. P.3-13.

17. Arnold F., Steinberg B. Synchronizing groups and automata// Theor. Comput. Sei. 2006. V.359. P.101-110.

18. Benenson Y., Adar R., Paz-Elizur T., Keinan E., Livneh Z., Shapiro E. DNA molecule provides a computing machine with both data and fuel// Proc. National Acad. Sei. USA. 2003. V.100. P.2191-2196.

19. Berstel J. Transductions and context-free languages// Teubner, Stuttgart. 1969.

20. Cerny J. Poznamka k homogennym eksperimentom s konecnymi auto-matamij/ Mat.-Fyz. Cas. Slovensk. Akad. Vied. 1964. V.14. P.208-216. in Slovak]

21. Cherubini A. Synchronizing and collapsing words// Milan J. of Math. 2007. V.75. No.l. P.305-321.84

22. Cherubini A., Gawrychowski P., Kisielewicz A., Piochi B. A combinatorial approach to collapsing words// Mathematical Foundations of Computer Science, Lect. Notes Comp. Sci., SpringerVerlag, Berlin-Heidelberg-New York. 2006. V.4162. P.256-266.

23. Cherubini A., Kisielewicz A. Recognizing collapsing words is co-NP complete// B kh. H.Leung, G.Pighizzini (eds.) Descriptional Complexity of Formal Systems, Las Cruces-New Mexico. 2006. P.106-117.

24. Cherubini A., Kisielewicz A. Collapsing words, permutation conditions and coherent colorings of trees// Theor. Comp. Sci. 2009. V.410. P.2135-2147.

25. Cherubini A., Kisielewicz A., Piochi B. A bound for the length of shortest 2-collapsing words// B kh. P. Arnoux, N. Bedaride, J. Cassaigne (eds.) Proc. 6th Int. Conf. on WORDS. 2007. P.90-99.

26. Cherubini A., Kisielewicz A., Piochi B. On the length of shortest 2-collapsing words// Discrete Math. Theor. Comput. Sci. 2009. V.ll. No.l. P.33-44.

27. Cook S. A. The complexity of theorem-proving procedures// Proc. of the 3rd IEEE Symp. on the Foundations of Computer Science. 1971. P.151-158.

28. Crochemore M., Mignosi F., Restivo A. Minimal Forbidden Words and Factor Automata// MFCS '98: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag, Berlin-Heidelberg-New York. 1998. P.665-673.

29. De Bruijn N. G. A combinatorial problem// Indagationes Math. 1946. V.8. P.461-467.

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

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

32. Fici G., Mignosi F., Restivo A., Sciortino M. Word assembly through minimal forbidden factors// Theor. Comput. Sci. 2006. V.359. P.214-230.85

33. Gallant J., Maier D., Storter J. On finding minimal length superstrings// Journal of Computer and System Sciences. 1980. V.20. P.50-58.

34. Giambruno L., Restivo A. An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid// RAIRO Theor. Inform, and Appl. 2008. V.42. No.3. R503-524.

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

36. Hall M. A topology for free group and related groups// Ann. Math. 1950. V.52. P.127-139.

37. Higgins P. M. The range order of a product of i transformations from a finite full transformation semigroup// Semigroup Forum. 1988. V.37. P.31-36.

38. Ito M., Shikishima-Tsuji K. Some results on directable automata// B kh. Theory is forever, Lect. Notes Comp. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2004. P.125-133.

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

40. Margolis S. W., Pin J.-E., Volkov M. V. Words guaranteeing minimum image// Int. J. Foundations Comp. Sci. 2004. V.15. No.2. P.259-276.

41. Martjugin P. V. A series of slowly synchronizing automata with a zero state over a small alphabet// Inform, and Comput. 2008. V.206. P.1197-1203.

42. Mateescu A., Salomaa A. Many-valued truth functions, Gerny's conjecture and road coloring// EATCS Bull. 1999. V.68. P.134-150.

43. Restivo A. Some remarks on complete subsets of a free monoid// Quaderni de "La ricerca scientifica", CNR Roma. 1981. V.109. P.19-25.87

44. Rystsov I. К. Reset words for commutative and solvable automata// Theor. Comput. Sci. 1997. V.172. P.273-279.

45. Samotij W. A note on the complexity of the problem of finding shortest synchronizing гиоп^//Электронная публикация] Proc. Int. Conf. AutoMathA. Palermo. 2007.

46. Sandberg S. Homing and synchronizing sequences// В кн. M. Broy et al (eds.) Model-Based Testing of Reactive Systems, Lect. Notes Comput. Sci, Springer-Verlag, Berlin-Heidelberg-New York. 2005. V.3472. P.5-33.

47. Sauer N., Stone M. G. Composing functions to reduce image size// Ars Combinatoria. 1991. V.31. P.171-176.

48. Schützenberger M. P., Marcus R. S. Full decodable code word sets// IRE Trans. Inf. Theory. 1959. V.5. P.12-15.

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

50. Прибавкина, Е. В. О некоторых свойствах 2-сжимающих слов// Междунар. алгебраич. конф., посвященная 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина. Тезисы докладов. Екатеринбург: Изд-во Урал, ун-та. 2005. С.189-191.

51. Прибавкина, Е. В. 2-Сжимающие слова и проблема реконструкции последовательности// Изв. Урал. гос. ун-та. 2009. Т.12. №66. С.160

52. Pribavkina Е. V. On some properties of the language of 2-collapsing words// В кн. С. De Felice, A. Restivo (eds.) Developments in Language Theory, Lect. Notes Сотр. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2005. V.3572. P.374-384.

53. Pribavkina E. V. On some properties of the language of 2-collapsing words// Workshop on Semigroups and Automata, a joint satellite workshop to ICALP'05 and Conference on Semigroups and Languages, Lisbon. 2005. P.112-122.

54. Pribavkina E. V. On some properties of the language of 2-collapsing words// Int. J. Found. Сотр. Sci. 2006. V.17. No.3. P.665-676.

55. Pribavkina E. V. 2-Collapsing words and a sequence reconstruction problem//Электронная публикация] Proc. Int. Conf. AutoMathA. Palermo. 2007.

56. Pribavkina E. V., Rodaro E. Finiteness problem for the language of minimal synchronizing words// Tecnical report. Turku Center for Computer Science, Turku. 2008. No.891.

57. Pribavkina E. V., Rodaro E. Finitely generated synchronizing automata// В кн. A.H. Dediu, A.M. Ionescu, C. Martin-Vide (eds.) Int. Conf. LATA 2009, Lect. Notes Сотр. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2009. V.5457. P.672-683.170.