WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

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

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

Мартюгин Павел Владимирович ОЦЕНКИ ДЛИНЫ И ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ СИНХРОНИЗАЦИИ КОНЕЧНЫХ АВТОМАТОВ 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

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

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

Научный руковoдитель: кандидат физико-математических наук, доцент Д. С. Ананичев

Официальные оппоненты: доктор физико-математических наук, доцент М. Ю. Хачай доктор физико-математических наук, профессор Б.Ф. Мельников

Ведущая организация: Институт математики Сибирского отделения РАН

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

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

Автореферат разослан “ ” октября 2008 г.

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

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

Актуальность темы. Детерминированным конечным автоматом (ДКА) называется тройка A =(Q,, ), где Q — конечное множество состояний, — конечный алфавит и — всюду определенная функция переходов, действующая из Q в Q. ДКА A = (Q,, ) называется синхронизируемым, если существует слово w, под действием которого все состояния автомата отображаются в какое-то одно, или, говоря формально, найдется такое состояние q0 Q, что для любого состояния q Q, (q, w) =q0.

Синхронизируемость конечных автоматов плотно изучается уже более сорока лет. Одним из первых понятие синхронизируемости сформулировал И. Черни в 1964 году в работе [4]. И. Черни высказал гипотезу о том, что любой синхронизируемый ДКА с n состояниями может быть синхронизирован словом длины не большей чем (n - 1)2. За годы, прошедшие с тех пор, предпринималось множество попыток доказать или опровергнуть эту гипотезу, но ни одна из них не увенчалась успехом. И. Черни в [4] построил серию примеров, обеспечивающую нижнюю оценку (n - 1)2 максмальной длины кратчайшего синхронизирующего слова для автомата с n состояниями. Получить такую же верхнюю оценку пока не смог никто. На данный момент лишь доказано, что длина кратчайшего слова, синхронизирующего ДКА с n n3-n состояниями не превосходит (см. [1]). Обзоры результатов, полученных в связи с рассмотрением понятия синхронизируемости ДКА, можно найти в [8] или в [13].

Гипотеза Черни доказана для многочисленных частных случаев ДКА.

Ниже перечислены основные классы ДКА, синхронизируемость для которых изучалась различными авторами. Обозначим через class(n) максимально возможную длину кратчайшего синхронизирующего слова для ДКА с n состояниями из некоторого подкласса автоматов, где class — некоторое обозначение, приписанное этому подклассу. В диссертации рассматриваются следующие классы автоматов.

• ДКА с нулем, обозначение — zero. ДКА A =(Q,, ) называется автоматом с нулем, если существует состояние q Q такое, что для всех букв a выполняется (q, a) = q. И.К. Рысцов в [10] n(n-1) доказал что zero(n) =.

• ДКА с циклом по всем состояниям, обозначение — cicle. В этот класс попадут все автоматы A = (Q,, ) такие, что существует буква a, действующая на множестве Q как циклическая перестановка порядка |Q| (цикл длины |Q|). Известно, что cycle(n) = (n - 1)2, верхняя оценка величины cycle(n) доказана Л. Дюбуком в [5], нижняя оценка доказана И. Черни в [4].

• Монотонные ДКА, обозначение — mon. ДКА A =(Q,, ) называется монотонным, если на множестве Q можно ввести линейный порядок такой, что для любых состояний q q и любой буквы a выполняется (q, a) (q, a). В работе Д.С. Ананичева и М.В.

Волкова [2] доказано, что mon(n) =n - 1.

• Апериодические ДКА, обозначение — aper. ДКА A =(Q,, ) называется апериодическим, если его моноид переходов не содержит неодноэлементных подгрупп. В [14] А.Н. Трахтман получил оценn(n-1) ку aper(n), причем он доказал, что для сильносвязных синхронизируемых апериодических автоматов длина кратчайшего n(n+1) синхронизирующего слова не превосходит. С другой сто n-роны, Д.С. Ананичев в [3] доказал, что aper(n) n - 1+.

• Коммутативные ДКА, обозначение — com. ДКА A = (Q,, ) называется коммутативным, если для любого состояния q Q и любых букв a, b выполняется равенство (q, ab) =(q, ba). И.К.

Рысцов в [10] установил, что com(n) =n - 1.

• ДКА с простыми идемпотентами, обозначение — sid. Преобразование конечного множества Q называется идемпотентом, если 2 =. Идемпотент называется простым, если |(Q)| = |Q| -1.

ДКА A =(Q,, ) называется автоматом с простыми идемпотентами, если все буквы из действуют на множестве Q либо как перестановки, либо как простые идемпотенты. Для автоматов с простыми идемпотентами выполняется sid(n) (n-1)2 см. [4]. Кроме того, в работе И.К. Рысцова [11] доказано, что sid 2 · (n - 1)2.

Совершенно естественными являются вопросы о том, как проверять заданный ДКА A = (Q,, ) на синхронизируемость, и как находить кратчайшее слово, синхронизирующее заданный автомат. Д. Эпштейн в [6] показал, что проверка заданного ДКА A = (Q,, ) на синхронизируемость может быть осуществлена за время O(|| · |Q|2), то есть за время, полиномиальное от размера автомата. В той же работе было доказано, что проверка на синхронизируемость заданного ДКА словом длины не превосходящей заданную NP-полна. В. Самотий в [12] установил, что задача поиска длины кратчайшего синхронизирующего слова для заданного ДКА является NP-трудной и co-NP-трудной одновременно.

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

На практике автоматы со всюду определенной функцией переходов встречаются редко. Чаще всего возможна следующая ситуация: автомат находится в некотором состоянии q, и если в этот момент применить некоторую букву a, то автомат сломается. Автомат при работе не должен ломаться, поэтому можно считать, что в такой ситуации функция переходов по букве a не определена на состоянии q, и буква a к состоянию q применяться не может. Понятие таких автоматов может быть формализовано, и для таких автоматов можно рассматривать обобщение понятия синхронизации.

Частичным конечным автоматом (ЧКА) называется тройка A = (Q,, ), где Q — конечное множество состояний, — конечный алфавит и — частичная функция переходов, действующая из Q в Q (последнее означает, что функция может быть не определена на некоторых парах из множества Q). ЧКА A =(Q,, ) называется бережно синхронизируемым, если существует слово w такое, что величина (Q, w) определена и |(Q, w)| = 1. Заметим, что любой ДКА является ЧКА, и если слово бережно синхронизирует ДКА, то оно является синхронизирующим для него.

Понятие бережной синхронизируемости было впервые сформулировано автором диссертации в [18]. Однако, чуть ранее задачу оценки длины кратчайших бережно синхронизирующих слов рассматривали М. Ито и К. Сикисима-Цудзи в [7] в качестве вспомогательной задачи. Обозначим через pfa(n) максимально возможную длину кратчайшего бережно синхронизирующего слова для ЧКА с n состояниями. В [7] получены следующие верхние и нижние оценки величины pfa(n).

pfa(n) 2n - 2n-2 - если n =2k, то pfa(n) 2n/2+.

если n =2k +1, то pfa(n) 3 · 2(n-3)/2+Естественно также рассмотреть нижние оценки величины pfa(n) для множества ЧКА с одним общим для всех алфавитом.

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

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

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

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

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

• Международной конференции по теоретическим компьютерным наукам, CSR 2006 WOWA (Санкт-Петербург, 2006) • Международной конференции по языкам и автоматам, LATA (Таррагона, Испания, 2007) • Международной конференции по языкам и автоматам, AFL (Балатонфюред, Венгрия, 2008) • 39-й региональной молодежной конференции “Проблемы теоретической и прикладной математики” (Екатеринбург, 2008) • Заседаниях семинара “Алгебраические системы” (УрГУ).

Публиации Основные результаты диссертации опубликованы в работах [15]–[20].

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

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

Вторая глава диссертации посвящена синхронизируемости ДКА.

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

Теорема 2.1. Для любого целого n 8, существует синхронизируемый двухбуквенный ДКА с нулем Azero(n), имею щий n состояний, такой, длина кратчайшего синхронизирующего слова для Azero(n) что n2 +6n - равна.

Далее приведены результаты компьютерных экспериментов по поиску максимальной длины кратчайшего синхронизирующего слова для двухбуквенных ДКА с нулем, имеющих небольшой размер. Пример, дающий оценку большую чем в Теореме 2.1, найден только для ДКА с состояниями.

Оставшаяся часть главы 2 посвящена вопросам сложности алгоритмических задач, связанных с синхронизируемостью ДКА. В [6] Д. Эпштейн показал, что заданный ДКА с n состояниями над k-буквенным алфавитом может быть проверен на синхронизируемость за время O(kn2).

В разделе 2.2 построены более быстрые алгоритмы проверки на синхронизируемость для ДКА с нулем, D - тривиальных ДКА, частичномонотонных ДКА, монотонных ДКА (время работы всех алгоритмов O(nk)) и коммутативных ДКА (время работы алгоритма O(kn ln n)).

Раздел 2.3 посвящен определению вычислительной сложности алгоритмических задач, связанных с синхронизацией ДКА. Пусть class — обозначение некоторого класса автоматов, содержащегося в классе всех ДКА. Рассматриваются задачи следующего вида:

Задача: SY N(class, L) Дано: ДКА A =(Q,, ) из класса class и целое число L>0.

Вопрос: Верно ли, что существует синхронизирующее слово для автомата A длины не большей чем L Задача: SY N(class, = L) Дано: ДКА A =(Q,, ) из класса class и целое число L>0.

Вопрос: Верно ли, что кратчайшее слово, синхронизирующее автомат A, имеет длину L Пусть Z — одна из только что определенных задач. Допустим, что на вход задачи могут подаваться не все автоматы, предусмотренные в задаче Z, а только те из них, которые имеют k-буквенный алфавит. В этом случае перед названием задачи Z добавляется k-.

Пусть dfa — обозначение класса всех ДКА. В [12] доказано, что задача SY N(dfa, L) — NP-полна, а задача SY N(dfa, = L) —NP-трудн а и co-NP-трудна. В Предложении 2.6 доказывается верхняя оценка сложности задач вида SY N(dfa, = L) и k-SY N(dfa, = L).

Предложение 2.6 Задачи SY N(dfa, = L) и k-SY N(dfa, = L) для всех k 1 принадлежат классу сложности p p.

2 Далее в диссертации описывается сложность задач вида SY N(class, L), SY N(class, = L) и соответствующих k-задач для большинства классов ДКА, которые ранее упоминались в литературе в связи с исследованием свойств синхронизируемых автоматов. Определим обозначения рассматриваемых классов автоматов. Пусть aper — класс апериодических ДКА, com — класс коммутативных ДКА, mon — класс монотонных ДКА, sid — класс ДКА с простыми идемпотентами, zero — класс ДКА с нулем, cycle — класс ДКА, содержащих букву, действующую как цикл по всем состояниям. Основные результаты работы, связанные со сложностью задач вида SY N(class, L) и SY N(class, = L), содержатся в следующих утверждениях. В каждом из утверждений предполагается, что на вход соответствующей задачи подается автомат с n состояниями и k буквами.

Предложение 2.8 1. Задачи SY N(zero, L), SY N(aper, L), а также соответствующие k-задачи для k 2 NP-полны.

2. Задачи SY N(zero, = L), SY N(aper, = L), а также соответствующие k-задачи для k 2 NP-трудны и co-NP-трудны.

Предложение 2.10 Пусть k 1, тогда задачи k-SY N(com, L) и k-SY N(com, = L) могут быть решены за время O(nk ln n).

Предложение 2.11 Задача SY N(com, L) является NP-полной, а задача SY N(com, = L) является NP-трудной и co-NP трудной.

Предложение 2.12 Задача SY N(sid, L) является NP-полной, а задача SY N(sid, = L) является NP-трудной и co-NP трудной.

Предложение 2.13 Задачи 2-SY N(sid, L) и 2-SY N(sid, = L) могут быть решены за время O(n).

Предложение 2.14 Задачи SY N(mon, L) и k-SY N(mon, = L) могут быть решены за время O(n2k).

Следствие 2.4 1. Задачи SY N(cycle, L) и k-SY N(cycle, L) для k 2 являются NP-полными.

2. Задачи SY N(cycle, = L) и k-SY N(cycle, = L) для k 2 являются NP-трудными и co-NP-трудными.

Для доказательства NP-трудности и co-NP-трудности вышеописанных задач используется классическая NP-полная задача ВЫПОЛНИМОСТЬ.

Третья глава диссертации посвящена бережной синхронизируемости ЧКА. В разделе 3.1 доказываются нижние оценки длины кратчайших бережно синхронизирующих слов для ЧКА как с произвольным алфавитом, так и с двух или трехбуквенным. Оценки доказываются при помощи построения серий ЧКА, обладающих длинными кратчайшими бережно синхронизирующими словами. Пусть через pfa(n) обозначается максимально возможная длина кратчайшего бережно синхронизируk ющего слова для ЧКА с n состояниями, а через pfa(n) — максимальная длина такого слова для k-буквенных ЧКА с n состояниями. Основные результаты сформулированы в следующих утверждениях:

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»