авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Дескриптивная сложность некоторых преобразований регулярных языков

Российская академия наук

Уральское отделение Институт математики и механики

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

Поваров Григорий Андреевич Дескриптивная сложность некоторых преобразований регулярных языков 01.01.09 дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург 2010

Работа выполнена на кафедре алгебры и дискретной математики ГОУ ВПО Уральский государственный университет им. А. М. Горького

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

Официальные оппоненты: доктор физико-математических наук, профессор В. А. Молчанов, кандидат физико-математических наук, старший научный сотрудник С. А. Афонин

Ведущая организация: Уральский государственный технический университет УПИ имени Б. Н. Ельцина

Защита диссертации состоится 14 апреля 2010 г. в 14 часов на за седании диссертационного совета Д 004.006.04 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Кова левской, 16.

С диссертацией можно ознакомиться в библиотеке Института мате матики и механики УрО РАН.

Автореферат разослан марта 2010 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, старший научный сотрудник В. Д. Скарин

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

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

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

Задача о максимально эффективном представлении языка детерми нированным автоматом является крайне естественной. О важности по добных исследований говорит еще и тот факт, что детерминированная сложность дает нижнюю оценку для временной сложности и сложности относительно количества памяти вычислений, связанных с регулярным языком, представленным при помощи детерминированного конечного ав томата. Вопросы эффективного представления языка при помощи детер минированных автоматов поднимаются в ранних работах, касающихся регулярных языков (в частности, в [14, 16]). Первыми отечественными исследованиями в данной области являются работы А. Н. Маслова. В [4] доказана точность известных верхних оценок детерминированной слож ности объединения, пересечения и итерации языков, а также получена верхняя оценка детерминированной сложности циклической перестанов ки букв слов языка. В [5] операция циклической перестановки рассмотре на более подробно и получены аналогичные результаты для контекстно свободных языков. Размер автомата именно как мера дескриптивной сложности языка впервые рассматривался в [10].

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

операция sc L1 L2 mn L1 L2 mn C(L1) n 2n R(L1) (2m 1)2n L1 · L L 3 · 2n Таблица 1: Детерминированная сложность некоторых операций Более формально, пусть имеется операция f (L), которая сохраняет регу лярность языка. Тогда детерминированной сложностью операции f яв ляется функция sc(f ) : N N, которая каждому натуральному числу n ставит в соответствие наиболь шее значение детерминированной сложности, которой может обладать язык f (L) при условии, что язык L имеет сложность n:

sc(f )(n) = max sc(f (L)).

sc(L)=n Аналогичным образом определяется детерминированная сложность опе рации, аргументами которой являются не один, а несколько языков. В этом случае областью определения функции sc(f ) является пространство Nk, где k количество аргументов операции f.

Современный вид теория дескриптивной сложности регулярных язы ков приняла в начале 90-х годов сначала в работах Ж.-К. Бирже [7, 8], а затем и в исследованиях Шень Ю и К. Саломаа [22]. С этого момента можно говорить о взрывном росте интереса к детерминированной слож ности регулярных языков: появляется значительное количество новых статей по этой теме, а спустя некоторое время организуется серия еже годных конференций Descriptive Complexity of Formal Systems, посвящен ных изучению этих вопросов. Хорошим обзором современного состояния дел в этой области является работа [21].



В таблице 1 представлена детерминированная сложность некоторых основных операций над регулярными языками на основе работы [22]. В этой таблице подразумевается, что языки L1 и L2 имеют сложность n и m соответственно. Через R обозначается реверсаль языка (разворот всех слов языка в обратном порядке), через C –– дополнение языка, через итерация языка.

Недетерминированная сложность регулярного языка определяет ся минимальным количеством состояний, на которых можно построить операция nsc L1 L2 m+n+ L1 L2 mn O(2n1) C(L1) R(L1) n+ L1 · L2 m+n L n+ Таблица 2: Недетерминированная сложность некоторых операций недетерминированный конечный автомат, распознающий рассматривае мый язык. Важно отметить, что для регулярного языка может не суще ствовать одного минимального недетерминированного автомата авто матов с минимальным количеством состояний может быть несколько, и они могут быть друг с другом не изоморфны. Однако само минималь ное количество состояний, тем не менее, всегда определяется однознач но. Для регулярного языка L его недетерминированную сложность бу дем обозначать через nsc(L). Недетерминированная сложность операции над регулярными языками определяется аналогично детерминированной сложности операции.





Несмотря на то, что в начале 1990-х гг. Бирже исследовал как детер минированную, так и недетерминированную сложность операций над ре гулярными языками, дальнейшее изучение недетерминированной слож ности другими исследователями было широко продолжено только в на чале 2000-х гг. Результаты этих исследований приведены в таблице 2 (в ней приняты те же соглашения, что и в таблице 1). Обзор основных ре зультатов по недетерминированной сложности регулярных языков дан в работе [17].

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

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

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

Эта задача также находит эффективное решение при помощи конечных автоматов: строится автомат, который вместе с образцом ищет также другие похожие варианты (с заданным количеством ошибок). Классиче скими работами в этой области являются [18, 20].

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

Другими словами, окрестность регулярного языка (регулярного выра жения) относительно некоторого расстояния будет регулярным языком.

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

Хороший обзор существующих алгоритмов приближенного поиска дан в [6, 13].

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

окрестность радиуса r языка L в метрике Хэммин га будем обозначать через O(L, r)). В [18] кроме собственно алгоритма построения автомата приводится оценка количества состояний в этом автомате. Однако данный вопрос рассматривается лишь для случая ре гулярного языка, состоящего из одного слова. В результате можно сфор мулировать следующую задачу Задача 1. Оценить дескриптивную сложность окрестности резуляр ного языка в метрике Хэмминга.

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

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

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

Важное значение для теории конечных трансдьюсеров имеет теорема о том, что образ регулярного языка при применении к нему конечного трансдьюсера остается регулярным языком ([15], теорема 1.6). В нашем случае это позволяет сформулировать следующую задачу:

Задача 2. Оценить дескриптивную сложность применения к регуляр ному языку конечного трансдьюсера.

Классические алгоритмы приближенного поиска, основанные на рас смотрении окрестности языка в некоторой метрике с фиксированным числом ошибок, не во всех приложениях дают желаемый результат. В [9] предлагается алгоритм (также на основе конечных автоматов) для по иска образца в тексте, который содержит не более чем заданное коли чество ошибок в каждом блоке заданной длины окрестность слова или языка, устроенную таким образом, будем называть динамической окрестностью. Если L некоторый язык, r максимально допустимое количество ошибок, а длина блока, то соответствующую динами ческую окрестность будем обозначать через O(L, r, ). Подобная поста новка задачи представляется очень естественной: чем более длинный об разец или текст мы обрабатываем, тем большее количество ошибок там может содержаться. Пожалуй, такая постановка задачи актуальней всего для имеющей большое практическое значение проблемы поиска образца в цепочке ДНК. Если имеется некоторый образец ДНК и нужно прове рить его вхождение в какую-то цепочку ДНК, то мы должны учитывать, что в цепочке вполне могли произойти какие-то мутации или погрешно сти экспериментов, в результате чего отдельные нуклеотиды могли быть изменены. Такие изменения не могут быть очень концентрированными (в противном случае цепочка ДНК разрушится), они должны быть бо лее или менее равномерно распределены по всей длине цепочки. Поиск достаточно длинного образца в такой цепочке необходимо производить с учетом приведенных особенностей. Более подробную информацию об особенностях поиска в цепочках ДНК можно найти в [12, 19].

Естественное желание обобщить поиск одного образца до поиска по регулярному выражению приводит к следующей задаче:

Задача 3. Оценить дескриптивную сложность динамической окрест ности регулярного языка.

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

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

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

Апробация результатов работы. Результаты диссертации докла дывались на Международной алгебраической конференции, посвящен ной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шев рина (Екатеринбург, 2005), Международной конференции по теории язы ков и автоматов и ее приложениям (Таррагона, 2007), научных семи нарах Алгебраические системы и Компьютерные науки кафедры алгебры и дискретной математики Уральского государственного уни верситета имени А. М. Горького (Екатеринбург, 2007–2009), Российско индийском семинаре Алгебра, комбинаторика, сложность (Екатерин бург, 2009), семинаре кафедры математической теории интеллектуаль ных систем Механико-математического факультета Московского госу дарственного университета имени М. В. Ломоносова (Москва, 2009).

Публикации. Основные результаты диссертации опубликованы в работах [23]–[27]. Работы [23] и [27] опубликованы в изданиях, входящих в перечень ВАК.

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

Краткое содержание работы Во введении диссертации обсуждается история вопроса и формулиру ются основные результаты диссертации.

В первой главе диссертации приводятся необходимые определения и вспомогательные утверждения.

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

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

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

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

регулярный язык, r 0. Тогда Пусть L Теорема 2.1.

nsc(O(L, r)) (r + 1) nsc(L).

При этом данная оценка является точной, а именно: для любых r и n r найдется такой регулярный язык L, что nsc(L) = n и nsc(O(L, r)) = (r + 1) nsc(L).

регулярный язык, r 0. Тогда Пусть L Теорема 2.2.

sc(O(L, r)) n · 2nr + 1.

При этом для n 4 найдется такой регулярный язык L, что sc(L) = n и sc(O(L, 1)) = n · 2n 2n4 + n.

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

Далее в §3.2 для заданных конечного нормализованного трансдьюсе ра и регулярного языка приводится конструкция недетерминированного конечного автомата, который распознает язык, получаемый в результа те применения данного трансдьюсера к данному языку. Это позволяет получить верхнюю оценку недетерминированной сложности применения конечного нормализованного трансдьюсера к регулярному языку. Дока зательство точности этой оценки осуществляется с использованием ре зультатов второй главы. В §3.3 получена верхняя оценка детерминиро ванной сложности применения конечного нормализованного трансдьюсе ра к регулярному языку как следствие полученной верхней оценки неде терминированной сложности этой операции.

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

Теорема 3.1. Пусть L регулярный язык, нормализованный конечный трансдьюсер. Тогда nsc( (L)) | | · nsc(L).

При этом данная оценка является точной, а именно: для любых r и n r + 1 найдутся такой регулярный язык L и нормализованный конечный трансдьюсер, что nsc(L) = n, | | = r и nsc( (L)) = | | · nsc(L).

В четвертой главе диссертации исследуется динамическая окрест ность регулярного языка относительно метрики Хэмминга и ее дескрип тивная сложность. В §4.1 доказаны некоторые вспомогательные утвер ждения относительно динамической окрестности регулярного языка. В §4.2 доказывается, что динамическая окрестность регулярного языка оста ется регулярным языком. Это позволяет использовать в качестве де скриптивной сложности динамической окрестности недетерминирован ную сложность. В §4.3 приводится верхняя оценка недетерминированной сложности динамической окрестности регулярного языка.

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

регулярный язык, r, 0, r 2. Тогда Пусть L Теорема 4.2.

2(/2r) nsc(O(L, r, )) 2 e nsc(L).

Основные результаты диссертации • Получена точная верхняя оценка недетерминированной сложности окрестности регулярного языка в метрике Хэмминга.

• Получена верхняя оценка детерминированной сложности окрест ности регулярного языка в метрике Хэмминга. Построена серия примеров, показывающих, что полученная оценка точна по поряд ку для единичной окрестности.

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

• Получена верхняя оценка недетерминированной сложности дина мической окрестности регулярного языка в метрике Хэмминга.

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

Литература [1] Гасфилд Д., Строки, деревья и последовательности в алгоритмах.

Информатика и вычислительная биология БХВ–Петербург, 2003.

656 с.

[2] Кудрявцев В. Б., Алешин С. В., Подколзин А. С., Введение в теорию автоматов М.: Наука, 1985. 320 с.

[3] Левенштейн В. И., Двоичные коды с исправлением выпадений, вста вок и замещений символов // Доклады Академии наук СССР 1965. Т. 163 (4) С. 846–848.

[4] Маслов А. Н., Оценки числа состояний конечных автоматов // Доклады Академии наук СССР 1970. Т. 194 (6). С. 1266– 1268.

[5] Маслов А. Н., О циклических перестановках языков // Проблемы передачи информации 1973. Т. 9 (4). С. 81–87.

[6] Baeza-Yates R., Ribeiro B. (eds.), Modern Information Retrieval Addison-Wesley, 1999. 544 p.

[7] Birget J.-C., Intersection and union of regular languages and state complexity // Information Processing Letters 1992. V. 43. P. 185– 190.

[8] Birget J.-C., Partial orders on words, minimal elements of regular languages, and state complexity // Theoretical Computer Science 1993. V. 119 (2). P. 267–291.

[9] Epifanio C., Gabriele A., Mignosi F., Restivo A., Sciortino M., Languages with mismatches // Theoretical Computer Science 2007.

V. 385 (1–3). P.152–166.

[10] Meyer A. R., Fischer M. J., Economy of description by automata, grammars, and formal systems // Proceedings of the Annual Symposium on Foundations of Computer Science 1971. P. 188– 191.

[11] Moore F., On the bounds for set-state size in the proofs of equivalence between deterministic, nondeterministic and two-way nite automata // IEEE Transactions on Computers 1971. V. 20. P. 1211–1214.

[12] Myers G., Algorithmic Advances for Searching Biosequence Databases // Suhai S. (ed.) Computational Methods in Genome Research Plenum Press, 1994. P. 121–135.

[13] Navarro G., NR-grep: a fast and exible pattern-matching tool // Software Practice and Experience 2001. V. 31. P. 1265–1312.

[14] Rabin M., Scott D., Finite automata and their decision problems // IBM Journal of Research and Development 1959. V. 3 (2). P. 114–125.

e [15] Sakarovitch J., Elments de thorie des automates Vuibert, 2003.

e 816 p.

[16] Salomaa A., On the reducibility of events represented in automata // Annales Academiae Scientiarium Fennicae, Series A, I. Mathematica 1964. V. 353.

[17] Salomaa K., Descriptional complexity of nondeterministic nite automata // Lecture Notes in Computer Science 2007. V. 4588.

P. 31–35.

[18] Ukkonen E., Finding approximate patterns in strings // Journal of Algorithms 1985. V. 6. P. 132–137.

[19] Waterman M., Introduction to Computational Biology: Maps, Sequences and Genomes Chapman and Hall, 1995. 448 p.

[20] Wu S., Manber U., Fast text searching allowing errors // Communications of the ACM 1992. V. 35 (10). P. 83–91.

[21] Yu S., State complexity: recent results and open problems // Fundamenta Informaticae 2004. V. 64 (1–4). P. 471–480.

[22] Yu S., Zuang Q., Salomaa K., The state complexities of some basic operations of regular languages // Theoretical Computer Science 1994. V. 125. P. 315–328.

Работы автора по теме диссертации [23] Поваров Г. А. Регулярность динамической окрестности регуляр ного языка // Труды института математики и механики 2009.

Т. 15 (2) С. 193–201.

[24] Поваров Г. А. Конечные трансдьюсеры и недетерминированная сложность регулярного языка // Уральский государственный уни верситет, Екатеринбург 2009. Деп. в ВИНИТИ 21.10.2009 №644 В2009. 15 с.

[25] Povarov G. State complexity of the conjugate closure of a regular language // Тезисы докладов международной алгебраической кон ференции, посвященной 100-летию со дня рождения П. Г. Конторо вича и 70-летию Л. Н. Шеврина Издательство Уральского уни верситета, Екатеринбург 2005. С. 198–199.

[26] Povarov G. Descriptive complexity of the Hamming neighborhood of a regular language // Proc. of Language and Automata Theory and Applications Conference Universitat Rovira i Virgili 2007. P. 509– 520.

[27] Povarov G. Regularity of a dynamic neighborhood of a regular language // Proc. of the Steklov Institute of Mathematics 2009. V. Suppl. 1. P. 201–209.

Ризография НИЧ ГОУ ВПО УГТУ УПИ 620002, г. Екатеринбург, ул. Мира,

 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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