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

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

На правах рукописи Петров Илья Владимирович

УНИВЕРСАЛЬНЫЕ СИНХРОНИЗИРУЮЩИЕ И УНИВЕРСАЛЬНЫЕ СЖИМАЮЩИЕ СЛОВА

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

АВТОРЕФЕРАТ

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

П . | ■

I

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

003471406

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

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

кандидат физико-математических наук, доцент Д. С. Ананичев

Официальные оппоненты: доктор физико-математических наук,

профессор Ф. М. Аблаев

кандидат физико-математических наук, старший научный сотрудник А. Э. Фрид

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

Тольятгинский государственный университет

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

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

Автореферат разослан « /Г» мая 2009 г.

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

ст. н. с.

В. Д. Скарин

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

Актуальность. Детерминированным конечным автоматом {ДКА) наг зывается тройка £/ = {(¡), Е, 6), где — конечное множество состояний, Е — конечный входной алфавит, и 5 — всюду определенная функция переходов, действующая из ф х Е в С?. Действие букв из Е на множество состояний <3, определяемое функцией переходов 5, естественным образом расширяется до действия слов из Е*, которое также будем обозначать через 6. Кроме того, для произвольного слова V £ Е* и произвольного ЯСС} определим образ множества К под действием слова V следующим образом:

ДКА л/ — {<5, £, 5) называется синхронизируемым, если найдется такое слово ги 6 Е*, что |<5(<3,го)| = 1, т. е. действие слова и) отображает все состояния этого автомата в некоторое одно состояние; говорят, что такое слово го синхронизирует автомат . Если мы имеем несколько одинаковых синхронизируемых автоматов, работающих независимо и находящихся в различных состояниях, то после одновременного применения ко всем этим автоматам синхронизирующего их слова все они окажутся в одном и том же состоянии — тем самым, дальнейшая работа этих автоматов под действием единого потока сигналов будет синхронизирована. Можно считать, что данное слово выполнило 'сброс' всех этих автоматов в 'начальное' состояние. Другим важным применением синхронизации является ситуация, когда у нас имеется один синхронизируемый автомат, но мы не знаем, в каком состоянии он находится. Тогда применение синхронизирующего этот автомат слова переведет его в заранее известное нам состояние. Некоторые другие способы использования синхронизации можно найти в работах [19; 23].

Понятие синхронизируемости можно обобщить, расширив область применения на несинхронизируемые автоматы. Возьмем произвольное натуральное число п. ДКА = (СЦ, Е, 8} называется п-сжимаемым, если найдется такое слово и; е Е*, что |5((3,и>)| < — п. Говорят, что такое слово ги сжимает автомат з/ на п состояний. Сжатие автомата, как и синхронизация. позволяет уменьшить неопределенность его поведения, так как непосредственно после применения к автомату сжимающего его слова этот автомат не может находиться в некоторых заранее известных состояниях.

Одним из первых понятие синхронизируемости сформулировал Черни (бешу)

в 1964 году, в работе [11]. В этой же работе Черни высказал гипотезу, вызвавшую наибольший интерес в области синхронизации:

Гипотеза 1 (Сегпу, 1964). Любой синхронизируемый ДКА = {<5,Е,5) может быть синхронизирован словом длины не большей, чем (|<3| — I)2.

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

(см. [2; 10; 15; 17;28; 32]), а в общем случае получена только кубическая верхняя оценка ^ (см. [1]). В 1983 году Пэн (Pin) в работе [24] высказал гипотезу, обобщающую гипотезу Черни:

Гипотеза 2 (Pin, 1983). Любой п~сжимаемый ДКА может, быть сжат на п словом длины не большей, чем п2.

Однако, Кари (Kari) в 2000 году опроверг эту гипотезу [20], построив автомат с 6-ю состояниями такой, что кратчайшее сжимающее этот автомат на 4 состояния слово имеет длину 17 = 42 +1. Других примеров, опровергающих данную гипотезу, пока не найдено.

В работе [17] Эпштейн (Eppstein) показал, что проверить возможность синхронизации данного автомата sä = (Q, Е, S) можно за время 0(|£||Q|2), используя 0(|<2|2) пространства, а найти некоторое синхронизирующее его слово можно за время 0(|E||Q|2 + |Q|3); длина такого слова + 0(|Q|2). Оказалось, что используя те же идеи, можно за время 0(|E||Q|2+|Q|3+n|<2|2) проверить, является ли данный автомат sä n-сжимаемым. Кроме того, Са-ломаа (Salomaa) [29] и Эпштейн [17] доказали, что задача, в которой для заданного автомата ¡é и заданного натурального числа L требуется определить, имеет ли автомат sä синхронизирующее слово длины не больше L, является NP-полной. А недавно Самотий (Samotij) показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат sä, имеет длину ровно L, является одновременно iVP-трудной и co-NP-трудной [30].

Возьмем произвольное натуральное число п. Слово tí) € Е* называется:

• универсальным п-синхронизирующим словом, если оно синхронизирует каждый синхронизируемый автомат sä = {Q, Е, 6) со входным алфавитом Е, у которого \Q\ = п + 1;

• универсальным п-сжимающим словом, если оно сжимает на п каждый гс-сжимаемый ДКА со входным алфавитом Е.

Для краткости такие слова называют n-синхронизирующими и «-сжимающими соответственно, опуская прилагательное 'универсальное'. Заметим, что каждое тг-сжимающее слово является n-синхронизирующим, так как каждый синхронизируемый автомат с п + 1 состоянием является n-сжимаемым, и для него синхронизация совпадает с сжатием на п состояний. Таким образом n-сжимающие слова являются более мощными по своей сути.

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

слово. Одна из таких ситуаций описана в работах [3;4], где автоматами и словами являются молекулы, и весь процесс происходит во взаимодействии растворов, содержащих молекулы-автоматы и молекулы-слова; конечно же, разбирать раствор на отдельные молекулы-автоматы не представляется возможным. Другим естественным вариантом применения универсального синхронизирующего слова является решение задачи синхронизации классов автоматов при условии, что нам удобнее вместо множества отдельных синхронизирующих слов хранить одно единственное слово. Приведенные рассуждения можно в равной степени отнести и к универсальным сжимающим словам. Оба введенных понятия выглядят вполне естественно с точки зрения теории автоматов и в то же время отлично вписываются в классический подход Мура (Moore) [22]: применение универсального синхронизирующего или универсального сжимающего слова к автомату-'черному ящику', для которого мы не знаем ни внутреннее строение, ни состояние, в котором автомат находится, уменьшает неопределенность в его поведении.

Понятие универсальных синхронизирующих слов неявно рассматриваг лось в работе [16] 1983 года и было явно введено в 2002 году в работе [9]. Понятие универсальных сжимающих слов в литературе впервые появилось (под другим названием) в начале 1990х годов в связи с задачами комбинаторики и абстрактной алгебры [25; 31]. В последнее время идет интенсивное изучение универсальных синхронизирующих и универсальных сжимающих слов, их связей с теорией автоматов, теорией сложности вычислений и теорией формальных языков [12; 14; 18; 26]. Кроме того, недавно были найдены новые приложения универсальных сжимающих слов [5; 6; 27].

Легко показать, что универсальные п-синхронизирующие слова существуют для каждого алфавита и каждого значения параметра п, но не так просто показать это для универсальных п-сжимающих слов. Дело в том, что в определении последних количество состояний у автоматов неограничено сверху, и одно и то же универсальное n-сжимающее слово должно сжимать на п бесконечное число n-сжимаемых автоматов. В работе [31] эта задача была решена: Зауэр (Sauer) и Стоун (Stone) привели рекурсивный способ построения n-сжимающих и n-синхронизирующих слов. Правда, длина получающихся слов является дважды экспоненциальной функцией от п. Позже оказалось, что та же самая идея может привести к серии более коротких слов; а именно, в работе [21] авторы показали, что можно построить слова с

длиной 0(|S| а ). И все-таки эта длина достаточно велика, а на практике интересуют именно короткие слова. В связи с этим возникают следующие задачи, сформулированные в работах [9] и [31]:

Задача 1. Определить длины s(n,k) и с(п,к) кратчайших п -синхронизирующих и п-сжимающих слов над к-буквенным алфавитом для всех значений пик.

Задача 2. Найти кратчайшие п-синхронизирующие и п-сжимающие сл ва над к -буквенным алфавитом для заданных значений пик.

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

Занимаясь изучением универсальных синхронизирующих и универсаль ных сжимающих слов, невозможно обойти стороной такую базовую задач} как их распознавание. Проверить, является ли заданное слово № 6 Е* уни версальным п-синхронизирующим словом, можно по определению, т. е. пере брать все автоматы сп+1 состоянием и входным алфавитом Е и убедиться, что слово и) синхронизирует все синхронизируемые автоматы из этого спис ка. Однако, тот же подход не работает для универсальных п-сжимающи: слов: мы снова сталкиваемся с бесконечным числом автоматов, участвующих в определении. Таким образом, имеем нетривиальную задачу:

Задача 3. Построить для каждого натурального числа п алгоритм прс верки входного слова и) £ Е* на п-сжимаемость.

В работе [8] задача распознавания п-сжимающих слов была сформулирована и решена для первого нетривиального случая п = 2. Более наглядна: версия этого решения была представлена в работе [7].

Для п > 2 задача распознавания п-сжимающих слов оставалась открытой на протяжении нескольких лет. Для начала автору диссертации удалое показать, что язык С„(Е) всех п-сжимающих слов над алфавитом Е является рекурсивным подмножеством множества Е*. Для этого достаточно был найти для каждого п вычислимую функцию /„ : N —> N такую, что слов и> £ Е* является п-сжимающим тогда и только тогда, когда ю сжимает н п каждый п-сжимаемый ДКА ¡г4 = (<2,Е,5), у которого |<3| < /П(М)- Дей" ствительно, имея такую функцию /„, достаточно проверить слово ги лишь на, конечном числе автоматов, и либо будет найден контрпример, либо п выбору функции /п будет следовать, что слово V) является п-сжимающим.

Конечно, теперь можно утверждать, что мы имеем алгоритм, распознающий п-сжимающие слова, для каждого п, но этот алгоритм должен просмотреть тт1£' автоматов, где т = /п(М) > и> учитывая, что универсальны сжимающие слова имеют достаточно большую длину, мы тут же приходим выводу о практической непригодности данного алгоритма. А на чем мы могли бы сэкономить время работы? Ответ очевиден: мы никак не использовали для подбора тестовой базы автоматов знания о слове т, кроме его длины.

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

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

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

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

Публикации. Основные результаты диссертации опубликованы в работах [33-36], две из которых входят в состав изданий, рекомендованных ВАК. Работа [33] опубликована совместно с научным руководителем; постановка описанной в ней задачи принадлежит научному руководителю, а решение — автору диссертации. Публикация [35] также является совместной; в целом она носит обзорный характер, но в ней приведена достаточно подробная схема принадлежащего автору диссертации доказательства алгоритмической разрешимости задачи распознавания универсальных сжимающих слов.

Апробация результатов работы. Основные результаты диссертации докладывались на:

• 4-й международной конференции по комбинаторике слов WORDS'03 (Турку, Финляндия, 2003);

• международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005);

• международной школе и конференции по комбинаторике, автоматам и теории чисел CANT 2006 (Льеж, Бельгия, 2006);

• международной конференции по теоретическим компьютерным наукам CSR 2006 WOWA (Санкт-Петербург, 2006).

Ссылки на результаты диссертации присутствуют также в работах других авторов: [9;12-14;21;26].

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

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

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

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

Теорема 2.1. Для каждого слова ш б Е', не являющегося п-сжимаю-щим словом, найдется п-сжимаемый автомат ¿г/ = ((¿¿^¡б) с ограниченным числом состояний |<5| < 2|ги|(п — 1) + 2 такой, что слово ги сжимает его менее, чем на п состояний.

В доказательстве этого результата сначала показано, как из имеющегося п-сжимаемого ДКА, который не сжимается на п словом эд, можно выделить некоторое 'ядро', размер которого не превосходит (2|гу| — 1 )(п — 1) состояний. После чего показано, как можно достроить это ядро до искомого автомата-контрпримера, добавив не более п + 1 состояний.

Из линейности приведенной оценки относительно длины слова IV мы немедленно получаем недетерминированный линейный по пространству и полиномиальный по времени алгоритм распознавания дополнения языка С„(Е) всех п-сжимающих слов над алфавитом Е. Этот алгоритм угадывает контрпример в виде ДКА — (<3, Е, 5) с числом состояний |<5| < 2|ш|(п — 1) + 2 и затем проверяет, что является п-сжимаемым и что слово ю не сжимает на п этот автомат. Из существования такого алгоритма вытекают следующие следствия:

Следствие 2.2. Языки СП(Е) всех п-сжимающих слов над алфавитом Е являются контекстными.

Следствие 2.3. Задача распознавания п-сжимающих слов лежит в классе сложности со-ЫР.

Недавно Киселевич (Юв^еЬтлсг) и Керубини (СЬегиЫш) показали, что эта задача является со-ЫР-трудной [12; 13]. Таким образом, получаем, что

Следствие 2.4. Задача распознавания п-сжимающих слов са-ЫР-полна.

Основным результатом третьей главы и центральным результатом дис-ертации является алгоритм проверки универсальной сжимаемости слов:

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

Вход: слово ю е Е* и число п.

Выход: ответ на вопрос, является ли входное слово го п-сжимающим; в случае отрицательного ответа на выходе также п-сжимаемый ДКА, который словом ьз сжимается менее, чем на п состояний.

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

С другой стороны проверку можно описать следующим образом. Алгоритм оперирует классами автоматов. Он начинает работу с класса всех автоматов и работает рекурсивно. Для очередного класса автоматов алгоритм отвечает на вопрос: "существует ли в этом классе контрпример, т. е. п-сжима-емый автомат, который не сжимается на п заданным словом?". Если невозможно сразу дать ответ на поставленный вопрос, то алгоритм производит разбиение класса на конечное число подклассов и рекурсивно решает поставленную задачу для подклассов. Если найдется контрпример хотя бы в одном из подклассов, то будет найден тем самым контрпример в исходном классе, в противном случае контрпримера в исходном классе не существует. Каждый построенный алгоритмом класс автоматов привязан к некоторому префиксу проверяемого слова, и все автоматы этого класса соответствующим префиксом сжимаются одинаково (что это означает, подробно описано в диссертации). Увеличивая длину префикса на 1, алгоритм разбивает класс на подклассы, в которых автоматы сжимаются одинаково уже новым префиксом. Легко показать, что вся проверка конечна.

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

Рис. 1: Распределение слов по времени обработки.

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

Хотя размеры получающихся контрпримеров имеют тот же порядок, что дает оценка теоремы 2.1, количество перебираемых вариантов значительно меньше количества всех п-сжимаемых автоматов указанного размера. Например, если мы захотим проверить двубуквенное слово длины 130 на 3-сжимаемость, и оно окажется таковым, то, перебирая все 3-сжимаемые автоматы с двумя буквами и указанным в теореме 2.1 количеством состояний, мы должны будем просмотреть не менее 519! ~ 3 * 101185 автоматов. В то же время описанному алгоритму для проверки большинства таких сжимающих слов достаточно будет перебрать всего лишь 3 * 106 вариантов.

Указать временную сложность описанного алгоритма достаточно трудно, в первую очередь из-за того, что в самом центре алгоритма лежит перебор с возвратом, работа которого очень сильно зависит от входного слова. В связи с этим автором диссертации были проведены эксперименты для небольших алфавитов и значений параметра п, направленные на исследование времени работы описанного алгоритма. Их результаты представлены в диссертации. Эксперименты выявили удивительный факт: большая часть слов требует меньшего времени на обработку. Например, на рис. 1 приведен результат одного из экспериментов, где опять же двубуквенные слова длины 130 проверялись на 3-сжимаемость. По оси абсцисс отложено время, требуемое на проверку слова, выраженное в количестве построенных вариантов ядра автомата-контрпримера, а по оси ординат отложена доля проверенных за это время слов. Важно, что подобное распределение имеют как слова, не являющиеся универсальными сжимающими, так и универсальные сжимающие слова.

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

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

Алгоритм MFS.

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

Выход: полный список кратчайших п -синхронизирующих слов над к-буквенным алфавитом.

Алгоритм IFS.

Вход: список синхронизируемых автоматов и целое число M.

Выход: список некоторых слов, синхронизирующих все заданные автоматы; длина слов зависит от значения параметра M.

Первый алгоритм, делая полный перебор слов заданной длины, проверяет каждое слово на n-синхронизируемость. Особенностью этого алгоритма являются предложенные автором диссертации ускорения по проверке слов, позволяющие, например, слова над трехбуквенным алфавитом проверять на 2-синхронизируемость в среднем на 2-х автоматах из З9 — 19683 автоматов, участвующих в определении 2-синхронизирующих слов.

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

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

Предложение 4.1. Список кратчайших 2-синхронизирующих слов над трехбуквенным алфавитом с точностью до переобозначения букв состоит из следующих слов:

abaacacbbcbàbcbaaccb abbaaccbabcbaacacbbc abbacaccbabcbaaccbbc abbcbcaacabacabbccab abbcbcaacabaccbbacab abbcbcaacabbccabacab abbcbcacaabbccaababc abbccaabbcbcacaababc

abbccabacaacbcbbacab abbccabacabaabcbccac abbccabacabbcbcaacab abbccabbcbcaacabacab abcacaabbccaababcbca abcbaacacbbcbabccaab abcbaaccbabcbbcacaab abcbabcbbcacaabccaab

abcbabccaabcbbcacaab abcbbcacaabcbabccaab abcbcacaabbccaababca abcbccaabbccacababbc abcbccacababbccaabbc abccaabcbabcbbcacaab

Напомним, что s(n, к) и с(п, к) обозначают длины кратчайших п-синхро-низирующих и n-сжимающих слов над ^-буквенным алфавитом. Из предложения 4.1 получаем следующее следствие.

Следствие 4.1. s(2,3) = 20.

Предложение 4.2. Список кратчайших 2-сжимающих слов над трехбуквенным алфавитом с точностью до переобозначения букв состоит из следующих слов:

abaaccbabbacbabcacbcb abbccbabcacbacabcbaac abcbaacbacabaccbbacbc

abaaccbabcacbabbacbcb abbccbabcbacabcacbaac abcbaacbaccbbacabacbc

abacbabcaaccbbcacbcab abbccbacabcacbabcbaac abcbaaccbacacbbacbabc

abacbabcacbbccaacbcab abbccbacabcbabcacbaac abcbaaccbacbbacacbabc

abacbabcacbcaaccbbcab abcaabbcacbcababccabc abcbabcabbcacabccaabc

abacbbaacbcacbaccbabc abcaabbcacbcabccababc abcbabcacabbcabccaabc

abacbbccaacbabcacbcab abcaabcbcabacabbccabc abcbabcacbacabccbbaac

abacbbccaacbcacbabcab abcaabcbcabbccabacabc abcbabccaabcabbcacabc

abacbcaaccbbcacbabcab abcaacbccacbbcabcbaca abcbabccaabcacabbcabc

abacbcacbabcaaccbbcab abcaaccbbcabacbcacbab abcbacabaccbbacbaacbc

abacbcacbbaacbaccbabc abcaaccbbcacbcabacbab abcbacabcacbabccbbaac

abacbcacbbccaacbabcab abcabacabbccabcbcaabc abcbacacbbacbaaccbabc

abaccbacbbaacbcacbabc abcabacbbccaacbcacbab abcbacbbacacbaaccbabc

abaccbacbcacbbaacbabc abcabacbcaaccbbcacbab abcbaccbbacabacbaacbc (2)

abbacaacbabcbacabccac abcabacbcacbbccaacbab abcbcaabcabacabbccabc

abbacaacbacabcbabccac abcabbcacabcbabccaabc abcbcaabcabbccabaca.bc

abbacabcbacaacbabccac abcabbcacabccaabcbabc abcbcabacabbccabcaabc

abbcabacbabcacbcaaccb abcabbccabacabcbcaabc abcbcabbccabacabcaabc

abbcabacbcacbabcaaccb abcacabbcabcbabccaabc abccaabcabbcacabcbabc

abbcacbabcabacbcaaccb abcacabbcabccaabcbabc abccaabcacabbcabcbabc

abbcacbcabacbabcaaccb abcacbabcbacabccbbaac abccaabcbabcabbcacabc

abbccaacbabcabacbcacb abcacbacabcbabccbbaac abccaabcbabcacabbcabc

abbccaacbabcacbcaoacb abcacb'occaacbcabacbab abccababcaabbcacbcabc

abbccaacbabcbacabcacb abcacbcaabbcababccabc abccababcacbcaabbcabc

abbccaacbacabcbabcacb abcacbcaabbcabccababc abccabcaabbcacbcababc

abbccaacbcabacbabcacb abcacbcaaccbbcabacbab abccabcacbcaabbcababc

abbccaacbcacbabcabacb abcacbcabacbbccaacbab

Следствие 4.2. c(2,3) = 21.

Предложение 4.3. С точностью до переобозначения букв существует единственное кратчайшее 3-синхронизирующее слово над двубуквенным алфавитом:

abbabaaabbaabababbaabbbabaabaabba (3)

Следствие 4.3. з(3,2) = 33.

Легко показать, что слово (3) не является 3-сжимающим. Получаем

Предложение 4.4. с(3,2) > ¿(3,2) = 33.

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

Предложение 4.5. Следующее слово является 3-сжимающим словом над двубуквенным алфавитом:

ааЬЪЪаЬаааЬЬаЬааЬЪаЪаЬаЬааЬааЪЬааЬаЬааЬаЪаЬЪаЬЪаЪаЬЪааЬЬа (4)

Следствие 4.4. с(3,2) < 57.

Предложение 4.6. Следующее слово является 2-синхронизирующим словом над четырехбуквенным алфавитом:

аЬсаёЫЬсйсЬаЬЫЬ(1аассс1с1аа1сЬс1асаЬсЬс1аЬЬс1а (5)

Следствие 4.5. ¿(2,4) < 42.

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

Используя в качестве подслов слова из списков (1) и (2), авторы работы [14] построили примеры 2-синхронизирующих н 2-сжимающих слов над четырех- и пятибуквенным алфавитами.

В пятой главе доказано, что язык всех универсальных 2-синхронизиру-ющих слов над произвольным алфавитом замкнут относительно зеркального отображения. Это сформулировано в следующей теореме:

Теорема 5.1. Если слово ги = йхОг... а« является 2-синхронизирующим, то слово у7 = а(... а,2в, 1 также является 2-синхронизирующим.

Например, первое слово в списке (1) после прочтения справа налево переходит в 2-синхронизирующее слово ЪссааЪсЪаЬсЬЬсасааЬа, которому с точностью до переобозначения букв (а —> с, 6 —> а, с—>6) соответствует второе слово второго столбца того же списка 2-синхронизирующих слов.

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

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

1. Доказана алгоритмическая разрешимость задачи распознавания «-сжимающих слов для всех п. Показано, что эта задача лежит в классе сложности со-ИР, а язык всех п-сжимающих слов над заданным алфавитом Е является контекстным.

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

3. Предложены 2 алгоритма поиска п-синхронизирующих слов. Найдены новые примеры коротких п-синхронизирующих и п-сжимающих слов для небольших алфавитов и значений параметра п.

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

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

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

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

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

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

[3] Programmable and autonomus computing machine made of biomolecules / R. Adar, Y. Benenson, E. Keinan [et al.] // Nature. Vol. 414 №1. P. 430-434.

[4] DNA molecule provides a computing machine with both data and fuel / R. Adar, Y. Benenson, Z. Livneh [et al.] // Proceedings of the National Academy of Sciences of USA. 2003. Vol. 100. P. 2191-2196.

[5] Almeida J., Volkov M.V. Profinite identities for finite semigroups whose subgroups belong to a given pseudovariety // Journal of Algebra and Its Applications. 2003. №2. P. 137-163.

[6] Almeida J., Volkov M.V. Subword complexity of profinite words and subgroups of free profinite semigroups // International Journal of Algebra and Computation. 2006. Vol. 15 №2. P. 221-258.

[7] Ananichev D.S., Cherubini A., Volkov M.V. An inverse automata algorithm for recognizing 2-collapsing words // Lecture Notes in Computer Science: Developments in Language Theory / Eds. M. Ito, M. Toyama. Berlin-Heidelberg-New York: Springer-Verlag, 2003. Vol. 2450. P. 270-282.

[8] Ananichev D.S., Cherubini A., Volkov M.V. Image reducing words and subgroups of free groups // Theoretical Computer Science. 2003. Vol. 307. P. 77-92.

[9] Ananichev D.S., Volkov M.V. Collapsing words vs. synchronizing words // Lecture Notes in Computer Science: Developments in Language Theory (5th International Conference, Vienna, 2001). Berlin-Heidelberg-New York: Springer-Verlag, 2002. Vol. 2295. P. 166-174.

[10] Ananichev D.S., Volkov M.V. Synchronizing monotonic automata // Lecture Notes in Computer Science: Developments in Language Theory (7th International Conference, Szeged, 2003). Berlin-Heidelberg-New York: Springer-Verlag, 2003. Vol. 2710. P. 111-121.

[11] Cemy J. Pozndmka k homogennym eksperimentom s konecnymi avtomatami // Matematicko-Fyzikalny Casopis. Slovenskej Akademie Vied, 1964. Vol. 14. P. 208-216.

[12] Cherubini A., Kisielewicz A. Recognizing collapsing words is co-NP-complete // Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems / Eds. H. Leung, G. Pighizzini. Las Cruces, 2006. P. 106-117.

[13] Cherubini A., Kisielewicz A. Collapsing words, permutation conditions and coherent colorings of trees // Theoretical Computer Science. 2009. Vol. 410. P. 2135-2147.

[14] Cherubini A., Kisielewicz A., Piochi B. A Bound for the Length of Shortest 2-Collapsing Words // Proceedings of the 6th International Conference on Words / Eds. P. Arnoux, N. Bédaride, J. Cassaigne. Marseille: Institute de Mathématiques de Luminy, 2007. P. 90-99.

[15] Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Theoretical Informatics and Application. 1998. Vol. 32. P. 21-34.

[16] Duske J., Ito M. On cofinal and definite automata // Acta Cybernetica. 1983. Vol. 6. P. 181-189.

[17] Eppstein D. Reset sequences for monotonie automata // SIAM Journal on Computing. 1990. Vol. 19. P. 500-510.

[18] Gawrychowski P., Kisielewicz A. 2-Synchronizing words // Lecture Notes in Computer Science: Languages and Automata: Theory and Applications (LATA 2008) / Eds. C. Martin-Vide, F. Otto, H. Fernau. Berlin-Heidelberg-New York: Springer-Verlag, 2008. Vol. 5196. P. 221-231.

[19] Jurgensen H. Synchronization. // Proceedings of International Conference on Language and Automata Theory and Applications. Tarragona, 2007. P. 27-49.

[20] Kari J. A counter example to a conjecture concerning synchronizing words in finite automata ,// EATCS Bull. 2001. Vol. 73. P. 146.

[21] Margolis S., Pin J.-E., Volkov M.V. Words guaranteeing minimum image // International Journal of Foundations of Computer Science. 2004. Vol. 15. P. 259-276.

[22] Moore E. Gedanken-experiments with sequential machines // Annals of Mathematics Studies: Automata Studies / Eds. C. E. Shannon, J. McCarthy. Princeton: Princeton University Press, 1956. №34. P. 129-153.

[23] Natarajan B.K. An algorithmic approach to the automated design of parts orienters // Foundations of Computer Science: 27th Annual Symposium. IEEE, 1986. P. 132-142.

[24] Pin J.-E. On two combinatorial problems arising from automata theory // Annals of Discrete Mathematics. 1983. Vol. 17. P. 535-548.

[25] Identities in full transformation semigroups. / R.Pôschel, M.V. Sapir, N. Sauer [et al.] //Algebra Universalis. 1994. Vol. 31. P. 580-588.

[26] Pribavkina E.V. On some properties of the Language of 2-collapsing words // International Journal of Foundations of Computer Science. 2006. Vol. 17. P. 665-676.

[27] Reilly N.R., Zhang S. Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands //Algebra Universalis. 2000. Vol. 44. P. 217-239.

[28] Rystsov I.C. Reset words for commutative and solvable automata // Theoretical Computer Science. 1997. Vol. 172. P. 273-279.

[29] Salomaa A. Composition sequences for functions over a finite domain. // Theoretical Computer Science. 2003. Vol. 292. P. 263-281.

[30] Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // Proceedings of International Conference AutoMathA. Palermo, 2007.

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

[32] Trahtman A.N. The Cerny conjecture for aperiodic automata // Discrete Mathematics and Theoretical Computer Science. 2007. Vol. 9 №2. P. 3-10.

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

[33] Ananichev D.S., Petrov I.V. Quest for short synchronizing words and short collapsing words // Proceedings of the 4th International Conference on Combinatorics on Words (WORDS'03) / Eds. T. Harju, J. Karhumaki. Turku: Turku Centre of Computer Science General Publication, 2003. №27. P. 411-418.

[34] Petrov I.V. An algorithm for recognition of n-collapsing words // Pre-proceedings of International School and Conference on Combinatorics, Automata and Number Theory (CANT 2006: EMS Summer School). Liège: Université de Liège, 2006. Prepublication №06.002.

[35] Ananichev D.S., Petrov I.V., Volkov M.V. Collapsing words: a progress report // International Journal of Foundations of Computer Science. 2006. Vol. 17 №3. P. 507-518.

[36] Petrov I.V. An algorithm for recognition of n-collapsing words // Theoretical Computer Science. 2008. Vol. 391. P. 99-108.

Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира 19

1 Введение

1.1 Синхронизируемость и сжимаемость.

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

1.3 Универсальные сжимающие слова.

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

2 Разрешимость задачи распознавания сжимающих слов

3 Алгоритм распознавания сжимающих слов

3.1 Предварительные сведения и определения.

3.1.1 Фишки и дырки.

3.1.2 Послойное представление.

3.1.3 Строение слоя.

3.1.4 Строение слоя п-собственного автомата.

3.1.5 Метки состояний и роли букв.

3.1.6 Основа

3.1.7 Операции по изменению основы.

3.1.8 Вычисления по основе.

3.2 Алгоритм.

3.2.1 Общее описание алгоритма.

3.2.2 Проверка слова на п-полноту.

3.2.3 Генерация ролей букв.

3.2.4 Распределение ролей и начало рекурсии.

3.2.5 Шаг рекурсии (разбиение на подклассы).

3.2.6 Классы автоматов, не требующие разбиения.

3.2.7 Корректность.

3.3 Неизоморфность рассматриваемых автоматов.

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

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

4.1 Переборный алгоритм поиска кратчайших синхронизирующих слов.

4.2 Поиск сжимающих слов.

4.3 Распознаватель слов, синхронизирующих автомат

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

4.5 Результаты.

5 Зеркальный образ 2-синхронизирующих слов

1.1 Синхронизируемость и сжимаемость

Детерминированным конечным автоматом (или кратко ДКА) мы будем называть тройку srf — (Q, Е, S), где Q — конечное множество состояний, Е — конечный входной алфавит, и 5 — всюду определенная функция переходов, действующая из Q х Е в Q. Действие букв из Е на множество состояний Q, определяемое функцией переходов 5, естественным образом расширяется до действия слов из свободного Е-порожденного моноида Е* с пустым словом е; последнее действие будем также обозначать через 5. Для произвольного слова v е Е* и произвольного RQ Q мы определим действие словом v на множество R следующим образом: S(R,v) = {S(q,v)\q 6 .R}. Дефектом действия слова v на автомат назовем dfv(stf) — \Q\ — г>)|.

ДКА = (Q, Е, 5) называется синхронизируемым, если действие некоторого слова w G Е* отображает все состояния этого автомата в некоторое одно состояние, т.е. существует состояние р G Q такое, что для всех состояний q £ Q выполняется 5(q,w) = р; такое слово w будем называть синхронизирующим словом для автомата ,<г/.

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

На рис. 1 представлен пример синхронизируемого автомата. Легко проверить, что любое состояние этого автомата словом ab3ab3a отображается в состояние 2, т.е. слово ab3ab3a является синхронизирующим словом для данного автомата. Отметим, что у любого синхронизируемого автомата существует бесконечно много синхронизирующих слов, так как если мы припишем к синхронизирующему автомат слову в начало и в конец любые слова, то полученное слово по-прежнему будет синхронизировать этот автомат. Оказывается, что слово аЪ3аЪ3а не только является синхронизирующим словом для автомата Черни с 4 состояниями, но еще и кратчайшим с данным свойством.

Что же хорошего в синхронизирующем автомат слове и почему здесь уместно слово 'синхронизация' ? Для ответа представим, что мы имеем несколько одинаковых синхронизируемых автоматов, работающих независимо, и пусть каждый из этих автоматов находится в некотором состоянии, причем начальные состояния для разных автоматов могут различаться. Если мы ко всем этим автоматам одновременно применим синхронизирующее их слово, то все они окажутся в одном и том же состоянии — тем самым, дальнейшая работа этих автоматов под действием единого потока сигналов будет синхронизирована. Можно считать, что данное слово выполнило 'сброс' всех этих автоматов в 'начальное' состояние. Другим важным применением синхронизирующего автомат слова является ситуация, когда у нас имеется один синхронизируемый автомат, но мы не знаем, в каком состоянии он находится. Тогда применение синхронизирующего его слова переведет автомат в заранее известное нам состояние. Т. е. синхронизирующее автомат слово позволяет уменьшить неопределенность поведения автомата! Существует множество других применений, некоторые из них описаны в работах [23; 29].

Одним из первых понятие синхронизируемости сформулировал Черни (Сегпу) в 1964 году, в работе [15]. Черни также высказал гипотезу:

Гипотеза 1.1 (Сегпу, 1964). Любой синхронизируемый ДКА srf = (Q,E,<5) может быть синхронизирован словом длины не большей, чем (|(3| — I)2 •

С тех пор было много попыток доказать или опровергнуть эту так легко формулируемую гипотезу, но ни одна из них не увенчалась успехом. На данный момент гипотеза доказана для многочисленных классов автоматов (см. [5; 14; 19; 21; 34;38]), а в общем случае получена только кубическая верхняя оценка М (см. [1]). Сам же Черни в работе [15] построил бесконечную серию автоматов, кратчайшие синхронизирующие слова которых имеют длину (|<2| — I)2, и доказал тем самым, что данную оценку нельзя понизить.

Первой алгоритмической задачей, связанной с синхронизируемостью, является задача проверки данного автомата srf = (Q, Е, S) на синхронизируе-мость. Оказывается, что можно выполнить эту проверку за время 0(|Е||<5|2), используя 0(\Q\2) пространства (см. [21]). Для этого необходимо построить автомат на парах = где Q^ = Q х Q,

М((р,</),*) = (5(р, a), S(q, a)) V(p, g) 6 Q[2] Va G E.

После этого достаточно рассмотреть пары вида (р,р) и проверить, что из этого множества пар можно, идя по обратным ребрам автомата , достичь все остальные пары. Это условие эквивалентно тому, что любую пару (г, s) состояний автомата sf можно склеить, т. е. подходящим словом v G Е* перевести состояния г и s в некоторое состояние р.

В работе [21] Эпштейн (Eppstein) также показал, что для данного автомата = (Q, Е, 8) можно найти некоторое синхронизирующее слово за время 0(|E||Q|2 + |Q|3). Длина такого слова ^ + 0(\Q\2).

А как найти кратчайшее синхронизирующее автомат srf — (Q, Е, слово? Для этого используем автомат на подмножествах = (2®, Е, А), где 2® обозначает множество всех подмножеств множества Q, а функция Д : 2*2 х Е —> 2^ определена следующим образом:

Д(М, а) = {5{q, a)\q G М} УМ С Q Va 6 Е.

Теперь осталось найти кратчайший путь из множества всех состояний Q в некоторое одноэлементное подмножество. Такой подход дает не самую лучшую оценку на длину кратчайшего синхронизирующего автомат srf слова, а именно 2'°' — |Q| — 1, но все же позволяет найти кратчайшее слово.

Саломаа (Salomaa) [35] и Эпштейн [21] доказали, что задача, в которой для заданного автомата srf и заданного числа L требуется определить, имеет ли автомат srf синхронизирующее слово длины L, является NP-полной. По-другому эту задачу можно сформулировать так: проверить, что кратчайшее синхронизирующее слово для автомата имеет длину, не превосходящую L. Самотий (Samotij) в работе [36] также показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат имеет длину ровно L, является одновременно iVP-трудной и со - NP -трудной.

Не каждый ДКА может быть синхронизирован, но для каждого ДКА srf = (Q,E,<5) можно указать ранг автомата rk(#/) = min{|£(Q, г>)| \ v е Е*}. Ранг показывает, какое минимальное количество состояний может получиться в образе множества Q под действием различных слов; так, для синхронизируемых автоматов ранг равен 1. Как для синхронизируемых автоматов, так и для несинхронизируемых автоматов можно говорить о сжимаемости. Возьмем произвольное натуральное число п. ДКА srf = (Q, Е, S) называется п-сжимаемым, если найдется такое слово w 6 Е*, что |5(Q,w)| < — и, другими словами, dfw(я/) > п. Такое слово w называется п-сжимающим для автомата я/. Будем также говорить, что слово w сжимает данный автомат j/нап состояний. Ясно, что для любого числа 0 < и < \Q\ — rk(stf) автомат srf является п-сжимаемым.

Проверить, является ли данный автомат srf = (Q, Е, S) п-сжимаемым, можно за время 0(|E||Q|2 + \Q\3 -I- n\Q\2), используя те же идеи, что и в работе Эпштейна [21].

В 1983 году Пэн (Pin) в работе [30] обобщил гипотезу Черни:

Гипотеза 1.2 (Pin, 1983). Любой п-сжилшемый ДКА может быть сжат на п словом длины не большей, чем п2.

Однако, Кари (Kari) в 2000 году опроверг эту гипотезу [24], построив автомат с 6-ю состояниями такой, что кратчайшее сжимающее этот автомат на 4 состояния слово имеет длину 17 = 42+1. Других примеров, опровергающих данную гипотезу, пока не найдено.

Синхронизируемости и ее обобщениям посвящено множество работ, в том числе недавние работы Павла Мартюгина [2-4; 26; 27].

6 Заключение

В главе 2 показано, что для каждого слова w € Е*, не являющегося универсальным гг-сжимающим словом, найдется автомат-контрпример, имеющий не более 2|ги|(п — 1) + 2 состояний. Таким образом, языки Сп(Е) всех n-сжимающих слов над алфавитом Е являются рекурсивными для всех гг., что обобщает известный ранее результат о рекурсивности языка всех 2-сжимающих слов. Кроме того, из линейности представленной оценки следует, что, во-первых, языки Сп являются контекстными, а, во-вторых, задача распознавания тг-сжимающих слов принадлежит классу сложности co-NP.

В главе 3 определены частичные послойные автоматы (основы), задающие классы полных автоматов, и показано, как, читая проверяемое слово w, можно достраивать частичные послойные автоматы до полных автоматов с целью поиска контрпримера. Также показано, что описанные варианты достраивания приводят к неизоморфным между собой автоматам. Кроме того приведена некоторая статистика времени работы построенного таким образом алгоритма проверки слов на тг-сжимаемость.

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

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

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

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

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

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

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

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

6. Хопкрофт Дж. Алгоритм для минимизации конечного автомата // Кибернетический сборник. Новая серия. М.: Мир, 1974. Вып. 11. С. 177-184.

7. Programmable and autonomus computing machine made of biomolecules / R. Adar, Y. Benenson, E. Keinan et al.] // Nature. Vol. 414 №1. P. 430-434.

8. DNA molecule provides a computing machine with both data and fuel / R. Adar, Y. Benenson, Z. Livneh et al.] // Proceedings of the National Academy of Sciences of USA. 2003. Vol. 100. P. 2191-2196.

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

10. Almeida J., Volkov M.V. Subword complexity of profinite words and subgroups of free profinite semigroups // International Journal of Algebra and Computation. 2006. Vol. 15 №2. P. 221-258.

11. Ananichev D.S., Cherubini A., Volkov M.V. Image reducing words and subgroups of free groups // Theoretical Computer Science. 2003. Vol. 307. P. 77-92.

12. Ananichev D.S., Volkov M.V. Synchronizing monotonic automata // Lecture Notes in Computer Science: Developments in Language Theory (7th International Conference, Szeged, 2003). Berlin-Heidelberg-New York: Springer-Verlag, 2003. Vol. 2710. P. 111-121.

13. Cerny J. Poznamka к homogennym eksperimentom s konecnymi avtomatami // Matematicko-Fyzikalny Casopis. Slovenskej Akademie Vied, 1964. Vol. 14. P. 208-216.

14. Cherubini A., Kisielewicz A. Recognizing collapsing words is co-NP-complete // Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems / Eds. H. Leung, G. Pighizzini. Las Cruces, 2006. P. 106-117.

15. Cherubini A., Kisielewicz A. Collapsing words, permutation conditions and coherent colorings of trees // Theoretical Computer Science. 2009. Vol. 410. P. 2135-2147.

16. Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Theoretical Informatics and Application. 1998. Vol. 32. P. 21-34.

17. Duske J., Ito M. On cofinal and definite automata // Acta Cybernetica. 1983. Vol. 6. P. 181-189.

18. Eppstein D. Reset sequences for monotonic automata / / SI AM Journal on Computing. 1990. Vol. 19. P. 500-510.

19. Jurgensen H. Synchronization. // Proceedings of International Conference on Language and Automata Theory and Applications. Tarragona, 2007. P. 27-49.

20. Kari J. A counter example to a conjecture concerning synchronizing words in finite automata // EATCS Bull. 2001. Vol. 73. P. 146.

21. Margolis S., Pin J.-E., Volkov M.V. Words guaranteeing minimum image // International Journal of Foundations of Computer Science. 2004. Vol. 15. P. 259-276.

22. Martyugin P.V. Complexity of problems concerning reset words for commutative automata and automata with simple idempotents / / Proceedings of the 12th International Conference on Automata and Formal Languages. 2008. P. 314-324.

23. Martyugin P.V. A series of slowly synchronizable automata with a zero state over a small alphabet // Information and Computation. 2008. Vol. 206. P. 1197-1203.

24. Moore E. Gedanken-experiments with sequential machines // Annals of Mathematics Studies: Automata Studies / Eds. С. E. Shannon, J. McCarthy. Princeton: Princeton University Press, 1956. №34. P. 129-153.

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

26. Pin J.-E. On two combinatorial problems arising from automata theory // Annals of Discrete Mathematics. 1983. Vol. 17. P. 535-548.

27. Identities in full transformation semigroups. / R.Poschel, M.V. Sapir, N. Sauer et al.] //Algebra Universalis. 1994. Vol. 31. P. 580-588.

28. Pribavkina E.V. On some properties of the Language of 2-collapsing words // International Journal of Foundations of Computer Science. 2006. Vol. 17. P. 665-676.

29. Reilly N.R., Zhang S. Decomposition of the lattice of pseudovarieties of finite semigroups induced by bands //Algebra Universalis. 2000. Vol. 44. P. 217-239.

30. Rystsov I.C. Reset words for commutative and solvable automata // Theoretical Computer Science. 1997. Vol. 172. P. 273-279.

31. Salomaa A. Composition sequences for functions over a finite domain. // Theoretical Computer Science. 2003. Vol. 292. P. 263-281.

32. Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // Proceedings of International Conference AutoMathA. Palermo, 2007.

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

34. Trahtman A.N. The Cerny conjecture for aperiodic automata // Discrete Mathematics and Theoretical Computer Science. 2007. Vol. 9 №2. P. 3-10.

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

36. Ananichev D.S., Petrov I.V., Volkov M.V. Collapsing words: a progress report // International Journal of Foundations of Computer Science. 2006. Vol. 17 №3. P. 507-518.

37. Petrov I.V. An algorithm for recognition of n-collapsing words // Theoretical Computer Science. 2008. Vol. 391. P. 99-108.