Введение к работе
Актуальность темы. Детерминированным конечным автоматом (ДКА) называется тройка «й/ = (Q,E,#), где Q — конечное множество состояний, Е — конечный алфавит и 8 — всюду определенная функция переходов, действующая из Q х Е в Q. ДКА «й/ = (Q,E,#) называется синхронизируемым, если существует слово w Є Е*, под действием которого все состояния автомата отображаются в какое-то одно, или, говоря формально, найдется такое состояние qo Є Q, что для любого состояния qe Q, 8(q,w) = q0.
Синхронизируемость конечных автоматов плотно изучается уже более сорока лет. Одним из первых понятие синхронизируемости сформулировал И. Черни в 1964 году в работе [4]. И. Черни высказал гипотезу о том, что любой синхронизируемый ДКА с п состояниями моэюет быть синхронизирован словом, длины не большей чем, (п — I)2. За годы, прошедшие с тех пор, предпринималось множество попыток доказать или опровергнуть эту гипотезу, но ни одна из них не увенчалась успехом. И. Черни в [4] построил серию примеров, обеспечивающую нижнюю оценку {п — I)2 максмальной длины кратчайшего синхронизирующего слова для автомата с п состояниями. Получить такую же верхнюю оценку пока не смог никто. На данный момент лишь доказано, что длина кратчайшего слова, синхронизирующего ДКА с п состояниями не превосходит п ~п (см. [1]). Обзоры результатов, полученных в связи с рассмотрением понятия синхронизируемости ДКА, можно найти в [8] или в [13].
Гипотеза Черни доказана для многочисленных частных случаев ДКА. Ниже перечислены основные классы ДКА, синхронизируемость для которых изучалась различными авторами. Обозначим через uiciass(n) максимально возможную длину кратчайшего синхронизирующего слова для ДКА с п состояниями из некоторого подкласса автоматов, где class — некоторое обозначение, приписанное этому подклассу. В диссертации рассматриваются следующие классы автоматов.
ДКА с нулем, обозначение — zero. ДКА «г/ = (Q,E,#) называется автоматом с нулем, если существует состояние q Є Q такое, что для всех букв а Є Е выполняется 8(q, a) = q. И.К. Рысцов в [10]
/ \ п(п—1)
доказал что u)zero{n) = -^—
ДКА с циклом по всем состояниям, обозначение — сісіе. В этот класс попадут все автоматы «й/ = (Q,T.,8) такие, что существует буква а Є Е, действующая на множестве Q как циклическая перестановка порядка |Q| (цикл длины |Q|). Известно, что uicycie{n) = (п — I)2, верхняя оценка величины шсусіе(п) доказана Л. Дюбуком в [5], нижняя оценка доказана И. Черни в [4].
Монотонные ДКА, обозначение — топ. ДКА «й/ = (Q,E,#) называется монотонным, если на множестве Q можно ввести линейный порядок < такой, что для любых состояний q < q' и любой буквы а выполняется 5(q,a) < 5(q',a). В работе Д.С. Ананичева и М.В. Волкова [2] доказано, что и)тап(п) = п — 1.
Апериодические ДКА, обозначение — арег. ДКА «г/ = (Q, Е, 6) на
зывается апериодическим, если его моноид переходов не содержит
неодноэлементных подгрупп. В [14] А.Н. Трахтман получил оцен
ку ^aperij1) ^ ^2—і пРичем он доказал, что для сильносвязных
синхронизируемых апериодических автоматов длина кратчайшего
синхронизирующего слова не превосходит ^^—- . С другой стороны, Д.С. Ананичев в [3] доказал, что шарег(п) > п — 1 + \jkYL\
Коммутативные ДКА, обозначение — сот. ДКА «г/ = (Q, Е, 6) называется коммутативным, если для любого состояния q Є Q и любых букв a, b Є Е выполняется равенство 8(q, ab) = 5(q, ba). И.К. Рысцов в [10] установил, что uicam{n) = п — 1.
ДКА с простыми идемпотентами, обозначение — sid. Преобразование о конечного множества Q называется идемпотентом, если а2 = а. Идемпотент а называется простым, если |
Совершенно естественными являются вопросы о том, как проверять заданный ДКА «й/ = (Q,T.,8) на синхронизируемость, и как находить кратчайшее слово, синхронизирующее заданный автомат. Д. Эпштейн
в [6] показал, что проверка заданного ДКА «й/ = (Q, Е, 8) на синхро-низируемость может быть осуществлена за время 0(|Е| |Q|2), то есть за время, полиномиальное от размера автомата. В той же работе было доказано, что проверка на синхронизируемость заданного ДКА словом длины не превосходящей заданную NP-полна. В. Самотий в [12] установил, что задача поиска длины кратчайшего синхронизирующего слова для заданного ДКА является NP-трудной и co-NP-трудной одновременно.
Аналогичные алгоритмические задачи могут быть поставлены не только для класса всех ДКА, но и для подклассов ДКА, описанных выше. В данной диссертации изучается сложность этих задач. Интересным оказывается изучение сложности этих задач отдельно как для подклассов ДКА без ограничения на размер алфавита, так и для ДКА с фиксированным алфавитом.
На практике автоматы со всюду определенной функцией переходов встречаются редко. Чаще всего возможна следующая ситуация: автомат находится в некотором состоянии q, и если в этот момент применить некоторую букву а, то автомат сломается. Автомат при работе не должен ломаться, поэтому можно считать, что в такой ситуации функция переходов по букве а не определена на состоянии q, и буква а к состоянию q применяться не может. Понятие таких автоматов может быть формализовано, и для таких автоматов можно рассматривать обобщение понятия синхронизации.
Частичным конечным автоматом (ЧКА) называется тройка «й/ = (Q,T.,8), где Q — конечное множество состояний, Е — конечный алфавит л 8 — частичная функция переходов, действующая из Q х Е в Q (последнее означает, что функция 8 может быть не определена на некоторых парах из множества Q х Е). ЧКА «г/ = (Q, Е, 8) называется бережно синхронизируемым, если существует слово w Є Е* такое, что величина 8(Q,w) определена и \8(Q,w)\ = 1. Заметим, что любой ДКА является ЧКА, и если слово бережно синхронизирует ДКА, то оно является синхронизирующим для него.
Понятие бережной синхронизируемости было впервые сформулировано автором диссертации в [18]. Однако, чуть ранее задачу оценки длины кратчайших бережно синхронизирующих слов рассматривали М. Ито и К. Сикисима-Цудзи в [7] в качестве вспомогательной задачи. Обозначим через u)pfa(n) максимально возможную длину кратчайшего бережно
синхронизирующего слова для ЧКА с п состояниями. В [7] получены следующие верхние и нижние оценки величины U)pfa(n).
0Jpfa(n) <Т- Т-2 - 1
если п = 2к, то ujpfa{n) > 2га/2+1
если п = 2к + 1, то ujpfa{n) > 3 2(га"3)/2+1 '
Естественно также рассмотреть нижние оценки величины u)pfa(n) для множества ЧКА с одним общим для всех алфавитом.
Аналогично обычной синхронизируемости ДКА, естественно также определить вычислительную сложность задачи проверки заданного ЧКА на бережную синхронизируемость и задачи поиска длины кратчайшего бережно синхронизирующего слова для заданного ЧКА.
Целью работы является построение оценок максимальной длины кратчайших слов, синхронизирующих ДКА или бережно синхронизирующих ЧКА, а также оценка сложности алгоритмических задач, связанных с синхронизируемостью ДКА и бережной синхронизируемостью ЧКА.
Научная новизна. Результаты являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории конечных автоматов и терии сложности вычислений.
Апробация результатов работы. Основные результаты диссертации докладывались на:
Международной конференции по теоретическим компьютерным наукам, CSR 2006 WOWA (Санкт-Петербург, 2006)
Международной конференции по языкам и автоматам, LATA 2007 (Таррагона, Испания, 2007)
Международной конференции по языкам и автоматам, AFL 2008 (Балатонфюред, Венгрия, 2008)
39-й региональной молодежной конференции "Проблемы теоретической и прикладной математики" (Екатеринбург, 2008)
Заседаниях семинара "Алгебраические системы" (УрГУ).
Публиации Основные результаты диссертации опубликованы в работах [15]-[20].
Структура и объем диссертации Диссертация состоит из введения, двух глав, заключения и списка литературы. Объем диссертации составляет 123 страницы. Библиографический список содержит 46 наименований.
Похожие диссертации на Оценки длины и вычислительной сложности синхронизации конечных автоматов
