Исследование задачи регулярной реализуемости Рубцов Александр Александрович

Содержание к диссертации

Введение

Глава1.Вспомогательные сведения 14

1.1. Слова, языки и подстановки 14

1.2. Машины Тьюринга и модель обобщённо-недетерминирован-ных автоматов 16

1.3. Основные классы сложности и модели вычислений 19

1.4. Преобразователи и сводимости 22

1.5. КС-языки 24

1.6. Базовые конструкции с автоматами и грамматиками 28

Глава 2. Модель обобщённо-недетерминированных ав томатовивопросы разрешимости 31

2.1. Модель обобщённо-недетерминированных автоматов 32

2.2. Вопросы разрешимости 36

2.3. Задачи реализуемости для сверхслов и монадические теории 41

2.4. Эквивалентность задач регулярной и префиксной реализуемости 45

Глава 3. Регулярная реализуемость для КС-языков 49

3.1. Рациональные конусы 51

3.1.1. Основные свойства и примеры 52

3.1.2. Структурные свойства рациональных конусов 56

3.1.3. Рациональные конусы и задачи регулярной реализуемости

3.2. Регулярные языки 63

3.3. Лёгкие NRR задачи для КС-фильтров 70

3.4. Трудные NRR задачи для КС-фильтров 76

3.5. Полиномиальный рациональный индекс 85

Глава 4. Автоматысословарём 89

4.1. Определение и свойства 89

4.1.1. Примеры языков 92

4.1.2. Нормальные формы

4.2. P и NP-полные языки 102

4.3. Автоматы со словарём и рациональные конусы 106

4.4. Принадлежность языков класса SA классу NP

4.4.1. Общий план 112

4.4.2. Вспомогательные конструкции 116

4.4.3. Основная часть доказательства 120

Заключение 132

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

• Машины Тьюринга и модель обобщённо-недетерминирован-ных автоматов
• Задачи реализуемости для сверхслов и монадические теории
• Рациональные конусы и задачи регулярной реализуемости
• Автоматы со словарём и рациональные конусы

Введение к работе

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

Классификации формальных языков. Одним из направлений в области компьютерных наук является классификация формальных языков: хорошо известны, например, иерархия Н. Хомского и классификация по вычислительной сложности - центральный предмет исследования одноимённого научного направления.

Однако, эти классификации не различают такие случаи, как языки Peri = {(1^к#)^п І к,п Є N} и Per2 = {(w#)ⁿ\w Є *}, = {0,1}, состоящие из повторения слов с разделителями над унарным и двоичным алфавитами. Мы называем эти языки периодическими фильтрами.

Также эти классификации не различают между собой контекстно-свободные языки PAL - язык палиндромов и D2 - язык правильных скобочных выражений с двумя типами скобок, который известен как язык Дика, и регулярные языки 0* и {0,1}*.

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

Для этих целей М. Н. Вялым была введена задача регулярной реализуемости. Задача регулярной реализуемости состоит в проверке пересечения фиксированного языка F с регулярным языком на входе задачи.

Мы различаем два случая описания регулярного языка на входе задачи: если язык задан описанием детерминированного конечного автомата, то мы имеем дело с детерминированной задачей регулярной реализуемости, а если описанием недетерминированного конечного автомата, то задача называется

недетерминированной задачей регулярной реализуемости.

Мы называем параметр задачи, язык F, фильтром, для того чтобы выделять его среди других формальных языков. Задачи мы обозначаем как RR(F) и NRR(F) соответственно. Мы определяем задачи регулярной реализуемости как формальные языки:

RR(F) = {Л | Л Є DFA, L(A) Г\ F Ф 0},

NRR(F) = {Л | Л Є NFA, L(A) Г\ F Ф 0}.

Сразу оговоримся, что на вход детерминированной задачи регулярной реализуемости подаётся всюду определённый ДКА (множество DFA), каждое состояние которого достижимо из начального, а на вход недетерминированной - НКА, возможно с переходами по пустому слову (множество NFA).

Задача регулярной реализуемости позволяет ввести новую классификацию на формальных языках. Поставив в соответствие формальному языку F вычислительную сложность задачи NRR(F) или RR(F), получаем классификацию формальных языков по сложности соответствующей задачи регулярной реализуемости. Данная классификация устанавливает связь между формальными языками малой вычислительной сложности и классами сложности.

В области формальных языков известны другие классификации, которые также играют важную роль. Представители французской школы Ж. Берстель, Л. Боассон и др. исследовали классификацию контекстно-свободных языков по отношению рационального доминирования. Для определения этого отношения нам потребуется ввести вспомогательные понятия.

Автоматным преобразователем назовём недетерминированный конечный автомат с выходной лентой, автомат может совершать переходы по пустому слову. При переходах между состояниями автомат пишет некоторое слово, возможно пустое, на выходную ленту. Автоматный преобразователь Т ставит слову и в отношение слово -и, если существует путь вычисления со словом и на ленте входа, на котором автомат записывает слово v на выходную ленту,

оказавшись в результате в принимающем состоянии. Запись Т{и) = L означает, что L - язык всех слов, которые автомат ставит в отношение к слову и. Если А - множество, то Т(А) = В, если в В входят те и только те слова, которые Т ставит в отношение к некоторому слову из А. Будем говорить, что язык В является автоматным преобразованием языка А.

В случае если Т - детерминированный автоматный преобразователь, то язык В является детерминированным автоматным преобразованием языка

A. Мы допускаем переходы по пустому слову в детерминированном преоб
разователе - детерминированность преобразователя равносильна тому, что
отношение переходов является функцией.

Автоматные преобразователи задают отношение рационального доминирования, которое мы обозначаем ^_rat: B^_ratA тогда и только тогда, когда существует автоматный преобразователь Т, такой что Т(А) = В. Детерминированные автоматные преобразователи задают отношение ^drat: если выполнено A ^drat В, то мы говорим, что язык А автоматно сводится к

B, а язык В автоматно накрывает А. Отношения ^_rat и ^drat являются
транзитивными.

Множество языков С является рациональным конусом, если оно замкнуто относительно отношения рационального доминирования: для любого языка L из С и любого автоматного преобразователя Т выполняется T(L) Є С. Множество языков С образует главный рациональный конус, если существует язык F, такой что для любого языка L Є С существует преобразователь Т, такой что T(F) = L. Мы обозначаем главный рациональный конус как T(F), язык F мы называем генератором.

Отношения рационального доминирования и автоматного накрытия хорошо согласуются со сложностью задач недетерминированной и детерминированной регулярной реализуемости: если A ^_rat Б, то NRR(A) ^_lo NRR(B); если ^4 ^drat В, то RR(A) ^ RR(5). Более подробно связь автоматных преобразований с задачами регулярной реализуемости мы описываем в разделе 3.1.3.

О важности данного подхода к исследованию КС-языков свидетельствует

тот факт, что он отражён в соответствующих главах таких книг как Handbook of Formal Languages и Handbook of Theoretical Computer Science. Мы называем указанную технику, разработанную французской школой, техникой рациональных конусов.

Исследование структурных и сложностных свойств моделей вычислений. Актуальность исследования КС-языков вызвана их важностью для приложений. Центральной проблемой теории формальных языков является исследование моделей вычислений: исследование структурных свойств распознаваемых моделью языков и классификация их по вычислительной сложности. Одним из самых выдающихся успехов этого направления является применение детерминированных КС-языков для разработки компиляторов языков программирования. Центральный результат, относящийся к LR-анализу, получен Д. Кнутом¹.

При этом класс КС-языков обладает достаточно редкими хорошими структурными свойствами и свойствами разрешимости основных задач, таких как проблема пустоты языка. Следующий за КС-языками класс в иерархии Хом-ского - контекстно-зависимые языки - уже не обладает столь замечательными свойствами, что затрудняет использование КЗ-языков в приложениях. Поиск классов формальных языков с хорошими структурными и вычислительными свойствами является важным вопросом теории формальных языков в связи с возможностью их приложения по опыту регулярных и КС-языков.

К современным исследованиям в данном направлении относится открытие М. Кутрибом, А. Мальхером и М. Ведландтом модели вычислений - автоматов со словарём, в оригинале - Set Automata; детерминированная версия этой модели была представлена в 2014 году на конференциях Developments in Language Theory и Descriptional Complexity of Formal Systems. Авторы модели показали, что языки, распознаваемые детерминированными автоматами со словарём, обладают хорошими свойствами, близкими к детерминированным

¹Knuth D. On the Translation of Languages from Left to Right // Information and Control. — 1965.

КС-языкам, что открывает возможность для их приложения на практике.

Связь теории автоматов с монадическими теориями. В работе Ж. Бюхи² установлена связь между теорией автоматов и монадическими теориями второго порядка для бесконечных вправо слов - сверхслов. Бюхи доказал, что разрешимость монадической теории для сверхслова эквивалентна разрешимости задачи о поведении автомата на сверхслове: необходимо проверить, оказывается ли автомат на входе задачи в принимающем состоянии бесконечно много раз при обработке сверхслова. В работе академика А.Л. Семёнова³ получен критерий разрешимости монадических теорий для сверхслов. Данная тема остаётся актуальной, о чём свидетельствуют работы⁴ О. Картона, А. Рабиновича и В. Томаса.

Степень разработанности темы исследования. На классах сложности хорошо известно следующее соотношение:

При этом, в силу теоремы об иерархии, одно из этих включений является строгим. Вопрос о строгости каждого включения является открытым вопросом о разделении классов сложности. Самый известный из этих вопросов - одна из задач тысячелетия о соотношении между классами Р и NP.

Для каждого из приведённых выше формальных языков задача регулярной реализуемости является полной относительно т-сводимости на логарифмиче-

²Buuchi J. R. On a Decision Method in Restricted Second Order Arithmetic // Proceedings of International Congress for Logic, Methodology and Philosophy of Science. - 1962.

³Семёнов А. Л. Логические теории одноместных функций на натуральном ряду // Известия АН СССР. Серия математическая. — 1983.

⁴Carton O., Thomas W. The Monadic Theory of Morphic Infinite Words and Generalizations // Information and Computation. — 2002.

Rabinovich A. On Expressive Power of Regular Expressions over Infinite Orders // 11th International Computer Science Symposium in Russia, - 2016.

Rabinovich A., Thomas W. Decidable Theories of the Ordering of Natural Numbers with Unary Predicates // Computer Science Logic: 20th International Workshop, CSL, - 2006. Rabinovich A. On decidability of monadic logic of order over the naturals extended by monadic predicates // Information and Computation. — 2007.

ской памяти ^j в одном из указанных классов сложности.

Таблица 1: Фильтры, для которых задачи полны в основных классах сложности.

Обратимся к таблице 1. Результаты сложности задач для периодических фильтров получены независимо М. Н. Вялым⁵ и T. Anderson, J. Loftus, N. Rampersad, N. Santean, J. Shallit⁶, которые также доказали результат о сложности задачи для палиндромов; полнота задачи для языка Дика следует из хорошо известного факта полноты задачи о непустоте языка, задаваемого контекстно-свободной грамматикой, а результаты для регулярных языков несложно следуют из свойств классов L и NL - мы приводим доказательства этих утверждений в главе 3.

Следующим естественным вопросом является вопрос о вычислительной сложности задач регулярной реализуемости для произвольных регулярных и контекстно-свободных языков: если найдётся регулярный или КС-язык, для которого соответствующая задача регулярной реализуемости будет иметь

⁵Вялый М. Н. О задачах регулярной реализуемости // Пробл. передачи информ. — 2011.

⁶Special Issue: 2nd International Conference on Language and Automata Theory and Applications (LATA 2008) Detecting palindromes, patterns and borders in regular languages / T. Anderson [et al.] // Information and Computation. — 2009.

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

Авторы модели автоматов со словарём исследовали структурные свойства детерминированной версии модели, однако вопрос об аналогичных свойствах недетерминированной модели формально не поднимался (большинство свойств не зависят от детерминированности модели), а вопрос о сложностной классификации языков, распознаваемых моделью, не был исследован.

Другой естественной задачей о поведении автомата на сверхслове является вопрос о том, окажется ли он в принимающем состоянии хотя бы один раз. Этот вопрос можно сформулировать в виде задачи регулярной реализуемости специального вида. Фильтром этой задачи является множество префиксов сверхслова – мы называем такую задачу задачей префиксной реализуемости. Из схожести описанных задач о поведении автомата на сверхслове вытекает вопрос об исследовании связи между задачей префиксной реализуемости и монадическими теориями.

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

В работе решаются следующие задачи.

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

1. Классификация по сложности детерминированной задачи регулярной реализуемости регулярных языков и недетерминированной задачи основных подклассов КС-языков.

2. Классификация по сложности вычислений языков, распознаваемых автоматами со словарём, и установление их структурных свойств.

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

Теоретическая и практическая значимость. Работа носит теоретический характер. Разработанный математический аппарат открывает возможность переноса применённого подхода на другие модели вычислений, что может оказаться полезным для дальнейших теоретических исследований в области формальных языков и сложности вычислений. В частности, установлено, что широкий подкласс КС-языков является кандидатом на промежуточную сложность задачи регулярной реализуемости между NL и P, это открывает новый подход к вопросу о соотношении между этими классами. Подход, применённый для классификации по сложности модели автоматов со словарём, базируется на технике рациональных конусов и, возможно, может быть применён к другим моделям, распознающим языки со схожими структурными свойствами.

Полученный в работе результат о том, что детерминированные автоматы со словарём распознают языки из класса P, в том числе полные, является аргументом в пользу надежды авторов данной модели на её практическое применение.

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

также методы теории вычислений.

Положения, выносимые на защиту.

1. Существование сверхслов, для которых разрешима задача префиксной реализуемости, но не разрешима монадическая теория.

2. Эквивалентность по разрешимости произвольной задачи регулярной реализуемости и некоторой задачи префиксной реализуемости.

3. Классификация* регулярных языков по сложности детерминированной задачи регулярной реализуемости. Классификация состоит из двух классов: ограниченных и неограниченных языков.

4. Принадлежность задачи недетерминированной регулярной реализуемости для КС-языков с полиномиально ограниченным рациональным индексом классу NSPACE(log² n).

5. Классификация* основных рациональных подконусов конуса КС-языков по сложности задачи недетерминированной регулярной реализуемости.

6. Существование языка, который не является генератором конуса КС-языков, такого, что задача регулярной реализуемости P-полна.

7. Классификация* по вычислительной сложности языков, распознаваемых автоматами со словарём.

* – Классификации проведены в предположении стандартных теоретико-сложностных гипотез.

Степень достоверности и апробация результатов. Высокая степень обоснованности результатов диссертации обеспечивается корректностью применения математического аппарата, апробацией результатов на международных конференциях и публикацией результатов исследований в рецензируемых научных изданиях, в том числе включённых в список ВАК. Результаты работы были доложены на следующих семинарах, российских и международных конференциях:

54,55,56,57 научных конференциях МФТИ (Москва, 2011-2015), причем на 54 и 55 научных конференциях работы автора были отмечены секционными дипломами,

17th International Workshop Descriptional Complexity of Formal Systems (Waterloo, ON, Canada, 2015),

IX международной конференции «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 2015),

XVII международной конференции «Проблемы теоретической кибернетики» (Казань, 2014),

7th School «Computer Science Days in Ekaterinburg» (Екатеринбург, 2014),

научном семинаре по теории сложности ВЦ РАН (Москва 2011, 2014),

Колмогоровском семинаре мехмата МГУ (Москва, 2011).

По теме диссертации соискателем опубликовано 12 печатных работ [1— 12], три из них [4; 10; 11] - в реферируемых изданиях, включённых ВАК РФ в список изданий, рекомендуемых для опубликования основных научных результатов диссертаций.

Объем и структура диссертации.

Машины Тьюринга и модель обобщённо-недетерминирован-ных автоматов

Класс (или семейство) языков - это некоторое непустое множество языков. Мы будем накладывать на класс языков следующее требование: если язык L С принадлежит классу языков Л и при этом язык V С А является копией языка L, то есть между алфавитами Е и А существует биекция, которая при расширении на слова является биекцией между L и L, тогда V Є . Мы будем обозначать абстрактные классы языков, необходимые для теоретических построений, как Л и .Ж.

Мы определяем на языках операцию подстановки. Зафиксируем алфавит Еп. Пусть Li С А для і Є l..n. Операцию подстановки определим следующим образом: на буквах Va Є Sn : (Т{(ІІ) = Lj, на словах w = if і if 2 ... ifn, Wi Є Sn : a (if) = r(ifi) r(if2) o"(ifn), на языках (j{M) = [J a (if). Таким образом, операция подстановки - это функция weM а : Sn — 2 . Мы обозначаем 2х множество всех подмножеств множества X. Нам потребуется обобщить понятие подстановки на классы языков. Пусть .Ж - класс языков. Будем называть -подстановкой подстановку вида а : такую что Va Є Е : a(a) Є #. Поскольку языки из семейства Л могут быть языками над разными алфавитами, то обозначим алфавит языка L. Определим операцию подстановки на классах языков: Jzfа .Ж = {cr(L) L Є Jzf, а : S —) 2 - -подстановка}. 1.2. Машины Тьюринга и модель обобщённо-недетерминированных автоматов Мы переходим к определению моделей вычислений и начинаем с понятия машины Тьюринга. Мы описываем основные классы языков при помощи машины Тьюринга, а также определяем специальную модель вычислений на её основе - обобщённо-недетерминированный автомат.

Определение 1.1. Детерминированная Машина Тьюринга М имеет / лент, к головок, множество состояний Q, множество принимающих состояний F С Q, входной алфавит , функцию перехода 5 : Т,к xQ — Т,к xQx {0, +1, — 1} - за такт работы машина меняет состояние, меняет символы под головками и двигает каждую головку влево, вправо или оставляет её неподвижной. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово х. В начале работы головка стоит на первом символе слова ж, все остальные ячейки заполнены пустыми символами Л. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово.

Будем говорить, что машина Тьюринга М вычисляет функцию М(х), которая равна 1, в случае если машина М на входе х останавливается в принимающем состоянии, если машина М на входе х останавливается в непри-нимающем состоянии, то М(х) = 0, а если машина М не останавливается на входе ж, то функция М(х) не определена. М(х) = 1, М остановилась в принимающем состоянии на ж; О, М остановилась в непринимающем состоянии на ж; Машина М принимает язык L, если она принимает каждое слово из языка L, а если машина М принимает язык L и к тому же все слова, принимаемые машиной М, лежат в языке L, то будем говорить, что М распознаёт L. Язык, распознаваемый машиной М, будем обозначать L(M). Если в определении 1.1 заменить функцию переходов на отношение переходов, мы получим определение недетерминированной машины Тьюринга. Если не оговорено противного, то мы считаем, что машина Тьюринга имеет одну ленту и одну головку. Взяв за основу машину Тьюринга, мы строим обобщённо-недетерми 18 нированные модели вычислений. Для построения этих моделей мы используем вспомогательную конструкцию. Лентой-подсказкой назовём одностороннюю бесконечную вправо ленту, доступную только для чтения, на которой всего одна головка, которая движется только вправо. Алфавит этой ленты будем обозначать А. По умолчанию в каждой клетке ленты-подсказки записан пустой символ Л А. Слово, записанное на ленте-подсказке, будем называть подсказкой. Определение 1.2. Под машиной Тьюринга М с лентой-подсказкой, будем понимать машину Тьюринга, у которой есть лента-подсказка, причём на вход машины подаётся два аргумента - входное слово и слово-подсказка. В случае, если головка выходит за пределы слова, записанного на ленте-подсказке, МТ завершает работу в отвергающем состоянии. Аналогично обычной машине, обобщённо-недетерминированная машина вычисляет функцию М(х,у), причём М(х,у) = 1, если машина М перешла в принимающее состояние на входе х при подсказке у. Мы будем ограничивать множество слов, подающихся на вход у. Язык F С А , содержащий все допустимые слова для входа у, будем называть фильтром. Машину Тьюринга с лентой-подсказкой, с фильтром F, обозначим Мр. Будем называть такую машину Мр обобщённо-недетерминированной машиной Тьюринга. Определение 1.3. Обобщённо-недетерминированная машина Тьюринга Мр принимает язык L, если

Задачи реализуемости для сверхслов и монадические теории

Теперь докажем разрешимость задачи префиксной реализуемости Rp(W). Поскольку в конструкции используется вычислимая биекция между автоматами и натуральными числами, по автомату Л можно определить его номер п. Из построения следует, что слова щ, Wk при к п составлены только из блоков, принадлежащих множеству Sn (множество остановившихся машин не уменьшается с ростом числа тактов работы). Слово ип форсирует проход через принимающее состояние при чтении таких блоков, если это вообще возможно. Поэтому если автомат Л не побывал в принимающем состоянии после чтения префикса vnun сверхслова W, то он никогда не попадает в принимающее состояние при чтении сверхслова W.

С другой стороны, из построения следует, что блок Ъп встречается в сверх слове W бесконечно часто тогда и только тогда, когда n-я машина не останав ливается на пустом входе. Отсюда следует неразрешимость задачи R(W). Вопрос о том, содержит ли сверхслово W бесконечно много подслов из регу лярного языка R равносилен вопросу задачи R(VK) для языка Y R.

Мы поставим в соответствие каждому фильтру F такое сверхслово Vp, что задача RR(F) эквивалентна по Тьюрингу задаче RP(VF). В качестве основного инструмента мы используем критерий Семёнова разрешимости мо 46 надических теорий.

Как мы уже показали, из разрешимости монадической теории для сверхслова W следует разрешимость задачи Rp(H/). Мы будем использовать вариант критерия Семёнова [11] в терминах регулярных языков, приведённый в работе [15].

Теорема (Критерий Семёнова). Условие разрешимости монадической теории MT(N, ,W) равносильно следующему условию. Существует алгоритм, который для регулярного языка R на входе проверяет, принадлежит ли некоторое подслово каждого суффикса WiWi+\... Wn ... сверхслова W языку R, и в случае отрицательного ответа возвращает номер п, для которого суффикс WnWn+i... не содержит ни одного слова из R в качестве подслова.

Мы используем критерий Семёнова для доказательства основной леммы. Лемма 2.3. Пусть для языка F разрешима задача регулярной реализуемости RR(F) и пусть сверхслово W имеет вид W\W2 wn ..., где Wi Є F, и при этом каждое слово языка F входит в W в качестве подслова. Тогда разрешима монадическая теория MT(N, , W).

Доказательство. Заметим, что если разрешима задача регулярной реализуемости RR(F), то разрешима и задача регулярной реализуемости RR(F ). Пусть А - автомат на входе задачи RR(F ). Рассмотрим всевозможные автоматы1 Arq,q,r Є QA и решим для каждого из них задачу регулярной реализуемости RR(F). Если существует такая последовательность состояний до, 0_2-, Яп QA, что QO – начальное состояние A, qn - принимающее, и для каждого языка L(Aq 1) ответ на вопрос задачи регулярной реализуемости положителен, то тогда и ответ на вопрос задачи RR(F ) для автомата А положителен. Очевидно, что если такой последовательности не существует, то ответ на вопрос задачи RR(F ) отрицательный.

Автомат с начальным состоянием q и принимающим г, см. раздел 1.6. Пусть R - регулярный язык на входе алгоритма критерия Семёнова. Покажем, что язык Д содержит хотя бы одно слово xyz из языка F , такое что у Є Л, тогда и только тогда, когда слово у содержится в каждом суффиксе W. Пусть іЖ Є RR(F ). Тогда, по построению W, любая конкатенация слов из F является подсловом W, а значит некоторый префикс WiW2 .wn,Wi Є F сверхслова содержит xyz в качестве подслова. Но тогда, по построению W, некоторый префикс W содержит в качестве подслова и слово W\W2 wnxyz, а значит для любого п слово (xyz)n+l содержится в суффиксе wn+iWn+2 поскольку в префиксе WiW2.wn оно содержаться не может. Отсюда следует, что каждый суффикс W содержит в качестве подслова слово у в силу определения W.

В обратную сторону. Если сверхслово W содержит у в некотором суффик се, то у можно продолжить до конкатенации слов из F по определению W. Получаем, что алгоритм для критерия Семёнова устроен следующим обра зом: он проверяет соотношение S i?S Є RR(F ) и в случае отрицательного ответа возвращает 1.

Приведём пример построения сверхслова, для которого выполняется условие леммы 2.3. Мы будем опираться на этот пример при доказательстве основной теоремы раздела. Сначала построим вспомогательное сверхслово Wa над бесконечным счётным алфавитом Soo = {скі, «2, скп,...}. Пусть слово wn состоит из конкатенации всех слов длины п над алфавитом {скі,... ,ап} в лексикографическом порядке. Определим сверхслово Wa = W\W2 .. .wn ... как конкатенацию Wi. Очевидно, что каждое (конечное) слово над бесконечным алфавитом входит как подслово в Wa бесконечное число раз, и, кроме того, сверхслово Wa является вычислимым.

Покажем теперь, как по языку F с разрешимой задачей регулярной реализуемости построить сверхслово Wp с разрешимой монадической теорией MT(N, , Wp). Из леммы 2.3 и приведённого примера очевидно следует Утверждение 2.8. Занумеруем все слова языка F С S . Определим мор-физм ср : SQO — Е , поставив в соответствие символу СЇІ слово языка F под номером і. В случае если F конечный язык, поставим всем ап, п \F\, в соответствие пустое слово. Тогда если разрешима задача регулярной реализуемости RR(F), то для сверхслова Wp = cp(Wa) разрешима монадическая теория MT(N, , Wp).

Теперь мы готовы доказать основной результат раздела. Теорема 2.3. Для любого языка F существует сверхслово Vp, такое что задачи RR(F) и RP(VF) эквивалентны по Тьюрингу.

Доказательство. Построим сверхслово Vp следующим образом. Пусть F С , Е, Т ф = Е U {if}. Возьмём в качестве Vp сверхслово Wp#. Заметим, что VF является сверхсловом для фильтра F (в смысле определения на стр. 37). Очевидно, что задача RR(F) разрешима тогда и только тогда, когда разрешима задача RR(F ): дописывание к каждому слову F маркера конца не влияет на разрешимость.

Рациональные конусы и задачи регулярной реализуемости

Перейдём теперь к анализу рациональных конусов с другой половины рисунка 3.1. Конус ROCL является главным конусом, порождённым языком Дика D\ с одним типом скобок. У этого конуса есть естественное описание: этому конусу принадлежат языки, распознаваемые автоматами со счётчиком, которые не могут проверить равенство счётчика нулю. Формально, автоматом со счётчиком называют МП-автомат, в алфавите стека которого всего один символ, допускающий слово одновременно по принимающему состоянию и пустому стеку.

Лемма 3.9. Пусть Lc – КС-язык, распознаваемый автоматом со счётчиком, тогда задача регулярной реализуемости NRR(Lc) лежит в классе NL. В доказательстве леммы мы используем следующий факт, полученный модификацией леммы из [38].

Лемма 3.10. Пусть M является автоматом со счётчиком, который имеет n состояний. Тогда кратчайшее слово w, принимаемое автоматом M, имеет длину не более чем n3, и при этом значение счётчика автомата M при работе на слове w не превосходит n2.

Доказательство. Рассмотрим пути вычислений автомата M из начальной конфигурации в принимающую и покажем, что есть путь, на котором счётчик не обращается в ноль слишком часто и не принимает слишком большие значения, поэтому длина слова в итоге будет ограничена кубом по числу состояний M.

Пусть M имеет множество состояний Q, Q = n. Поставим каждой конфигурации M в соответствие пару из множества Q N: пара (q,i) означает, что автомат находится в состоянии q со значением счётчика i. Допустим, на пути из (q0,0) в (qf,cw) по самому короткому слову w автомат два раза оказался в паре (q, m) – на k-м и j-м символе. Тогда, w1 . . . wkwj+1 . . . wn – более короткое слово, которое принимает МП-автомат M, поэтому два раза одно и то же состояние с одним и тем же значением счётчика встречаться не может. Покажем, что при этом значение счётчика не может превосходить n2.

Обозначим wli ...wri отрезок символов слова w, концам которого соответствуют пары (qli,i) и (qri , i), при этом между wli и wri счётчик не опускается ниже i. Пусть отрезок wlj ...wrj вложен в отрезок wli ...wri, i j. Если у двух вложенных отрезков пары, соответствующие концам, имеют одинаковые состояния: qli = qlj , qri = qrj , где j 1, слово w можно укоротить, заменив в нём отрезок wi.... wr. на отрезок wi... .wr.. Таким образом, для любого і последовательность вложенных отрезков wit... wn, wii+1 ... wn г,... , wik... wrk имеет не более п2 элементов, а значит значение счётчика не превосходит п2, в том числе и для і = 0. Заметим, что из достижения автоматом со счётчиком на некотором пути вычисления значения счётчика j следует наличие отрезка if/.... wrj, поскольку на концах слова счётчик принимает значение 0.

А раз значение счётчика на w не может превосходить п2, то длина w не превосходит п3. Рассмотрим НКА Л, в котором все состояния имеют вид (д, і) и і п2, а переходы согласованы с таблицей переходов МП-автомата М. Таким образом, в графе автомата Л есть путь из начального состояния в принимающее, а самый короткий путь линеен по числу состояний, число ко торых п3. Доказательство леммы 3.9. Пусть М - автомат со счётчиком, допускающий по принимающему состоянию, причём автомат М распознаёт язык Lc. Пусть Л - автомат на входе задачи регулярной реализуемости.

Построим автомат со счётчиком Мд, распознающий язык L(M) P\L(A) = Lc П L(A), стандартной конструкцией произведения: автомат имеет множество состояний QM х QA, начальное состояние (q f ,qo ), множество принимающих состояний FM х FA и отношение переходов дмл, причём 6м{я,&,%) Ь (q ,z ), бдІРіСг) = pf влечёт 8мл{{(і-,р)-, с", z) Ь {{q ,p ), z ).

Таким образом, автомат Мд является автоматом со счётчиком с \QM\ \QA\ = с х п состояниями. По лемме 3.10 получаем, что значение счётчика автомата Мд не превосходит (сп)2 при работе на самом коротком принимаемом слове. Построим теперь такой НКА Б, что язык Ь(В) включает в себя все слова из Ь(Мд), на которых счётчик автомата Мд не превышает (сп)2.

Автомат В имеет 0(п ) состояний, и его построение выполнимо на логарифмической памяти естественным образом. Схожая конструкция приведена далее в доказательстве утверждения 3.14. Отметим, что Ь(Мд) ф 0 тогда и только тогда, когда Ь(Б) Ф 0. Таким образом, отображение Л — В яв ляется сводимостью задачи NRR(LC) к задаче NRR( ), которая лежит в классе NL. Очевидно, что язык Дика D\ распознаётся автоматом со счётчиком. Таким образом мы получаем следствие. Следствие 3.2. NRR(Di) є NL.

Аналогично линейным языкам, замыканием конуса ROCL относительно операции подстановки является конус FCL = T ROCL) (Finite counter languages), который также содержит только лёгкие языки. Известно, что конусы QRT и FCL находятся в общем положении. Их замыкание относительно подстановки является конусом, известным как конус языков Грейбах GRE. Таким образом, доказав леммы 3.6, 3.8 и следствие 3.2, мы доказали основной результат данного раздела.

В этом разделе мы исследуем трудные КС-языки - мы переформулируем классическую Р-полную задачу о непустоте языка, заданного КС-грамматикой, в терминах задачи регулярной реализуемости, а также предъявим пример КС-языка, который является трудным, однако не является при этом генератором конуса КС-языков. Наличие такого примера означает, что классификация по отношению рационального доминирования и сложностная классификация КС-языков различны.

Автоматы со словарём и рациональные конусы

Далее мы приводим лемму, которая устанавливает связь между рациональными преобразованиями языка протоколов и автоматами со словарём. Лемма 4.7. Пусть L - язык, распознаваемый некоторым автоматом со словарём М. Тогда существует автоматный преобразователь Т, такой что w Є L тогда и только тогда, когда T(w) П SA-PROT ф 0.

Нам требуется эффективный вариант данной леммы для переноса свойств автомата М на преобразователь Т. Для этих целей мы используем понятие активной нормальной формы автомата со словарём, предложенное в [8] и описанное нами в разделе 4.1.2.

Лемма 4.8. При условиях леммы 4.7, преобразователь Т определён на том же множестве состояний, что и М, при этом каждому языку запроса LShg. автомата М соответствует язык #LSiyS #ор#, слова из которого преобразователь может записать на рабочую ленту на пути Si Sj.

Доказательство. Мы строим преобразователь Т по автомату М в активной нормальной форме естественным образом. Если М имеет переход, такой же переход имеет и Т: Т пишет на выходную ленту слово, которое М пишет на рабочую ленту, но, кроме того, Т также добавляет разделитель , когда М пишет первую букву запроса на рабочую ленту, добавляет ор , когда М совершает запрос, и переходит в состояние множества Sop сразу после запроса. Таким образом, если М пишет и на пути Si Sj - когда М находится в состоянии й , рабочая лента пуста, - и выполняет запрос ор в состоянии Sj, тогда Т пишет слово-запрос #и#ор# на данном пути.

Заметим, что в случае операции test, преобразователь Т имеет оба перехода как в состояние для test+, так и в состояние для test-. Если слово w принимается автоматом М, то тогда корректный протокол для w принадлежит образу T(w): Т недетерминированно угадывает результаты всех тестов для М. Отсюда следует, что если w Є L(M), то T{w) П SA-PROT ф 0. Если же w L(M), тогда не существует последовательности результатов тестов, которая позволяет Т вывести на входе w корректный протокол. Таким обра зом, T{w) П SA-PROT = 0. Определение 4.5. Мы будем называть преобразователь Т экстрактором для автомата М.

Замечание 4.3. Заметим, что если М - автомат в бесконечной активной нормальной форме, то и соответствующие языки LSuS (языки слов-запросов, которые Т пишет на пути Si Sj ) преобразователя Т также бесконечны. Если автомат М находился в атомарной активной нормальной форме, то свойства, налагаемые ААНФ на языки LSi;S , переносятся на соответствующие языки преобразователя. Замечание 4.4. Мы свели задачу о проверке принадлежности слова w языку L(M), распознаваемому автоматом со словарём М, к задаче регулярной реализуемости для языка SA-PROT специального вида: все регулярные языки имеют вид TM{W), где Тм - экстрактор для М. Нам также потребуется следующее вспомогательное определение. Определение 4.6. Пусть Лм – НКА, полученный из автомата со словарём М путём игнорирования рабочей ленты, в случае операций test оба перехода допустимы. Назовём язык RM = Ь(Лм) регулярным языком, индуцированным конечным управлением М.

Теперь мы готовы доказать основную теорему данного раздела Теорема 4.3. Языки, распознаваемые автоматами со словарём, образуют рациональный конус T(SA-PROT).

Доказательство. После утверждения 4.2 осталось доказать, что для каждого языка L, распознаваемого некоторым автоматом со словарём М, существует автоматный преобразователь Т", такой что L = Т (SA-PROT). Рассмотрим автоматный преобразователь Т из леммы 4.7. Как мы упоминали в разделе 3.1.1., для каждого автоматного преобразователя существует обратный автоматный преобразователь Т 1. По определению, T l(u) = {w \ T(w) = и}.

Пусть RM - регулярный язык, индуцированный конечным управлением ав томата М. Тогда получаем искомый преобразователь Т путём пересечения выхода Т 1 с языком RM. Языки, распознаваемые (недетерминированными) автоматами со словарём, очевидно, замкнуты относительно объединения и пересечения с регулярными, а также замкнуты относительно объединения и конкатенации. Заметим также, что, помимо естественных конструкций, эти свойства можно получить из факта того, что класс SA является главным рациональным конусом, опираясь на раздел 3.1.2.

Заметим, что лемма 4.7 является частным случаем применения утверждения 3.7, которое устанавливает сводимость между проверкой принадлежности слова языку и частным случаем задачи регулярной реализуемости. Нам потребовалось отдельное доказательство, чтобы выявить свойства, описанные в лемме 4.8.

Заметим также, что задача регулярной реализуемости разрешима для любого языка из класса SA: это следует из разрешимости проверки на пустоту языка, распознаваемого детерминированным автоматом со словарём, установленной в [8]. Из разрешимости проблемы пустоты для любого DSA следует её разрешимость для языка SA-PROT, который является генератором конуса SA, а далее задача RR(F) сводится к задаче проверки на пустоту языка R П F Є DSA. Отсюда же следует и разрешимость задачи NRR(F). Фактически мы уточнили здесь доказательство частного случая леммы 3.3, показав, что в данном случае сводимость осуществима на логарифмической памяти.

Что можно сказать о вычислительной сложности задач принадлежности слова языку и проблемы пустоты, опираясь на сложность задачи регулярной реализуемости? Увы, в силу специальности входа задачи регулярной реализуемости для проверки принадлежности слова языку, сложность задачи регулярной реализуемости является плохим приближением проверки на принадлежность. Периодический фильтр Рег2, определённый во введении, очевидно распознаётся DSA аналогично примеру 4.1. Отсюда следует, что сложность задачи регулярной реализуемости для языка SA-PROT ограничена снизу классом PSPACE, а посему это ограничение справедливо и для задачи проверки на пустоту - построение DSA, распознающего язык R П SA-PROT очевидно осуществимо на логарифмической памяти, если регулярный язык R задан ДКА Л.