WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

Pages:   || 2 |

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

-- [ Страница 1 ] --

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

КАФЕДРА МАТЕМАТИЧЕСКИХ ОСНОВ УПРАВЛЕНИЯ

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

УДК 519.71

РУБЦОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ

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

реализуемости

Специальность 01.01.09 - дискретная математика и

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

ДИССЕРТАЦИЯ

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

Научный руководитель:

кандидат физико-математических наук, доцент Михаил Николаевич Вялый МОСКВА – 2016 Оглавление Стр.

Введение 4 Глава 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. Рациональные конусы и задачи регулярной реализуемости.... 57

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

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

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

3.5. Полиномиальный рациональный индекс................ 85 Глава 4. АВТОМАТЫ СО СЛОВАРЁМ 89

4.1. Определение и свойства......................... 89 4.1.1. Примеры языков..........................

–  –  –

ЗАКЛЮЧЕНИЕ 132 СПИСОК ЛИТЕРАТУРЫ 133 ВВЕДЕНИЕ Актуальность темы В диссертационной работе затрагиваются следующие актуальные для областей формальных языков и вычислительной сложности темы.

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

Однако, эти классификации не различают такие случаи, как языки Per1 = {(1k #)n | k, n N} и Per2 = {(w#)n | w }, = {0, 1}, состоящие из повторения слов с разделителями над унарным и двоичным алфавитами. Мы называем эти языки периодическими фильтрами.

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

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

Для этих целей М. Н. Вялым была введена задача регулярной реализуемости, которая впервые была определена в [1; 2] как задача достижимости, а в [3] приведены её устоявшаяся формулировка и название. Задача регулярной реализуемости состоит в проверке пересечения фиксированного языка F с регулярным языком на входе задачи.

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

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

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

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

–  –  –

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

– НКА, возможно с переходами по пустому слову (множество NFA).

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

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

Автоматным преобразователем назовём недетерминированный конечный автомат с выходной лентой, автомат может совершать переходы по пустому слову. При переходах между состояниями автомат пишет некоторое слово, возможно пустое, на выходную ленту. Автоматный преобразователь T ставит слову u в отношение слово v, если существует путь вычисления со словом u на ленте входа, на котором автомат записывает слово v на выходную ленту, оказавшись в результате в принимающем состоянии. Запись T (u) = L означает, что L – язык всех слов, которые автомат ставит в отношение к слову u. Если A – множество, то T (A) = B, если в B входят те и только те слова, которые T ставит в отношение к некоторому слову из A. Будем говорить, что язык B является автоматным преобразованием языка A.

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

Автоматные преобразователи задают отношение рационального доминирования, которое мы обозначаем как следуя [4]: B тогда и только rat A rat тогда, когда существует автоматный преобразователь T, такой что T (A) = B.

Детерминированные автоматные преобразователи задают отношение drat :

–  –  –

транзитивными.

Множество языков C является рациональным конусом, если оно замкнуто относительно отношения рационального доминирования: для любого языка L из C и любого автоматного преобразователя T выполняется T (L) C.

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

–  –  –

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

О важности данного подхода к исследованию КС-языков свидетельствует тот факт, что он отражён в соответствующих главах таких книг, как Handbook of Formal Languages [5] и Handbook of Theoretical Computer Science [6]. Мы называем указанную технику, разработанную французской школой, техникой рациональных конусов.





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

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

К современным исследованиям в данном направлении относится открытие М. Кутрибом, А. Мальхером и М. Ведландтом модели вычислений – автоматов со словарём, в оригинале – Set Automata; детерминированная версия этой модели была представлена в 2014 году в работах [8; 9]. Авторы модели показали, что языки, распознаваемые детерминированными автоматами со словарём, обладают хорошими свойствами, близкими к детерминированным КС-языкам, что открывает возможность для их приложения на практике.

Связь теории автоматов с монадическими теориями. В работе Ж. Бюхи [10] установлена связь между теорией автоматов и монадическими теориями второго порядка для бесконечных вправо слов – сверхслов. Бюхи доказал, что разрешимость монадической теории для сверхслова эквивалента разрешимости задачи о поведении автомата на сверхслове. Необходимо проверить, оказывается ли автомат на входе задачи в принимающем состоянии бесконечно много раз при работе на сверхслове. В работе академика А.Л. Семёнова [11] получен критерий разрешимости монадических теорий для сверхслов. Данная тема остаётся актуальной, о чём свидетельствуют работы О. Картона, А. Рабиновича и В. Томаса [12 15].

Степень разработанности темы исследования.

На классах сложности хорошо известно следующее соотношение:

L NL P NP PSPACE.

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

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

–  –  –

Таблица 0.1.

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

Обратимся к таблице 0.1. Результаты сложности задач для периодических фильтров получены независимо М. Н. Вялым [3] и T. Anderson, J. Loftus, N.

Rampersad, N. Santean, J. Shallit в работе [16], в этой же работе получен результат о сложности задачи для палиндромов; полнота задачи для языка Дика следует из хорошо известного факта полноты задачи о непустоте языка, задаваемого контекстно-свободной грамматикой, а результаты для регулярных языков несложно следуют из свойств классов L и NL (мы приводим доказательства этих утверждений в главе 3).

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

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

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

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

Из схожести описанных задач о поведении автомата на сверхслове вытекает вопрос об исследовании связи между задачей префиксной реализуемости и монадическими теориями.

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

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

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

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

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

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

Теоретическая и практическая значимость

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

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

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

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

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

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

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

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

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

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

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

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

Степень достоверности и апробация результатов.

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

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

• 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 печатных работ [17 28], три из них

– в реферируемых изданиях, включённых Высшей аттестационной комиссией Минобрнауки России в список изданий, рекомендуемых для опубликования основных научных результатов диссертаций на соискание ученой степени кандидата и доктора наук, [20; 26; 27].

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

Диссертация состоит из введения, вспомогательной главы с основными определениями, трёх глав собственных исследований, заключения и списка цитируемой литературы. Работа изложена на 138 страницах, иллюстрирована одним рисунком и двумя таблицами. В списке цитируемой литературы 46 наименований.

Глава 1 ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ

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

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

Мы придерживаемся обозначений из книг [29], [30], [31], [4].

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

Мы обозначаем алфавиты буквами,,. Мы называем элементы алфавита символами и буквами. В зависимости от удобства мы обозначаем символы алфавита строчными буквами a, b, c,... или цифрами 0, 1. В случае алфавита большого размера мы обозначаем n алфавит размера n. Как правило n = {a1, a2,..., an }. Также мы используем специальные алфавиты.

Первый из них – размеченный алфавит, в этом случае мы обозначаем разметку следующим образом: n n = {a1, a2,..., an } {1, a2,..., an }. В случае, a когда мы добавляем к алфавиту символ, не входящий в него, мы называем этот символ разделителем, чаще всего обозначаем его #, а алфавит с разделителем обозначаем # = {#}. Мы обозначаем пустое слово как, а пустой символ как =. Мы используем для обозначения произвольной буквы алфавита (и иногда, возможно, пустого слова).

Под словом мы понимаем конечную последовательность букв w = w[1]w[2]... w[n], w[i]. Длину слова мы обозначаем как |w| = n. Подпоследовательность w[k]w[k + 1]... w[l] букв идущих подряд мы обозначаем как w[k, l] и называем подсловом. Подслова вида w[1, l] мы называем префиксами, а подслова вида w[l, n] суффиксами.

Пусть v = v[1]v[2]... v[l]. Под конкатенацией w · v = wv слов мы понимаем операцию добавления последовательности букв v в конец последовательности букв w: wv = w[1, n]v[1, l]. Мы в основном используем обозначение w = w1 w2... wn вместо w[1]w[2]... w[n], однако это обозначение также используется и когда речь идёт о конкатенации слов w1, w2,... wn, поэтому мы всюду уточняем это обозначение.

Определим операцию обращения:

wR = (w[1]w[2]... w[n])R = w[n]w[n 1]... w[1].

Операция конкатенации и обращения переносится на множества: X · Y = {x · y | x X, y Y }, X R = {w | wR X}. Используя конкатенацию на множествах, определим возведение языка в степень: X n = X · X ·... · X, будем n полагать, что X 0 = {} = – мы отождествляем буквы и слова единичной длины, а также слова и одноэлементные множества. Степень языка позволяет определить две базовые операции замыкания: X + = X +X 2 +X 3 +... X n +...

и операцию итерации X = + X +. Здесь и далее под операцией + над множествами мы понимаем операцию объединения.

Помимо обычных слов, мы исследуем в данной работе бесконечные вправо слова, которые называем сверхсловами. Мы говорим, что последовательность W = W [1]W [2]... W [n]..., W [i], является сверхсловом. Сверхслова мы обозначаем большими буквами. Мы обозначаем множество всех сверхслов над алфавитом как.

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

Поэтому мы будем считать, что каждый алфавит – это некоторое подмножество бесконечного (счётного) алфавита.

Класс (или семейство) языков – это некоторое непустое множество языков. Мы будем накладывать на класс языков следующее требование: если язык L принадлежит классу языков L и при этом язык L является копией языка L, то есть между алфавитами и существует биекция, которая при расширении на слова является биекцией между L и L, тогда L L. Мы будем обозначать абстрактные классы языков, необходимые для теоретических построений, как L и M.

Мы определяем на языках операцию подстановки. Зафиксируем алфавит n. Пусть Li для i 1..n. Операцию подстановки определим следующим образом: на буквах ai n : (ai ) = Li, на словах w = w1 w2 ·... · wn, wi n : (w) = (w1 ) · (w2 ) ·... · (wn ), на языках (M ) = (w). Таким образом, операция подстановки – это функция wM : n 2. Мы обозначаем 2X множество всех подмножеств множества X.

Нам потребуется обобщить понятие подстановки на классы языков. Пусть

M – класс языков. Будем называть M -подстановкой подстановку вида :

2, такую что a : (a) M. Поскольку языки из семейства L могут быть языками над разными алфавитами, то обозначим L алфавит языка L. Определим операцию подстановки на классах языков:

–  –  –

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

Определение 1.1. Детерминированная Машина Тьюринга M имеет l лент, k головок, множество состояний Q, множество принимающих состояний F Q, входной алфавит, функцию перехода : k Q k Q {0, +1, 1}k

– за такт работы машина меняет состояние, меняет символы под головками и двигает каждую головку влево, вправо или оставляет её неподвижной. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово x. В начале работы головка стоит на первом символе слова x, все остальные ячейки заполнены пустыми символами. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово.

Будем говорить, что машина Тьюринга M вычисляет функцию M (x), которая равна 1, в случае если машина M на входе x останавливается в принимающем состоянии, если машина M на входе x останавливается в непринимающем состоянии, то M (x) = 0, а если машина M не останавливается на входе x, то функция M (x) не определена.

1, M остановилась в принимающем состоянии на x;

M (x) = 0, M остановилась в непринимающем состоянии на x;

Машина M принимает язык L, если она принимает каждое слово из языка L, а если машина M принимает язык L и к тому же все слова, принимаемые машиной M, лежат в языке L, то будем говорить, что M распознаёт L. Язык, распознаваемый машиной M, будем обозначать L(M ).

Если в определении 1.1 заменить функцию переходов на отношение переходов, мы получим определение недетерминированной машины Тьюринга.

Если не оговорено противного, то мы считаем, что машина Тьюринга имеет одну ленту и одну головку.

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

Определение 1.2. Под машиной Тьюринга M с лентой-подсказкой, будем понимать машину Тьюринга, у которой есть лента-подсказка, причём на вход машины подаётся два аргумента – входное слово и слово-подсказка. В случае, если головка выходит за пределы слова, записанного на ленте-подсказке, МТ завершает работу в отвергающем состоянии.

Аналогично обычной машине, обобщённо-недетерминированная машина вычисляет функцию M (x, y), причём M (x, y) = 1, если машина M перешла в принимающее состояние на входе x при подсказке y.

Мы будем ограничивать множество слов, подающихся на вход y.

Язык F, содержащий все допустимые слова для входа y, будем называть фильтром. Машину Тьюринга с лентой-подсказкой, с фильтром F, обозначим MF. Будем называть такую машину MF обобщённонедетерминированной машиной Тьюринга.

Определение 1.3. Обобщённо-недетерминированная машина Тьюринга MF принимает язык L, если

x L y F : MF (x, y) = 1.

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

В случае, если F =, определение принимает вид стандартного для классической модели вычислений, в случае F =, || 2, определение принимает вид стандартного для недетерминированной модели вычислений.

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

Мы обозначаем DTIME(t(n)) и NTIME(t(n)) классы языков, распознаваемых детерминированными и недетерминированными машинами Тьюринга, соответственно, которые останавливаются за O(t(n)) тактов работы. Мы обозначаем DSPACE(s(n)) и NSPACE(s(n)) классы языков, распознаваемых детерминированными и недетерминированными машинами Тьюринга, соответственно, которые при работе используют O(s(n)) ячеек памяти.

Выразим через данные обозначения известные классы сложности:

–  –  –

Мы также будем работать с классами L = DSPACE(log n) и NL = NSPACE(log n). Однако их определение требует уточнения – в случае буквального наложения логарифмических ограничений по памяти на машину Тьюринга она не сможет прочитать вход до конца, поскольку вход занимает линейную память. В случае сублинейного ограничения s(n) по памяти мы полагаем, что машина Тьюринга имеет входную ленту, доступную только для чтения (изменение значений в ячейках входной ленты запрещено), и рабочую ленту, на которой МТ доступно для использования O(s(n)) ячеек памяти.

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

Изначально в работах [1; 2] под моделью обобщённо-недетерминированных автоматов понимали модель, получившуюся путём обобщённой недетерминизации многоголовочного автомата. hголовочный двусторонний автомат A это машина Тьюринга имеющая одну ленту, доступную только для записи, и h головок.

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

Теорема (Cobham1 ). Многоголовочные двухсторонние автоматы принимают языки, принадлежащие классу сложности L.

Поэтому здесь мы определим модель ОНА с фильтром F как множество обобщённо-недетерминированных машин Тьюринга на логарифмической памяти {MF } с фильтром F. Далее, мы будем обозначать обобщённонедетерминированные автоматы как AF.

Наиболее используемой в данной работе моделью вычислений является конечный автомат.

Определение 1.4. Детерминированный конечный автомат A – это устройство, описываемое набором (Q,, q0,, F ), где

• Q – конечное множество состояний автомата;

• – алфавит, слова над которым обрабатывает автомат;

• q0 – начальное состояние автомата;

• : Q Q – функция переходов;

• F Q – множество принимающих состояний.

Для краткости мы пишем A = (Q,, q0,, F ). В случае когда речь идёт об автомате A, для указания на элемент из его набора мы используем индексы: например, QA – множество состояний автомата A, даже если ранее автомат A не был явно описан набором (QA,, q0, A, FA ).

A О. Ибара утверждает, что Кобхэм получил этот результат, но не опубликовал. Доказательство описано в [32].

На вход автомата подаётся слово w = w1... wn, wi. Автомат обрабатывает слово слева направо по тактам.

За такт работы ДКА находясь в состоянии q, считывает символ и вычисляет функцию перехода (q, ). Если (q, ) = q, то автомат переходит в состояние q, если же значение (q, ) не определено, то автомат прекращает работу. Слово принимается автоматом, если после обработки слова автомат оказался в принимающем состоянии.

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

Мы продолжаем функцию и отношение переходов на слова естественным w образом: мы обозначаем (q, w) p, q p, в случае когда (q, w1 ) q1, (q1, w2 ) q2,..., (qn2, wn1 ) qn1, (qn1, wn ) p, здесь w = w1 w2... wn, wi.

Мы называем детерминированный конечный автомат всюду определённым, если для каждого состояния q и каждого символа a функция (q, a) определена.

Детерминированные и недетерминированные конечные автоматы распознают регулярные языки, класс которых мы обозначаем REG.

Машина Тьюринга, её ограничения по времени и по памяти, а также конечные автоматы реализуют функции вида {0, 1} – функция равна 1, если слово принимается МТ, и 0, если не принимается. Нас также будут интересовать функции вида. В первую очередь нас интересуют такие функции, поскольку они позволяют определить отношения на языках, которые мы используем для сложностной классификации задач регулярной реализуемости. Для определения таких функций мы используем понятие преобразователя.

1.4. Преобразователи и сводимости Мы будем называть преобразователями машины Тьюринга, у которых выделена выходная лента – односторонняя лента с одной головкой, доступная только для записи. Вообще говоря, алфавит на этой ленте может быть отличен от алфавита входной ленты. Будем говорить, что детерминированный преобразователь T вычисляет функцию T : и T (x) = y, если преобразователь T на входе x перешёл в принимающее состояние и в этот момент на выходной ленте написано слово y. В случае недетерминированного преобразователя мы говорим, что преобразователь T ставит x в отношение с y, если у T на x существует путь вычисления, в результате которого на выходной ленте написано слово y. Множество всех слов в отношении с x мы обозначаем как T (x).

Функция f : называется вычислимой, если существует детерминированный преобразователь T, который реализует данную функцию:

T (x) = f (x). В случае когда функция f является всюду определённой, преобразователь T останавливается на каждом входе. Также нам потребуются вычислимые функции вида f : N – данные вычислимые функции позволяют определить вычислимые сверхслова.

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

Определение 1.5. Пусть для языка A существует такая всюду определённая вычислимая функция f :, что слово x принадлежит A тогда и только тогда, когда слово f (x) принадлежит языку B. Будем говорить, что язык A сводится к языку B m-сводимостью и обозначать это A B.

m В случае различных ограничений на преобразователи мы получаем хорошо известные виды m-сводимости: детерминированные преобразователи, работающие за полиномиальное время, реализуют полиномиальную mсводимость P; детерминированные преобразователи, работающие на логарифмической памяти, реализуют m-сводимость на логарифмической памяти log.

<

–  –  –

Детерминированные автоматные преобразователи реализуют автоматную сводимость, которую мы обозначаем как drat. Мы говорим, что если существует такой детерминированный автоматный преобраA drat B, <

–  –  –

существует такой автоматный преобразователь T, что A = T (B).

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

1.5. КС-языки

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

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

Определение 1.7. Контекстно-свободная грамматика G определяется набором (N,, P, S), где

• N – множество нетерминальных символов, • – множество терминальных символов,

• P – множество правил вывода вида A, A N, (N ),

• S – аксиома, S N.

Все множества из описания грамматики конечные. При этом N =.

–  –  –

Моделью вычислений, которая распознаёт класс КС-языков, является автомат с магазинной памятью (магазинный автомат). Под магазинной памятью понимают стек, однако название стековый автомат исторически закрепилось за другой, более редкой, моделью вычислений ([31]).

Определение 1.8. Автомат с магазинной памятью P задан набором (,, Q, q0, z0,, F ), где • – входной алфавит;

• – алфавит стека;

• Q – множество состояний автомата;

• q0 Q – начальное состояние автомата;

• z0 – единственный символ, находящийся в стеке при начале работы автомата;

• : Q { } 2Q – функция переходов;

• F – множество принимающих состояний.

В начале работы автомат находится в состоянии q0, и в магазине лежит только символ z0. За такт работы автомат считывает букву из входного слова (или же не считывает и тогда выполняет -переход) и действует согласно одному из правил перехода.

А именно, пусть автомат находится в состоянии q, на вершине стека лежит символ z, и автомат считывает букву. Тогда автомат выбирает одну из пар (q, ) (q,, z), переходит в состояние q, снимает с вершины символ z и добавляет в стек слово, причём, если = 1 2... n, то n оказывается снизу, а 1 сверху. Автомат завершает работу с ошибкой, если не может выполнить переход, а входное слово ещё не обработано.

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

–  –  –

условие требуется для определения автоматов со счётчиками (по [4]), используемых в разделе 3.3. МП-автомат M называется автоматом со счётчиком без теста на ноль, если его алфавит стека состоит из одного символа.

Сформулируем условие приёма слова автоматом со счётчиком M в терминах конфигураций: L(M ) = {w | (q0, w, z0 ) (qf,, ), qf F }.

Автоматы со счётчиком с тестом на ноль имеют два символа в алфавите стека – например, = {x, z0 }.

Однако, один из этих символов, z0, встречается в каждой конфигурации автомата ровно один раз на дне магазина:

конфигурации такого автомата имеют вид (q, v, xn z0 ).

Определение 1.10. Магазинный автомат P является детерминированным, если множество (q,, Z) содержит не более одного правила {}, Z. Если для некоторой буквы =, (q,, Z) =, то (q,, Z) =.

То есть все переходы в автомате P определены однозначно, и когда из пары (q, Z) есть -переход, то других переходов из данной пары нет.

Детерминированные магазинные автоматы, допускающие по принимающему состоянию и по пустому стеку, распознают разные классы языков. Первый из них называют классом детерминированных КС-языков DCFL, а второй является подклассом первого.

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

–  –  –

(Q,, q,, S). Если мы меняем только начальное состояние или множество принимающих состояний, то мы опускаем соответствующий индекс:

Aq = AF, AS = AS0.

q q Часто удобно указать в каком состоянии оказывается конечный автомат после обработки из состояния q слова w. Для этого мы используем обознаw чение q p, в случае если w = w1 ·... · wn, где wi, q1 (q, w1 ), q2 (q, w2 ),..., qn1 (qn2, wn1 ) и qn1 = p.

Также, когда мы пишем (q, w), мы понимаем естественное расширение отношения переходов на слова: множество (q, w) содержит все состояния, достижимые из q по w.

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

Приведём стандартные примеры конструкции произведения. Путём конструкции произведения можно построить ДКА, реализующий объединение или пересечение языков, заданных ДКА. В случае пересечения языков, заданных ДКА A и B, достаточно потребовать, чтобы начальное состояние было парой начальных q0 = (q0, q0 ), множество принимающих состояний AB состояло из пар принимающих F = FA FB, а переходы по компонентам осуществлялись независимо: ((q, p), a) = (A (q, a), B (p, a)).

В случае пересечения двух НКА, отношение переходов устроено следующим образом:

p.

((q, p), a) (q, p ), A (q, a) q, B (p, a) Нас будет также интересовать ограничение области определения и множества значений автоматного преобразователя. Регулярные ограничения легко достигаются применением конструкции произведения, аналогичной кон

–  –  –

Задача регулярной реализуемости была введена М. Н. Вялым в работе [3] с целью исследования связи свойств простых относительно сложностной классификации формальных языков с известными классами сложности. В работе [33] показано, что задача регулярной реализуемости является полной для широкого ряда классов сложности. Изначально для выявления этой связи в работах [1; 2] была предложена модель обобщённо-недетерминированных автоматов (ОНА). В данной главе мы описываем связь модели ОНА с задачей регулярной реализуемости, а также исследуем вопросы разрешимости, естественно вытекающие из анализа этой модели.

Напомним, что под обобщённым-недетерминированным автоматом мы понимаем машину Тьюринга на логарифмической памяти, которая имеет дополнительную одностороннюю бесконечную вправо ленту, доступную только для чтения. Мы называем эту ленту лентой подсказки. Автомат ОНА MF получает на вход пару (x, y), где x – входное слово над алфавитом, а y – слово из языка F, записанное на ленту подсказки. В ячейках ленты подсказки, не занятых символами слова y, записан пустой символ.

Автомат MF принимает слово x, если существует такое слово y F, что на входе (x, y) автомат MF переходит в принимающее состояние; при этом слово y полностью прочитано автоматом – головка ленты подсказки перешла на символ. Более подробно модель ОНА описана в разделе 1.2.

Мы покажем, что задача RR(F ) для непустого фильтра является полной в соответствующем классе ОНА относительно log -сводимости: модель ОНА с фильтром F распознаёт класс языков {L | L RR(F )}.

log Из модели ОНА естественным образом возникает вопрос о разрешимости задач регулярной реализуемости специального вида – задач для языков вида Pref(W), состоящих из префиксов бесконечного вправо слова W. Мы называем бесконечные вправо слова сверхсловами. Мы называем задачу регулярной реализуемости RR(Pref(W)) задачей префиксной реализуемости Rp (W ).

Задача Rp (W ) оказывается связанной с монадической теорией второго порядка MT(N,, W) для сверхслова W. Раздел 2.3. посвящён исследованию этой связи: из разрешимости MT(N,, W) следует разрешимость Rp (W ), однако сводимость в обратную сторону отсутствует. В разделе 2.4. мы доказываем, что для любой задачи регулярной реализуемости существует эквивалентная по разрешимости задача префиксной реализуемости, используя в качестве основного инструмента критерий Семёнова разрешимости монадических теорий.

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

Мы покажем, что языки, распознаваемые моделью ОНА с непустым фильтром F, – это в точности языки, которые сводятся к задаче RR(F ) на логарифмической памяти. Заметим, что, поскольку модель ОНА с фильтром распознаёт класс L, сводимость на логарифмической памяти является самой слабой из подходящих.

Пусть язык F определён над алфавитом и. Определим F = F. В общем случае (если допускать пустой фильтр), языки, распознаваемые моделью ОНА с фильтром F, сводятся на логарифмической памяти к задаче RR(F ). Эта задача является более естественной для модели ОНА.

Однако, язык F является лишь техническим инструментом – задачи RR(F ) и RR(F ) сводятся друг к другу на логарифмической памяти, если язык F не пуст.

Утверждение 2.1. Пусть F – непустой язык, тогда

–  –  –

ратную сторону очевидна: если ДКА A имеет переходы только по символам из алфавита, то слово w принадлежит пересечению L(A) F тогда и только тогда, когда w L(A) F, поэтому при сводимости автомат A на входе задачи RR(F ) переходит в себя в качестве входа задачи RR(F ).

По построению языка F, если w F, |w| = n и wi =, то wi+1 =,..., wn =. Пусть ДКА A является входом задачи RR(F ).

Определим для каждого состояния q автомата A последовательность {sn (q)} :

s0 = q, sn+1 = A (sn, ). Каждая такая последовательность содержит не более |QA | различных состояний, и если sk = sm+k, то начальный отрезок s0,..., sm+k содержит все состояния последовательности. Таким образом, проверка, содержит ли последовательность {sn (q)} принимающее состояние автомата A, осуществима на логарифмической памяти.

Построим по автомату A автомат B, являющийся входом задачи RR(F ).

Зафиксируем слово w0 F, которое существует в силу непустоты F, и ДКА B0, распознающий язык {w0 }. В случае, если последовательность {sn (q0 )} соA держит принимающее состояние, автомат B совпадает с автоматом B0. Иначе, автомат B содержит те же состояния, что и A, имеет то же начальное состояние, а также все переходы A, за исключением переходов по символу.

Множество принимающих состояний B состоит из тех состояний q, последовательность {sn (q)} которых содержит принимающее состояние A.

Итак, построение автомата B осуществимо по описанию автомата A на логарифмической памяти. При этом L(A) RR(F ) тогда и только тогда, когда L(B) RR(F ): в случае если автомат A принимает слово языка, автомат B = B0 принимает слово w0 F. Иначе, если язык L(A) непустой, то A принимает слово yk, y +, k 0. Автомат B перейдёт по y в то же состояние q, что и A, при этом q является принимающим состоянием тогда и только тогда, когда автомат A переходит из q в принимающее состояние по некоторому слову k.

Перейдём к доказательству того, что модель ОНА с непустым фильтром F распознаёт класс языков, сводящихся к задаче регулярной реализуемости RR(F ) на логарифмической памяти. Покажем сначала, что существует ОНА с фильтром F, который решает задачу регулярной реализуемости RR(F ).

Утверждение 2.2. Задача регулярной реализуемости RR(F ) разрешима автоматом ОНА с фильтром F.

Доказательство. Пусть ДКА A является входом задачи регулярной реализуемости RR(F ). Если A RR(F ), то существует слово y F, принимаемое A. Тогда ОНА AF, решающий задачу, на входе (A, y) запоминает текущее состояние автомата A и обрабатываемый символ слова y, проходит по таблице переходов A, меняет состояние, если нашёлся подходящий переход, и считывает следующий символ y. Если при достижении символа состояние автомата A является принимающим, то ОНА AF принимает пару (A, y).

ОНА AF на каждом шаге работы хранит в памяти только одно состояние q автомата A, один символ a с ленты подсказки и проверяет существование перехода (q, a). Это очевидно осуществимо на логарифмической памяти.

–  –  –

рифмической памяти T, реализующий данную сводимость. На вход задачи RR(F ) поступает описание ДКА T (x), число состояний и число переходов которого полиномиальны по входу x, а значит состояние и описание правила перехода автомата T (x) можно хранить на логарифмической по |x| памяти. Построим по преобразователю T ОНА AF (x, y), который будет запускать T (x) на входе y. Это осуществимо на логарифмической памяти: для этого AF будет хранить в памяти текущее состояние q автомата T (x) и запускать T на x, храня в памяти последнее конечное число символов с выходной ленты T, пока в них не встретится подходящее правило для состояния q и текущего символа слова y.

В случае, если слово y было прочитано автоматом T (x) и принято, автомат AF принимает пару (x, y), в ином случае автомат AF дочитывает слово y до конца и отвергает пару (x, y).

Покажем, что задача регулярной реализуемости RR(F ) является полной в классе языков, распознаваемых моделью ОНА.

Лемма 2.2.

Любой язык, распознаваемый автоматом ОНА с фильтром F, сводится log -сводимостью к задаче регулярной реализуемости RR(F ).

Доказательство. Рассмотрим произвольный автомат AF. Поскольку AF является МТ на логарифмической памяти с дополнительной лентой, то, как и в случае с МТ на логарифмической памяти, при фиксированном входе x число конфигураций AF является полиномом от |x|.

Построим граф переходов на множестве конфигураций AF, на рёбрах которого написан символ с ленты подсказки из множества {, }, являющийся аргументом функции переходов при данном переходе. Данное построение осуществимо на логарифмической памяти по длине описания в силу полиномиальности числа конфигураций.

В силу однозначности переходов при стягивании полученного графа по рёбрам получим граф детерминированного конечного автомата Ax, начальное состояние которого есть начальная конфигурация, а принимающие состояния – конфигурации с принимающими состояниями AF. Очевидно, что AF (x, y) = Ax (y). Автомат Ax является входом задачи регулярной реализуемости. Таким образом, AF : L(AF ) RR(F ).

log

–  –  –

Доказательство. Задача регулярной реализуемости RR(F ) разрешается некоторым ОНА с фильтром F по утверждению 2.2. В одну сторону включение следует из леммы 2.1.

В другую сторону. Лемма 2.2 устанавливает сводимость RR(F ) для произвольного ОНА AF. При этом, в силу непустоты L(AF ) log

–  –  –

2.2. Вопросы разрешимости Мы установили соответствие между задачами регулярной реализуемости и моделями ОНА. Формализм ОНА удобен при исследовании вопросов разрешимости: из анализа модели ОНА возникает естественный вопрос о разрешимости задач регулярной реализуемости специального вида – задач для префиксов сверхслов. Далее мы покажем, что такие задачи являются универсальными – для любой задачи регулярной реализуемости существует эквивалентная по Тьюрингу задача специального вида. Кроме того, разрешимость этих задач связана с разрешимостью монадических теорий.

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

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

Сверхслово W = W1 W2... Wn..., Wi назовем вычислимым, если вычислима функция n Wn. В дальнейшем мы рассматриваем только вычислимые сверхслова и не оговариваем это каждый раз в формулировках утверждений. Напомним, что мы обозначаем Pref(W) множество префиксов сверхслова W.

Рассмотрим ОНА с фильтром F. Будем говорить, что сверхслово WF = #y1 #y2 #... #yi #..., где #, является сверхсловом для фильтра F, если сверхслово WF содержит в качестве подслова все слова языка #F #, причём если слово #u#, u, является подсловом сверхслова WF, то u F. Покажем, что задача о том, принимается ли слово x ОНА AF сводится к задаче распознавания слова x ОНА APref(WF ). Для этого достаточно доказать, что существует ОНА APref(WF ), который решает задачу регулярной реализуемости RR(F ).

Утверждение 2.3. RR(F ) L(APref(WF ) ).

log Доказательство. Пусть A – ДКА на входе задачи RR(F ). ОНА APref(WF ) запускает A поочерёдно на словах y1,..., y2,..., yn, которые входят в префикс w = y1 #y2 #... #yn #yn+1, где yn+1 – префикс слова yn+1, возможно пустой.

Если некоторое слово yi принимается автоматом A, то ОНА AF дочитывает подсказку до конца, после чего принимает префикс; если yi не принимается, то ОНА AF запускает ДКА A из начального состояния на слове yi+1, продолжая так, пока не дойдёт до конца слова, при этом, даже если A перешёл в принимающее состояние на слове yn+1, ОНА отвергает вход, встретив вместо символа # символ.

В случае, когда A принимает yi, ОНА APref(WF ) принимает описание A, в противном случае отвергает пару (A, w).

Таким образом, используя полноту задачи регулярной реализуемости в классе ОНА, мы фактически доказали следующее утверждение.

Утверждение 2.4. Пусть WF является сверхсловом для фильтра F. Тогда RR(F ) RR(Pref(WF )) = Rp (WF ).

log Таким образом, любая задача регулярной реализуемости сводится к задаче префиксной реализуемости – отсюда возникает естественный вопрос о разрешимости задач префиксной реализуемости.

С другой стороны, при данной сводимости задача регулярной реализуемости Rp (WF ) может оказаться сложнее задачи RR(F ) даже в плане разрешимости.

Утверждение 2.5. Существует такое вычислимое сверхслово W, для которого задача Rp (W ) неразрешима.

Доказательство. Укажем условия на сверхслово W, при которых к задаче Rp (W ) сводится проблема остановки машины Тьюринга. После чего покажем, что существует вычислимое сверхслово W, удовлетворяющее данным условиям.

Зафиксируем некоторую нумерацию машин Тьюринга, в которой по номеру i МТ Mi вычислимо её описание Mi. Мы предполагаем, что описание машин Тьюринга и их конфигураций устроено таким образом, что ни одно слово не является одновременно описанием некоторой МТ и описанием некоторой конфигурации МТ; причем слов, не являющихся описанием МТ или конфигурации, бесконечно много, и языки описаний и конфигураций МТ разрешимы.

Пусть слова wi (M ) образуют последовательность описаний конфигураций машины Тьюринга M при работе на пустом входе. Если МТ M остановилась на шаге n, то wm+1 (M ) = wm (M ), m n.

Пусть в сверхслове W = #y1 #y2 #... для каждой последовательности wi (M ) существует подпоследовательность yki = wi (M ), и при этом yj = M тогда и только тогда, когда yj+1 лежит на последовательности yki. Тогда к задаче Rp (W ) сводится проблема останова: автомату на входе Rp (W ) достаточно проверить, что за словом # M # в сверхслове W следует слово, содержащее код принимающего состояния M.

Покажем, что существует вычислимое сверхслово W, обладающее описанными свойствами. Зафиксируем вспомогательные последовательности, используемые для построения W. Определим последовательность v1, v2,...

как последовательность всех слов, за исключением описаний МТ, упорядоченных лексикографически. Последовательность {vi } очевидно вычислима.

Пусть f – вычислимая биекция N N N, такая что если f (n) = (i, j), f (m) = (i, k), то j k тогда и только тогда, когда n m. Стандартная биекция с нумерацией элементов декартова квадрата по диагоналям, приведённая в [29] (Figure 4.16), удовлетворяет этому свойству.

Пусть последовательность (x1, z1 ), (x2, z2 ),... состоит из таких пар слов, что f (k) = (i, j), xk = Mi и zk = wj (Mi ). Такая последовательность является вычислимой.

Построим сверхслово W = #y1 #y2 #... следующим образом: y3k = vk, y3k+1 = xk, y3k+2 = zk. Таким образом, сверхслово W действительно является сверхсловом для, является вычислимым, и при этом задача Rp (W ) неразрешима.

Итак, из анализа модели ОНА возникает естественный вопрос о существовании для каждого фильтра F такого сверхслова WF, что задача RR(F ) разрешима тогда и только тогда, когда разрешима задача Rp (WF ) – сверхслова WF, для которого данные задачи эквивалентны по Тьюрингу. Мы доказываем существование такого сверхслова в разделе 2.4.

В других терминах задача префиксной реализуемости является задачей о поведении автоматов на сверхслове. Вопрос задачи состоит в том, окажется ли автомат в принимающем состоянии хотя бы один раз при чтении сверхслова. Другой естественной задачей о поведении автоматов на сверхслове является проверка того, окажется ли автомат в принимающем состоянии бесконечное число раз. Её эквивалентное описание – задача о проверке бесконечности пересечения регулярного языка и множества префиксов данного сверхслова. Мы будем называть эту алгоритмическую задачу задачей Бюхиреализуемости и обозначать R. Формально, p

–  –  –

от A лишь тем, что каждое принимающее состояние A становится поглощающим: если q – принимающее состояние, то для любого a выполнено A (a, q) = q.

Обратной сводимости не существует: мы приводим пример сверхслова, которое префиксно разрешимо, но не разрешимо по Бюхи, в разделе 2.3.

В работе Бюхи [10] была обнаружена связь между задачей Бюхиреализуемости и разрешимостью монадических теорий второго порядка.

Дальнейшие результаты о разрешимости этих теорий основывались на этой связи (см., например, [11; 12]).

Мы устанавливаем эквивалентность по Тьюрингу произвольной задачи регулярной реализуемости RR(F ) и задачи префиксной реализуемости Rp (WF ) для некоторого сверхслова WF, опираясь на критерий Семёнова [11] разрешимости монадических теорий.

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

–  –  –

сти монадической теории второго порядка MT(N,, W), W. Это расширение теории первого порядка натуральных чисел с отношением порядка и одноместными предикатами a(n) для каждого a. В монадической теории добавляются монадические переменные по одноместным предикатам на N.

При интерпретации формул теории MT(N,, W) полагаем предикат a(n) истинным, если, и только если, W [n] = a; отношение порядка интерпретируется естественным образом.

Для формулы теории MT(N,, W) через L () обозначим множество сверхслов, для которых истинна. Оказывается, что для любой формулы множество L () является регулярным -языком.

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

Ходом автомата A с множеством состояний Q на сверхслове W называется сверхслово в алфавите Q (2.1) = q0 q1... qn..., в котором qn+1 получается из qn при чтении n-го символа сверхслова. Для детерминированных автоматов ход определяется однозначно по сверхслову.

Предельным множеством lim A на заданном ходе автомата A назовем множество тех состояний, которые встречаются в последовательности (2.1) бесконечное число раз.

Автомат Бюхи принимает сверхслово W тогда и только тогда, когда существует такой ход автомата на этом сверхслове, на котором одно из принимающих состояний попадает в lim A.

В автомате Мюллера множество финальных состояний заменяется на семейство финальных макросостояний F 2Q, где Q множество состояний. Автомат Мюллера принимает сверхслово W тогда и только тогда, когда существует такой ход автомата на этом сверхслове, на котором lim A F.

Через L (A) будем обозначать множество сверхслов, принимаемых автоматом A, и называть это множество регулярным -языком. Оказывается, что (см. [34; 35]) совпадают классы -языков, распознаваемых недетерминированными автоматами Бюхи и автоматами Мюллера (как детерминированными, так и недетерминированными). При этом построение эквивалентных автоматов эффективно.

Теорема (Бюхи, [10]). Существует алгоритм, который по недетерминированному автомату Бюхи A строит такую формулу монадической теории второго порядка, что L (A) = L (). Существует также обратный алгоритм, который строит по формуле автомат Бюхи, принимающий в точности сверхслова из L ().

Детерминированные автоматы Бюхи принимают меньший класс сверхслов. Однако если нас интересует разрешимость теории MT(N,, W), то разницы между детерминированными автоматами Бюхи и остальными видами

-автоматов нет.

Утверждение 2.7. Проверка того, что данный недетерминированный автомат Бюхи принимает сверхслово W, эквивалентна по Тьюрингу проблеме R (W) Бюхи-реализуемости.

p Доказательство. Сведём сначала задачу о проверке приёма автоматом Бюхи сверхслова W к задаче R (W). По недетерминированному автомату Бюхи p N построим эквивалентный ему детерминированный автомат Мюллера M.

По автомату Мюллера M построим семейство детерминированных автоматов Бюхи {M {qf } }, где qf состояние, принадлежащее хотя бы одному макросостоянию F F автомата M. Автомат Бюхи M {qf } получается из M путём замены множества принимающих макросостояний на одно принимающее состояние qf с сохранением графа исходного автомата – мы используем здесь базовую конструкцию, описанную для ДКА в разделе 1.6.

Автомат Мюллера M принимает сверхслово W тогда и только тогда, когда какое-то макросостояние из семейства финальных макросостояний автомата M встречается на ходе автомата бесконечно часто. Но это равносильно тому, что для некоторого принимающего макросостояния F автомата M каждый автомат Бюхи из множества {M {qf } | qf F } принимает W, и при этом ни один из автоматов {M {qf } | qf QM \ F } не принимает сверхслово W.

Обратное утверждение очевидно, так как детерминированный автомат Бюхи – частный случай недетерминированного.

Таким образом, разрешимость по Бюхи сверхслова W равносильна разрешимости теории MT(N,, W). Значит, в силу утверждения 2.6, из разрешимости теории MT(N,, W) для сверхслова W следует его префиксная разрешимость.

В частности, из результатов [11; 36] вытекает префиксная разрешимость эффективно обобщённо почти периодических сверхслов, а из результатов [12] префиксная разрешимость морфических сверхслов.

Обратной сводимости не существует.

Теорема 2.2.

Существует префиксно разрешимое сверхслово W, для которого задача Бюхи-реализуемости неразрешима.

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

Сверхслово W {0, 1} имеет вид

–  –  –

где слова wn и un являются конкатенациями блоков: слов вида bm = 10m 1 (число m будем называть рангом блока).

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

Слово wn является конкатенацией блоков всех рангов j Tn в порядке возрастания j.

Слово un зависит от того, может ли автомат An (в выбранной нумерации автоматов) пройти через принимающее состояние при чтении продолжения слова vn = w1 u1 w2 u2... wn какой-нибудь конкатенацией блоков, отвечающих всем машинам, кроме тех, которые уже остановились к этому времени.

Более формально, определим множество слов

–  –  –

автомат, который отличается от An только начальным состоянием, которое у него равно q (подробнее см. раздел 1.6.).

Если L(An ) Sn =, то в качестве un выбираем лексикографически q

–  –  –

Построение сверхслова W закончено. Проверим его вычислимость. Вычислимость слов wn не вызывает сомнений. Для проверки вычислимости un докажем, что язык Sn регулярный. В самом деле, в Sn не входит лишь ко

–  –  –

ков относительно теоретико-множественных операций. По тем же причинам язык L(An ) Sn также регулярный. Построение лексикографически наиq меньшего слова в регулярном языке очевидно разрешимо: достаточно найти все кратчайшие пути из начального состояния в графе автомата некоторое принимающее и выбрать из соответствующих путям слов лексикографически наименьшее.

Теперь докажем разрешимость задачи префиксной реализуемости Rp (W).

Поскольку в конструкции используется вычислимая биекция между автоматами и натуральными числами, по автомату A можно определить его номер n. Из построения следует, что слова uk, wk при k n составлены только из блоков, принадлежащих множеству Sn (множество остановившихся машин не уменьшается с ростом числа тактов работы). Слово un форсирует проход через принимающее состояние при чтении таких блоков, если это вообще возможно. Поэтому если автомат A не побывал в принимающем состоянии после чтения префикса vn un сверхслова W, то он никогда не попадает в принимающее состояние при чтении сверхслова W.

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

p

–  –  –

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

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

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

Мы используем критерий Семёнова для доказательства основной леммы.

Лемма 2.3.

Пусть для языка F разрешима задача регулярной реализуемости RR(F ) и пусть сверхслово W имеет вид w1 w2... wn..., где wi F, и при этом каждое слово языка F входит в W в качестве подслова. Тогда разрешима монадическая теория MT(N,, W).

Доказательство. Заметим, что если разрешима задача регулярной реализуемости RR(F ), то разрешима и задача регулярной реализуемости RR(F ).

Пусть A – автомат на входе задачи RR(F ). Рассмотрим всевозможные автоматы1 Ar, q, r QA и решим для каждого из них задачу регулярной реq <

–  –  –

положителен, то тогда и ответ на вопрос задачи RR(F ) для автомата A положителен. Очевидно, что если такой последовательности не существует, то ответ на вопрос задачи RR(F ) отрицательный.

Автомат с начальным состоянием q и принимающим r, см. раздел 1.6.

Пусть R – регулярный язык на входе алгоритма критерия Семёнова. Покажем, что язык R содержит хотя бы одно слово xyz из языка F, такое что y R, тогда и только тогда, когда слово y содержится в каждом суффиксе W. Пусть R RR(F ). Тогда, по построению W, любая конкатенация слов из F является подсловом W, а значит некоторый префикс w1 w2... wn, wi F сверхслова содержит xyz в качестве подслова. Но тогда, по построению W, некоторый префикс W содержит в качестве подслова и слово w1 w2... wn xyz, а значит для любого n слово (xyz)n+1 содержится в суффиксе wn+1 wn+2..., поскольку в префиксе w1 w2... wn оно содержаться не может. Отсюда следует, что каждый суффикс W содержит в качестве подслова слово y в силу определения W.

В обратную сторону. Если сверхслово W содержит y в некотором суффиксе, то y можно продолжить до конкатенации слов из F по определению W.

Получаем, что алгоритм для критерия Семёнова устроен следующим образом: он проверяет соотношение R RR(F ) и в случае отрицательного ответа возвращает 1.

Приведём пример построения сверхслова, для которого выполняется условие леммы 2.3. Мы будем опираться на этот пример при доказательстве основной теоремы раздела. Сначала построим вспомогательное сверхслово W над бесконечным счётным алфавитом = {1, 2,..., n,...}. Пусть слово wn состоит из конкатенации всех слов длины n над алфавитом {1,..., n } в лексикографическом порядке. Определим сверхслово W = w1 w2... wn...

как конкатенацию wi. Очевидно, что каждое (конечное) слово над бесконечным алфавитом входит как подслово в W бесконечное число раз, и, кроме того, сверхслово W является вычислимым.

Покажем теперь, как по языку F с разрешимой задачей регулярной реализуемости построить сверхслово WF с разрешимой монадической теорией MT(N,, WF ). Из леммы 2.3 и приведённого примера очевидно следует Утверждение 2.8. Занумеруем все слова языка F. Определим морфизм :, поставив в соответствие символу i слово языка F под номером i. В случае если F конечный язык, поставим всем n, n |F |, в соответствие пустое слово. Тогда если разрешима задача регулярной реализуемости RR(F ), то для сверхслова WF = (W ) разрешима монадическая теория MT(N,, WF ).

Теперь мы готовы доказать основной результат раздела.

Теорема 2.3.

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

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

Таким образом, по утверждению 2.8, мы установили сводимость по Тьюрингу MT(N,, VF ) Пользуясь теоремой Бюхи и утвержденияT RR(F).

ми 2.6 и 2.7, получаем цепь сводимостей

–  –  –

Сводимость в обратную сторону строится явным образом. Пусть R – вход задачи RR(F ), тогда, по построению VF, R RR(F ) тогда и только тогда, когда #R# Rp (VF ).

#

–  –  –

На рисунке 3.1 изображён рациональный конус КС-языков с собственными подконусами. Этот рисунок хорошо известен по книге Ж. Берстеля [4] о рациональных конусах и КС-языках. На её обложке изображён оригинальный конус, на основе которого построен наш рисунок. Отношение рационального доминирования вводит отношение порядка на рациональных конусах. Сложность задачи недетерминированной регулярной реализуемости согласована с этим порядком: если генератор одного рационального конуса рационально доминирует генератор другого, то задача регулярной реализуемости для любого языка из второго конуса не сложнее задачи регулярной реализуемости для генератора первого. Мы описываем связь между задачей регулярной реализуемости и рациональными конусами в разделе 3.1. Мы назовём классификацию по сложности задачи регулярной реализуемости NRR(F ) КС-языка F сложностной классификацией.

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

Из рисунка видно, что все представленные рациональные конусы, кроме конуса CFL, содержат лёгкие языки. Естественно предположить, что все языки, кроме генераторов конуса КС-языков, лёгкие. Однако, это не так. В разделе 3.4. мы приводим пример языка, который не является генератором конуса КС-языков, однако является трудным. На рисунке это язык S#.

Как мы уже упоминали во введении, отношение рационального доминирования согласовано с недетерминированной версией задачи регулярной реализуемости: из A следует сводимость NRR(A) NRR(B). Поэтому rat B log мы исследуем недетерминированную версию задачи для КС-языков. Однако, как будет показано в разделе 3.1., все результаты этой главы по классификации сложности конусов также переносятся на детерминированную версию задачи. Важное различие между недетерминированной и детерминированной версиями задачи проявляется на регулярных языках: для любого непустого регулярного языка F задача NRR(F ) является NL-полной, но это неверно для детерминированной версии задачи – очевидно, что для любого конечного языка F задача RR(F ) лежит в классе L.

Мы начинаем главу с описания связи детерминированных и недетерминированных автоматных преобразований, задающих, соответственно, отношения рационального доминирования и автоматного накрытия drat, с rat задачами регулярной реализуемости. Затем мы переходим к исследованию сложности задачи детерминированной регулярной реализуемости для регулярных языков. Для них выполняется дихотомия: либо для регулярного языка F задача RR(F ) лежит в классе L, либо она полна в классе NL.

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

– КС-языки с полиномиально ограниченным рациональным индексом. Для них мы доказываем, что задача регулярной реализуемости лежит в классе NSPACE(log2 n).

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

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

Говоря о рациональных конусах, мы опираемся на изложение этой темы в книге [4]. Мы придерживаемся приведённых в ней определений и наименований рациональных конусов. Также в ней доказаны основные используемые нами факты об отношении рационального доминирования и рациональных конусах. Заметим однако, что в книге Берстеля изложение в основном ведётся на алгебраическом языке, а нужные нам факты следуют из доказанных в книге, если перейти к формализму автоматных преобразователей – автоматные преобразователи реализуют рациональные отношения. Эквивалентность данных формализмов доказана в книге. Мы приводим в этом разделе нужные нам факты о рациональных конусах и автоматных преобразователях, а также устанавливаем связь между отношением рационального доминирования и задачами регулярной реализуемости.

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

Мы называем отношение T 1 (u) = {w | T (w) = u} обратным автоматным преобразованием к автоматному преобразованию, заданному преобразователем T.

Утверждение 3.1 ([4]). Для каждого (недетерминированного) автоматного преобразователя T существует автоматный преобразователь, реализующий обратное автоматное преобразование T 1.

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

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

Рассмотрим два автоматных преобразователя T1 и T2, реализующих рациональные отношения R1 и R2. Будем говорить, что преобразователь T = T1 T2 является композицией T1 и T2, если отношение R, реализуемое T, имеет вид R = {(u, v) | y(u, y) R1, (y, v) R2 }.

Определим композицию автоматного преобразователя T и автомата A аналогичным образом: будем говорить, что автомат B = T A распознаёт язык {w | y L(A), (w, y) R}.

Следующее утверждение является алгоритмической версией теоремы Элгота-Мецеи (формулировку теоремы см., например, в [4, Th. III.4.4]).

Утверждение 3.2. Композиция автоматных преобразователей, а также композиция автоматного преобразователя и конечного автомата вычислимы на логарифмической памяти.

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

Явные конструкции композиции автоматных преобразователей или преобразователя и конечного автомата хорошо известны (см., например, в [5, с. 88, 206]). Легко видеть, что эти конструкции вычислимы на логарифмической памяти. Для полноты изложения мы приведём здесь доказательство этого утверждения.

Доказательство. Используем известный факт о том, что для каждого преобразователя существует эквивалентный, который пишет не более одной буквы на выходную ленту за такт. Построить эквивалентный преобразователь, удовлетворяющий данному свойству, несложно: если преобразователь пишет слово u1 u2... un при обработке из состояния q символа a, то заменим правило (q, u1 u2...

un ) на цепочку правил:

(q, a)

–  –  –

При этом происходит добавление вспомогательных состояний вида [q, v]. Алфавиты лент, начальное состояние и множество принимающих состояний при данном преобразовании не изменяются. Такое построение очевидно корректно и осуществимо на логарифмической памяти.

Перейдём к построению композиции преобразователей, предполагая, что каждый преобразователь пишет не более одной буквы на выходную ленту за такт работы. В качестве множества состояний преобразователя T, результата композиции T1 T2, выступает множество пар QT1 QT2.

Опишем, как устроено отношение переходов T. В случае, если T1 (q, ) = (q, a) и T2 (p, a) (p, b), таблица отношения переходов преобразователя T содержит строку T ((q, p), ) ((q, p ), b); здесь T1 {}, a T1 = T2, b T2. А в случае, если T2 (p, ) (p, ), преобразователь T имеет переход T ((q, p), ) ((q, p ), ).

Начальным состоянием T является пара начальных состояний T1 и T2, а принимающими состояниями являются пары, в которых каждое состояние принимающее.

Данное построение очевидно реализует композицию T1 T2 : если u T1 (v), w T2 (u), то преобразователь T эмулирует работу преобразователей T1 и T2 : как только T1 пишет должен написать букву на выходную ленту, её получает T2 и выполняет такт вычисления. В другую сторону, если w T (v), то по протоколу T на (v, w) восстанавливается слово u.

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

Приведённая в доказательстве конструкция относится к так называемым конструкциям произведения, описанным в разделе 1.6.

Перейдём к примерам главных рациональных конусов.

Пример 3.1.

Регулярные языки образуют главный рациональный конус REG, порождённый : REG = T ( ).

Действительно, T ( ) – регулярный язык, полученный композицией автомата A, распознающего, и автоматного преобразователя T. Другими словами, проекция рационального отношения – регулярный язык. В обратную сторону, любой автомат A можно представить как композицию автоматного преобразователя с автоматом A. Возьмём автоматный преобразователь Id, реализующий тождественное преобразование, и сузим его область определения на L(A). Сужение осуществляется стандартной конструкцией произведения – множество принимающих состояний получившегося преобразователя состоит из пар принимающих состояний преобразователя Id и автомата A; переходы по компонентам пар осуществляются независимо.

Заметим также, что для любого непустого регулярного языка R справедливо T (R) = T ( ). Действительно, пусть u R. Тогда для любого регулярного языка L существует преобразователь T, реализующий рациональное отношение {(u, v) | v L}. Поэтому любой регулярный язык L принадлежит конусу T (R).

Второй базовый пример рационального конуса – конус контекстносвободных языков CFL. Наиболее важным для нас (и главным в смысле рациональных конусов) КС-языком будет язык Дика Dn : язык правильных скобочных выражений с n типами скобок, который задан грамматикой:

–  –  –

Следующий вариант формулировки теоремы Хомского-Шютценберже, приведённый в [4], иллюстрирует, что класс CFL является главным рациональным конусом.

Теорема (Хомский, Шютценберже).

При n 2 язык Дика Dn является генератором рационального конуса КС-языков:

–  –  –

В разделе 3.3. мы исследуем сложность задачи регулярной реализуемости для языков, входящих в основные рациональные конусы, приведённые на рисунке 3.1, которые являются подмножествами CFL. Там мы приводим их подробное описание. Среди этих конусов встречаются и неглавные, полученные стандартными конструкциями над рациональными конусами. Мы излагаем эти конструкции и приводим примеры неглавных конусов в разделе 3.3. для ясности изложения.

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

Главные конусы представляют интерес, поскольку они позволяют получать свойства для класса языков, опираясь на простые свойства генератора.

Некоторые структурные свойства просто следуют из главности конуса. Например, хорошо известно следующее свойство.

Утверждение 3.3 ([4]). Класс языков, образующий главный конус T (F ), замкнут относительно объединения.

Это свойство тривиально следует из факта замкнутости рациональных преобразований относительно объединения: для двух преобразователей T1 и T2 преобразователь T строится путём добавления переходов по пустому слову в начальные состояния преобразователей. Некоторые свойства, например, замкнутость класса относительно объединения и пересечения с регулярными языками, следуют из того, что класс является рациональным конусом (не обязательно главным).

Приведём примеры других свойств. Ниже мы полагаем, что фильтр F определён над алфавитом, символ # является разделителем и не входит в. Язык F обозначает копию языка F при некоторой однозначной замене букв алфавита на буквы алфавита язык F переходит в F, при этом алфавиты и не пересекаются.

Пример 3.2.

Если F #F или F · F rat F, то конус T (F ) замкнут rat F относительно операции конкатенации.

Пример 3.3.

Если (F #) rat F, то конус T (F ) замкнут относительно операции итерации.

Доказательство. Приведём доказательство только для первого случая конкатенации – доказательства остальных утверждений аналогичны этому. Зафиксируем преобразователи TA и TB, которые переводят F в языки A, B T (F ), соответственно. Построим преобразователь T, реализующий преобразование A·B rat F #F : получая на вход слово u#v, преобразователь T запус

–  –  –

Из теоремы Хомского-Шютценберже следует, что класс КС-языков является главным рациональным конусом. Из этого факта следует ряд свойств замкнутости для класса КС, а другие свойства замкнутости можно легко получить, опираясь на этот факт, – например, показать, что язык Дика D2 удовлетворяет свойствам, указанных в примерах 3.2 и 3.3. В работах [8; 9], опубликованных в 2014 году, была предложена новая модель вычислений – автомат со словарём (Set Automata) – конечный автомат со структурой данных множество. Авторы этой модели исследовали ряд структурных свойств для детерминированного класса автоматов со словарём – эта модель представляет интерес ввиду схожести с КС-языками по структурным свойствам и по свойствам разрешимости. В главе 4 мы показываем, что языки, распознаваемые недетерминированным автоматом со словарём, образуют главный рациональный конус – это и объясняет многие структурные свойства, полученные в работах [8; 9].

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

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

–  –  –

Доказательство. Пусть T – такой автоматный преобразователь, что F1 = T (F2 ), и пусть автомат A является входом задачи NRR(F1 ). Построим автомат B = T A, который будет входом задачи NRR(F2 ). Данное построение осуществимо на логарифмической памяти согласно утверждению 3.2.

В частности, отсюда следует, что если задача NRR(F ) полна в классе C, то для произвольного фильтра F из рационального конуса T (F ) задача NRR(F ) лежит в классе C.

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

Лемма 3.2.

Если F1 drat F2, то RR(F1 ) RR(F2 ).

log

–  –  –

Построение T# по T аналогично – необходимо только добавить к переходу (q, i) p слово, записываемое на выходную ленту.

Утверждение 3.4 объясняет, почему аналоги рациональных конусов для детерминированных автоматных преобразований не вызывают большого интереса: для совпадения главных конусов достаточно, чтобы для генератора F нашёлся детерминированный преобразователь T #, который переводит F в F#. Действительно, тогда для любого недетерминированного автоматного преобразователя T найдётся детерминированный T, такой что T (F ) = T (F ).

Построим по T преобразователь T# и получим, что T (F ) = T# (F# ), а далее, в силу замкнутости автоматных преобразователей относительно композиции, получаем T = T# T #. То есть если F автоматно накрывает F#, то языки, сводящиеся к F сводимостью drat, образуют рациональный конус T (F ). Детерминированность преобразователя в этом случае роли не играет.

Заметим, что утверждение 3.5 имеет ту же природу. Его можно пересказать так: если F автоматно накрывает F#, то NRR(F ) RR(F ), и задачи log детерминированной и недетерминированной регулярной реализуемости эквивалентны, т.к. обратную сводимость мы получаем бесплатно – за счёт того, что ДКА есть частный случай НКА.

Пример 3.4.

RR(D2 ) log NRR(D2 ).

Доказательство. Построим автоматное преобразование, которое переводит {#,# }, реализуемое детерминированным преобразователем язык D2 в D2

–  –  –

следующим образом. При обработке a, преобразователь T ожидает, что за a следует либо a, либо b a. Тогда T осуществляет замену, согласно правилам, bbb а в противном случае, T отвергает вход. Аналогично для b. За b либо следует b, тогда T запишет на выходную ленту b по обработке группы из двух b, либо aa тогда T запишет на выходную ленту # после обработки baa a ab, a ab.

Заметим, что каждое правильное скобочное выражение имеет прообраз:

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

–  –  –

Для всех известных случаев фильтров, имеющих сложность задачи регулярной реализуемости выше NL, оказывается, что задачи детерминированной и недетерминированной регулярной реализуемости эквивалентны по сложности. Где-то это можно легко показать, как в случае с D2, воспользовавшись утверждением 3.5, в других случаях (например, с периодическими фильтрами) доказательства не зависят от того, НКА или ДКА подан на вход задачи. Различия по модулю сложностных гипотез известны для регулярных языков (регулярные языки для детерминированной версии задачи задают либо L-полную, либо NL-полную задачу), мы исследуем этот вопрос в следующем разделе. Интересным открытым вопросом остаётся существование нерегулярного фильтра, для которого детерминированная и недетерминированная задача принадлежат разным классам сложности.

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

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

Утверждение 3.6. Пусть для языка F разрешима задача регулярной реализуемости, тогда для любого языка L T (F ) разрешима проверка на пустоту.

Доказательство. Для любого языка L T (F ) существует такой автоматный преобразователь T, что T (F ) = L. Рациональные преобразования обратимы, поэтому для T существует обратный автоматный преобразователь T 1. Применив его к языку, получаем регулярный язык T 1 ( ), который является входом задачи RR(F ). Ответ на вопрос задачи положителен тогда и только тогда, когда язык L не пуст.

Лемма 3.3.

Пусть семейство языков L образует главный рациональный конус T (F ), тогда разрешимость проверки на пустоту языка L L равносильна разрешимости задачи регулярной реализуемости.

Доказательство. Сводимость в условно-трудную сторону показана в утверждении 3.6. В обратную сторону утверждение очевидно. Из замкнутости рациональных конусов относительно пересечения с регулярными языками получаем, что для любого регулярного языка R выполнено F R T (F ).

Задача регулярной реализуемости RR(F ) сводится к задаче о проверке языка на пустоту естественным образом: по входу R задачи RR(F ) строим вход L = F R задачи проверки на пустоту.

Утверждение 3.7. Пусть F – генератор главного конуса T (F ). Тогда задача проверки принадлежности слова w языку L T (F ) сводится к задаче регулярной реализуемости специального вида.

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

Сводимость из утверждения 3.7 позволила классифицировать по сложности открытую в 2014 году модель вычислений – автомат со словарём. Этому посвящена глава 4.

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

При этом исследование самой задачи регулярной реализуемости приводит к интересному классу моделей вычислений – обобщённонедетерминированным автоматам, описанным выше.

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

В этом разделе мы исследуем детерминированную версию задачи регулярной реализуемости для регулярных фильтров. Мы докажем, что для каждого регулярного языка F выполняется одно из двух: либо задача регулярной реализуемости RR(F ) лежит в классе L, либо она NL-полна.

Эта классификация совпадает с хорошо известной классификацией регулярных языков на ограниченные и неограниченные. Напомним, что регулярный язык R называется ограниченным (bounded), если существуют такие слова w1, w2,... wn, что R w1 · w2 ·... · wn, в противном случае регулярный язык называется неограниченным.

В этом разделе под задачей регулярной реализуемости и автоматными преобразованиями мы понимаем детерминированные версии задачи и преобразований. Напомним, что на вход детерминированной задачи регулярной реализуемости подаётся всюду определённый ДКА, каждое состояние которого достижимо из начального. Также напомним, что детерминированные автоматные преобразования задают отношение drat. Если выполнено A drat B, то мы говорим, что язык A автоматно сводится к B, а язык B автоматно накрывает A.

При исследовании задачи регулярной реализуемости для ограниченных языков нам будет удобнее рассматривать не сам ограниченный язык R, а содержащий его язык w1 w2... wn.

–  –  –

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

Из определения неограниченного языка следует Утверждение 3.9. Любой неограниченный регулярный язык имеет регулярное подмножество вида p(u|v) s, где u и v различные непустые слова, а p и s некоторые (возможно пустые) слова.

–  –  –

и это объединение является ограниченным языком. Заменим в графе автомата все простые циклы на петли, на которых написано слово ui, соответствующее обходу простого цикла; каждому простому пути v1 v2... vn из начального состояния в некоторое принимающее соответствует регулярное выражение вида 3.1, а всего таких путей конечное число. Конечное объединение языков вида 3.1 является ограниченным языком: объединеi Ri <

–  –  –

L(A). В другую сторону – каждое слово, принимаемое автоматом A, лежит на некотором пути из начального состояния в принимающее, а значит и принадлежит некоторому языку Ri.

В случае если каждый автомат, распознающий регулярный язык L, имеет вершинно-пересекающиеся простые циклы, то в автомате, все состояния которого достижимы, и при этом из каждого состояния достижимо принимающее, такие циклы встречаются на некотором пути из начального состояния в принимающее, а значит L содержит подмножество вида p(u|v) s, u = v.

Покажем, что классификация языков на ограниченные и неограниченные согласована с (детерминированными) автоматными преобразованиями: ограниченные языки замкнуты относительно автоматных преобразований. Для этого сначала покажем, что любой неограниченный язык R автоматно накрывает язык всех слов: затем мы покажем, что ни один ограниdrat R;

ченный язык не накрывает язык всех слов.

Утверждение 3.10. Любой неограниченный язык R автоматно накрывает язык всех слов.

Доказательство. По утверждению 3.9, из условия неограниченности регулярного языка R следует, что R содержит подмножество p(u|v) s, u = v.

Автоматный преобразователь T зададим следующим образом. В случае, если на вход преобразователя было подано слово не из языка p(u|v) s, преобразователь отвергает вход. Преобразователь T считывает префикс p, далее при считывании слова u пишет a, а при считывании слова v пишет b, в случае прочтения s, автоматный преобразователь переходит в принимающее состояние. В случае, если s совпадает с u или v, преобразователь пишет соответствующую букву, только если после s на входе оказалась некоторая буква.

Очевидно, что преобразователь T переводит множество p(u|v) s в язык всех слов, а значит он также переводит неограниченный язык R, содержащий данное подмножество в язык всех слов.

Замечание 3.1. Поскольку автоматно накрывает любой регулярный язык (см. пример 3.1), то любой неограниченный язык автоматно накрывает любой регулярный по транзитивности.

Утверждение 3.11. Любой ограниченный язык не накрывает автоматно язык всех слов.

–  –  –

вает. Докажем, что это невозможно.

Заметим сначала, что, обрабатывая из любого состояния достаточно длинные слова вида w, автоматный преобразователь пишет на выходную ленту слова из языка pv S, где p, v – некоторые, возможно пустые, слова, а S – некоторое конечное множество слов. Поскольку преобразователь T содержит лишь конечное число состояний, то при большом m в процессе чтения wm преобразователь T окажется дважды в одном и том же состоянии после чтения wk и wk+l, а значит на выходной ленте окажется слово указанного вида

– префикс и итерируемая часть будут одинаковыми для всех длинных слов вида wm, а их суффиксы, являющиеся префиксами v, могут отличаться.

Докажем теперь, что язык w1 w2... wn не накрывает автоматно язык всех слов. Действительно, выберем минимальное число m, такое, что для каждо

–  –  –

содержит в качестве подслова одно из фиксированных непустых слов vi,q. Но при этом существуют слова, которые не содержат в качестве подслова ни одно из указанных слов. В качестве примера подходят начальные отрезки последовательности Туэ-Морса: хорошо известно [37], что в ней не встречается ни одно слово u3 в качестве подслова.

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

Следствие 3.1. Класс ограниченных регулярных языков замкнут относительно детерминированных автоматных преобразований.

Мы переходим к доказательству основной теоремы раздела.

Теорема 3.1. Для каждого регулярного языка F выполняется одно из двух:

если язык F является ограниченным, задача регулярной реализуемости RR(F ) лежит в классе L, если же язык F является неограниченным, задача полна в классе NL.

Теорема естественным образом разбивается на следующие вспомогательные утверждения.

Утверждение 3.12. Задача регулярной реализуемости RR( ) полна в классе NL при || 2.

Доказательство. К задаче RR( ) очевидным образом сводится задача достижимости из вершины s вершины t в ориентированном графе G. Для каждой вершины u закодируем рёбра, исходящие из u, префиксным кодом. Таким образом, в корне дерева префиксного кода, соответствующего u, находится u, а в листьях находятся все такие вершины v, что в G есть ребро (u, v).

Построим ДКА A, состояниями которого будут вершины G, а также узлы деревьев префиксного кода для каждой вершины. Переходы в A определим естественным образом: внутри префиксного кода переходы автомата совпадают с размеченными рёбрами дерева кода. Заметим, что автомат A детерминированный. Начальным состоянием A будет вершина s, а принимающим

– вершина t.

Данная сводимость очевидно осуществима на логарифмической памяти.

Таким образом, мы показали, что задача RR( ) является NL-трудной.

Но сама задача RR( ) очевидным образом сводится к задаче достижимости:

графом G является граф автомата A, а вершинами (s, t) являются пары (q0, qf ), где q0 – начальное состояние, а qf – принимающее. Поэтому задача RR( ) лежит в NL, а значит она NL-полна.

Лемма 3.4.

Задача регулярной реализуемости RR(F ) для неограниченного языка F является NL-полной.

Доказательство. Задача RR( ) является NL-полной по утверждению 3.12.

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

к. язык автоматно накрывает любой регулярный язык. С другой стороны, по утверждению 3.10, получаем, что RR( ) RR(F ) для любого неограниченного log языка F. Следовательно, задача регулярной реализуемости RR(F ) является NL-полной для любого неограниченного языка F.

Лемма 3.5.

Задача реализуемости RR(F ) для ограниченного языка F лежит в классе L.

–  –  –

что RR(F ) L.

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

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

Мы переходим от регулярных языков к общему случаю КС-языков. Для согласованности с хорошо исследованным отношением рационального доминирования мы переходим к рассмотрению недетерминированной версии задачи регулярной реализуемости NRR. Как мы уже отмечали на рисунке 3.1, для всех генераторов хорошо известных рациональных конусов, вложенных в КС-языки, задача регулярной реализуемости лежит в классе NL. Мы называем такие языки, для которых задача NRR лежит в NL, лёгкими. В то же время, сложность задачи для КС-языков ограничена классом P. Языки, для которых задача недетерминированной регулярной реализуемости P-полна, мы называем трудными.

Самым простым примером являются регулярные языки. Для любого непустого регулярного языка R задача NRR(R) является NL полной: поскольку НКА может содержать -переходы, то задача достижимости в ориентированном графе сводится к задаче NRR(R) путём маркировки рёбер графа и добавлением пути по некоторому слову из R в принимающее состояние из искомой вершины.

Перейдём теперь к нетривиальным подконусам. Конус линейных языков LIN является главным конусом, порождённым симметрическим языком 2, над размеченным алфавитом Sn = S a1 S1 + · · · + an Sn +, n a a n = {a1, a2,..., an } {1, a2,... an }. Заметим, что симметрический язык S a схож с языком палиндромов PAL: если убрать пометки с букв в словах S, получится язык, состоящий из палиндромов чётной длины; при этом в словах S помечены все буквы второй половины каждого слова.

Доказательство того, что язык S является лёгким, аналогично доказательству следующей теоремы.

Теорема (Anderson, Loftus, Rampersad, Santean, Shallit, [16]).

–  –  –

До этого мы имели дело только с главными рациональными конусами – конусами, порождёнными некоторым языком-генератором. Однако, в теории КС-языков также играют важную роль некоторые неглавные рациональные конусы.

Мы будем строить их с помощью операции подстановки. Детально операции подстановки описаны в разделе 1.1. Напомним, что подстановка – это отображение : 2, то есть символу алфавита a сопоставлен язык La.

Тогда образ (L) языка L определяется естественным образом как множество таких слов, которые могут быть получены заменой каждого символа a на какое-то слово из языка La. Эта операция переносится на семейства языков. Напомним, что M -подстановка – это подстановка вида : 2, такая что a : (a) M. Поскольку языки из одного семейства могут быть определены над разными алфавитами, мы обозначаем L алфавит языка L.

Определение 3.1. Следующая операция определяет класс, получаемый подстановкой языков семейства M в языки класса L :

L M = {(L) | L L, : L 2 – M -подстановка}.

Эта операция сохраняет свойства рациональных конусов.

Теорема ([6]). Если L и M рациональные конусы, то и L M тоже рациональный конус. Более того, если L и M главные конусы, то L M также главный конус.

На основе рационального конуса LIN строится семейство квазирациональных языков QRT. Определим его индуктивно: QRT(1) = LIN; QRT(k) = QRT(k). При этом известно ([4]), что QRT(k) LIN QRT(k 1); QRT = k=1 QRT(k +1). Из теоремы о подстановках следует, что для каждого k семейство QRT(k) является главным рациональным конусом. Семейство QRT является рациональным конусом, поскольку любое объединение рациональных конусов является рациональным конусом.

Семейство квазирациональных языков имеет естественное описание: это КС-языки, описываемые нерасширяющими грамматиками.

Определение 3.2 ([5]). Нетерминал A КС-грамматики, для которого существует вывод A AA, называют расширяющим. КС-грамматику, не = содержащую расширяющих нетерминалов, называют нерасширяющей.

Определим рациональный конус T (L ) как минимальный по включению конус, который содержит семейство L и при этом замкнут относительно операции подстановки: T (L ) T (L ) = T (L ). Очевидно, что QRT = T (LIN). Следующая лемма показывает, что QRT не является главным конусом.

Лемма 3.7 ([6]).

Либо рациональный конус L замкнут относительно подстановки, либо конус T (L ) не является главным.

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

Лемма 3.8.

Если языки L и La, a L, являются лёгкими, тогда и язык (L) также является лёгким.

–  –  –

Перейдём теперь к анализу рациональных конусов с другой половины рисунка 3.1. Конус ROCL является главным конусом, порождённым языком

Дика D1 с одним типом скобок. У этого конуса есть естественное описание:

этому конусу принадлежат языки, распознаваемые автоматами со счётчиком, которые не могут проверить равенство счётчика нулю. Формально, автоматом со счётчиком называют МП-автомат, в алфавите стека которого всего один символ, допускающий слово одновременно по принимающему состоянию и пустому стеку.

Лемма 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... wk wj+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 можно укоротить, заменив в нём отрезок wli... wri на отрезок wlj... wrj. Таким образом, для любого i последовательность вложенных отрезков wli... wri, wli+1... wri+1,..., wlk... wrk имеет не более n2 элементов, а значит значение счётчика не превосходит n2, в том числе и для i = 0. Заметим, что из достижения автоматом со счётчиком на некотором пути вычисления значения счётчика j следует наличие отрезка wlj... wrj, поскольку на концах слова счётчик принимает значение 0.

А раз значение счётчика на w не может превосходить n2, то длина w не превосходит n3. Рассмотрим НКА A, в котором все состояния имеют вид (q, i) иi n2, а переходы согласованы с таблицей переходов МП-автомата M.

Таким образом, в графе автомата A есть путь из начального состояния в принимающее, а самый короткий путь линеен по числу состояний, число которых n3.

Доказательство леммы 3.9. Пусть M – автомат со счётчиком, допускающий по принимающему состоянию, причём автомат M распознаёт язык Lc. Пусть A – автомат на входе задачи регулярной реализуемости.

Построим автомат со счётчиком MA, распознающий язык L(M ) L(A) = Lc L(A), стандартной конструкцией произведения: автомат имеет множество состояний QM QA, начальное состояние (q0, q0 ), множество принимаMA ющих состояний FM FA и отношение переходов MA, причём M (q,, z) (q, z ), A (p, ) = p влечёт MA ((q, p),, z) ((q, p ), z ).

Таким образом, автомат MA является автоматом со счётчиком с |QM | · |QA | = c n состояниями. По лемме 3.10 получаем, что значение счётчика автомата MA не превосходит (cn)2 при работе на самом коротком принимаемом слове. Построим теперь такой НКА B, что язык L(B) включает в себя все слова из L(MA ), на которых счётчик автомата MA не превышает (cn)2.

Автомат B имеет O(n3 ) состояний, и его построение выполнимо на логарифмической памяти естественным образом. Схожая конструкция приведена далее в доказательстве утверждения 3.14. Отметим, что L(MA ) = тогда и только тогда, когда L(B) =. Таким образом, отображение A B является сводимостью задачи NRR(Lc ) к задаче NRR( ), которая лежит в классе NL.

Очевидно, что язык Дика D1 распознаётся автоматом со счётчиком. Таким образом мы получаем следствие.

Следствие 3.2. NRR(D1 ) NL.

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

Таким образом, доказав леммы 3.6, 3.8 и следствие 3.2, мы доказали основной результат данного раздела.

Теорема 3.2.

Пусть язык F является языком Грейбах. Тогда задача NRR(F ) лежит в классе NL.

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

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

Первым примером трудного КС-языка будет язык Дика D2.

Используя лемму 3.1 и теорему Хомского-Шютценберже, мы получим, что любой генератор конуса КС-языков является трудным языком. Как показано ниже, генераторами конуса CFL трудные языки не исчерпываются.

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

Лемма 3.11.

Пусть G = (N,, P, S) фиксированная КС-грамматика. Тогда существует алгоритм на логарифмической памяти, который получает на вход описание НКА A = (QA,, A, q0, FA ) и строит грамматику G = (N,, P, S ), порождающую язык L(G) L(A). Данная грамматика имеет полиномиальный по |QA | размер.

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

Доказательство. Для простоты предположим сначала, что автомат A не имеет -переходов. Пусть множество нетерминалов N состоит из аксиомы S и нетерминалов вида [qAp], где A N и q, p QA. Построим множество правил P путём добавления для каждого правила A X1 X2... Xn из P множества правил

–  –  –

в P. Также добавим в множество P правила [qp], если p A (q, ), и S [q0 Sqf ] для каждого состояния qf из FA.

Докажем теперь, что L(G ) = L(G) L(A). Пусть грамматика G порождает слово w = w1 w2... wn. Тогда грамматика G порождает все возможные сентенциальные формы

–  –  –

где qf FA и ri QA. Вывод [q0 w1 r1 ][r1 w2 r2 ]... [rn1 wn qf ] w1 w2... wn реализуется тогда и только тогда, когда автомат A принимает слово w, то есть когда по w существует последовательность переходов из начального состояния в принимающее. Эта последовательность и закодирована в приведённой выше сентенциальной форме. Таким образом, если слово w порождается грамматикой G и принимается автоматом A, то оно порождается и грамматикой G.

Обратно, если грамматика G порождает слово w, тогда каждый символ wi порождён из некоторого нетерминала [qwi p]. По построению грамматики G, слово w было выведено из некоторой сентенциальной формы вида [q0 w1 r1 ][r1 w2 r2 ]... [rn1 wn qf ], которая кодирует последовательность переходов автомата A из начального состояния в принимающее при чтении слова w. Таким образом, если грамматика G породила слово, то оно принимается автоматом A. Ясно также, что грамматика G порождает только те слова, которые порождает грамматика G. Таким образом, L(G ) = L(G) L(A).

Грамматика G имеет полиномиальный по |QA | размер. Множество нетерминалов N имеет размер O(|N |·|QA |2 ). Пусть k – длина самого длинного правила из P. Тогда для каждого правила из P построено не более чем |QA |k+1 соответствующих правил в P, а для правил вида [qp] или S [q0 Sqf ] построено не более чем O(|QA |2 ) правил.

Поэтому построение грамматики G осуществимо на логарифмической памяти: множество правил P разбивается на подмножества, соответствующие правилам из P, которые строятся перебором всевозможных наборов из (k+1)го состояния автомата A, где k = O(1).

Добавление -переходов лишь увеличивает константу k + 1 до 2k. Для каждого правила A X1... Xn добавим правила

–  –  –

Также нам потребуется алгоритмическая версия теоремы ХомскогоШютценберже.

Лемма 3.12.

Существует алгоритм на логарифмической памяти, который получает на вход описание КС-грамматики G = (N,, P, S) и строит такой автоматный преобразователь T, что T (D2 ) = L(G).

Доказательство этого утверждения легко получается из подходящих доказательств теоремы Хомского-Шютценберже. Например, конструкции из доказательства в книге [4, Th II.3.10] реализуются на логарифмической памяти очевидным образом (заметим, что любой морфизм реализуется автоматным преобразователем).

Из лемм 3.11 и 3.

12 легко следует P-трудность языка Дика D2.

Теорема 3.3.

Задача NRR(D2 ) является P-полной.

Доказательство. Сведём известную P-полную проблему проверки пустоты языка, порождённого КС-грамматикой [39], к NRR(D2 ).

Построим по грамматике G такой автоматный преобразователь T, что T (D2 ) = L(G), используя конструкцию из леммы 3.12.

Пусть A – недетерминированный автомат, полученный из автоматного преобразователя T игнорированием выходной ленты. Пересечение L(A) D2 непусто тогда и только тогда, когда непуст язык L(G). Отображение G A и есть искомая сводимость.

Осталось доказать, что задача NRR(D2 ) лежит в классе P.

Сведём эту задачу к задаче о проверке непустоты языка, порождаемого КС-грамматикой:

по автомату A на входе построим такую грамматику G, что L(G) = L(A) D2, используя лемму 3.11.

Следствие 3.3. Любой генератор рационального конуса CFL является трудным языком.

Приведём пример трудного языка, отличного от генератора CFL. Боассон в [40] доказал, что существует главный рациональный конус, не совпадающий

–  –  –

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

Определение 3.3. Синтаксической подстановкой языка M в язык L, заданных над непересекающимися алфавитами M и L, соответственно, называется язык L M в алфавите M L, состоящий из слов вида m1 x1 m2 x2... mn xn, где xi L, mi M, x1 ·... · xn L.

Обозначим S# = S #.

Пусть M = aS# a. Определим рекурсивно язык M () следующим образом:

w M () тогда и только тогда, когда либо w M, либо

–  –  –

Назовём высотой позиции разность между числом символов из n и из n, стоящих перед этой позицией. В этих терминах слова из языка D определяются двумя условиями: высота любой позиции неотрицательна и высота итоговой позиции равна нулю.

Утверждение 3.13. Пусть НКА A удовлетворяет условию D2 L(A) =.

Тогда существует такое слово w D2 L(A) =, что высота любой позиции w есть O(|QA |)2.

Доказательство. Высота позиций ограничена сверху высотой дерева вывода в грамматике, порождающей язык D2 L(A), который не пуст.

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

Грамматика, построенная конструкцией из леммы 3.11, имеет O(|QA |2 ) нетерминалов, если использовать грамматику в нормальной форме Хомского, порождающую язык D2, что и завершает доказательство.

–  –  –

маркированного автомата A = µ(A), такого что

• L(A) D2 = L(A ) D2 = ;

• для любого слова w L(A ) высота любой позиции неотрицательна и высота итоговой позиции 0.

Преобразование µ вычислимо на логарифмической памяти.

Замечание 3.3. Поскольку высота есть разность между числом открывающих и закрывающих скобок обоих типов, то язык L(A ) не обязательно является подмножеством языка D2.

–  –  –

Из w L(B) следует u L(A ). По построению автомата A, высота позиций в слове u неотрицательна, и высота итоговой позиции равна 0. Из вида морфизма (3.3) ясно, что то же самое справедливо и для слова w. Следовательно, w M (+) = A (A \ D), т.е. A (w) D. Скобки в правильном / скобочном выражении разбиваются на соответственные пары.

Возьмём пару соответственных скобок a, a в слове w:

w = w0 axi w1 xj aw2.

По определению языка M (), после удаления из подслова w1 всех подслов вида az от слова axi w1 xj a останется слово axi vj a из языка M. То есть, a x xi vj S#, так что i = j.

x Отсюда следует, что u D2 L(A ).

Итак, мы доказали корректность сводимости. Теперь перейдём к алгоритмической сложности. Автомат B = T A строится на логарифмической памяти в силу утверждения 3.2. Автомат B отличается от B препроцессинговыми и постпроцессинговыми состояниями для обработки префикса ax1 x2

–  –  –

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

Рациональный индекс L (n) языка L – это функция, которая возвращает максимальную (по автоматам с n состояниями) длину кратчайшего слова из пересечения языка L с языком L(A), распознаваемым недетерминированным автоматом A с n состояниями, при условии, что L(A) L = :

(3.4) min{|u| | u L(A) L}.

L (n) = max A:|QA |=n, L(A)L= Рациональный индекс был введен в работе [41]. Он оказался довольно полезной характеристикой КС-языков, потому что рациональный индекс не увеличивается значительно при автоматных преобразованиях.

Заметим, что рациональный индекс генератора конуса CFL имеет достаточно точную оценку.

Теорема (Pierre, 1992, [42]). Рациональный индекс любого генератора конуса CFL лежит в exp((n2 / log n)).

Языки (не обязательно КС) с полиномиально ограниченным рациональным индексом представляют интерес. Они образуют рациональный конус POL, который обладает хорошими свойствами – этот конус замкнут относительно подстановок и является полным AFL конусом [41].

Поскольку рациональные конусы замкнуты относительно пересечения, существует конус CFL POL КС-языков с полиномиально ограниченным рациональным индексом. Известно [41], что языки Грейбах являются подмножеством CFL POL, а посему все основные конусы из раздела 3.3. имеют полиномиальный рациональный индекс.

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

В пользу этой гипотезы есть аргументы.

Например, КС-языки с рациональным индексом (n ) для любого положительного алгебраического числа 1 были предложены в работе [43]. Все эти языки построены из линейных языков путём специфической подстановки.

Поэтому по лемме 3.8 все они являются лёгкими.

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

Теорема 3.5.

Пусть F – контекстно-свободный фильтр с полиномиально ограниченным рациональным индексом. Тогда задача NRR(F ) лежит в классе NSPACE(log2 n).

Мы используем технику, близкую к технике из работы [44]. Нам потребуется вспомогательный результат.



Pages:   || 2 |
Похожие работы:

«Содержание 1 Область применения 3 2 Нормативные ссылки 7 3 Характеристики основных применяемых материалов и изделий 10 4 Организация и технология производства работ 13 5 Потребность в материально-технических ресурсах 27 6 Контроль качества и...»

«150 УДК 66.011.001.57 МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СТАДИИ ФРАКЦИОНИРОВАНИЯ РЕАКЦИОННО-РЕКТИФИКАЦИОННОГО ПРОЦЕССА ПРОИЗВОДСТВА ЭТИЛЕНГЛИКОЛЯ Самойлов Н.А. Уфимский государственный нефтяной технический университет, г. Уфа e-mail: naum.samoilow@yandex.ru Мнушкин И.А. ООО "Петон", г. Уфа Аннота...»

«УТВЕРЖДАЮ Генеральный директор ООО Инвестиционная палата В.В. Кузьмин 15 июля 2010 года (приказ № 86-В от 15.07.2010 г.) РЕГЛАМЕНТ обслуживания клиентов на рынке ценных бумаг и срочном рынке ООО "Инвестиционная палата" (...»

«42 1820 Код продукции Код ТН ВЭД МОДУЛЬ ВВОДА СИГНАЛОВ NAMUR МВСН-Ех РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ ЦКЛГ.426433.011 РЭ ЗАО НПП Центравтоматика г. Воронеж МВСН-Ех ЦКЛГ.426433.011 РЭ изм. 1 СОДЕРЖАНИЕ ВВЕДЕНИЕ...3 НАЗНАЧЕНИЕ ТЕХНИЧЕСКИЕ 2 ХАРАКТЕРИСТИКИ СОСТАВ 3 ИЗДЕЛИЯ УСТРОЙСТВО 4 И РА...»

«№ 1 (37), 2016 Технические науки. Машиностроение и машиноведение УДК 621.787:539.319 А. М. Смыслов, М. К. Смыслова, А. И. Дубин, В. П. Сазанов, В. Ф. Павлов ИССЛЕДОВАНИЕ ВЛИЯНИЯ ОСТАТОЧНЫХ НАПРЯЖЕНИЙ НА СОПРОТИВЛЕ...»

«ПАСПОРТ № от " 2015 г. " Наименование: Биопирен ® (антипирен-антисептик) "Пирилакс ® " Prime ТУ 2499-027-24505934-05 (ОКП 249990) Производится правообладателем ООО "НПО НОРТ" в г. Ижевске, Удмурт ская Республика С...»

«УДК 669.017:620.197 ВЛИЯНИЕ ЛАНТАНА НА АНОДНОЕ ПОВЕДЕНИЕ СПЛАВА AI + 6 % Li Назаров Ш.А1., Ганиев И.Н1., Норова М.Т1., Ганиева Н.И1. Irene Calliari2 Институт химии им. В.И. Никитина АН Республики...»

«Структура программы учебного предмета I. Пояснительная записка Характеристика учебного предмета, его место и роль в образовательном процессе;Срок реализации учебного предмета;Объем учебного времени, предусмотренный учебным планом образовательного учреждени...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ НАЦИОНАЛЬНЫЙ ГОСТ Р (проект, окончательная СТАНДАРТ редакция) РОССИЙСКОЙ ФЕДЕРАЦИИ СЖИЖЕННЫЙ ПРИРОДНЫЙ ГАЗ Отбор проб Настоящий проект стандарта не подлежит применению до его утверждения Москва Стандартинформ ГОСТ Р, проект,...»

«ГЛАВА АДМИНИСТРАЦИИ КУЛОМЗИНСКОГО СЕЛЬСКОГО ПОСЕЛЕНИЯ ОКОНЕШНИКОВСКОГО МУНИЦИПАЛЬНОГО РАЙОНА ОМСКОЙ ОБЛАСТИ ПОСТАНОВЛЕНИЕ от 6 мая 2016 года № 22п Об установлении Правил определения нормативных затра...»

«ХАЛЫАРАЛЫ БІЛІМ БЕРУ КОРПОРАЦИЯСЫ МЕЖДУНАРОДНАЯ ОБРАЗОВАТЕЛЬНАЯ КОРПОРАЦИЯ INTERNATIONAL EDUCATIONAL CORPORATION АО "МОК" создано 18 января 2007 года (свидетельство о государственной регистрации № 98672-1910-АО от 02.07.2009 г.).Акционеры:...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНОСТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ Кафедра водоснабжения и водоотведения ИССЛЕДОВАНИЕ ТРАНСФОРМАТОРНЫХ ПРЕОБРАЗОВАТЕЛЕ...»

«VIII Всероссийская конференция с международным участием "Горение твердого топлива" Институт теплофизики им. С.С. Кутателадзе СО РАН, 13–16 ноября 2012 г. УДК 661.862.222:662.7 ИСПОЛЬЗОВАНИЕ ВТОРИЧНЫХ РЕСУРСОВ (ОТХОДОВ УГЛЕОБОГАЩЕНИЯ) ДЛЯ СЖИГАНИЯ В ТОПКАХ...»

«СОВРЕМЕННОЕ СОСТОЯНИЕ И МЕХАНИЗМЫ РЕАЛИЗАЦИИ СИСТЕМЫ КВАЛИФИКАЦИЙ В РЕСПУБЛИКЕ БЕЛАРУСЬ Июнь 2015 г. Обзор подготовили эксперты Арьен Дей и Родион Колышко ПРОЕКТ ДОКЛАДА ДЛЯ ОБСУЖДЕНИЯ БУДЕТ ЗАВЕРШЕН ПОСЛЕ СЕМИНАРА 2 СОДЕРЖАНИЕ Введение Список сокращений 1. Квалификации и...»

«Научно-техническая библиотека Статьи и Публикации http://www.sciteclibrary.ru/rus/catalog/arts/ ЭЛЕКТРОДИНАМИЧЕСКИЕ СИЛЫ НИКОЛАЕВА © Воронков С.С. доцент, к.т.н Контакт с автором: vorss60@yandex.ru Аннотация Рассматриваются новые электродинамические...»

«Тютюкин С.В.1 РОССИЯ, 1905-й. //Свободная мысль,1995, №5 Близится к концу XX, едва ли не самое парадоксальное и противоречивое по своим результатам столетие человеческой истории. Век разума и безумия, фантастического научно-технического прогр...»

«Открытые информационные и компьютерные интегрированные технологии № 47, 2010 УДК 629.735.23:620.22 Е.Т. Василевский, А.З. Двейрин, Я.С. Карпов, С.П. Кривенда Система экспериментального обеспечения расчета на прочность механических соединений деталей из композитов Государ...»

«"Ученые заметки ТОГУ" Том 7, № 3, 2016 ISSN 2079-8490 Электронное научное издание "Ученые заметки ТОГУ" 2016, Том 7, № 3, С. 164 – 169 Свидетельство Эл № ФС 77-39676 от 05.05.2010 http://pnu.edu.ru/ru/ejournal/about/ ejournal@pnu.edu.ru УДК: 68...»

«ТЕПЛОВЫЧИСЛИТЕЛЬ ВЗЛЕТ ТСРВ ИСПОЛНЕНИЕ ТСРВ-043 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ Часть I В84.00-00.00 РЭ Россия, Санкт-Петербург В84.00-00.00-43 Система менеджмента качества АО "Взлет" сертифициров...»

«® Цветной принтер Xerox Color C60/C70 Руководство пользователя © Xerox Corporation, 2016 г. Все права защищены. XEROX® и XEROX и фигуративный знак Design® являются товарными знаками корпорации Xer...»

«Извещение о проведении закупки (в редакции № 1 от 07.12.2016 ) Номер извещения: 31604448918 Наименование закупки: Реконструкция платформ: о.п. Виноградово – платформа №2, о.п. Алабино – платформа №2 Московской железной дороги – филиала ОАО...»

«ТЕХНИЧЕСКОЕ ОПИСАНИЕ КОМПЕТЕНЦИЯ "Холодильная техника и системы кондиционирования воздуха" Организация WorldSkills Russia (WSR) с согласия технического комитета в соответствии с уставом организации и правилами проведения конкурсов установила нижеизложенные минимально необходимые требов...»

«Руководство по эксплуатации ГЖИК.641200.134РЭ ВЫСОКОВОЛЬТНЫЕ РАЗЪЕДИНИТЕЛИ ВНУТРЕННЕЙ УСТАНОВКИ ТИПА РВ, РВО, РВЗ, РВФЗ СОВМЕСТНО С ПРИВОДОМ ПР-10 И ЗАЗЕМЛИТЕЛИ ТИПА ЗР Россия, 305000, г. Курск, ул. Луначарского, 8 Настоящее руководство по эксплуатации предназначено для ознакомления потребителей с техническими...»

«Анналы хирургической гепатологии. 1997. Т. 2 С. 32-35 Новые технологии при резекциях печени В. И. Булынин, Статья посвящена проблемам резекции печени и поиску путей, способствуют: А. А. Глухов, улучшению результатов хирургического лечения больных с очаговыми...»

«Я.И. Тульку БИРЖЕВЫЕ МЕХАНИЗМЫ КОММЕРЦИАЛИЗАЦИИ ИННОВАЦИЙ В УСЛОВИЯХ НЕЭФФЕКТИВНОЙ СИСТЕМЫ ЗАЩИТЫ ПРАВ ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ Как отмечается в "Руководстве Осло" (Рекомендации по сбору и анализу данных по инновация...»

«ТЕПЛОВЫЕ РЕЖИМЫ И НАДЕЖНОСТЬ ПРИБОРОВ И СИСТЕМ УДК 536.2.08:536.082.62:536.082.64:53.087.45 DOI: 10.17586/0021-3454-2016-59-7-578-583 ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОЙ ТЕПЛОПРОВОДНОСТИ БАЗАЛЬТО-АРМИР...»

«Каталог технических систем Воздушное охлаждение 2 Каталог технических систем Rittal/Воздушное охлаждение Воздушное охлаждение Даже при очевидно некритичных условиях окружающей среды, например, при чистом и достаточно холодном воздухе, имеет смысл осуществлять кон...»

«Ускенбаева Р.К., Калижанова А.У.,Козбакова А.Х. Казахский национальный технический университет имени К.И.Сатпаева, г.Алматы, Казахстан ПРИКЛАДНЫЕ ЗАДАЧИФУНКЦИОНАЛЬНОСТИ РАСПРЕДЕЛЕННОЙ КОМПЬЮТЕР...»

«ЕЖЕНЕДЕЛЬНЫЙ АНАЛИТИЧЕСКИЙ ОБЗОР МИРОВЫЕ ФОНДОВЫЕ РЫНКИ И МАКРОЭКОНОМИЧЕСКАЯ КОНЪЮНКТУРА (09.08.2010 – 13.08.2010) _ Руководитель аналитического отдела Абелев Олег Александрович Аналитик Мосина Ирина Олеговна (499) 241-53-07, 241-52-85 доб. 259, 161 РИКОМ ТРАСТ 2 СОДЕРЖАНИЕ: 1. Общий взгляд на рынок.. 3 2. Росси...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.