Содержание к диссертации
Введение
1 Перезапись регулярных путевых запросов и полугруппы регулярных языков 11
1.1 Вычисление запросов с использованием представлений 11
1.1.1 Базы данных, запросы, представления 11
1.1.2 Области применения перезаписей запросов 17
1.2 Перезапись регулярных путевых запросов 19
1.2.1 Основные понятия и обозначения 20
1.2.2 Модель полуструктурированных данных 21
1.2.3 Максимальная перезапись запросов 23
1.2.4 Частичная перезапись запросов 24
1.2.5 Однословная перезапись запросов 25
1.3 Применение алгоритмических методов алгебры в задачах перезаписи запросов 26
1.3.1 Перезапись запросов как задача принадлежности для полугруппы регулярных языков 27
1.3.2 Поиск перезаписи с дополнительными ограничениями 28
1.3.3 Применение задачи равенства слов при перезаписи запросов 28
1.3.4 Оценка выразительной силы набора представлений 29
1.4 Полугруппы с эффективно решаемой задачей равенства слов 30
1.4.1 Автоматные полугруппы 31
1.4.2 Рациональные полугруппы 31
1.4.3 Полугруппы Клини 33
1.5 Выводы 34
2 Рациональные множества регулярных языков 36
2.1 Принадлежность полугруппе и рациональному множеству 36
2.1.1 Принадлежность рациональному множеству 37
2.1.2 Анализ сложности алгоритма проверки принадлежности рациональному множеству 42
2.2 Ядро полугруппы или класс эквивалентности 44
2.2.1 Регулярность класса эквивалентности полугруппы 44
2.2.2 Алгоритм построения класса эквивалентности 45
2.2.3 Оптимальная перезапись запроса 46
2.3 Конечность полугруппы и рационального множества 50
2.3.1 Конечность полугруппы 51
2.3.2 Конечность рационального множества 54
2.3.3 Анализ сложности алгоритма проверки конечности рационального множества 56
2.4 Эквивалентность полугрупп и рациональных множеств 56
2.4.1 Алгоритм проверки вложенности полугрупп 57
2.4.2 Неразрешимость задачи эквивалентности рациональных множеств . 57
2.5 Выводы 58
3 Задача равенства слов для полугрупп регулярных языков 60
3.1 К автоматности полугрупп регулярных языков 60
3.1.1 Автоматность рациональных полугрупп 62
3.1.2 Нерациональность конечно порожденной полугруппы регулярных языков 64
3.2 Случай однобуквенного алфавита 65
3.2.1 Строение полугрупп в случае конечных порождающих элементов . 66
3.2.2 Строение полугрупп в случае произвольных порождающих элементов, содержащих пустое слово 77
3.2.3 Автоматность полугрупп регулярных языков 90
3.2.4 Клиновость, рациональность полугрупп регулярных языков 101
3.3 Выводы 107
4 Реализация и тестирование алгоритмов 108
4.1 Реализованные алгоритмы 108
4.1.1 Подсистема вычисления запроса 108
4.1.2 Построение максимальной перезаписи 110
4.1.3 Построение однословной перезаписи 111
4.2 Эксперименты с перезаписью 113
4.2.1 К задаче равенства слов 113
4.2.2 К константе Хашигучи 115
4.3 Выводы 121
Заключение 123
Приложения 124
Литература 130
- Применение алгоритмических методов алгебры в задачах перезаписи запросов
- Полугруппы с эффективно решаемой задачей равенства слов
- Анализ сложности алгоритма проверки принадлежности рациональному множеству
- Строение полугрупп в случае произвольных порождающих элементов, содержащих пустое слово
Введение к работе
Актуальность темы
Современное общество, которое принято именовать информационным, характеризуется тем, что эффективные технологии обработки данных во многом определяют успехи в области материального производства, в научно-технической, социально-зкономичесісой и в политической сферах деятельности человека. В условиях быстрого развития сетевой инфраструктуры и объемов, сосредоточенных в ней данных, методы их поиска, систематизации и анализа на сегодня отстают от возрастающих еще более высокими темпами потребностей общества. Одна из причин сложностей, возникающих на пути их удовлетворения, связана с существенно неоднородным характером подлежащей обработке информации, как с позиции поддерживающей ее аппаратно-программной платформы, так и в плане модели представления этих данных. На сегодня сложно представить себе случай, когда интересующие пользователя практически значимые данные могут находиться под управлением традиционной реляционной СУБД, какой либо другой модели их описания (модели данных) или системы. Для того, чтобы удовлетворять такие потребности, необходимо интегрировать данные из автономных, независимо администрируемых информационных источников, как правило, слабо связанных между собой или обладающих разной моделью описания данных. Как следствие, задача управления данными с неоднородной, перманентно изменяющейся или частично неизвестной структурой становится практически важной и актуальной. Такие данные принято называть слабоструктурированными или полуструктурированными. Далее чаще используется второе из этих определений.
Одним из результатов в задаче поиска информации по разнородным источникам данных является новая абстракция управления информацией, именуемая пространством данных [34,41,47]. Цель поддержки пространства данных состоит в обеспечении базового набора функций над всеми источниками данных. Понятие пространства данных предполагает поддержку нескольких уровней доступа к информации, отличающихся степенью детальности описания данных. На самом нижнем уровне поддерживается поиск по ключевым словам. При обработке более сложных поисковых запросов, учитывающих структуру документов, могут применяться модели как полуструктурированных данных, рассматриваемые в настоящей диссертации, так и модели реляционных данных. При этом следует принимать во вни-
мание, чем выше уровень, тем сложнее организация доступа к данным.
Формальной моделью полуструктурированных данных является модель регулярных путевых запросов, предполагающая описание данных в виде графовых структур. Вычисление регулярных путевых запросов является трудоемкой операцией. Однако, применение ряда механизмов оптимизации, в том числе рассматриваемых в качестве основных в настоящей работе материализованных представлений, позволяет во многих случаях значительно сократить время вычисления запросов. Исследованиям на этом направлении посвящены работы большого числа зарубежных ученых, отмеченные в тексте диссертации и в списке литературы. Актуальность данной работы определяется тем обстоятельством, что существующие алгоритмы построения перезаписи регулярных путевых запросов по заданной системе представлений позволяют построить максимальную перезапись, которая обладает значительной избыточностью. Вычисление максимальной перезаписи может быть эквивалентно вычислению исходного запроса'даже в том случае, когда представления в явном виде содержат результат вычисления запроса.
Цель и задачи работы
Целью данной диссертации является разработка алгоритмов построения однословной перезаписи регулярных путевых запросов по заданной системе представлений при наличии дополнительных ограничений на структуру перезаписи. Для достижения этой цели решаются следующие задачи.
Формализуется понятие ограничения на структуру перезаписей и разрабатывается алгоритм построения однословной перезаписи при наличии дополнительного ограничения.
Разрабатывается механизм оценки выразительной силы набора представлений, а также выразительной силы набора представлений при наличии ограничений.
Разрабатываются алгоритмы построения всех возможных однословных перезаписей запроса.
Алгоритмы реализуются в виде программ и их работоспособность демонстрируется в ходе тестовых испытаний.
Основные результаты работы
В рамках настоящей работы автором получены следующие основные результаты.
Предложен метод описания ограничения на структуру перезаписи в виде рационального множества регулярных языков и разработан алгоритм проверки их принадлежности рациональному множеству регулярных языков.
Сформулированы необходимое и достаточное условия конечности полугруппы и рационального множества регулярных языков.
Доказана регулярность класса эквивалентности конечно порожденной полугруппы регулярных языков. Разработан алгоритм, позволяющий построить регулярный,язык, который соответствует классу эквивалентности полугруппы.
Исследованы свойства полугрупп регулярных языков над однобуквенным алфавитом, доказана их рациональность. Разработан алгоритм, выписывающий автоматную структуру для данных полугрупп.
Программно реализованы алгоритмы построения однословной перезаписи регулярного путевого запроса. В ходе их тестовых испытаний продемонстрировано, что вычислительная сложность алгоритмов может быть существенно снижена.
Научная новизна работы
С учетом введенного в диссертации понятия однословной перезаписи регулярных путевых запросов и формулировки основной задачи в терминах полугрупп регулярных языков, научной новизной обладают следующие ее результаты. Решена задача принадлежности регулярного языка рациональному подмножеству полугруппы регулярных языков, что является обобщением результатов Хашигучи [44]. Сформулировано условие конечности полугруппы и рационального множества регулярных языков, которое существенно сильнее известных ранее критериев конечности полугруппы [29, 65]. Исследована структура полугрупп регулярных языков, доказана регулярность класса эквивалентности. Доказано, что полугруппы регулярных языков над однобуквенным алфавитом являются рациональными, автоматными и полугруппами Клини.
Практическая ценность
Результаты работы могут применяться при разработке систем управления полуструктурированными данными, в основе которых лежит графовая модель их описания, в частности, в системах интеграции данных и в информационно-поисковых системах, учитывающих
логическую структуру документов. Предложенные алгоритмы могут быть использованы для повышения эффективности вычисления регулярных путевых запросов.
Структура и объем работы
Работа состоит из введения, четырех глав, заключения, приложения и списка литературы. Общий объем диссертации 135 страниц. Список литературы содержит 68 наименований.
Краткое содержание работы
В первой главе вводятся основные понятия модели полуструктурированных данных. Описывается общая постановка и подходы к решению задачи перезаписи регулярных путевых запросов для поиска данных в этой модели с учетом материализованных представлений. Приводятся различные виды перезаписей, такие как максимальные, точные, частичные, полные, однословные, и рассматриваются возможные области их применения. Анализируются известные алгоритмы решения задачи построения перезаписей регулярных путевых запросов. Показывается избыточность максимальной перезаписи и обосновывается выбор однословных перезаписей в качестве объекта исследований. В первой главе излагаются1 постановки задач поиска перезаписей-с дополнительными ограничениями, оценки выразительной силы набора имеющихся представлений. Описывается задача проверки равенства однословных перезаписей. Приводятся формальные постановки перечисленных задач в терминах полугрупп регулярных языков. В первой главе рассматриваются также возможные области применения задачи равенства слов при перезаписи запросов. Описываются классы полугрупп, которые допускают эффективные алгоритмы решения задачи равенства слов.
, Во второй главе рассматриваются ограничения на возможные наборы перезаписей. В этой главе доказывается, что задача определения принадлежности регулярного языка рациональному множеству разрешима. Приводится алгоритм проверки наличия такой принадлежности. Рассматриваются задачи о конечности и эквивалентности рациональных множеств. В частном случае рассматривается задача о конечности и эквивалентности полугрупп, как способ формального описания вопросов оценки выразительной силы представлений. Доказывается, что задача конечности рациональных множеств разрешима (приводится алгоритм проверки конечности), задача проверки эквивалентности рациональных множеств в общем случае не разрешима, а в частном случае, когда рациональное множество является полугруппой — разрешима. Доказывается, что класс эквивалентности полугруппы является ре-
гулярным. Приводятся алгоритмы построения класса эквивалентности.
В третьей главе рассматривается задача равенства слов для полугрупп регулярных языков. Рассматривается случай однобуквенного алфавита и доказывается, что полугруппы являются автоматными, рациональными и полугруппами Клини. Как следствие, они допускают эффективное решение задачи равенства слов. В общем случае доказывается, что полугруппы регулярных языков не являются рациональными. Отмечено, что принадлежность таких полугрупп к другим классам не установлена и этот вопрос остается открытым. Приводятся предложенные автором алгоритмы построения автоматных и рациональных структур для полугрупп в случае однобуквенного языка.
В четвертой главе описывается полученная автором программная реализация предложенных в работе алгоритмов на языке Mathematica. Тестируются алгоритмы построения однословных перезаписей. Проводятся эксперименты, результаты которых демонстрирют важное значение решения задачи равенства слов для полугрупп регулярных языков. Показывается практическая значимость построения класса эквивалентности запроса. Результаты экспериментов показывают, что алгоритмы построения однословных перезаписей можно реализовать на практике.
Доклады и публикации
Основные положения данной работы докладывались на конференциях.
Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005.
International Conference on Semigroups and Languages, Lisbon, Portugal, July 12-15, 2005.
11th International Conference on Automata and Formal Languages, AFL'05, May 17-20, 2005, Dobogykx, Hungary.
Международная конференция «Актуальные проблемы вычислительной математики» посвященная памяти академика Н.С. Бахвалова, 28.08-29.08, 2006.
12th International Conference on Automata and Formal Languages, AFL'08, May 27-30, 2008, Balatonfured, Hungary.
Международная конференция «Алгебра, логика и приложения (Мальцевские чтения)», Новосибирск, 2008 г.
Результаты, представленные в диссертации, проходили апробацию на механико-математическом факультете МГУ им. М. В. Ломоносова на семинаре «Проблемы современных информационно-вычислительных систем» под руководством проф. В. А. Васенина (2005, 2007 гг.), на кафедре Математической теории интеллектуальных систем механико-математического факультета МГУ им. М. В. Ломоносова на семинаре «Дискретный анализ» под руководством проф. С. В. Алешина, проф. В. А. Буевича, с.н.с. М. В. Носова (2008 г.).
По теме диссертации опубликовано 6 печатных работ, в том числе две из них [3,5] в журналах, внесенных в список ВАК.
«О представлении регулярных языков в виде конкатенации заданных», Е.Е.Хазова // Информационные технологии и программирование: Межвузовский сборник статей. Вып. 3(8), 23-38; - М.гМГИУ, 2003.
«Membership and Finiteness Problems for Rational Sets of Regular Languages», Sergey Afonin and Elena Khazova, Lecture Notes in Computer Science // Springer-Verlag GmbH, 88-99, 2005.
«Membership and Finiteness Problems for Rational Sets of Regular Languages», Afonin S., Khazova E., International Journal of Foundations of Computer Science // World Scientific, 17(3), 493-506, 2006.
«A note on finitely generated semigroups of regular languages», Afonin S, Khazova E, International Conference «Semigroups and Languages» // World Scientific, 1-8, 2007.
«К вопросу об автоматности полугрупп регулярных языков», Хазова Е., Вестник Московского университета, сер.1, математика, механика, 6, 55-59, 2007.
«Semigroups of regular languages over one letter alphabet are rational », Afonin S., Khazova E., Proceedings of 12th International Conference on Automata and Formal Languages, AFL'08, 61-73, 2008.
Применение алгоритмических методов алгебры в задачах перезаписи запросов
В области интеграции данных некоторые походы (в том числе, упоминавшийся ранее LAV) используют представления для описания локальных источников Li через глобальную базу данных G. В контексте модели ОЕМ-данных и регулярных путевых запросов такое задание можно описать следующим образом: для каждого локального источника Ьг существует некоторый запрос . к глобальной базе данных такой, что верно L% = Rl(G). Для того чтобы вычислить произвольный запрос М, поступивший извне, необходимо разложить его через запросы {-}. Если предположить, что доступна только одна операция над запросами, условно назовем ее композицией (о), то необходимо найти такой набор li} ...Ik, что М = R о Rtl,.. о Rik, либо констатировать, что такого разложения не существует.
Одним из этапов семантического кеширования является проверка того, можно ли поступивший запрос М выразить через те запросы {Rt}, результаты вычисления которых уже известны и хранятся в кеше-памяти системы.
Обратимся к упомянутому ранее вопросу защиты данных с помощью представлений. В данном случае необходимо уметь проверять факт того, принадлежит ли какой-либо запрещенный запрос М множеству запросов, выразимых через множество разрешенных представлений {Ri}.1
Перечисленные три задачи имеют общую схему их формализации. Как отмечалось ранее, конечный .набор регулярных путевых запросов можно представлять конечным множеством регулярных языков, а для эффективности вычисления перезаписей область поиска можно ограничивать только однословными перезаписями. Если предполагать, что композиция запросов — это конкатенация регулярных языков, то описанная задача сводится к проверке принадлежности регулярного языка полугруппе.
Задача Г.2. Пусть р : А+ — 2s — регулярная подстановка, R С — произвольный регулярный язык. Существует ли алгоритм проверки принадлежности языка R полугруппе v, порожденной регулярной подстановкой р Можно ли найти слово w Є А такое, что верно ip(w) = R?
В задаче 1.2 вопрос существования алгоритма проверки принадлежности- является более существенным, чем вопрос поиска однословной перезаписи. В случае существования алгоритма проверки, перезапись может быть найдена конечным перебором. Однако в данном случае значительную роль играет и сложность решения задачи. По этой причине следует рассматривать оба вопроса. Данная задача решена Хашигучи [44] и описана ранее в разделе 1.2.5.
Во всех перечисленных задачах может возникнуть необходимость вводить некоторые ограничения на структуру искомой перезаписи. Например, в задачах интеграции и кеши-рования это может быть связано с временными ограничениями на выполнение запросов, в области информационной безопасности — непосредственно с моделями логического разграничения доступа к защищаемым данным.
Подобные ограничения могут быть сформулированы на основе применения рациональных множеств регулярных языков. В случае, если используются ограничения, которые накладываются рациональными множествами, описанные задачи могут быть сформулированы следующим образом.
Задача 1.3. Пусть Л = (К, /?) — рациональное множество регулярных языков над Е и R С Е — произвольный регулярный язык. Существует ли алгоритм проверки принадлежности языка R множеству CR. Можно ли найти слово w Є А такое, что оно принадлежит языку К и верно p(w) = R?
Два пользователя системы хранения данных могут задать один и тот же запрос по-разному. Как следствие этого факта, перезаписи запросов через представления могут отличаться по виду. Если система позволяет сравнивать перезаписи запросов, то в случае поступления запроса, идентичного поступившему ранее, новых вычислений не потребуется. Таким образом, с использованиии идеи проверки эквивалентности перезаписей при кешировании данных возможно сокращение времени обработки запросов. В модели полуструктурированных баз данных вопрос сравнения однословных перезаписей запросов формально звучит как задача равенства слов в полугруппе, где полугруппа порождена конечным числом регулярных языков.
В общем случае, когда полугруппа задана определяющими соотношениями на порождающие элементы, а именно — задача равенства слов является неразрешимой [8]. В рассматриваемом случае, когда порождающие элементы являются регулярными языками, задача равенства слов разрешима. Для сравнения слов полугруппы, необходимо построить соответствующие автоматы и проверить их на равенство. Однако, и это необходимо отметить, задача эквивалентности недетерминированных конечных автоматов является NP-полной относительно размера автоматов. Вместе с тем, полугруппы, которые допускают решение задачи равенства слов за полиномиальное время, существуют. Например, автоматные полугруппы, которые будут описаны в разделе 1.4, допускают решения задачи за квадратичное время относительно длины слов. Полугруппы являются автоматными, если они обладают автоматной структурой, с помощью которой происходит сравнение слов. Автоматная структура может быть построена заранее, таким оброзом, она является своего рода индексом для задачи равенства слов. В настоящей работе делается предположение, что полугруппы регулярных языков являются автоматными. Однако доказывается оно только для полугрупп регулярных языков над однобуквенным алфавитом.
Возвращаясь к вопросу о кешировании данных, следует отметить, что одна из возникающих в данной области задач — это минимизация объема содержимого кеш-памяти с сохранением его выразительной силы. Необходимость уменьшать размер кеш-памяти появляется в целом ряде случаев практически значимых задач. Как следствие, возникает задача проверки эквивалентности наборов представлений. Переходя от абстрактных запросов и данных к регулярным путевым запросам и к OEM-модели, задача об эквивалентности наборов представлений формально может быть сформулирована следующим образом.
Рассматривая задачу о построении наилучшей кеш-памяти, при минимизации объема ее содержимого, можно оценивать количество элементов в представлении. Как следствие, возникает необходимость в решении задач о редуцировании базиса конечно порожденной полугруппы.
Полугруппы с эффективно решаемой задачей равенства слов
Как упоминалось ранее, задача равенства слов для полугрупп, заданных определяющими соотношениями на порождающие элементы, является неразрешимой [8]. В случае, когда порождающие элементы являются регулярными языками, задача равенства слов разрешима и является NP-полной относительно размера автоматов, представляющих сравниваемые слова. Возникает вопрос, можно ли сравнивать слова полугруппы, не обращаясь к языкам, которые соответствуют порождающим элементам полугруппы? В данном разделе будут перечислены некоторые виды полугрупп, которые допускают решение задачи равенства слов за полиномиальное время относительно длины слов. Дадим определение автоматных полугрупп [21]. Отправным для такого определения является автомат, принимающий на вход пары слов (и, v) алфавита Д, и = 81S2 . 8т, и = 5[5 2...5 п. Если длины слов u,v равны, то достаточно рассматривать автомат с входным алфавитом Д х Д, читающий пары (5i, 5(),(52,5 2) и так далее. Если длины слов и, v не равны, то необходимо ввести вспомогательный символ $. Определим отображение 9 : Д+ х Д+ — Д(2,$) , где Д(2,$) = ((Д U {$}) х (Д U {$})) - {($,$)}, следующим образом: Понятие автоматности применимо к таким алгебраическим структурам, как группы и полугруппы. В последние годы свойство «быть автоматным» было широко изучено для групп [20,67]. Определение автоматности для групп естественно расширяется на полугруппы, несмотря на то, что многие свойста, верные для автоматных групп, не наследуются автоматными полугруппами. Например, геометрическая характеризация, именуемая «свойством попутчика», играет фундаментальную роль в теории автоматных групп, однако она не так существенна для полугрупп.
Важным свойством автоматных полугрупп является разрешимость задачи равенства слов за квадратичное время. Автоматными полугруппами являются такие как конечные, конечно порожденные подполугруппы свободных полугрупп [21]. Множество рациональных полугрупп является подмножеством автоматных. Данный факт будет доказан в подразделе 3.1.1 настоящей работы. Важным свойством рациональных полугрупп является то, что задача равенства слов разрешается за линейное время относительно длин слов. Дадим определение. Пусть Р HQ два множества. Отношением р на Р и Q называется подмножество PxQ. Обратное отношение к р — это отношение р 1 на Q х Р, определяемое следующим образом: Отношение р на Р и Q можно также рассматривать как функцию из Р в 2Q (множество подмножеств Q) : Отношения между полугруппами (моноидами2) часто называют преобразователями. Преобразователь из полугруппы S в полугурппу "Р называется рациональным, если он является рациональным подмножеством S х СР. Определение 1.8. Полугруппа S называется рациональной, если существует рациональный преобразователь р ; А — А для некоторого конечного алфавита А (называемый описанием ) такой, что: Поскольку, согласно определению рациональной полугруппы S, она изоморфна А \ Кег(р), то существует представление полугруппы через алфавит А. Образ р является сечением ядра Кег(р), поэтому для каждого класса эквивалентности над А преобразователь р сопоставляет каждому элементу единственного представителя из класса эквивалентно-сти(фактора факторпространства А \ Кег(р)). В этой связи 1т(р) называется множеством нормальных форм. Для того, чтобы сравнить два слова u i, W2 Є А , представляющих элементы полугруппы, достаточно сравнить их нормальные формы. Рациональный преобразователь переводит каждое слово в его нормальную форму за линейное время, так же сравнение двух слов — это линейная операция. Таким образом, в рациональных полугруппах задача равенства слов решается за линейное время. Полугруппы Клини (их определение будет приведено далее) обладают следующим свойством: если они обладают коммутативностью, то они являются рациональными [59]. Следовательно, коммутативные полугруппы Клини допускают решение задачи равенства слов за линейное время.
Определение 1.9. На подмножествах полугруппы S определены три рациональные операции: PUQ — теоретико-мнооїсественное объединение; произведение P-Q, определяемое как {pq j р Є P,q Є Q} и операция плюс Клини Р+, определяющая подполугруппу полугруппы , порожденную Р. Рациональное подмножество полугруппы S — это множество, построенное из конечных подмножеств S посредством конечного числа рациональных операций. Через Rat(B) обозначается множество всех рациональных подмножеств полугруппы. Определение 1.10. Подмножество Р полугруппы S является распознаваемым, если существует конечная полугруппа З и гомоморфизм (р : S — У такой, что Р = _1( /?(Р)). Через Rec(S) обозначается множество всех распознаваемых подмножеств полугруппы. Определение 1.11. Полугруппа В называется полугруппой Клини; если Rec( ) = Rat(B). Теорема 1.2. (Клини). Для конечного алфавита Е, Яес(Е ) = Rat(H ). Пример 1.1. Полугруппа (y,z : yz = zy — z) является полугруппой Клини и рациональной полугруппой. На рисунке 1.3 представлен недетерминированный преобразователь, являющийся описанием полугруппы. Состояния 1 и 2 являются начальными, состояния 1 и 3 — заключительные. Если входное слово содержит букву z, то слово распознается только начиная с состояния 2.
При чтении символа у, на выходе появляется пустое слово, при чтении z, оно копируется на выход. Заключительное состояние не будет достигнуто до тех пор, пока не поступит символ z. Если входное слово состоит только из символов у, тогда оно распознается только с состояния 1. Символы у копируются со входа на выход. Регулярное выражение для описания р : {у, z} — {у, z} соответствует автомату на рисунке 1.3. Образ преобразователя состоит из множества слов {у} U {z} . Факторами множества А \ Кег(р) являются следующие регулярные языки
Анализ сложности алгоритма проверки принадлежности рациональному множеству
Доказательство теоремы 2.1 является конструктивным, то есть определен алгоритм проверки принадлежности регулярного языка R рациональному множеству Л = (К, р). Сформулируем алгоритм. Во-первых, строим разложение перезаписи М = М,(Л) П К в объединение языков свободных от объединения. Если полученное разложение не содержит точной перезаписи, то R . Л. В противном случае, применяем утверждение 2.4 к каждой точной перезаписи, и получаем конечное число языков свободных от объединения, удовлетворяющих условиям леммы 2.1. Далее по лемме 2.2 достаточно проверить ограниченность соответствующих автоматов расстояния. Таким образом, алгоритм состоит из пяти следующих шагов.
Сложность построения максимальной перезаписи является экспоненциальной относительно размера детерминированного автомата, представляющего регулярный язык R [58]. Пусть детерминированные автоматы языков R и К имеют размеры р и q соответственно. Тогда размер автомата, представляющего перезапись М, не больше, чем q 2Р, так как для построения пересечения автоматов строится декартовое произведение множеств состояний.
Число простых путей в автомате с j состояниями над алфавитом не больше Ер , а длина простого пути не больше, чем j. В разложении М в объединение языков U"=1Mi, свободных от объединения, п не может быть больше, чем S9 2P, так как существует разложение по простым путям. Каждому МІ соответствует простой путь, и все пути СЛОВ ИЗ МІ в автомате для M проходят данный простой путь. В этом случае каждый из языков МІ может быть представлен автоматом, размер которого не больше, чем (q-2p)2. Следует заметить, что хранить автоматы Мг- нет необходимости, так как каждый из них выписывается по автомату М.
Сложность проверки точности перезаписи, представленной недетерминированным автоматом, является экспоненциальной (EXPSPACE). Длина самого короткого слова в языке ограничена числом состояний автомата, поэтому размеры автоматов, представляющих языки множества Ж могут быть меньшего размера, чем (q 2Р)2 (р -+-1). Преобразование автомата из множества М в автомат расстояния, а также проверка его ограниченности требуют полиномиальных затрат памяти.
Таким образом, задача проверки принадлежности языка, представленного детерминированным автоматом, имеет дважды экспоненциальную верхнюю оценку сложности.
Автомат расстояния с j состояниями ограничен, если он ограничивается константой 24j +jiog(j+2)+j [45]. Как следствие, слово из языка L будет являться точной перезаписью, если
оно построено следующим образом. Язык L является языком без объединения, рассмотрим его некоторое регулярное выражение без объединения. Если в этом регулярном выражении каждую итерацию заменить степенью 24j +ЛеО"+2)+.7г Где j числ0 состояний автомата расто-яния, представляющего L, то получим искомое слово.
С учетом изложенного, задача построения точной однословной перезаписи также имеет дважды экспоненциальную сложность.
В данном разделе доказывается, что для любой полугруппы регулярных языков и любого слова w Є S данной полугруппы верно утверждение, что множество слов, равных w, является регулярным. Данный факт позволяет выбирать оптимальную перезапись регулярного путевого запроса через материализованные представления. В третьем подразделе сформулирован алгоритм поиска оптимальной перезаписи.
Регулярность класса эквивалентности элемента полугруппы является следствием теоремы 1.1 и леммы Хигмана, которую можно сформулировать следующим образом.
Лемма 2.3. В каждой бесконечной последовательности {Щ}І І слов над алфавитом А существуют индексы г и j такие, что U{ » щ.
Пусть w = 5 ...8im слово над А и А С А. Будем называть язык w ft А = А 5ігА 6і2.. .A 8imA полным расширением слова w. Через E(w,A) будем обозначать язык (го ft А ) П Mv(tp{w)). Заметим, что E(w,A) является регулярным языком для любого слова w Є А+.
Утверждение 2.5. Пусть (р : А+ — 22 регулярная подстановка, и Є Д+, А0 = {6 Є А є Є Ц (5)}. Для каждого v Є Е&0(и) верно
Доказательство. Пусть S Є А0. Рассмотрим слово v = щбщ, где щ,и2 Є А и и = щи2. Заметим, что верно вложение р{и) С іріиїдщ) для любых щ,и2 Є А , удовлетворяющих и = щи2 (достаточно рассмотреть длину самого короткого слова). По определению языка Е&0(и) верно вложение
Доказательство. По теореме 1.1 множество Mv(w) — {и Є Д+ f{u) С p(w)} является регулярным. Заметим, что [w] С Mv(w). Пусть [w] — бесконечный язык. Докажем, что существует конечное подмножество F С [w] удовлетворяющее
Строение полугрупп в случае произвольных порождающих элементов, содержащих пустое слово
В данном подразделе рассматриваются полугруппы, порожденные языками над одно-буквенным алфавитом, содержащими ноль. Будет доказано, что множество элементов таких полугрупп, кроме конечного числа, можно разбить на непересекающиеся классы. В каждом классе таком элементы обладают свойством (С, Б)-похожести, классов конечное число, и каждый из них задается регулярным множеством. При умножении элементов одного класса на один и тот же элемент полугруппы результаты оказываются в одном и том же классе (С, Б)-похожести. Главным результатом данного подраздела является сформулированная и доказанная автором теорема 3.9.
В начале подраздела рассматриваются различные виды представлений регулярных языков над однобуквенным алфавитом: заключительно-периодическое подмножество натуральных чисел, его компактное представление, последовательность из нулей и единиц. Рассматривается подкласс регулярных языков, который называется звездновыделяемым. Устанавливается связь между различными представлениями. Вводится определение классов (С, В)-похожих языков, доказываются их свойства, которые необходимы для доказательства теоремы 3.9.
Определение 3.7. Множество натуральных чисел называется заключительно-периодическим, если оно представимо в виде
Заметим, что каждому заключительно-периодическому множеству натуральных чисел соответствует регулярный язык над однобуквенным алфавитом и наоборот. Таким образом, заключительно-периодические множества можно считать еще одним определением регулярных языков над однобуквенным алфавитом. Заметим также, что каждое заключительно периодическое множество может иметь такое представление (далее будем называть его компактным), что
Определение 3.8. Заключительно-периодическое множество является звездновыделяе-мым, если для его компактного представления М0 U {ni + j \ j Е J,i Є N} верно вложение М0 С J. Лемма 3.6. Свойство заключительно-периодического множества быть звездновыделяе-мым не зависит от компактного представления.
Доказательство. Предположим, что существует два компактных представления для некоторого множества М:
Как известно, бесконечный язык, над однобуквенным алфавитом, содержащий пустое слово, обладает свойством конечной степени. Более того, полугруппа, порожденная конечным числом бесконечных языков, содержащих пустое слово, является конечной. Действительно, языки коммутируют, и в разложении любого элемента полугруппы каждый порождающий элемент обладает свойством конечной степени. Для анализа строения полугрупп, порождающими элементами которых являются и конечные элементы в том числе, следует делать различие между бесконечными языками, которые являются звездновыделяемыми, и теми, которые таковыми не являются. Если все бесконечные порождающие элементы являются звездновыделяемыми, то полугруппа содержит лишь конечное число бесконечных элементов. Этот факт будет доказан в дальнейшем. Если же существуют порождающие элементы, не являющиеся звездновыделяемыми, то полугруппа может содержать и бесконечное число бесконечных элементов.
Лемма 3.8. Конкатенация двух языков, один из которых является звездновыделяемым, является звездновыделяемым языком. Доказательство. Пусть L = Fw — звездновыделяемый язык, A U К(и) — произвольный регулярный. Справедливы равенства: где P — конечное множество, состоящее из слов длины i\u\ + j\w\, где i,j — натуральные числа такие, что г\и\ + j\w\ меньше, чем наименьшее общее кратное чисел \и\ и гу.
Еще одним способом представления языка L над однобуквенным алфавитом является последовательность (конечная или бесконечная строка) Sec(L) = SQ,S\,S2, ... из нулей и единиц. Элемент Sj последовательности Sec(L) равен 1 тогда и только тогда, когда язык L содержит слова а1 (а0 = є).
Определение (СО)-похожих языков можно переписать следующим образом.
Определение 3.9. Пусть C,D — некоторые константы, назовем конечные языки R\ и Ri (С,D)-похожими, если существуют слова U\,U2,w,x,из Є {0,1} такие, чтои-і = wx, \щ\ = С, из = D; слово wu-$ меньше слова w+1; слово щ1 меньше слова (г )-1 при лексикографическом сравнении2, и натуральные числа Yi,Y2 такие, что верно:
Определение 3.10. Пусть C,D — некоторые константы, назовем бесконечные языки R\ и i?2 (С, D)-похожими, если существуют слова ui,U2,w,x,u3,u i Є {0,1} такие, что и2 = wx, \щ\ = С, и3 = D, гі4 иг, и натуральные числа Yi, Y2 такие, что верно: D,it2 = wx, слово гищ меньше слова u2+l, слово щ1 меньше слова (и )-1 при лексикографическом сравнении и для любого языка L Є Т существует натуральное число Y(L) такое, что выполнено:
