Введение к работе
Актуальность. Детерминированным конечным автоматом (ДКА) называется тройка «й/ = (Q,E,#), где Q — конечное множество состояний, Е — конечный входной алфавит, и 8 — всюду определенная функция переходов, действующая из Q х Е в Q. Действие букв из Е на множество состояний Q, определяемое функцией переходов 8, естественным образом расширяется до действия слов из Е*, которое также будем обозначать через 8. Кроме того, для произвольного слова v Є Е* и произвольного R С Q определим образ множества R под действием слова v следующим образом: 8(R,v) = {8(q,v)\qeR}.
ДКА «й/ = (Q,T.,8) называется синхронизируемым, если найдется такое слово w Є Е*, что \8(Q,w)\ = 1, т.е. действие слова w отображает все состояния этого автомата в некоторое одно состояние; говорят, что такое слово w синхронизирует автомат «г/. Если мы имеем несколько одинаковых синхронизируемых автоматов, работающих независимо и находящихся в различных состояниях, то после одновременного применения ко всем этим автоматам синхронизирующего их слова все они окажутся в одном и том же состоянии — тем самым, дальнейшая работа этих автоматов под действием единого потока сигналов будет синхронизирована. Можно считать, что данное слово выполнило 'сброс' всех этих автоматов в 'начальное' состояние. Другим важным применением синхронизации является ситуация, когда у нас имеется один синхронизируемый автомат, но мы не знаем, в каком состоянии он находится. Тогда применение синхронизирующего этот автомат слова переведет его в заранее известное нам состояние. Некоторые другие способы использования синхронизации можно найти в работах [19; 23].
Понятие синхронизируемости можно обобщить, расширив область применения на несинхронизируемые автоматы. Возьмем произвольное натуральное число п. ДКА «й/ = (Q,T.,8) называется п-сжимаемым, если найдется такое слово w Є Е*, что |^(Q,w)| < \Q\ — п. Говорят, что такое слово w сжимает автомат «й/ на п состояний. Сжатие автомата, как и синхронизация, позволяет уменьшить неопределенность его поведения, так как непосредственно после применения к автомату сжимающего его слова этот автомат не может находиться в некоторых заранее известных состояниях.
Одним из первых понятие синхронизируемости сформулировал Черни (Сегпу) в 1964 году, в работе [11]. В этой же работе Черни высказал гипотезу, вызвавшую наибольший интерес в области синхронизации:
Гипотеза 1 (Сегпу, 1964). Любой синхронизируемый ДКА «й/ = (Q,E,#) может быть синхронизирован словом длины не большей, чем (\Q\ — I)2.
С тех пор было много попыток доказать или опровергнуть эту так легко формулируемую гипотезу, но ни одна из них не увенчалась успехом. На данный момент гипотеза доказана для многочисленных классов автоматов
(см. [2; 10; 15; 17; 28; 32]), а в общем случае получена только кубическая верхняя оценка ' ' g ' (см. [1]). В 1983 году Пэн (Ріп) в работе [24] высказал гипотезу, обобщающую гипотезу Черни:
Гипотеза 2 (Pin, 1983). Любой п-сжимаемый ДКА может быть сжат на п словом длины не большей, чем п2.
Однако, Кари (Кагі) в 2000 году опроверг эту гипотезу [20], построив автомат с 6-ю состояниями такой, что кратчайшее сжимающее этот автомат на 4 состояния слово имеет длину 17 = 42 + 1. Других примеров, опровергающих данную гипотезу, пока не найдено.
В работе [17] Эпштейн (Eppstein) показал, что проверить возможность синхронизации данного автомата «й/ = (Q,E,#) можно за время 0(|Е||(5|2), используя 0(|(5|2) пространства, а найти некоторое синхронизирующее его слово можно за время 0(|Е||(5|2 + |Q|3); длина такого слова '-Щ—\- 0(\Q\2). Оказалось, что используя те же идеи, можно за время 0(|Е||(5|2 + |(5|3+?г|(5|2) проверить, является ли данный автомат «й/ ?г-сжимаемым. Кроме того, Са-ломаа (Salomaa) [29] и Эпштейн [17] доказали, что задача, в которой для заданного автомата «г/ и заданного натурального числа L требуется определить, имеет ли автомат «г/ синхронизирующее слово длины не больше L, является iVP-полной. А недавно Самотий (Samotij) показал, что задача проверки того, что кратчайшее слово, синхронизирующее автомат «г/, имеет длину ровно L, является одновременно iVP-трудной и со-NP-трудной [30].
Возьмем произвольное натуральное число п. Слово w Є Е* называется:
универсальным п-синхронизирующим словом, если оно синхронизирует каждый синхронизируемый автомат «г/ = {Q,T.,8) со входным алфавитом Е, у которого | Q | = п + 1;
универсальным п-сжимающим словом, если оно сжимает на п каждый гг-сжимаемый ДКА со входным алфавитом Е.
Для краткости такие слова называют п-синхронизирующими и ?г-сжима-ющими соответственно, опуская прилагательное 'универсальное'. Заметим, что каждое гг-сжимающее слово является п-синхронизирующим, так как каждый синхронизируемый автомат с п + 1 состоянием является ?г-сжимае-мым, и для него синхронизация совпадает с сжатием на п состояний. Таким образом ?г-сжимающие слова являются более мощными по своей сути.
Универсальные синхронизирующие слова находят свое применение при последовательной или одновременной синхронизации нескольких классов однотипных автоматов. Это может быть, например, ситуация, при которой мы не имеем возможности в силу тех или иных причин работать с каждым классом в отдельности, подбирая для каждого класса свое синхронизирующее
слово. Одна из таких ситуаций описана в работах [3;4], где автоматами и словами являются молекулы, и весь процесс происходит во взаимодействии растворов, содержащих молекулы-автоматы и молекулы-слова; конечно же, разбирать раствор на отдельные молекулы-автоматы не представляется возможным. Другим естественным вариантом применения универсального синхронизирующего слова является решение задачи синхронизации классов автоматов при условии, что нам удобнее вместо множества отдельных синхронизирующих слов хранить одно единственное слово. Приведенные рассуждения можно в равной степени отнести и к универсальным сжимающим словам. Оба введенных понятия выглядят вполне естественно с точки зрения теории автоматов и в то же время отлично вписываются в классический подход Мура (Moore) [22]: применение универсального синхронизирующего или универсального сжимающего слова к автомату-'черному ящику', для которого мы не знаем ни внутреннее строение, ни состояние, в котором автомат находится, уменьшает неопределенность в его поведении.
Понятие универсальных синхронизирующих слов неявно рассматривалось в работе [16] 1983 года и было явно введено в 2002 году в работе [9]. Понятие универсальных сжимающих слов в литературе впервые появилось (под другим названием) в начале 1990х годов в связи с задачами комбинаторики и абстрактной алгебры [25; 31]. В последнее время идет интенсивное изучение универсальных синхронизирующих и универсальных сжимающих слов, их связей с теорией автоматов, теорией сложности вычислений и теорией формальных языков [12; 14; 18; 26]. Кроме того, недавно были найдены новые приложения универсальных сжимающих слов [5; 6; 27].
Легко показать, что универсальные п-синхронизирующие слова существуют для каждого алфавита и каждого значения параметра п, но не так просто показать это для универсальных гг-сжимающих слов. Дело в том, что в определении последних количество состояний у автоматов неограничено сверху, и одно и то же универсальное ?г-сжимающее слово должно сжимать на п бесконечное число ?г-сжимаемых автоматов. В работе [31] эта задача была решена: Зауэр (Sauer) и Стоун (Stone) привели рекурсивный способ построения ?г-сжимающих и п-синхронизирующих слов. Правда, длина получающихся слов является дважды экспоненциальной функцией от п. Позже оказалось, что та же самая идея может привести к серии более коротких слов; а именно, в работе [21] авторы показали, что можно построить слова с
длиной 0(|S| г ). И все-таки эта длина достаточно велика, а на практике интересуют именно короткие слова. В связи с этим возникают следующие задачи, сформулированные в работах [9] и [31]:
Задача 1. Определить длины s(n,k) и с(п,к) кратчайших п-синхронизи-рующих и п-сжимающих слов над к-буквенным алфавитом для всех значений пик.
Задача 2. Найти кратчайшие п-синхронизирующие и п-сжимающие слова над к-буквенным алфавитом для заданных значений пик.
Автором диссертации были решены эти задачи для небольших алфавитов и значений параметра п, а также был предложен алгоритм построения относительно коротких п-синхронизирующих слов. Это позволило уменьшить дефицит конкретных примеров, сдерживающий изучение данной тематики.
Занимаясь изучением универсальных синхронизирующих и универсальных сжимающих слов, невозможно обойти стороной такую базовую задачу, как их распознавание. Проверить, является ли заданное слово w Є Т.* универсальным гг-синхронизирующим словом, можно по определению, т. е. перебрать все автоматы с п-\-1 состоянием и входным алфавитом Е и убедиться, что слово w синхронизирует все синхронизируемые автоматы из этого списка. Однако, тот же подход не работает для универсальных гг-сжимающих слов: мы снова сталкиваемся с бесконечным числом автоматов, участвующих в определении. Таким образом, имеем нетривиальную задачу:
Задача 3. Построить для каждого натурального числа п алгоритм проверки входного слова w Є Е* на п-сжимаемость.
В работе [8] задача распознавания ?г-сжимающих слов была сформулирована и решена для первого нетривиального случая п = 2. Более наглядная версия этого решения была представлена в работе [7].
Для п > 2 задача распознавания ?г-сжимающих слов оставалась открытой на протяжении нескольких лет. Для начала автору диссертации удалось показать, что язык Сга(Е) всех ?г-сжимающих слов над алфавитом Е является рекурсивным подмножеством множества Е*. Для этого достаточно было найти для каждого п вычислимую функцию fn:N^N такую, что слово w Є Е* является гг-сжимающим тогда и только тогда, когда w сжимает на п каждый гг-сжимаемый ДКА «й/ = (Q, Е, 6), у которого \Q\ < fn(\w\). Действительно, имея такую функцию fn, достаточно проверить слово w лишь на конечном числе автоматов, и либо будет найден контрпример, либо по выбору функции fn будет следовать, что слово w является гг-сжимающим.
Конечно, теперь можно утверждать, что мы имеем алгоритм, распознающий гг-сжимающие слова, для каждого п, но этот алгоритм должен просмотреть ram's' автоматов, где т = fn(\w\), и, учитывая, что универсальные сжимающие слова имеют достаточно большую длину, мы тут же приходим к выводу о практической непригодности данного алгоритма. А на чем мы могли бы сэкономить время работы? Ответ очевиден: мы никак не использовали для подбора тестовой базы автоматов знания о слове w, кроме его длины.
Автором диссертации был разработан и реализован алгоритм проверки входных слов на гг-сжимаемость, учитывающий их структуру.
Целью работы является решение задачи распознавания универсальных сжимающих слов, построение коротких примеров универсальных синхронизирующих и универсальных сжимающих слов, а также изучение свойств универсальных синхронизирующих и универсальных сжимающих слов.
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории конечных автоматов и теории сложности вычислений.
Публикации. Основные результаты диссертации опубликованы в работах [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 наименования.
