Введение к работе
Актуальность темы. Под словом «автомат» понимается конечный
етерминированный автомат, т.е. тройка srf — (Q, Е, 6), где Q - конечное
ножество состояний, Е - входной алфавит, и 5 - всюду определенная
функция перехода, действующая из Q х Е в Q. Автомат srf называется
инхронизируемым, если существует слово w Є А*, переводящее его в
дно выделенное состояние, независимо от текущего состояния автомата,
i.e. 5(q, w) = <%', w) для всех q, q' Є Q. Любое слово с таким свойством
азывается синхронизирующим для автомата s4.
Автоматы являются простой и удобной математической моделью дис-ретно работающих устройств (например, компьютеров). Одним из важ-ых вопросов, связанных с такими устройствами, является вопрос о воз-ожности восстановления контроля над ними в условиях неопределен-ости (неизвестного текущего состояния устройства). В этой связи естественным образом возникают понятия синхронизируемого автомата и синхронизирующего слова - сигнала, «перезагружающего» устройство, независимо от его текущего состояния. Теория синхронизируемых автоматов активно развивается с середины 60-х годов прошлого века ввиду многочисленных приложений синхронизируемых автоматов в различных областях: тестировании реактивных систем, роботике, символической динамике, биоинформатике и др., см. обзор [21]. В связи с этими приложениями возникают различные вопросы об оптимальном управлении, прежде всего, вопрос о кратчайшей возможной длине синхронизирующих слов.
С другой стороны, для математиков синхронизируемые автоматы сами по себе представляют интересный комбинаторный объект, и их изучению уделяется большое внимание, прежде всего, в связи с гипотезой Черни. Для удобства в дальнейшем автомат с п состояниями будем называть n-автоматом. Черни [5] построил серию n-автоматов над двухбук-венным алфавитом, для которых кратчайшие синхронизирующие слова имеют длину (n — I)2. Пример автомата Черни с четырьмя состояниями приведен на рис. 1. Нетрудно проверить, что слово w = baaabaaab длины 9 синхронизирует этот автомат (более того, w является единственным кратчайшим синхронизирующим для ^). Позднее Черни предположил, что эта конструкция реализует наихудший случай, т.е. что любой синхронизируемый п-автомат обладает синхронизирующим словом длины не более (п — I)2. За годы, прошедшие с тех пор, было
Рис. 1: Автомат Черни ^4
предпринято множество попыток доказать или опровергнуть эту гипо тезу, но ни одна из них не увенчалась успехом - гипотеза доказана лиш для частных классов автоматов, и простота ее формулировки до сих по продолжает привлекать внимание многочисленных исследователей.
В общем случае лучшая оценка длины кратчайшего синхронизирую щего слова, известная на сегодняшний день, принадлежит Пэну [15]. О показал, что для любого синхронизируемого п-автомата существует син хронизирующее слово длины не более 2Lfn. В дальнейшем усилия был направлены на получение оценок длины кратчайших синхронизирую щих слов для различных частных классов автоматов. Одним из таки классов является рассматриваемый в первой главе диссертации клас синхронизируемых автоматов с нулем, т.е. автоматов, обладающих вы деленным состоянием 0, для которого 6(0, а) = 0 для любой буквы а є Отметим, что этот класс является особенно важным в связи с гипотезо' Черни, так как известно, см., например, [20, предложение 3], что ее до казательство в общем случае сводится к доказательству в двух частны случаях: когда автомат обладает нулем, и когда граф автомата являете сильно-связным, т. е. каждое состояние достижимо из любого другого.
Что касается алгоритмов поиска коротких синхронизирующих ело то лучший алгоритм, известный на сегодняшний день, выдающий в слу чае синхронизируемости автомата некоторое синхронизирующее его ело во, был найден Эпштейном в [11]. Он работает за время 0(|<5|3) и находи синхронизирующее слово длины 0(|Q|3). Например, для автомата Чер ни ^4 этот алгоритм находит слово v = baababaaab длины 10. Слово не является кратчайшим синхронизирующим, однако оно является оп тимальным в том смысле, что ни один его более короткий фактор н
вляется синхронизирующим. В диссертации слова с таким свойством
азываются минимальными синхронизирующими. Известно, что задача
оиска кратчайших синхронизирующих слов для данного автомата NP-
рудна и co-NP-трудна одновременно [17J, поэтому с практической точ-
и зрения имеет смысл поиск именно минимальных синхронизирующих
лов. Отметим, что таких слов для данного синхронизируемого автома-
а может быть бесконечно много: например, для любого натурального
слово bo36fca36 является минимальным синхронизирующим для авто-
іата Черни ^. Для автомата ^ на рис. 2, напротив, существует лишь
ва минимальных синхронизирующих слова (они же являются кратчай-
ими синхронизирующими): vj\ = abab и и>2 = bbaa. Синхронизируемые
Рис. 2: Конечно порожденный автомат «04
втоматы, обладающие лишь конечным набором минимальных синхро-изирующих слов, называются конечно порожденными. Свойства таких втоматов, а также связанные с ними вопросы оптимальности изучаются о второй главе диссертации.
Предположим, что некоторое вычислительное устройство состоит из ескольких различных синхронизируемых автоматов с одинаковым чис-ом состояний, которые работают параллельно. Тогда, чтобы «переза-рузить» систему, нужно одновременно синхронизировать каждый из их. Это приводит к понятию универсальных синхронизирующих слов. усть п - натуральное число. Слово ю Є * называется универсальным -синхронизирующим или кратко п-синхронизирующим, если оно син-ронизирует все синхронизируемые автоматы с n-1-l состоянием над фиксированным алфавитом [4]. Понятие синхронизируемости можно обобщить, расширив область применения на несинхронизируемые автоматы. Автомат si — (Q, Е, 5) (не обязательно синхронизируемый) называется
п-сжимаемым, если существует слово w Є 2* такое, что \Q\ — \S(Q, w)\ п (при этом говорят, что слово w сжимает автомат srf на п состо ний). Слово юєЕ* называется п-сжимающим, если оно сжимает на состояний все n-сжимаемые автоматы с входным алфавитом Е. Поняти универсальных синхронизирующих и универсальных сжимающих ело сами по себе выглядят вполне естественно с точки зрения теории а томатов, помимо этого они находят приложения и в алгебре [3]. Други их возможным приложением является управление устройством-«черны ящиком», т.е. автоматом, для которого не известно ни его внутренне строение, ни состояние, в котором он находится. Применение униве сального синхронизирующего или универсального сжимающего слова такому автомату уменьшает неопределенность в его поведении настол ко, насколько это возможно.
Ввиду возможных приложений возникают вопросы об алгоритм-распознавания n-синхронизирующих и n-сжимающих слов, оптимально длине таких слов, а также о способах построения примеров коротких синхронизирующих и n-сжимающих слов. С точки зрения теории фо мальных языков, интересен вопрос о месте языка всех п-сжимающи слов над заданным алфавитом в классической иерархии Хомского. Ис следованию указанных вопросов посвящены работы [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 наименования.
