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

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

□□347Э8БЭ

На правах рукописи

Прибавкина Елена Владимировна

ВОПРОСЫ ОПТИМАЛЬНОСТИ В ТЕОРИИ СИНХРОНИЗИРУЕМЫХ АВТОМАТОВ

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

АВТОРЕФЕРАТ

1 5 ОКТ 2009

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

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

003479859

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

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

Официальные оппоненты:

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

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

доктор физико-математических наук, профессор Ф. М. Аблаев

доктор физико-математических наук, профессор В. А. Молчанов

Механико-математический факультет Московского государственного университета им. М. В. Ломоносова

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

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

Автореферат разослан " ОЬТММ 2009 г.

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

В. Д. Скарин

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

Актуальность темы. Под словом «автомат» понимается конечный етерминированный автомат, т.е. тройка si — (Q, Е, 5), где Q - конечное ножество состояний, Е - входной алфавит, и 5 - всюду определенная функция перехода, действующая из Q х Е в Q. Автомат si называется инхронизируемым, если существует слово w € А*, переводящее его в дно выделенное состояние, независимо от текущего состояния автомата, i.e. S(q,w) = S(q',w) для всех q,q' G Q. Любое слово с таким свойством азывается синхронизирующим для автомата srf.

Автоматы являются простой и удобной математической моделью дис-ретно работающих устройств (например, компьютеров). Одним из важ-ых вопросов, связанных с такими устройствами, является вопрос о воз-ожности восстановления контроля над ними в условиях неопределен-ости (неизвестного текущего состояния устройства). В этой связи естественным образом возникают понятия синхронизируемого автомата и синхронизирующего слова - сигнала, «перезагружающего» устройство, независимо от его текущего состояния. Теория синхронизируемых автоматов активно развивается с середины 60-х годов прошлого века ввиду многочисленных приложений синхронизируемых автоматов в различных областях: тестировании реактивных систем, роботике, символической динамике, биоинформатике и др., см. обзор [21]. В связи с этими приложениями возникают различные вопросы об оптимальном управлении, прежде всего, вопрос о кратчайшей возможной длине синхронизирующих слов.

С другой стороны, для математиков синхронизируемые автоматы сами по себе представляют интересный комбинаторный объект, и их изучению уделяется большое внимание, прежде всего, в связи с гипотезой Черни. Для удобства в дальнейшем автомат с п состояниями будем называть n-автоматом. Черни [5] построил серию n-автоматов над двухбук-венным алфавитом, для которых кратчайшие синхронизирующие слова имеют длину (п — I)2. Пример автомата Черни с четырьмя состояниями приведен на рис. 1. Нетрудно проверить, что слово w = baaabaaab длины 9 синхронизирует этот автомат (более того, w является единственным кратчайшим синхронизирующим для ^). Позднее Черни предположил, что эта конструкция реализует наихудший случай, т.е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — I)2. За годы, прошедшие с тех пор, было

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

В общем случае лучшая оценка длины кратчайшего синхронизирую щего слова, известная на сегодняшний день, принадлежит Пэну [15]. О показал, что для любого синхронизируемого п-автомата существует син хронизирующее слово длины не более В дальнейшем усилия был направлены на получение оценок длины кратчайших синхронизирую щих слов для различных частных классов автоматов. Одним из таки классов является рассматриваемый в первой главе диссертации клас синхронизируемых автоматов с нулем, т.е. автоматов, обладающих вы деленным состоянием 0, для которого ¿(0, а) = 0 для любой буквы а е Отметим, что этот класс является особенно важным в связи с гипотезо' Черни, так как известно, см., например, [20, предложение 3], что ее до казательство в общем случае сводится к доказательству в двух частны случаях: когда автомат обладает нулем, и когда граф автомата являете сильно-связным, т. е. каждое состояние достижимо из любого другого.

Что касается алгоритмов поиска коротких синхронизирующих ело то лучший алгоритм, известный на сегодняшний день, выдающий в слу чае синхронизируемости автомата некоторое синхронизирующее его ело во, был найден Эпштейном в [11]. Он работает за время 0(|<5|3) и находи синхронизирующее слово длины 0(|<5|3). Например, для автомата Чер ни этот алгоритм находит слово V = ЬааЬаЬаааЪ длины 10. Слово не является кратчайшим синхронизирующим, однако оно является оп тимальным в том смысле, что ни один его более короткий фактор н

вляется синхронизирующим. В диссертации слова с таким свойством азываются минимальными синхронизирующими. Известно, что задача оиска кратчайших синхронизирующих слов для данного автомата рудна и со-ИР-трудна одновременно [17], поэтому с практической точи зрения имеет смысл поиск именно минимальных синхронизирующих лов. Отметим, что таких слов для данного синхронизируемого автома-а может быть бесконечно много: например, для любого натурального слово Ьа3Ь*а36 является минимальным синхронизирующим для авто-1ата Черни ^4. Для автомата на рис. 2, напротив, существует лишь ва минимальных синхронизирующих слова (они же являются кратчай-ими синхронизирующими): = аЬаЬ п и)2 = ЬЬаа. Синхронизируемые

Рис. 2: Конечно порожденный автомат «04

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

Предположим, что некоторое вычислительное устройство состоит из ескольких различных синхронизируемых автоматов с одинаковым чис-ом состояний, которые работают параллельно. Тогда, чтобы «переза-рузить» систему, нужно одновременно синхронизировать каждый из их. Это приводит к понятию универсальных синхронизирующих слов. усть п - натуральное число. Слово го £ £* называется универсальным -синхронизирующим или кратко п-синхронизирующим, если оно син-ронизирует все синхронизируемые автоматы с п+1 состоянием над фиксированным алфавитом [4]. Понятие синхронизируемое™ можно обобщить, расширив область применения на несинхронизируемые автоматы. Автомат — (<2, Е, <5) (не обязательно синхронизируемый) называется

п-сжимаемым, если существует слово такое, что |<2| — (¿(<2,

п (при этом говорят, что слово ги сжимает автомат ¿г/ на п состо ний). Слово т е Е* называется п-сжимающим, если оно сжимает на состояний все п-сжимаемые автоматы с входным алфавитом Е. Поняти универсальных синхронизирующих и универсальных сжимающих ело сами по себе выглядят вполне естественно с точки зрения теории а томатов, помимо этого они находят приложения и в алгебре [3]. Други их возможным приложением является управление устройством-«черны ящиком», т.е. автоматом, для которого не известно ни его внутренне строение, ни состояние, в котором он находится. Применение униве сального синхронизирующего или универсального сжимающего слова такому автомату уменьшает неопределенность в его поведении настол ко, насколько это возможно.

Ввиду возможных приложений возникают вопросы об алгоритм-распознавания п-синхронизирующих и п-сжимающих слов, оптимально длине таких слов, а также о способах построения примеров коротких синхронизирующих и п-сжимающих слов. С точки зрения теории фо мальных языков, интересен вопрос о месте языка всех п-сжимающи слов над заданным алфавитом в классической иерархии Хомского. Ис следованию указанных вопросов посвящены работы [2,4,6-10,12,14]. третьей главе диссертации эти вопросы исследуются для первого нетри виального случая п = 2.

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

Научная новизна. Результаты являются новыми.

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

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

Ссылки на результаты диссертации присутствуют в работах других авторов: [3,6-10,14].

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

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

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

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

В первой главе диссертации строится серия медленно синхронизируемых автоматов с нулем над произвольным алфавитом. Для формулировки основного результата этой главы дадим необходимые определения. Введем в рассмотрение функцию Черни £(п) как наибольшую длину кратчайших синхронизирующих слов для синхронизируемых п-автоматов. Для класса zero автоматов с нулем известна верхняя оценка функции Черни €zero(n) < см. напр. [1]. В той же работе для

каждого п был построен синхронизируемый п-автомат с нулем, имег щий п — 1 входной символ, для которого кратчайшее синхронизирующи слово имеет длину в точности . Особенность этого примера состой в том, что число букв растет вместе с числом состояний, что контраст рует с примером Черни, где число букв не зависит от числа состояни Таким образом, вопрос об определении нижней границы функции Черн для класса автоматов с нулем над фиксированным алфавитом остае ся открытым. В 2007 году Мартюгин с помощью компьютерных эксп риментов построил серию синхронизируемых п-автоматов с нулем на двухбуквенным алфавитом, кратчайшие синхронизирующие слова дл которых имеют длину + о(п2) [13]. Отметим, что конструкция из [1 весьма нетривиальна и, кроме того, не обобщается на случай ббльши алфавитов. Чтобы придать точный смысл последнему утверждению, н зовем синхронизируемый автомат = (С^, Е, 5) существенным, есл каждая буква алфавита £ входит в каждое синхронизирующее данны автомат слово. Иначе говоря, каждая буква является существенной дл синхронизации такого автомата. Ясно, что задачу об оценке функци Черни уместно ставить именно для существенных автоматов, а доба ление новых букв к автоматам из конструкции Мартюгина приводит тому, что они перестают быть существенными. Основным результате главы 1 диссертации является следующая теорема:

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

Конструкция основана на комбинаторных свойствах непокрывающи множеств в свободных моноидах. Дадим соответствующее определени Пусть X - конечное множество слов над алфавитом Е. Слово и) 6 £ называется покрываемым в X*, если и является фактором некоторог слова из X*, в противном случае V) называется непокрываемым. Гов рят, что множество X является покрывающим, если любое слово на алфавитом Е является покрываемым в X*. В противном случае X непокрывающее множество. Понятие покрывающих множеств возникл в связи с некоторыми задачами теории кодирования. В частности, из вестная в теории кодирования теорема (см., например, [19]) утверждае

что в случае, когда множество X является кодом, т.е. любое слово из X* представляется единственным образом в виде конкатенации слов из X, множество X - покрывающее тогда и только тогда, когда X - максимальный код. Некоторые свойства покрывающих и непокрывающих множеств изучались в [16].

В §1.1 приводятся необходимые определения и доказывается предложение о длине кратчайшего непокрываемого слова для непокрывающего множества вида X = Ек \ {и}. В §1.2 дается определение полуцветочного автомата для конечного множества слов, а в §1.3 устанавливается взаимосвязь между непокрываемыми в некотором множестве X словами и словами, синхронизирующими полуцветочный автомат для множества X. Далее доказывается основная теорема 1. Стоит отметить, что конструкция из теоремы 1 приводит к тому же порядку роста длины кратчайшего синхронизирующего слова, что и конструкция, предложенная в [13], но существенно отличается от последней отсутствием ограничений на число входных букв, а также большей прозрачностью. Важно и то, что она была найдена не с помощью компьютерного перебора, а как результат анализа взаимосвязей между комбинаторными объектами разной природы (кодами и автоматами), что представляет собой и самостоятельный интерес.

Во второй главе вводится понятие минимальных синхронизирующих слов, обобщающих понятие кратчайших синхронизирующих слов. Напомним, что слово называется минимальным синхронизирующим для данного автомата, если оно синхронизирует этот автомат, однако ни один его собственный фактор не является синхронизирующим. Далее рассматривается класс Рв синхронизируемых автоматов, обладающих лишь конечным числом минимальных синхронизирующих слов. Такие автоматы называются конечно порожденными. В §2.1 найдена характеризация класса ЕС, на основе которой получаются все остальные результаты главы. Для ее формулировки дадим несколько вспомогательных определений. Зафиксируем синхронизируемый автомат ~ Е, 5). Подмножество 5 множества называется достижимым, если существует слово т е Е*, что т) = 5. Для подмножества 5 множества С? через С (Б) будем обозначать множество всех слов, стабилизирующих 3:

С(5) = {Ш€ Е* \ ¿(Б, = Б}.

Через обозначим множество всех слов, синхронизирующих 5:

7г(5) = {ш е Е* | |5(5,«»)| = 1}.

Для произвольного слова го € II* через гп(ги) обозначим максимальное п включнению подмножество множества такое, что 5(т(ю), ги) — т(ю).

Теорема 2. Пусть $4 = {С}, Е, 5) - синхронизируемый автомат. Тогд следующие условия эквивалентны:

(г) ¿г/ е

(и) для любого неодноэлементного достижимого подмножества Б '¡-¿Сд, для любого т 6 С (5) выполняется равенство

71(5) = 7г(т(ш)).

В §2.4 оценивается функция Черни для класса конечно порожденны автоматов. Нетрудно показать, что > п — 1. Основным результа

том этого параграфа является следующая теорема:

Теорема 5. Пусть = {(2,Е,<5) - конечно порожденный синхрони зируемый п-автомат. Тогда для него существует синхронизирующе слово длины, не превосходящей 3п — 5.

Еще одной интересной задачей, связанной с конечно порожденным автоматами, является задача проверки данного синхронизируемого авто мата на принадлежность классу ЕС. Сформулируем формально задач ПШТЕИЕЗЭ:

УСЛОВИЕ: Синхронизируемый автомат ¿эГ = (С},Е,6).

ВОПРОС: Конечен ли язык

В §2.2 на основе приведенной выше характеризации класса ЕС полу чен алгоритм ЕшСнеск проверки данного синхронизируемого автомат на принадлежность этому классу:

ЕШСнеск(^):

1 По данному я? — {<5, Е, 8) построить автомат подмножеств Т>{я/) = (<2, Е,5), состоящий лишь из подмножеств, достижимы из СЦ.

2 Для каждого состояния S € Q выполнять:

2.1 Для каждого состояния Т G Q: S С Т выполнять: 2.2 Если C(T)nC(S)¿0

2.3 Если 7Z(T) ф 7Z(S), то выйти и вернуть N0

3 Иначе выйти и вернуть YES

В §2.3 доказана теорема о временной сложности алгоритма FinCheck:

Теорема 3. Пусть синхронизируемый автомат si имеет п состояний. Алгоритм FinCheck^J осуществляет проверку конечности языка Sf(¿f) за 0(12п) операций.

Алгоритм FinCheck, основанный на характеризации конечно порожденных автоматов, имеет меньшую сложность, чем «наивный» алгоритм, рассмотренный в §2.1. Тем не менее он остается экспоненциальным от числа состояний исходного автомата. В §2.6 доказывается, что при стандартных в теории сложности предположениях для задачи FINITENESS не существует полиномиального алгоритма:

Теорема 7. Задача FINITENESS co-NP-трудна.

Этот результат доказывается с использованием двойного полиномиального сведения известной труднорешаемой задачи ВЫПОЛНИМОСТЬ к данной. При этом используется вспомогательная задача ДОСТИЖИМОСТЬ вместе с некоторым специальным множеством I ее конкретизации. Эта задача формулируется следующим образом:

УСЛОВИЕ: Автомат .с/ = (Q, Е, 5) и подмножество Я С Q.

ВОПРОС: Существует ли слово wsS* такое, что ó(Q,w) = Я?

Сначала задача ДОСТИЖИМОСТЬ, рассматриваемая для множества конкре-тизаций I, полиномиально сводится к дополнению задачи FINITENESS. Далее произвольная конкретизация задачи ВЫПОЛНИМОСТЬ полиномиально сводится к конкретизации задачи ДОСТИЖИМОСТЬ, принадлежащей множеству I. Результатом такого двойного сведения является входной автомат для задачи FINITENESS, число букв в алфавите которого зависит от числа его состояний. В §2.7 с помощью подходящего кодирования букв этого алфавита словами над двухбуквенным алфавитом этот автомат модифицируется в автомат над трехбуквенным алфавитом, откуда следует основной результат:

Теорема 8. Задана FINITENESS co-NP-трудна для автоматов над по стоянным алфавитом А, |Д| > 2.

Третья глава посвящена некоторым вопросам оптимальности, свя занным с 2-сжимающими и 2-синхронизирующими словами. В §3.1 фор мулируется известный теоретико-групповой критерий 2-сжимаемости сл ва и приводятся некоторые следствия из него, адаптированные для ис пользования в доказательствах основных результатов главы. §3.2 посвя щен вопросу об оптимальной длине 2-сжимающих слов. Обозначим чере c(n,i) длину кратчайших n-сжимающих слов над í-буквенным алфави том. Лучшие известные на сегодняшний день оценки функции с(п, t) бы ли найдены в работе [12]:

tn + n- 1 < c(n, t) < t^n+1) +{п + 1 )Мп+1)~1 + ■ ■ ■ + (п - l)í.

В первом нетривиальном случае п — 2 из предыдущего неравенства по лучаем

í2 -Ь 1 < е(2, t) <t3 + 3í2 +1.

Известно два точных значения с(2,2) = 8 [18] и с(2,3) = 21 [2]. Кром того, известно, что с(2,4) < 56, с(2,5) < 119 [10]. Керубини, Кисиле вич и Пьоки [10] улучшили верхнюю оценку функции с(2, t) на осно ве комбинаторной характеризации 2-сжимающих слов, найденной в [7] А именно, в [10] показано, что c(2,í) < в §3.2 диссертации н

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

Теорема 10. Длина произвольного 2-сжимающего слова над t-буквен ным алфавитом не меньше 2t2.

Полученная оценка точна для t = 1,2, а для t = 3 дает значение 18 что довольно близко к известному точному значению с(2,3) = 21.

Рассмотрим язык Cn(t) всех n-сжимающих слов над í-буквенным ал фавитом для t > 1 и п > 1. Известно, что этот язык не является регуляр ным [4]. (Подробное доказательство этого утверждения приведено в [4 только для случая п = 2.) С другой стороны, Cn(t) является контекстн зависимым [14]. Тем самым, для окончательного выяснения положен и

зыка Cn(t) относительно классической иерархии Хомского, остается вы-снить, является ли этот язык контекстно свободным. В §3.3 этот вопрос ешается для двухбуквенного алфавита:

еорема 11. Язык 0^(2) не является контекстно свободным.

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

Что касается алгоритмов распознавания n-синхронизирующих и п-жимающих слов, то они не являются практически пригодными: из-естно, что задача распознавания n-сжимающих слов co-NP-полна [8], язык <S„(i) всех n-синхронизирующих слов над ¿-буквенным алфави-ом хоть и является регулярным, но распознается автоматом с числом остояний, экспоненциально зависящим от п. Следовательно, представ-яют интерес модификации существующих алгоритмов распознавания зыков ¿>2(í) и ^(í), ускоряющие их работу. Автором диссертации в §3.6 редложена такая модификация на основе реконструкции 2-сжимающих 2-синхронизирующих слов по некоторому специальному множеству их акторов. Кроме того, такой подход позволяет находить более короткие -сжимающие и 2-синхронизирующие слова по существующим приме-ам. Так, применяя алгоритм реконструкции к 2-сжимающему слову

Wi2o = babeaebea2b2eabe2ab • aeacebcaeac2 e2cbe ■ cabac2bacbcacb2a2c ■ баб-• dadbda2b2dabd2ab • adacdbcadac2d2cbdca ■ cedbeacdebdedbedade2d2ecedce

ад 5-буквенным алфавитом из работы [9], удалось получить более ко-откое 2-сжимающее слово длины 119 (получающееся из слова Wí2о уда-ением первой буквы b) и еще три 2-сжимающих слова длины 119. При-еняя алгоритм к 2-сжимающему слову

Wsq = cabac2bacbcacb2 а2 с • babdadbda2b2dabd2abada ■ cdbcada(?d2cbdca

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

cabacb2a2cbcacbac2 • babdadbda2b2dabd2abada • cdbcadac2d2cbdca cabacbcacb2a2cbac2 ■ ba,bdadbda¿b2dabd2 abada ■ cdbcadac2d2cbdca cabac?bacb2a2cbcac • babdadbda2b2dabd2abada • cdbcadac2d?cbdca.

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

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

• Построена новая серия медленно синхронизируемых автоматов нулем над произвольным алфавитом.

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

• Получена новая нижняя оценка длины кратчайших 2-сжимающи слов; построены новые примеры коротких 2-сжимающих слов.

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

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

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

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

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

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

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

[4] Ananichev D. S., Volkov M. V. Collapsing words vs. synchronizing words)/ В кн. W. Kuich, G. Rozenberg, A. Salomaa (eds.) Developments in Language Theory, Lect. Notes Сотр. Sci., Springer-Verlag, Berlin-Heidelberg-New York. V.2295. 2002. P.166-174.

[5] Cerny J. Poznámka к homogénnym eksperimentom s konecnymi auto-matami/f Mat.-fyz. Cas. Slovensk. Akad. Vied. 1964. V.14. P.208-216. [in Slovak]

[6] Cherubini A. Synchronizing and collapsing words// Milan J. Math. 2007. V.75. No.l. P.305-321.

[7] Cherubini A., Gawrychowski P., Kisielewicz A., Piochi B. A combinatorial approach to collapsing words// Mathematical Foundations of Computer Science, Lect. Notes Сотр. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2006. V.4162. Р.2Б6-266.

[8] Cherubini A., Kisielewicz A. Collapsing words, permutation conditions and coherent colorings of trees// Theor. Сотр. Sci. 2009. V.410. P.2135-2147.

[9] Cherubini A., Kisielewicz A., Piochi B. A bound for the length of shortest 2-collapsing words// В кн. P. Arnoux, N. Bédaride, J. Cassaigne (eds.) Proc. 6th Int. Conf. on WORDS. 2007. P.90-99.

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

11] Eppsteín D. Reset sequences for monotonic automata// SIAM J. Comput. 1990. V.19. P.500-510.

12] Margolis S. W., Pin J.-E., Volkov M. V. Words guaranteeing minimum image// Int. J. Foundations Сотр. Sci. 2004. V.15. No.2. P.259-276.

13] 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.

14] Petrov I. V. An algorithm for recognition of n-collapsing words// Theor. Comput. Sci. 2008. V.391. P.99-108.

15] Pin J.-E. On two combinatorial problems arising from automata theory// Ann. Discrete Math. 1983. V.17. P.535-548.

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

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

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

[19] Schiitzenberger M. P., Marcus R. S. Full decodable code word sets// IRE Tran Inf. Theory. 1959. V.5. P.12-15.

[20] Volkov M. V. Synchronizing automata preserving a chain of partial orders/ B kh. J.Holub and J. Zdirek (eds.), Proc. 12th Int. Conf. CIAA 2007, Lect Notes Comp. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2007. V.4783 P.27-37.

[21] Volkov M. V. Synchronizing automata and the C'erny conjecture// B kh C. Martin-Vide, F. Otto, H. Fernau (eds.), LATA 2008, Lect. Notes Comp. Sci. Springer-Verlag, Berlin-Heidelberg-New York. 2008. V.5196. P.ll-27.

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

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

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

[25] Pribavkina E. V. On some properties of the language of 2-collapsing words/ Workshop on Semigroups and Automata, a joint satellite workshop t 1С ALP'05 and Conference on Semigroups and Languages, Lisbon. 2005 P.112-122.

[26] Pribavkina E. V. On some properties of the language of 2-collapsing words/ Int. J. Found. Comp. Sci. 2006. V.17. No.3. P.665-676.

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

[28] Pribavkina E. V., Rodaro E. Finiteness problem for the language of minima synchronizing words// Tecnical report. Turku Center for Computer Science

T\irku. 2008. No.891. [29] Pribavkina E. V., Rodaro E. Finitely generated synchronizing automata// kh. A.H. Dediu, A.M. Ionescu, C. Martin-Vide (eds.) Int. Conf. LATA 2009 Lect. Notes Comp. Sci., Springer-Verlag, Berlin-Heidelberg-New York. 2009 V.5457. P.672-683.

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

2007.

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

Введение

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

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.