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

• Масленникова, Марина Игоревна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Масленникова, Марина Игоревна

Содержание

Введение

0.1 Конечные автоматы

0.2 Синхронизируемые автоматы и гипотеза Черни

0.3 Представление идеальных языков синхронизируемыми автоматами

0.4 Определения и обозначения

0.5 Предварительные сведения о конечно порожденных синхронизируемых автоматах

0.6 Предварительные сведения о синтаксической полугруппе

регулярного языка

0.7 Предварительные сведения из теории сложности вычислений

0.8 Апробация результатов

1 Языки синхронизирующих слов медленно синхронизируемых автоматов

1.1 Верхняя оценка синхронизационной сложности идеального языка

1.2 Синхронизационная и дескриптивная сложность языков синхронизирующих слов медленно синхронизируемых автоматов

1.3 Вопрос о единственности МСА

2 Главные идеальные языки и синхронизируемые автоматы

2.1 Вопрос о единственности МСА в классе сильно связных автоматов

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

2.3 Доказательство корректности алгоритма

2.4 Синхронизационная сложность главного идеального языка

2.5 Синтаксическая полугруппа главного идеального языка

3 Конечно порожденные идеальные языки и синхронизируемые автоматы

3.1 Идеальный язык, порожденный

3.2 Идеальный язык, порожденный множеством слов постоянной длины

3.3 Идеальный язык, порожденный конечным множеством слов

3.4 Идеальный язык, порожденный двумя словами

4 Вычисление синхронизационной сложности идеальных язы-

ков

4.1 Принадлежность классу PSPACE

4.2 PSPACE-иолнота

5 Представление регулярных языков синхронизируемыми автоматами

5.1 Левые факторы главных левых идеальных языков

5.2 Регулярные языки и синхронизируемые автоматы

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

Введение диссертации (часть автореферата) на тему «Идеальные языки и синхронизируемые автоматы»

Введение

0.1 Конечные автоматы

Детерминированным конечным, автоматом (ДКА) мы будем называть тройку 8$ = {(¿^.д), где С) - конечное множество состояний. Е - конечный входной алфавит, ад: С^хТ, - всюду определенная функция переходов. Отмстим, что в теории формальных языков к набору данных, определяющему конечный детерминированный автомат, обычно добавляют выделенное начальное состояние (¿0 € ф и множество Р заключительных (или конечных) состояний. Мы также будем пользоваться этим вариантом определения и писать «с/ = ((¿,Т,.8,до,Р), когда речь будет идти о языках, распознаваемых автоматами. Для заданного ДКА .в/ = Е. д. до, Р) положим Ь[.о/] — {и; | с^.и; 6 Р}. при эюм будем говорить, что язык принимается (или распознается) автоматом

л/. Язык называется регулярным, если он распознается некоторым детерминированным конечным автоматом. Всюду в данной работе будем использовать слово "автомат" в качестве синонима термина "детерминированный конечный автомат".

Конечный автомат является довольно естественной моделью дискретно работающего устройства, которая находит применение во множестве областей. Прообраз такой модели был представлен в работе нейрофизиологов МакКаллока и Питтса [36], написанной в 1943 году. В ней автоматы были введены как упрощенная модель функционирования нейронов. Примечательно, что в этой работе также были заложены основы машинного обучения. Позднее Клини [33] уточнил и развил модель, предложенную МакКаллоком и Питтсом, чем и заложил основы теории автоматов, как математической дисциплины. Именно в работе [33] был получен основополагающий результат теории автоматов, утверждающий совпадение класса языков, распознаваемых конечными автоматами, с классом языков, задаваемых при помощи регулярных операций -объединения, произведения и итерации. Таким образом, Клини рассматривал конечные автоматы как распознаватели формальных языков. Исторически же первую модель распознавателя языков предложил в 1936 году английский математик Тьюринг [63]. Машина Тыоринга (которая является более общим объектом, нежели конечный автомат) могла не только распознавать строки символов, но и преобразовывать одни строки в другие. На ее основе Тьюринг спроектировал один из первых в

мире компьютеров. Более того, термин "'компьютер'" в его современном значении впервые употребил именно Тьюринг. Благодаря развитию вычислительной техники теория автоматов пополнилась многочисленными приложениями. На сегодняшний день теория автомаюв лежит в основе теории компиляторов и формальной верификации программ.

Теория автоматов также имеет глубокие взаимосвязи с логикой и алгеброй. Мысль о том что логические высказывания могут быть изучены в терминах конечных автоматов была высказана еще Тьюрингом в работе [63]. написанной в 1937 году. Эта мысль была поддержана и развита фон Нейманом в работе [66], где автомат, моделирующий логическое высказывание. представлялся "черным ящиком" с конечным числом входов и конечным числом выходов. Операция, выполняемая черным ящиком, в гаком случае задается законом, которые определяет, какие выходы активируются в ответ на посылаемые тем или иным входам сигналы. Отличительной особенностью модели фон Неймана является отсутствие информации о внутреннем устройстве автомата. Идею рассмотрения автомата как "черного ящика" можно обнаружить и в работе Мура [37] «Gedankeri-experiments on Sequential Machines», опубликованной в 1956 году. Автоматом Мура называется конечный автомат с множеством состояний Q. входным алфавитом Е и функцией переходов д, дополненный конечным множеством выходных символов А. а также выходной функцией 7, которая ставит в соответствие каждому состоянию q € Q символ алфавита Д. Таким образом, автомат Мура, находящийся в некотором состоянии q £ Q при чтении входною символа а 6 Е не только переходит в новое состояние р = S(q.a), но и выводит символ 7(р). Для Мура такой автомат служил моделью дискретно работающих устройств, о внутренней конструкции которых ничего не известно. В связи с этим, главный вопрос, интересовавший Мура, состоит в следующем. Предположим, над некоторым устройством потерян контроль. Какую последовательность входных символов необходимо подать на вход устройства, чтобы по наблюдаемым выходным символам можно было однозначно определить состояние, в котором будет находится устройство? В работе [37] такая последовательность входных символов называется экспериментом, при этом длиной эксперимента естественно назвать количество символов последовательности. Отметим, что эксперименты Мура имели адаптивный характер, т.е. каждый следующий символ входной последовательности зависел от уже полученной последовательности выходных символов. Одним из важнейших результатов работы Мура является по-

лученная оценка длины кратчайшего эксперимента, позволяющего определить состояние устройства в конце эксперимента. В [37] показано, чю для произвольного автомата Мура с н состояниями существует эксперимент длины не боаыле п(-п~1>, коюрым можно определить состояние автомата в конце эксперимента. С практической точки зрения длина эксперимента определяет, насколько быстро можно восстановить контроль над устройством.

Вскоре после работы Мура появилась статья Гинзбурга [30], где рассматривались эксперименты особого типа, которые были названы однородными. Такие эксперименты являются фиксированными конечными последовательностями входных символов, не зависящими от порождаемой выходной строки. В случае однородных экспериментов выходная последовательность используется только для определения заключительного состояния автомата после проведения эксперимента. Однако на практике далеко не всехда удастся наблюдать ответные сигналы устройства: например, в случае когда автомат, моделирующий работу данного устройства не имеет выходной функции. В связи с этим возникает следующий естественный вопрос: как в этом случае определить, существует ли последовательность входных символов, переводящая все состояния автомата в некоторое выделенное состояние? Ответ на этот вопрос был дан словацким математиком Черни [20] в 1964 году. Именно в этой работе и было впервые формально введено I лавное понятие данной диссертации.

0.2 Синхронизируемые автоматы и гипотеза Черни

Прежде, чем ввести основное понятие данной диссертации, зафиксируем некоторые обозначения. Пусть дан детерминированный конечный автомат ¿г/ = (<3,Е,<!>). Элементы заданного алфавита Е мы будем называть буквами, а конечные последовательности букв из Е - словами. Пустым словом мы будем называть пустую последовательность букв и обозначать через е. Множество всех слов над алфавитом Е. включая пустое, мы будем обозначать Е*, а множество непустых слов через Е+. Функция 5 естественным образом продолжается на (2 х Е*: для (/ е и ъо £ Е* полагаем 5{д.1и) = д. если и< = г. и <5(д. ш) = 5(д(д.г').а), если и.' = на для некоторою г £ Е* и а £ Е. Таким образом, функция 6 определяет действие каждого слова из Е* на множестве СТакже действие функции 5 можно расширить до действия на подмножествах СОпределим лля всякого Б С С) и всякого слова ш £ Е* образ множества 5 равен-

ством S(S, w) = {ö(q, w) | q £ S}. Часто для простоты обозначений, когда функция переходов понятна из контекста, мы б\дем вместо S(q.w) использовать запись q.u\ а вместо S(S.w) запись S .и\

Автомат ,о/ = (Q,E.<5) называется синхронизируемым, если существует слово w над алфавитом Е, под действием которого все состояния автомата переводятся в одно: q.w = q'. w для всех q,q' £ Q. Другими словами, для автомата существует некоторое слово w, переводящее множество состояний Q в одноэлементное подмножество. Всякое слово w с таким свойством называется синхронизирующим для автомата Таким образом, синхронизирующее слово в каком-то смысле "перезагружает" автомат: если текущее состояние автомата неизвестно, то после прочтения синхронизирующего слова состояние автомата будет определено однозначно. Обозначим через Syn(,c/) множество всех синхронизирующих слов для автомата .с-/. Минимум длин синхронизирующих слов автомата sé называется его порогом, сипхроииза ции. эту величину будем обозначать через || Syn(.o/)||. В качестве примера рассмотрим автомат s/4 с четырьмя состояниями, приведенный на рис. 1. Нетрудно проверить, что слово tu = aba является кратчайшим синхронизирующим словом для заданного автомата. Таким образом, || Syn(j2í^)|| = 3.

Ь а а, Ъ

Рис. 1: Автомат ,с/4

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

Отметим теперь, что для автомата над алфавитом Е = {а, 6} на рис. 1 можно найти синхронизирующее его слово путем анализа структуры автомата. В самом деле, каждое синхронизирующее слово для ,й/4 должно переводить все состояния автомата в состояние 3. поскольку оно фиксируется всеми буквами алфавита. В частности, необходимо, чтобы состояние 0 под действием некоторою слова перешло в 3. Самым коротким таким словом является w = aba. Для завершения проверки данного автомата на синхронизируемость осталось убедиться, что слово w переводит состояния 1 и 2 в состояние 3. Проделанные рассуждения позволяют, на самом деле, описать множество всех синхронизирующих слов для .е/4. Действительно, всякое слово вида xabay, где х,у € Е*, является синхронизирующим для автомата поскольку aba G Syn(._cÍ4). С другой стороны, всякое слово, переводящее состояние 0 в 3, нредегавимо в виде xabay для некоторых х, у G Е*. Таким образом. Syn(ja4) = Е*аЬаЕ*. В общем случае, глядя непосредственно на автомат, далеко не всегда удается легко найти некоторое синхронизирующее слово для заданного автомата, не говоря уже о том, чтобы найти множество всех синхронизирующих его слов. Кроме того, не каждый автомат является синхронизируемым. В связи с этим возникают сразу же два следующих естественных вопроса. Как по данному автомату проверить, является ли он синхронизируемым? Как найти синхронизирующее его слово? Ответ на первый вопрос содержится в следующем утверждении из [20].

Предложение 0.1 ( [20], Теорема 2). Автомат .я/ = (Q.E,<5) является синхронизируемым тогда и только тогда, когда для всякой пары состояний q, q' G Q найдется такое слово w G Е*. что q ■ w = q' • w.

Таким образом, автомат является синхронизируемым тогда и только тогда, когда любую пару различных состояний {q. с/} можно "склеить"', т.е. найти подходящее слово, переводящее состояния q и q' в некоторое состояние р. Для проверки этого условия удобно использовать следующую конструкцию. Построим для автомата = (Q. £. 5) автомат пар = Е. с множеством состояний

Q<-2) = {{q.q'}\q.,q'eQ.q¿q'}U{s},

входным алфавитом Е и функцией переходов д^К действие которой для всякой буквы a G Е определено следующим образом:

6^({q.q'}.a,) = { если S(q, а) ф b{c{ а) ^

v L J ' у s, если ó{q,a) = ó(q ,а):

s. а) = ,s.

Например, автомат пар для автомата изображенного на

рис. 1, приведен на рис. 2.

а

Рис. 2: Автомат пар

Из конструкции автомата пар лет ко видеть, что для произвольной пары состояний д, д' €Е автомата ,с/ имеет место равенство д. ш = д'. ш для некоторого ь> € £* тогда и только тогда, когда 6(2)({д,д'}.1с) = в. Таким образом, предложение 0.1 можно переформулировать следующим образом.

Предложение 0.2. Автомат является синхронизируемым тогда и только тогда, когда из каждого состояния достижимо состо-

яние з.

Предложение 0.2 представляет эффективный алгоритм проверки данного автомата на синхронизируемость. В самом деле, число состояний в автомате пар равно -[^ причем из каждою состояния этого авто-

мата определены переходы но к = |£| буквам алфавита. Теперь для проверки автомата .с/ гга синхронизируемость достаточно выяснить, достижимо ли состояние я из каждого состояния автомата 'Р^(^). Из теории алгоритмов на графах хорошо известно, что последняя задача решается алгоритмом поиска в ширину за время 0(|£^|2|Е[). Отметим, что приведенный алгоритм лишь устанавливает, является ли данный автомат синхронизируемым, но никакого синхронизирующего слова на выходе мы не

получим. В то же время, с точки зрения практических приложений синхронизируемых автоматов, оказывается важной задача поиска и оценки длины кратчайшего синхронизирующего слова. Алгоритм, выдающий в случае синхронизируемое™ автомата некоторое синхронизирующее его слово, был найден Эпштейном в [29]. Этот алгоритм работает за время 0(|<3|3 + |<5|2 • |Е|), требует 0(\0\2 + |(5| • |Е|) памяти и находит синхронизирующее слово длины 0(|<2|3).

Для нахождения кратчайшего синхронизирующего слова весьма удобной оказывается конструкция автомата подмножеств. Автомат подмножеств = (2*2, Е.8) автомата .я/ = определяется следующим образом. Множество состояний 2^ состоит из всех непустых подмножеств ф. а функция переходов определяется естественным образом по функции переходов и обозначается так же буквой Данная конструкция является классической в теории формальных языков и впервые появилась в работе Рабина и Скотта [52]. На рис. 3 изображены автомат

и его автомат подмножеств V{с6\).

Предложение 0.3. Слово ю £ Е* является синхронизирующим для автомата -й/ = Е. 8) тогда и только тогда, когда слово и: в автомате Р(.0/) переводит состояние ф в одноэлементное множество.

Таким образом, с помощью конструкции автомата подмножеств легко найти кратчайшее синхронизирующее слово для данного автомата. В самом деле, достаточно найти с помощью алгоритма поиска в ширину кратчайшее слово, переводящее С} в некоторое одноэлементное множество. Например, для автомата изображенною па рис. 3, кратчайшим синхронизирующим словом является ю = аЬЬЬаЬЬЬо. Путь, помеченный буквами этого слова, изображен в автомате подмножеств "Р^ц) на рис. 3 жирными стрелками.

Оценим сложность описанного выше алгоритма. Автомат Т'(£/) имеет 21е?! — 1 состояний. Таким образом, кратчайшее синхронизирующее слово для автомата находится поиском в ширину в автомате 'Р(.:о/) из состояния <3 за 0(2!^'[Е|). Следовательно, приведенный алгоритм является экспоненциальным от числа состояний в исходном автомате л/. Таким образом, в случае, когда автомат $ содержит достаточно много состояний, применение этого алгоритма представляет некоторые трудности. С другой стороны, существование квадратичного от числа состояний алгоритма проверки автомата на синхронизируемость с помощью

автомата пар наталкивает на мысль, что, возможно, найдется и эффективный алгоритм нахождения кратчайшего синхронизирующего слова. Однако есть результаты, позволяющие утверждать, что существование полиномиальною алюритма для этой задачи маловероятно. Эти результаты касаюгся вычислительной сложности следующих задач.

SHORT-RESET-WORD

УСЛОВИЕ. Заданы ДКА и натуральное число L

ВОПРОС. Верно ли. что автомат srf имеет синхронизирующее слово длины не больше

SHORTEST-RESET-WORD

УСЛОВИЕ. Заданы ДКА и натуральное число С.

ВОПРОС. Верно ли, что автомат имеет синхронизирующее слово длины ровно Р

Эпштейном в ¡29] показано, что задача SHORT-RESET-WORD является NP-полной Самотий в [58] показал, что задача SHORTEST-RESET-WORD является NP-трудной и co-NP-трудной. Таким образом, если NP ф co-NP. задача SHORTEST-RESET-WORD не может принадлежать классу NP Значит, даже недетерминированный алгоритм не может найти кратчайшее синхронизирующее слово для заданного автомата за полиномиальное время Более тою. нз-

вестно из [9], что не существует даже полиномиального алгоритма с конечной относительной погрешностью для задачи поиска кратчайшего синхронизирующего слова, т.е. нет полиномиального алгоритма, который находил бы для всякого синхронизируемого автомата синхронизирующее его слово длины не больше чем к-1| 8уп(..с/)|| при некотором фиксированном к. Недавно Ольчев-ский и Уммельс показали в [40], что задача БНОКТЕйТ-КЕЗЕТЛУСШБ полна для класса ОР1. Другой результат, который стоит упомянуть в этом контексте, касается сложности задачи вычисления порога синхронизации для заданного автомата. В 2010 году Ольчевский и Уммельс показали в [40], что задача вычисления порога синхронизации данного автомата полна для класса РР1^'06', функционального аналога класса Р^р[|об] задач распознавания, разрешимых за полиномиальное время на детерминированной машине Тьюринга, которая может логарифмическое от размера задачи число раз обращаться за подсказкой к оракулу для ЫР-полной задачи. Предположительно, задача нахождения кратчайшего синхронизирующего слова для заданного автомата сложнее задачи вычисления его длины. Однако точное положение в иерархии классов сложности задачи нахождения кратчайшего синхронизирующею слова остается неизвестным.

Так как задача точного вычисления значения порога синхронизации заданного автомата трудная, то возникает следующий естественный вопрос. Как зависит порог синхронизации от числа состояний в автомате? Для краткости будем называть автомат с п состояниями п-автоматом. В 1964 году Черни [20] построил для каждого п > 1 синхронизируемый п-автомат над двухбуквенным алфавитом с порогом синхронизации (п — I)2. Автомат Черни ^ с четырьмя состояниями представлен на рис. 3. Позднее Черни высказал предположение, что автоматы из этой серии реализуют наихудший случай, т.е. что всякий синхронизируемый 7?-автомат обладает синхронизирующим словом длины не более (п — I)2. Это предположение получило название гипотезы Черни.

Несмотря на простоту формулировки >1 усилия многочисленных исследователей. гипотеза Черни остается не доказанной и не опровергнутой уже 50 лет. Более того, до сих пор не найдена верхняя квадратичная опенка на порог синхронизации произвольного д-автомата. Лучшая известная на сегодняшний день верхняя оценка на длину кратчайшего синхронизирующего слова произвольного п-автомата была получена Пэном [47] еще в 1983 году. В [47] показано, что для произвольного синхронизируемого п-автомата .<г/ имеет место

Несмотря на го, что вопрос о справедливости гипотезы Черни остается не разрешенным в общем случае, эта гипотеза доказана для многих классов ав-

1 Класс ОР был определен формально в [42]

томатов [28, 29,-32. 46, 49, 62, 65]. Этот список результатов далеко не полный, однако результаты такого рода представляют и самостоятельный интерес, поскольку позволяют выяснить, как влияет то или иное свойство синхронизируемого автомата на длину его кратчайшего синхронизирующего слова. С другой стороны, в результате рассмотрения специальных классов синхронизируемых автоматов иногда удается установить связь между автоматами и объектами другой природы, что может оказаться полезным в соответствующих областях фундаментальной математики. Остановимся чуть подробнее на примере одной из таких связей. ДКА во/ = ((}, Е. 6) называется автоматом с нулем, если существует состояние я £ которое переводится всеми буквами алфавита Е в себя. Известно, что длина кратчайшего синхронизирующего слова для произвольного п-автомата с нулем не превосходит [56]. Более того, в [56] для каждого п построен синхронизируемый п-автомат с нулем, для которого кратчайшее синхронизирующее слово имеет длину . Таким образом, в классе автоматов с нулем гипотеза Черни верна. С другой стороны, в работе [5] для произвольного алфавита Е. содержащего хотя бы две буквы, и произвольного

к > |Е| построен синхронизируемый автомат с нулем с п — 2к состояниями над

2

алфавитом Е. порог синхронизации которого равен ^ + ^ — 1. Соответствующая конструкция из [о] была получена в результате анализа взаимосвязей между синхронизируемыми автоматами с нулем и непокрывающими множествами в свободных моноидах. В свою очередь, покрывающие и непокрываю-щие множества в свободных моноидах играют важную роль в теории кодов и комбинаторике слов в связи с понятием максимальных кодов [55].

0.3 Представление идеальных языков синхронизируемыми автоматами

Напомним, что язык I С Е* называется двусторонним идеалом (или просто идеалом), если 1 непустой и Е^Е* С 1. Язык / СЕ* называется левым (соответственно, правым) идеалом, если I непустой и Е* 1 С I (соответственно, /Е" С /). В данной работе рассматриваются только регулярные языки, поэтому для краткости мы будем опускать термин "регулярный", предполагая, что речь идет именно о таком языке. Говоря "идеальный язык", или коротко "идеал", мы будем подразумевать, что рассматривается двусторонний идеальный язык.

Понятие двустороннего идеала занимает центральное место в теории полугрупп [4]. Идеальные языки как двусторонние идеалы в свободном моноиде Е* активно изучаются в связи с различными приложениями в компьютерных пауках на протяжении последних пятидесяти лет [14.26,44]. Нетрудно проверить, что язык Ь С Е* является факторна л ьным (т.е. замкнутым относительно взя-

тия факторов) тогда и только тогда, когда ого дополнение E*\Z - идеал в Е*. Таким образом, факториальные языки суть в точности дополнения идеальных языков Любой факториальный язык можно описать с помощью антисловаря. т.е. списка запрещенных факторов Большую роль в теории и приложениях формальных языков играют факториальные языки с конечным антисловарем (КАС-языки), см.. например. |G]. КАС-языки регулярны и являются в точности дополнениями конечно порожденных идеальных языков, те. языков вида E*t(Ji£* U ... U где w\.... ,Wk слова над алфавитом Е. В свою оче-

редь, конечно порожденные идеальные языки как языки синхронизирующих слов автоматов изучались в цикле совместных работ Прибавкиной и Родаро. см. [48] - [51]. Идеальные языки (из различных классов) возникают также в задачах, связанных с поиском подстроки в строке. Например, пусть текст задан словом iu над некоторым апфавитом S Заданным шаблоном может быть как конечное множество слов, так и произвольный язык L над Е, представленный регулярным выражением Появлением шаблона, задаваемого языком L, в тексте w называется тройка (v,x,v) такая, что w = vxv. где х £ L. Таким образом, поиск в тексте w слова из L эквивалентен поиску префиксов w, принадлежащих языку Е*L. который является левым идеалом, порожденным L [22]. Задачу поиска всех появлений слов из конечного множества L в заданном тексте w можно реши1ь с помощью алгоритма Ахо-Кора( ик [7]. Еще один пример применения идеальных языков в задачах поиска в тексте по шаблону можно найти в недавней работе [67], где рассматривается задача просмотра и обработки с высокой скоростью пакетов данных, передаваемых по каналам связи.

В связи с различными практическими и теоретическими приложениями представляет интерес нахождение объекта для компактного представления идеальных языков. В диссертации идеальные языки ii3vчаются с точки зрения теории автоматов. П\сть si - синхронизируемый автомат с входным алфавитом Е. Язык всех слов, синхронизирующих ,е4, образует ре1улярный идеал вГ С другой стороны, несложно проверить, что справедливо и обратное утверждение если 1 - произвольный регулярный идеал в £*, то найдется синхронизируемый автомат si с входным алфавитом Е, для которого I будет множеством синхронизирующих слов Этот автомат можно использовать как своеобразный распознаватель языка 1 - для того, чтобы проверить, принадлежит ли какое-то слово w £ Е* языку I, достаточно применить w к каждому состоянию ДКА si и сравнить получающиеся состояния, w £ I тогда и только то!да, когда все эти состояния совпадают. Ясно, что описанная проверка занимает 0(|«'| ■ |Q|) времени, где Q - множество состояний si. Таким образом, автомат si можно рассматривать как сжатое представление языка I. Одной из основных мер описательной сложности регулярных языков является чис-

ло состояний в минимальном детерминированном конечном автомате, распознающем язык. Эта мера сложности называется дескриптивной сложностью регулярного языка. Изучению этой характеристики регулярных языков и ее поведению при различных операциях над языками посвящено множество работ (см.. например. [13] [18] и [68]). Эта характеристика регулярных языков удобна при их изучении в связи с реализацией различных алгоритмов. Дескриптивную сложность регулярного языка L будем обозначать через sc(L). В литературе рассматриваются и дру! ие меры сложности представления регулярных языков: недетерминированная сложность, синтаксическая сложность и др. Мы вводим в рассмотрение новую меру сложности регулярных языков, являющихся идеалами, связанную с их представлением посредством синхронизируемых автоматов. А именно, синхронизационной сложностью (кратко сип-хросложностью) гс{1) идеального языка I назовем минимальное возможное число состояний в синхронизируемом автомате, для которого 1 будет множеством синхронизирующих слов. Всякий синхронизируемый автомат, на котором достигается значение синхронизационной сложности идеального языка J, будем называть минималъньш синхронизируемым автоматом (кратко МСА) для I. Обозначим через srfj. минимальный автомат распознающий регулярный язык L. Нетрудно проверить, что для всякого идеального языка I имеет место равенство Syn(,c^) = /. Это означает, что синхронизационная сложность произвольного идеального языка I не превосходит его дескриптивной сложности, т.е. rc(I) < sc(I). С другой стороны, в первой главе мы покажем, что для всякого натурального п > 3 существует идеальный язык 1п такой, что rc(In) — п и sc(ln) — 2" — п. В частности, для языка синхронизиурющих слов ?г-автомата Черни [20], изображенного на рис. 4, имеют место равенства 7,c(Svn(<rif„)) = п и sc(Syn(<ifri)) = 2п — п при любом п > 1. Отметим, что все рассматриваемые языки, дескриптивная сложность которых экспоненциально больше сипхросложности, являются языками синхронизирующих слов медленно синхронизируемых д-автоматов. т.е. автоматов с порогом синхронизации близким к (те — I)2. Известные па данный момент серии медленно синхронизируемых автоматов приведены в [8].

Список литературы диссертационного исследования кандидат наук Масленникова, Марина Игоревна, 2015 год

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

[lj Ананичев Д С., Волков М. В . Гусев В. В. Примитивные орграфы с большими экспонентами и медленно синхронизируемые автоматы ,// Записки научных семинаров ПОМП. (Комбинаторика и теория графов. IV). — 2012. - Том 402. - С. 9-39.

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

[3] Левин JI.A. Универсальные задачи перебора // Пробл. передачи информ. - 1973. - Т.9, №3. - С. 115-116.

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

[о] Прибавкина Е.В. Медленно синхронизируемые автоматы с нулем и непо-крывающие множества // Матем. заметки — 2011 — Т.90, Вып. 3 — С. 422-430

(6J Шур A.M. Языки с конечным аптисповарем. индекс роста и свойства автоматов // Изв. Урал. юс. ун-та. — 2010. — Л-74 Математика, механика, информатика. Вып. 12. — С. 218-243.

[7] Aho A., Corasick М J. Efficient string matching, an aid to bibiligraphic search // Connnun. ACM. - 1975. - Vol. 18(6) - P. 333-340.

[8] Ananichev D.S., Gusev V. V.. Volkov M V. Slowly synchronizing automata and digraphs // In P. Hlmeny, A. Kucera (eds ) Mathematical Foundations of Computer Science. — Lect. Notes Comput. Sci. — Springer-Verlag, BerlinHeidelberg. 2010. - Vol. 6281. P. 55 64.

[9] Berlinkov M. V. Approximating the minimum length of synchronizing words is hard // In F. Ablayev. E. \V. Mayr (eds.) Computer Science Theory and Applications — Lect. Notes Comput. Sci. — Springer-Verlag, Berlm-Heidelberg-New York. - 2010 - Vol. 6072 - P. 37-47

[10] Berlinkov M V. Testing for synchronization // 2014. - CoRR abs/1401.2553

[11] Bomzzoni P . De Felice C.. Zizza Z. The structure of reflexive regular splicing languages via Schiitzenberger constants <j Theor. Сотр. Sci. — 2005. — Vol. 334. - P. 71-98

[12] 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.

[13] Brzozowski J. Quotient complexity of regular languages ''/ In J. Dassow, G. Pighizzmi, B. Truthe (eds.) — Proc. 11th Int. Workshop on Descriptional Complexity of Formmal Systems JDCFS 2009. - EPTCS. - 2009. - Vol. 3.

- P. 17 29

[14] Brzozowski J.. Ye. Y. Syntactic complexity of ideal and closed languages /7 In G. Mauri. A. Leporati (eds.) — DLT 2011. — Lect. Notes Comput. Sci. — Springer-Verlag, Berlin-Heidelberg. - 2011. - Vol. G795. - P. 117 128.

[15] Brzozowski. J. In search of most complex regular languages // In N. Moreira, R. Reis (eds.) - - CIAA 2012. - Lect. Notes Comput. Sci. - Springer-Verlag. Berlin-Heidelberg. 2012. - Vol. 7381. P. 5 24.

[16] Brzozowski J.. Jiraskova G., Li. B. Quotient complexity of ideal languages // Theor. Comp. Sci. - 2013. -- Vol. 470. P. 36-52.

[17] Brzozowski J., Liu U. Universal witnesses for state complexity of basic operations combined with reversal // In S. Konstantinidis (ed.) CIAA 2013.

Lect. Notes Comput. Sci. Springer-Verlag. Berlin-Heidelberg. - 2013. -Vol. 7982. - P. 72-83.

[18] Brzozowski J.. Liu. D. Universal witnesses for state complexity of boolean operations and concatenation combined with star // In H. Jiirgensen (ed.) DCFS 2013. Lect. Notes Comput. Sci. Springer-Verlag, Berlin-Heidelberg.

- 2013. - V.8031. - P. 30-41.

[19] Brzozowski J., Szykula M. Upper bounds on syntactic complexity of left and two-sided ideals // In Shur A.M., Volkov M.V. (eds.) - DLT 2014. - Lect. Notes Comput. Sci — Springer-Verlag, Berlin-Heidelberg. — 2014. — Vol 8633. - P. 13-25.

[20] Cerny J. Poznamka k homogeimym eksperimentom s konecnymi auto-matami / •' Mat.-Fyz. Cas. Slovensk. Akad. Vied. - 1964. - V.14. - P. 208-216. [in Slovak]

[21] Cook S.A. The complexity of theorem-proving procedures // Proc. of the 3rd IEEE Symp. on the Foundations of Computer Science. — 1971. — P. 151-158.

[22] 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.

[23] D'Aiigeli D.. Rodaro E Groups and semigroups defined by colorings of synchronizing automata // LJAC. - 2014. - Vol. 24(6). - P. 773-794.

[24] De Bruijn N.G. A combinatorial problem // Iudagationes Math. — 1946. — V.8. - P. 461-467.

[25] De Luca A., Perrin D., Re&tivo A. and Termini S. Synchronization and sympliiicat.ion // Discrete Math. 1979. Vol. 27. P. 297 308.

[26] De Luca A., Varricchio S. Finiteness and regularity in semigroups and formal languages // Springer. 1990.

|27] De Luca A., Varricchio S. Some combinatorial properties of factorial languages /'/ In R. Capocelli (ed.) Sequences: Combinatorics, Compression. Security and Transmission. — Springer. — 1990. — P. 258-266.

[28] Dubuc L. Sur les automates circulaires et la conjecture de Cerny // RAIRO Inform. Theor. Appl. - 1998. - Vol. 32, No. 1-3. - P. 21-34 [in French]

[29] Eppstein D. Reset sequences for monotonic automata // SIAM .1. Comput. — 1990. - Vol. 19 , Issue 3. - P. 500-510

[30] Ginsburg S. On the length of the smallest uniform experiment which distinguishes the terminal states of a machine // J. Assoc. Comput. Mach.

- 1958. - Vol. 5. - P. 266-280.

[31] Holzer M., König B. On deterministic finite automata and syntactic monoid size // Theor. Comput. Sei. - 2004. - Vol. 327. - P. 319-347.

[32] Kari J. Synchronizing finite automata on Eulerian digraphs // Theor. Comput. Sei. - 2003. - Vol. 295. - P. 223-232.

[33] Kleene S.C. Representation of events in nerve nets and finite automata // In C. E. Shannon and .]. McCarthy (eds.) Automata Studies, Ann. Math. Studies.

— Princeton Univ. Press, Princeton, N. J. — 1956. — Vol. 34. — P. 3-41.

[34] Kozen D. Lower bounds for natural proof systems // In: Proc. of the 18th FOCS. - 1977. - P. 254-266.

[35] Martygin P. Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Noiidctcrmiifistic Automata // In: F. Ablayev (eds.) — Theory Comput. Sei. - 2014. - Vol. 54. - P. 293-304.

[36] McCulloch W.S.. Pitts. W. A logical calculus of tlic ideas immanent in nervous activity //' Bull. Math. Biophys. — 1943. - Vol. 5. - P. 115-133.

[37] Moore E. Gedanken-experiinents with sequential machines // In C. E. Shannon, J. McCarthy (eds.) Automata Studies, Ann. Math. Studies.

— Princeton Univ. Press. Princeton, N. J. — 1956. - Vol. 34. - P. 129-153.

[38] 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. C-20(10). P. 1211 1214.

[39] Myhill J. Finite automata and representation of events // Wright Air Development Center Technical Report. — 1957. - P.57-y624.

[40] Olschewski J., Ummels M. The complexity of finding reset words in finite automata // In P. Hlineny, A. Kucera (eds.) Mathematical Foundations of Computer Science. — Lcct. Notes Coinput. Sei. — Springer-Verlag, BerlinHeidelberg. - 2010. - Vol. 6281. - P. 568-579.

[41] Papadimitriou C.H. Computational complexity // Rcading-Menlo Park-N.Y.: Addison-Wesley. - 1994.

[42] Papadimitriou C.H.. Jannakakis M. The complexity of facets (and some facets of complexity) // J. of Comp, and Syst. Sei. - 1984. - Vol. 28(2). - P. 244259.

[43] Paun G., Rozenberg G., Salomaa A. DNA computing, new computing paradigms. // Springer, Berlin. 1998.

[44] Paz A . Peleg B. Ultimate-definite and simmetric-definite events and automata // J. ACM. - 1965. - Vol 12(3). - P. 399-410.

|45] Perrin D. Finite automata. Handbook of theoretical computer science // J. van Leewen (eds.) — Elsevier. — 1990. — P. 1-57

[46] Pin J.-E. Sur un cas particulier de la conjecture de Cerny // In G. Ausiello, C. Böhm (eds.) Proc. 5th Colloq. on Automata, Languages, and Programming (ICALP). — Lect. Notes Comput. Sei.— Springer-\erlag. — 1978. — Vol. 62.

— P. 345-352. [in French]

[47] Pin J .-E. On two combinatorial problems arising from automata theory // Ann. Discrete Math. - 1983. — Vol. 17. - P. 535-548.

[48] Pribavkina E.V., Rodaro E. Finiteiicss problem for the language of minimal synchronizing words / / Technical report. — Turku Center for Computer Science, Turku. — 2008. - No. 861.

[49] 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-Heidelberg-New York. 2009. Vol. 5457. P.672-683.

[50] Pribavkina E.. Rodaro E. Synchronizing automata with finitely many minimal synchronizing words // Information and Computation. — 2011. — Vol. 209, Issue 3. - P. 568-579.

[51] Pribavkina E.V.. Rodaro E. Recognizing synchronizing automata with finitely xxiany minimal synchronizing words is PSPACE-complete // In B. Lowe (eds.) CiE 2011. — Lect. Notes Сотр. Sci. — Springer-Verlag, Berlin-Heidelberg. — 2011. - Vol. 6735. - P. 230-238

[52] Rabin M. O.. Scott D. Finite automata and their decision problems // IBM J. Res. Develop. - 1959. - Vol. 3, Issue 2. - P. 114-125.

[53] Reis R., Rodaro, E. Ideal regular languages and strongly connected synchronizing automata // [Электр. публ.] http://www.dcc.fc.up.pt/dcc/Pubs/TReports/TR13/dcc-2013-01.pdf

|54] Reis R., Rodaro. E. Regular ideal languages and synchronizing automata // In: Л. Ivarhumaki, A. Lepisto, L. Zamboni (eds.) WORDS 2013. Lect. Notes Сотр. Sci. - Springer, Heidelberg. - 2013. - Vol. 8079. - P. 205-216.

|55] Restivo A. Some remarks on complete subsets of a free monoid // Quaderni de "La ricerca scientifica". - CNR Roma. - 1981. - Vol. 109. - P. 19-25.

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

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

[58] Samotij W. A note on the complexity of the problem of finding shortest synchronizing words // [Электронная публикация] Proc. Int. Conf. AutoMathA. Palermo. - 2007.

[59] Sandberg S. Homing and synchronizing sequences // In M. Broy et al (eds.) Model-Based Testing of Reactive Systems. — Lect. Notes Comput. Sci. -

Springer-Verlag, Berlin-Hcidelbcrg-New York. — 2005. — Vol. 3472. — P. 533.

[60] Savitch W.J. Relationships between nondeterministic and deterministic tape complexities // Journal of Comput. and Syst. Sci. — 1970. — Vol. 4. — P. 177-192.

[61] Schùtzenberger M.P. Sur certains opérations de fermeture dans les languages rationnels // Sympos. Math. - 1975. Vol. 15. - P. 245 253 [in French],

[62] Trahtman A. N. The Cerny conjecture for aperiodic automata // Discrete Math. Theor. Comput. Sci. - 2007. - Vol. 9. No. 2. - P. 3-10.

[63] Turing A.M. On computable numbers, with an application to the Entscheidungsproblem // Proc. Lond. Math. Soc. — 1936-1937. — Ser. 2. — Vol. 42, 43. - P. 230-265, 544-546

[64] Volkov M. V. Synchronizing automata and the Cerny conjecture /7 In C. Martin-Vide, F Otto, H.Fernau (eds.) Languages and Automata: Theory and Applications. LATA 2008. — Lect. Notes Cornp. Sci. — Springer-Verlag, Berlin-Heidclberg-New York. - 2008. - Vol. 5196. - P. 11-27.

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

[66] Von Neumann J. Probabilistic logics and the synthesis of reliable organisms from unreliable components // In C. E. Shannon and J. McCarthy (eds.) Automata Studies, Ann. Math. Studies. Princeton Univ. Press, Princeton, N. J. - 1956. - Vol. 34. P. 43-98.

[67] Yu F., Chen Z . Diao Y"., Lakshman T.V., Ivat.z R.H. Fast and memory-efficient regular expression matching for deep packet inspection /7 In Proc. of the 2nd ACM/IEEE ANCS Conference - ACM. - 2006. - P. 93-102

[68] Yu S. Regular languages // In Rozenberg G.. Salomaa A. (eds.) Handbook of formal languages. — Springer — 1997. — P. 41-110.

Работы автора по теме диссертации

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

[70] 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.

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

[72] Gu&ev V.V., Maslennikova М.1., Pribavkina E.V. Finitely generated ideal languages and synchronizing automata. // In J. Karhumaki, A.Lepisto, L.Zamboni (eds.) 9th Int. Conf. WORDS 2013. Lect. Notes Сотр. Sci.

Springer-Verlag. Berlin-Heidelberg. 2013. Vol. 8079. P. 143 154.

[73] Gusev V.V., Maslennikova M.I., Pribavkina E.V. Principal ideal languages and synchronizing automata. // In V. Halava, J. Karhumaki, Yu. Matiyasevich (eds.) The Special Issue of the RuFiDiM 2012 — Fundainenta Infonnaticae.

- 2014. - Vol. 132(1). - P 95-108

[74] Maslennikova M. Complexity of checking whether two automata are synchronized by the same language. // In H.Jiirgensen, J.Karhumaki, A.Okhotin (eds.) 16th Int. Workshop DCFS 2014. — Lect. Notes Сотр. Sci.

- Springer-Verlag, Berlin-Heidelberg. — 2014. - Vol. 8614. - P. 306-317.

[75] 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.

[76] 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

[77] Maslennikova M., Rodaro E. Principal (left) ideal languages, constants and synchronizing automata. 'j (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.

[78] Maslennikova M., Rodaro E. Representation of (left) ideal regular languages by synchronizing automata. // In L. Beklemishev (Ed.) 10th Int. Comp. Sci. Symp. CSR 2015. -- Lect. Notes Comp. Sci. - Springer-Verlag, BerlinHeidelberg. - 2015. - Vol 9139.