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

На ирамах ру^онис!

А

Маслешшкона Марина Игоревна

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

01.01.00 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

г 3 СЕН 2015

005562487

Екатеринбург 2015 г.

005562487

Работа выполнена па кафедре алгебры и дискретной математики Института математики н компьютерных паук Уральского федерального университет имени первого. Президента России Б. Н. Ельцина, г. Екатеринбург.

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

профессор Волков Михаил Владимирович

Официальные оппоненты: Гуторман Александр Эмилсвпч,- доктор

физико-математических наук, доцент, профессор кафедры высшей алгебры ФГБОУ ВО «Московский государственный университет им. М.В.Ломоносова», г. Москва.

Куликов Александр Сергеевич, кандидат физико-математических наук, научный сотрудник лаборатории алгоритмических методов ФГВУН «Санкт-Петербургское отделенно Математического института им. В.А.Стеклова РАН», г. Санкт-Петербург.

Ведущая организация: ФГАОУ ВПО «Казанский

(Приволжский) федеральный университет», г. Казань.

на заседании диссер-

Заншта диссертации состоится «14» октября 2015 г. в_

таппоппого совета Д 004.006.04 на базе ФГБУН «Институт математики и механики им. Н. Н. Красовского УрО РАН» (620990, г. Екатеринбург, ул. С. Ковалевской, 16).

С диссертацией можно ознакомиться и библиотеке Института математики и механики н па сайте ИММ УрО РАН Шр:ш^Лшшлшш.ги/С1в/Ш&8/

Автореферат разослан « $ » сентября 2(115 г.

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

В. Д. Скарин

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

Актуальность темы. Всюду в данной работе под словом «язык» понимается формальный язык над конечным фиксированным алфапн-том Е, т.е. подмножество свободного моноида Е* над Е. Регулярные языки образуют важный класс формальных языков. Особенностью языков этого класса является возможность компактного описания в различных терминах (например, с помощью регулярных выражений, детерминированных автоматов, недетерминированных автоматов и др.). Разные способы описания имеют разные области применения и разную степень компактности, а изучение связи между различными способами составляет одно из наиболее активно развивающихся направлений в теории сложности формальных систем. Отметим, что для некоторых важных подклассов регулярных языков есть особые методы представления, которые учитывают специфику этих классов. Рассмотрим простои пример одного из таких классов. Слово и € Е+ называется фактором слова «?. если XV может быть представлено как те = хиу для некоторых т, 1/ € Е\ Язык Ь СЕ* является факториалъпым, если Ь замкнут относительно взятия факторов, т.е. для всякого ш е Ь все факторы го также принадлежат Ь. Любой факториальный язык можно описать с помощью антисловаря, т.е. списка запрещенных факторов. Большую роль в теории и приложениях формальных языков играют факторнальные языки с конечным антисловарем (КАС-языки), см. [3]. Естественным объектом, описывающим КАС-язык, является антисловарь этого языка. Другой важный класс составляют идеальные языки. Напомним, что язык /СЕ* называется двусторонним идеалом, если I непустой и Е*/Е* С /. Говоря «идеальный язык», или коротко «идеал», мы будем подразумевать, что рассматривается двусторонний идеальный язык. Понятие двустороннего идеала занимает центральное место в теории полугрупп |2] Идеальные языки как двусторонние идеалы в свободном моноиде Е* активно изучаются в связи с различными приложениями в компьютерных науках на протяжении последних пятидесяти лет [0,10]. Нетрудно проверить, что язык Ь С Е* является факториалъпым тогда и только тогда, когда его дополнение Е* \ Ь - идеал в Е*. Таким образом, факториаль-ные языки суть в точности дополнения идеальных языков. Идеальные языки возникают также в задачах, связанных с поиском подстроки в строке |8|. Формально поиск в тексте ш слова из Ь С Е* эквивален тен поиску факторов ш, принадлежащих языку Е*£Е*. который является двусторонним идеалом.

В связи о различными практическими и теоретическими приложениями представляет интерес нахождение объекта для компактного представления идеальных языков. В результате поиска такого объекта возникла идея представления идеальных языков с помощью синхронизируемых автоматов. Автоматы из этого класса можно рассматривать как своеобразные «распознаватели» идеальных языков. Точный смысл этой идее мы придадим чуть позже, а сейчас зафиксируем некоторые определения. Детерминированным конечным автоматом (ДКА) называется тройка .с/ = (С^, Е, (>), где С2 - конечное множество состояний, Е - конечный входной алфавит, а <): (} х Т] —> С] - всюду определенная функция переходов. Отметим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние до £ и множество Р .нгкяючиншлъных (или конечных) состояний. Мы также будем пользоваться этим вариантом определения и писать .с/ = Е, 6, (]й, Р), когда речь будет идти о языках, распознаваемых автоматами. Для заданного ДКА = 6,(¿о,Р) положим £[•£'/] = {гш | <%0,и>) € F}, при этом будем говорить, что язык Ь[&/\ принимается (или распознается) автоматом Язык называется регулярным, если он распознается некоторым детерминированным конечным автоматом. В дальнейшем будут рассматриваться только регулярные языки, поэтому для краткости будем опускать термин «регулярный», предполагая, что речь идет именно о таких языках. Всюду ниже будем использовать слово «автомат» в качестве синонима термина «детерминированный конечный автомат». Рассмотрим автомат ,й/ с множеством состояний С} и функцией переходов «): <3 х Е —> <2, задающей действие букв из заданного алфавита Е на состояния из С}. Автомат л/ называется синхронизируе.иым, если найдется слово и> над алфавитом Е, под действием которого все состояния переходят в одно: го) = 5(с/,ги) для всех q,q' Е <5- Всякое такое слово ги называется синхронизирующим для л/. Таким образом, если исходное состояние автомата неизвестно, то после прочтения синхронизирующею слова его состояние будет однозначно определено. В качестве примера рассмотрим автомат ^ с четырьмя состояниями, приведенный на рис. 1. Этот автомат синхронизируемый, поскольку слово ги = аЬа переводит каждое состояние в 3.

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

ь

а

а,Ь

а

8

Ь

Рне. 1: Автомат .с/4

протоколов, кодирование информации, роботпка, биоинформа тнка). а также возникают в некоторых разделах фундаментальной математики (символическая динамика, теория подстановочных систем). Основы теории синхронизируемых автоматов и их приложения в упомянутых областях обсуждаются довольно подробно в обзоре [20].

С точки зрения приложений важным параметром является длина синхронизирующего слова. Минимум длин синхронизирующих слов автомата -с/ называется его порогом синхронизации. Для краткости будем называть автомат с п состояниями п-автоматом. В 1964 году Черпи |7| построил для каждого п > 1 синхронизируемый п-автомат над двухбук-венным алфавитом с порогом синхронизации (п — I)2. Позднее Черни высказал предположение, что автоматы из этой серии реализуют наихудший случай, т.е. что всякий синхронизируемый н-автомат обладает синхронизирующим словом длины не более (п — I)2. Это предположение получило название гипотезы Черни. Несмотря на простоту формулировки и усилия многочисленных исследователей, гипотеза Черни остается не доказанной и не опровергнутой уже более 50 лет.

Пусть я/ - синхронизируемый автомат с входным алфавитом Е. Обозначим через 8уп(.с/) множество всех синхронизирующих слов дли автомата . Язык всех слов, синхронизирующих я/, образует регулярный идеал в Е*. С другой стороны, справедливо и обратное утверждение: если / - произвольный регулярный идеал в Е*, то найдется синхронизируемый автомат с входным алфавитом Е. для которого I будем' множеством синхронизирующих слов. Этот автомат можно использовать как своеобразный распознаватель языка I - для того, чтобы проверить, принадлежит ли какое-то слово го 6 Е* языку I, достаточно применить V) к каждому состоянию ДКА <с/ н сравнить получающиеся состояния: т е I тогда и только тогда, когда все эти состояния совпадают. Таким образом, автомат л/ можно рассматривать как сжатое представление языка I. В качестве меры сложности такого представления определим

новую характеристику регулярного языка, являющегося идеалом, связанную с его описанием посредством синхронизнруемых автоматов. А именно, синхронизационной сложностью (кратко синхросложностью) п { I) идеального языка I назовем минимальное возможное число состояний в синхронизируемом автомате, для которого I будет множеством синхронизирующих слов. Всякий синхронизируемый автомат, на котором достигается значение синхронизационной сложности идеального языка 7, будем называть минимальным синхронизируемым автоматом (кратко МСА) для I.

Отметим, что одной из основных мер описательной сложности регулярных языков является число состояний в минимальном детерминированном конечном автомате, распознающем язык. Эта мера сложности называется дескриптивной сло-жностыо регулярного языка. Изучению этой характеристики регулярных языков и ее поведению при различных операциях над языками посвящено множество работ, см., например. |5, б, 19|. Дескриптивную сложность регулярного языка L будем обозначать через sc(L). В рамках общего подхода к изучению различных мер сложности формальных языков возникает группа следующих естественных вопросов.

• Как соотносятся между собой синхронизационная и дескриптивная сложность идеального языка?

• Определяется ли МСА для заданного идеального языка единственным образом?

• Как: построить МСА для заданного языка по некоторому его конструктивному представлению (например, по минимальному детерминированному автомату, распознающему язык)'?

• Существует ли эффективный алгоритм проверки того, что заданный автомат является МСА для заданного языка?

• Насколько сложно проверить неравенство гс(1) < С для заданного натурального £1

Систематическому изучению этих вопросов и посвящается диссертация. Обозначим через .£4 минимальный детерминированный автомат, распознающий регулярный язык L. Нетрудно проверить, что для всякого идеального языка I имеет место равенство Syn(^) = I. Это означает,

что синхронизационная сложность произвольного идеального языка / не превосходит его дескриптивной сложности, т.е. rc(T) < sc(I). Теперь возникает естественным образом следующая задача.

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

В диссертации показано, что дескриптивная сложность идеального языка может быть экспоненциально больше синхронизационной сложности. Это означает, что для идеального языка представление посредством синхронизируемого автомата может быть значительно компактнее представления с помощью минимального детерминированного автомага. Из теории формальных языков известно, что недетерминированный автомат, распознающий регулярный язык, также может дать экспоненциальную экономию памяти по сравнению с минимальным детерминированным автоматом для этого языка [11]. Кроме того, для данного регулярного языка недетерминированный автомат с минимальным возможным числом состояний, распознающий этот язык, строится неоднозначно. Оказывается, что для идеального языка также нельзя однозначно восстановить МСА. Далее аналогия между синхронизируемыми детерминированными автоматами и недетерминированными автоматами как объектами для представления языков снова возникнет при определении класса сложности задачи проверки равенства идеальных языков, заданных синхронизируемыми автоматами. Оказывается, что эта задача принадлежит тому лее классу сложности, что и задача проверки равенства языков, распознаваемых двумя данными недетерминированными автоматами. Таким образом, можно утверждать, что представление идеального языка посредством синхронизируемого автомата сопоставимо е представлением регулярного языка недетерминированным автомагом в том смысле, что наиболее естественные вопросы, связанные с изучением этих представлений, имеют одни и те же ответы.

Поскольку ответ на вопрос о единственности МСА для заданного идеального языка отрицательный, то возникает следующий вопрос. В каком подклассе синхронизируемых автоматов стоит искать МСА для заданного идеального языка? Классическим подходом в теории синхронизируемых автоматов является рассмотрение двух основных классов: автоматов с нулем и сильно связных автоматов. Выбор этих двух классов обусловлен тем, что для доказательства гипотезы Черни необходимо и достаточно установить се справедливость в классе автоматов с нулем и в классе сильно связных автоматов [21]. Говорят, что ДКА яв-

ляется автоматом с нулем, если некоторое его состояние переводится всеми буквами алфавита в себя. В классе автоматов с нулем гипоте-, за Черни верна [18|. Напомним, что автомат я/ с множеством состоянии п функцией переходов 6 называется сально связным, если его орграф сильно связан, т.е., другими словами, для всякой пары состояний р, ([ € (} найдется слово го, для которого 6(р,и>) = q. В связи с изучением порога синхронизации сильно связных автоматов возникает следующий естественный вопрос: для всякого ли идеального языка. I существует сильно связный синхронизируемый автомат 3& такой, что 8уп(<^) = /? Отметим, что задача построения сильно связного синхронизируемого автомата 38, в котором Зуи(^) = I, нетривиальна. Реши и Родаро в |17] доказали, что такой автомат 38 можно построить для всякого идеального языка I над алфавитом Е, содержащим хотя бы две буквы. Конструкция из [17] сложная с технической точки зрения и дает очень грубую оценку на число состояний в соответствующем сильно связном автомате. Более того, компьютерные эксперименты дают основание предполагать, что эта. оценка далека от оптимальной. В связи с этим актуальна следующая задача.

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

Предположим теперь, что идеальный язык I задан некоторым синхронизируемым автоматом язык синхронизирующих слов которого совпадает с I. Пусть гс(Г) = п. Последнее равенство означает, что существует синхронизируемый п-автомат ЗВ такой, что Зуп(^) = Зуп(.с/) = I, причем ЗВ является минимальным синхронизируемым автоматом для I. Возникает следующий вопрос: насколько сложно проверить равенство языков синхронизирующих слов двух данных автоматов? Как следствие возникает вопрос о классе вычислительной сложности задачи проверки неравенства гс(1) < £, где I - язык синхронизирующих слов заданного синхронизируемого автомата а £ - фиксированное натуральное число. Таким образом, представляет интерес решение следующих задач.

Задача 3. Определить класс вычислительной сложности задачи БУМ-ЕС) иАЫТУ:

УСЛОВИЕ. Заданы синхронизируемые автоматы ,е/ и ЗВ. ВОПРОС. Верно ли, что ЭупЮ = Эуп(^)?

Задача 4. Определить класс вычислительной сложности задачи

RESET-INEQUALITY:

УСЛОВИЕ. Заданы синхронизируемый автомат ,с/ и число С G N. ВОПРОС. Верно ли, что гс{1) < }.. где I = Syii(.с/)?

Пусть дан ДКА s/ = (Q, Е, с/ц, F), распознающий некоторый регулярный язык L. Будем говорить, что srf является синхронизируемым, если таковым является ДКА я/' = (Q, Е, S). Нетрудно найти множество состояний S С Q, в которые можно синхронизировать ,с/. Это множество определяется следующим образом: q G S тогда и только тогда, когда S(Q, w) — {g} для некоторого w € S*.

Если S = F, то .с/ - синхронизируемый ДКА, причем имеет место равенство Syn(.c/) = L\&/\. Предположим теперь, что S ^ F и S ^ 0. Возникает вопрос, какую структуру должен иметь язык L, чтобы минимальный автомат, распознающий L, был синхронизируемым? Несложно привести пример, подтверждающий, что класс языков с таким свойством не совпадает с классом всех регулярных языков. Таким образом, представляет интерес решение следующей задачи.

Задача 5. Описать класс языков, распознаваемых синхронизируемыми автоматами.

Актуальность задачи 5 можно объяснить тем фактом, что синхронизирующие слова для автомата, распознающего данный регулярный язык, являются константами этого языка. Константы регулярных языков имеют приложение в биоинформатике в связи с изучением языком сплетения. В частности, в недавней работе Бонницони и Ноношкп |1| было показано, что всякий регулярный язык сплетения должен иметь констант}'. В свою очередь, теоретические результаты, устанавливающие тс или иные свойства языков сплетения, играют важную роль в развитии области теории формальных языков, связанной с моделированием биохимических процессов [12].

Целью работы является решение поставленных выше задач 1 5.

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

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая ценность. Диссертационная

работа носит теоретический характер. Полученные результаты могут быть использованы в дальнейших исследованиях по синхронизируемым автоматам, в теории сложности формальных систем, теории формальных языков и при чтении специальных курсов для студентов математических специальностей. Ссылки на результаты диссертации присутствуют в работах других авторов: [9,16,17].

Апробация результатов работы. Результаты диссертации докладывались на 38-й международной конференции по современным направлениям в теории и практике компьютерных наук SOFSEM 2012 (Шпиндлерув Млын, Чехия, 2012), 2-м российско-финском симпозиуме по дискретной математике RuFiDiM (Турку, Финляндия, 2012), 6-й научной школе по компьютерным наукам CSEDays 2013 (Екатеринбург, 2013), 9-й международной конференции по комбинаторике слов WORDS 2013 (Турку, Финляндия, 2013), 7-й научной школе по компьютерным наукам CSEDays 2014 (Екатеринбург, 2014), 16-м международном семинаре по описательной сложности формальных систем DCFS 2014 (Турку, Финляндия. 2014), 3-м российско-финском симпозиуме по дискретной математике RuFiDiM (Петрозаводск, 2014), 46-й молодежной школе-конференции «Современные проблемы математики и ее приложений» (Екатеринбург, 2015), 10-й международной конференции по компьютерным наукам CSR 2015 (Листвянка, 2015) на заседаниях семинара «Теоретические компьютерные науки* под рук. М. В. Волкова и семинара «Алгебраические системы» под рук. Л. Н. Шеврина (Екатеринбург, 2012 - 2015).

Публикации. По теме диссертации опубликовано 10 работ [22] -[31). Из них 4 работы опубликованы в ведущих изданиях, входящих в список ВАК [22] [25]. В работе [22] идея конструкций из теорем 1 и 2 принадлежит Е.В. Прнбавкнной, идея конструкции из теоремы 3 принадлежит В.В. Гусеву. Общая схема исследования и доказательства утверждений принадлежат диссертанту. В работе [23] идея алгоритма, построения сильно связного автомата принадлежит Е.В. Прибавкиной, предложение 4.1 и идея доказательства теоремы 4.2 принадлежат В.В. Гусеву. Реализация вычислительных экспериментов и доказательства основных утверждений принадлежат диссертанту. Доказательства основных результатов работы [24| при подготовке текста диссертации были качественно улучшены, что позволило, в частности, получить новые,

более сильные, результаты о сложности задачи RESET-INEQUALITY. В совместной работе |25] с Э. Родаро идея доказательства теоремы 5 и основные результаты параграфа 3 принадлежат Э. Родаро, доказательство теоремы 5 и все результаты параграфов 4 и 5 принадлежат диссертанту. Для полноты изложения в диссертации сформулированы без доказательства некоторые результаты параграфа 3 из [25], полученные Э. Родаро. Работы [2(1], [28] - [31] являются тезисами. В [28] представлен основной результат опубликованной позднее статьи [22]. а также некоторые другие результаты, полученные диссертантом. В тезисах [31] опубликованы без доказательств некоторые результаты, полученные Э. Родаро, связанные с развитием нового подхода к гипотезе Черни, а также сформулированы утверждения, полученные диссертантом, описывающие свойства, множества констант регулярного языка.

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

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

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

В первой главе доказываются результаты, которые не входят в число основных результатов диссертации, по представляют некоторый самостоятельный интерес. В параграфе 1.1 первой главы показано, что для всякого идеального языка I верно неравенство rc(I) < sc(I), более того, для всякого натурального п существует идеальный язык 1п такой, что rc(/n) = sc(Iu) = п + 1. С другой стороны, в параграфе 1.2 доказано, что для всякого натурального п > 3 существует идеальный язык 1п такой, что гс(/„) — п и sc(In) = 2" — п. В качестве такого языка /„ можно взять, например, язык синхронизирующих слов n-автомата Черни [7], изображенного на рис. 2. Одним из основных результатов первой главы является следующее предложение.

Предложение 1.4. sc(Syn(<?f,i)) - 2" — п для всякого п > 3.

Из предложения 1.4 следует, что ?-c(Syn(<jf„)) = п для всякого п > 3. Это равенство и результат предложения 1.4 дают, в частности, ответ на вопрос задачи 1.

а

Итак, представление идеального языка посредством синхронизируемого автомата может быть значительно компактнее представления с помощью минимального автомата, распознающего язык. Отметим еще одну важную особенность конструкции автомата %х. Этот п-автомат сильно связный и является минимальным синхронизируемым автоматом для своего языка, синхронизирующих слов. В связи с этим возникает следующий естественный вопрос. Для всякого ли идеального языка можно построить некоторый сильно связный МСА?

Мы начинаем изучение этого вопроса с рассмотрения класса главных идеальных языков, т.е. языков вида Е*и.'Е*, где w G Е*. Такой подход представляется довольно естественным, поскольку главный идеал является частным случаем конечно порожденного идеального языка, т.е. языка, вида E*WiE* U... U E*Wk%*, где wi,ид. - слова над алфавитом Е. В свою очередь, конечно порожденные идеальные языки уже изучались как языки синхронизирующих слов синхронизируемых автоматов в цикле совместных работ Прибавкиной и Родаро [13] - [15).

Обозначим длину слова w через \w\. Пусть задан идеальный язык ICH*. Всюду в дальнейшем будем предполагать, что |Е| > 1. Для идеального языка I обозначим через rdc(I) наименьшее возможное число состояний в сильно связном синхронизируемом автомате, язык синхронизирующих слов которого совпадает с I. В параграфе 2.2 второй главы приведен полиномиальный алгоритм построения сильно связного синхронизируемого автомата с |го| 4-1 состоянием, язык синхронизирующих слов которого, совпадает с Iw = Е*гоЕ*, где w € £*. Корректность работы алгоритма, доказана в параграфе 2.3. Основным результатом второй главы является следующая теорема-

Теорема 2.1. Для главного идеального языка. 1и, = Е*шЕ*, где |Е| > 1, существует сильно связный автомат 38 с |ш| + 1 состоянием, такой,

что Syn(^) = /„. Этот автомат строится за время 0(|и>| • |Е|).

Из теории формальных языков известно, что дескриптивная сложность Iw равна |-ш| + 1. В параграфе 2.4 доказана следующая теорема.

Теорема 2.3. Пусть дай идеальный язык Iw — E*u>E*. где w G Е*. Тогда rc(Iw) = |ш| + 1.

Таким образом, для главного идеального языка получаем равенства rdc(Iw) = rc(Iw) = зс(1г11) = Н + 1.

Ясно, что главный идеальный язык является частным случаем конечно порожденного идеального языка. Поэтому естественно теперь перейти к задаче вычисления величины rdc(I) для конечно порожденного идеала I. В третьей главе показано, что значение синхронизационной слолшости идеального языка не всегда достигается на сильно связном автомате. Более того, минимальный по числу состояний сильно связный синхронизируемый автомат, для которого данный язык 1п является языком синхронизирующих слов, может быть экспоненциально больше минимального синхронизируемого автомата для этого языка.. В частности, для всякого п > 1 существует идеальный язык 1п, для которого имеют место равенства rc(In) = sc(I„) = п + I и rdc(In) = 2". Примером такого языка I,, является язык Е-" всех слов длины не меньше п над алфавитом Е. В параграфе 3.1 продемонстрировано, что для языка In — Е-п над Е = {а, 6} существует единственный с точностью до изоморфизма сильно связный синхронизируемый автомат SB с 2га состояниями такой, что Syn(^) = /„.

Рассмотрим теперь произвольный конечно порожденный идеальный язык I — Е*5Е*, где 5 С Е+ - конечное множество слов. Без ограничения общности можно считать, что никакое слово из S не является фактором другого слова из этого множества. В таком случае естественно называть множество S антчфакториалъным. В третьей главе описывается алгоритм построения сильно связного синхронизируемого автомата языком синхронизирующих слов которого является конечно порожденный идеальный язык Е*5Е*. Основной результат третьей главы сформулирован в следующей теореме.

Теорема 3.3. Пусть S конечное, антифакториальное множество непустых слов над Е. Существует сильно связный синхронизируемый автомат сё$ такой, что Sjai(^s) — E*>SE*. Этот автомат, имеет не более 2" состояний, где п = rriax {|.s| | s E 5}.

Для множества S = Еп результирующий автомат с€$ совпадает с автоматом 38, построенным для языка S-", стало быть, в этом случае

имеет в точности 2" состояний. Кроме того, как было сказано выше, rrfc(E-") = 2". Значит, верхнюю оценку, полученную из теоремы 3.3, на число состояний в искомом автомате для которого SynC^s) = улучшить нельзя.

В четвертой главе решаются задачи 3 и 4, связанные с определением классов вычислительной (ложности задач SYN-EQUALITY н RESET-INEQUALITY. Из теории сложности вычислений известно, что PSPACE-полной является задача проверки равенства языков, распознаваемых двумя данными недетерминированными конечными автоматами |1). В четвертой главе доказано, что задача проверки равенства языков синхронизирующих слов двух данных автоматов также является PSPACE-полной. Наряду с задачей проверки равенства языков синхронизирующих слов двух данных автоматов, естественно рассмотреть также задачу SYN-INCLUSION:

УСЛОВИЕ. Заданы синхронизируемые автоматы ,&/ и 38. ВОПРОС. Верно ли, что Svn(>/) С Syn(^)?

Один из основных результатов четвертой главы сформулирован в следующей теореме.

Теорема 4.2. SYN-EQUALITY и SYN-INCLUSION PSPACE-гкшш.

Фактически в диссертации получен более сильный результат, утверждающий, что PSPACE-полной является задача проверки совпадения языка синхронизирующих слов данного автомата с языком синхронизирующих слов некоторого фиксированного 3-автомата 38. Теперь естественно задать вопрос о классе вычислительной сложности следующей задачи. Пусть дан синхронизируемый автомат „с/, и пусть задано некоторое натуральное число f. Насколько сложной является задача проверки неравенства гс{1) < £, где I = Syn(.^)? В четвертой главе показано, что эту задачу молено решить за полиномиальное от размера время в случае, когда С < 3. Но уже для С = 3 сформулированная задача оказывается PSPACE-полной. Таким образом, существование полиномиального алгоритма вычисления синхросложности данного идеального языка маловероятно. Результаты о сложности задачи RESET-INEQUALITY для £ = 3 (в случае четырехбуквенного алфавита) и t = 4 (в случае двух-буквенного алфавита) сформулированы в следующих двух теоремах.

Теорема 4.6. Пусть дан синхронизируемый автомат srf, алфавит ко-

торого содерэ/сит хотя бы четыре буквы. Задача проверки неравенства гс{1) < 3, где I — Syn(i/), является PSPACE-полной.

Теорема 4.8. Пусть дан синхронизируемый автомат .е/ над двухбук-вепным алфавитом. Задача проверки неравенства гс{1) < 4, где I — Syn^), является PSPACE-полной.

Пятая глава диссертации посвящена изучению класса регулярных языков, представнмых синхронизируемыми автоматами. В этом классе, очевидно, содержатся все идеальные языки. Более того, заданный регулярный язык L С Е* совпадает с языком синхронизирующих слов минимального ДКА ß/^ в том и только том случае, когда L — двусторонний идеал в Е*.

В параграфе 5.1 рассматривается некоторый специальный класс автоматов, для которого устанавливается, что всякий автомат sd из этого класса является синхронизируемым, более того, некоторое слово из распознаваемого автоматом .е/ языка является синхронизирующим для „с/. В параграфе 5.2 сформулировано необходимое и достаточное условие синхронизируемости минимального автомата, .с//., распознающего данный регулярный язык L, некоторым словом из L. В этом же параграфе найдено необходимое и достаточное условие для того, чтобы имело место равенство Syn(^) П L = 0. Таким образом, в пятой главе описывается класс всех регулярных языков, представнмых синхронизируемыми автоматами, что приводит к решению задачи 5. Для того, чтобы сформулировать основные результаты пятой главы, введем некоторые обозначения и определения. Напомним, что слово w € Е* называется константой для регулярного языка L, если для любых uj, и_>, и:), щ 6 Е* имеет место импликация

U\WU2 € L, щгигц & L => щи>щ € L.

Обозначим множество всех констант L через C(L). Заметим, что C(L) содержит множество Z(L) = (to | Е*шЕ* П L = 0}. Пусть LOT;*, через L обозначим L = Е* \ L. Напомним, что язык / СЕ* называется правым идеалом, если I непустой и 7£* С I. Основными результатами пятой главы являются следующие предложения.

Предложение 5.8. является синхронизируемым и LnSyn(.c/t) ф 0 тогда и только тогда, когда выполняются свойства:

(i) C_(L) ф 0;

(ii) L не codepoicum правых идеалов.

Предложение 5.9. s^i является синхронизируемым и LnSynfja^) ■ 0 тогда и только тогда, когда выполняются свойства: (г) ZJL) ф 0;

(ii) L содержит щмвый идеал.

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

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

• полиномиальный алгоритм построения сильно связного МСА для главного идеального языка;

• алгоритм построения сильно связного синхронизируемого автомата, язык синхронизирующих слов которого совпадает с данным конечно порожденным идеалом;

• доказательство PSPACE-полноты задачи SYN-EQUALITY;

• доказательство PSPACE-полноты задачи RESET-INEQUALITY при £ = 3 (£ = 4) в случае четырехбуквенного (двухбуквенного) алфавита;

• характеризация класса регулярных языков, распознаваемых синхронизируемыми автоматами.

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

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

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи // М.: Мир. — 1982.

[2] Клиффорд А., Престон Г. Алгебраическая теория полугрупп /7 Перевод с англ. В.А. Баранского н В.Г. Житомирского, под ред. Л.Н. Шеврина. Т. 1, 2 - М.: Мир. — 1972.

|3j Шур A.M. Языки с конечным антисловарем: индекс роста и свойства автоматов // Изв. Урал. гос. ун-та. — 2010. — №74. Математика, механика, информатика. Выи. 12. — С. 218-243.

[4] Bonizzoni P. Jonoska N. Existence of constants in regular splicing languages /7 Inf. Comput. — 2015. — Article in press. — http://dx.doi.Org/10.1016/j.ic.2015.04.001.

Brzozowski. Л. In search of most complex regular languages // In N. Moreira, R. Reis (eds.) — CIAA 2012. — Lect. Notes Coniput. Sci. — Springer-Verlag; Berlin-Heidelberg. — 2012. - Vol. 7381. — P. 5-24. Brzozowski ,1., .liraskova G., Li. B. Quotient complexity of ideal languages // Thcor. Сотр. Sci. - 2013. - Vol. 470. - P. 36-52. Cerny J. Poznanika к homogennyin eksperimentom s koneciiymi anto-matami // Mat.-FVz. Cas. Slovensk. Akad. Vied. — 19(54. — V.14. — P. 208-216.

Crochemore M., Hancart C. Automata for pattern matching // In G. Rozenberg, A. Salomaa, (eds.) Handbook of formal languages. — Springer. - 1997. - Vol. 2. - P. 399-462.

D'Angeli D., Rodaro E. Groups and semigroups defined by colorings of synchronizing automata // MAC. - 2011. - Vol. 24(6). - P. 773-794. De Luca A., Varricchio S. Finiteness and regularity in semigroups and formal languages // Springer. — 1999.

Moore F.R. On the bounds for the state-set. size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata // IEEE Transactions on Computers. — 1971. — Vol. G-20(10). - P. 1211-1214.

Paun G., Rozenberg G., Salomaa A. DNA computing, new computing paradigms. // Springer, Berlin. — 1998.

Pribavkina E. V., Rodaro E. Finitely generated synchronizing automata // In A. H. Dediu, A. M. Ionescu, C. Martin-Vide (eds.) Int. Conf. LATA 2009. — Lect. Notes Сотр. Sci. — Springer-Verlag, Berlin-IIeidelberg-New York. - 2009. - Vol. 5457. - P.672-683. . Pribavkina E., Rodaro E. Synchronizing automata with finitely many minimal synchronizing words // Information and Computation. — 2011. - Vol. 209, Issue 3. - P. 568 579.

Pribavkina E.V., Rodaro E. Recognizing synchronizing automata with

finitely many minimal synchronizing words is PSPACE-complete // In

B. Lowe (eds.) CiE 2011. — Lect. Notes Сотр. Sci. — Springcr-Verlag,

Berlin-Heidelberg. — 2011. - Vol. 6735. — P. 230-238.

Reis R., Rodaro, E. Ideal regular languages and strongly

connected synchronizing automata /./ [Электр. публ.)

http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR.13/dcc-2013-01.pdf

[17] Reís R., Rodara. E. Regular ideal languages and synchronizing automata // In: J. Karhumáki, A. Lepisto. L. Zamboui (eds.) WORDS 2013. — Lect. Notes Сотр. Sci. — Springer. Heidelberg. — 2013. — Vol. 8079. - P. 205-216.

[18] Rystsov I.K. Reset, words for commutative and solvable automata /'/' Theor. Comput. Sci. - 1997. - Vol. 172. - P. 273-279.

[19] Salomaa K., Yu S., Zhang Q. The state complexity of some basic operations on regular languages // Theor. Comput. Sci. — 1994. — Vol. 125. - P. 315-328.

[20| Volkov M. V. Synchronizing automata and the Cerny conjecture /./ In C. Martin-Vide, F. Otto. II. Fernau (eds.) Languages and Automata: Theory and Applications. LATA 2008. — Lect, Notes Сотр. Sci. — Springer-Verlag. Berlin-Heidelbcrg-Ncw York. - 2008. - Vol. 5196. -P. 11-27.

[21] Volkov M.V. Synchronizing automata, preserving a chain of partial orders. - Theor. Comput. Sci. - 2009. - Vol. 410. - P. 3513-3519.

Публикации автора по теме диссертации

Статьи, опубликованные в журналах из списка ВАК

[22] Gusev V.V., Maslennikova M.I., Pribavkina E.V. Finitely generated ideal languages ami synchronizing automata. // In J. Karhumáki, A.Lepisto, L.Zamboni (eds.) 9th Int. Conf. WORDS 2013. - Lect. Notes Сотр. Sci. - Springer-Verlag. Berlin-Heidelberg. - 2013. - Vol. 8079. - P. 143-154.

[23] Gusev V.V., Maslennikova M.I., Pribavkina E.V. Principal ideal languages and synchronizing automata. // In V. Halava, J. Karhumáki, Yu. Matiyasevich (eds.) The Special Issue of the RuFiDiM 2012. -Fundamenta Inforinaticae. - 2014. — Vol. 132(1). - P. 95-108.

[24j Maslennikova M. Complexity of checking whether two automata, are synchronized by the same language. // In H.Jiirgensen, .1.Karhumáki, A.Okhotin (eds.) 16th Int. Workshop DCFS 2014. - Lect. Notes Сотр. Sci. — Springer-Verlag, Berlin-Heidelberg. - 2014. - Vol. 8614. - P. 306-317.

[25] Maslennikova M., Rodara E. Representation of (left) ideal regular languages by synchronizing automata. // In L. Bcklemishev (Ed.) 10th

Int. Сотр. Sci. Symp. CSR 2015. — Lect. Notes Сотр. Sci. — SpringerVerlag, Berlin-Heidelberg. - 2015. - Vol. 9139. - P. 325-338.

Другие публикации

26] Масленникова М.И. Синхронизационная сложность идеальных языков. // Современные проблемы математики и ее приложений: Тез. 46-й Международной молодежной школы-конференции. — Екатеринбург, Институт математики и механики УрО РАН. — 2015. — С. 8-12.

27] Maslennikova M.I. Reset complexity of ideal languages. // In M. Bielikova, G. Friedrich, G. Gottlob, S. Katzenbeisser, R. Spanek, G. Turan (eds.) Int. Conf. SOFSEM 2012. - Proc. Institute of Computer Science Academy of Sciences of the Czech Republic. — 2012. — Vol. II.

— P. 33 44.

28] Gusev V.V., Maslennikova M.I., Pribavkina E.V. Algorithms and complexity aspects in I,he theory of synchronizing automata. // (Abstract) In A.S.Kulikov, A.M.Shur (eds.) Algorithms к Complexity, Proc. of the 6th School «Computer Science Days in Ekaterinburg». — Ekaterinburg, Ural University Press. - 2013. -- P. 64-67.

29] .Maslennikova M. Two PSPACE-complete problems concerning ideal languages. // In A.M.Shur (ed.) Strings, languages, automata. Abstracts of reports and other materials of the 7th School «Computer Science Days in Ekaterinburg». — Ekaterinburg, Ural University Press.

- 2014. - P. 22-24.

30] Maslennikova M. Complexity of checking whether two automata are synchronized by the same language. // (Abstract) In V.V.Mazalov, A.A.Ivashko (eds.): Proc. of the Third Russian Finnish Symposium on Discrete Mathematics. — Petrozavodsk, Russia, Institute of Applied Mathematical Research KarRC RAS. - 2014. - P. 122-125.

31] Maslennikova M., Rodaro E. Principal (left) ideal languages, constants and synchronizing automata. // (Abstract) In V.V.Mazalov, A.A.Ivashko (eds.): Proc. of the Third Russian Finnish Symposium on Discrete Mathematics. — Petrozavodsk, Russia, Institute of Applied Mathematical Research KarRC RAS. - 2014. - P. 114-121.

Подписано в печать 31.08.2015 Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,0 Тираж 100 экз. Заказ №2348

Отпечатано в копировальном центре «Таймер» 620075, Екатеринбург, ул. Луначарского, 136