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

• Мельникова, Александра Александровна
• кандидат наук
• 2014

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

Оглавление

1 Введение

1.1 Исторический обзор, актуальность

и новизна темы

1.2 Применяемые обозначения

1.3 Структура диссертационной работы

2 Базисные автоматы — определения

2.1 Дополнительные определения и обозначения

2.2 Базисный автомат - определение

2.3 Функции разметки состояний

2.4 Первый пример построения

2.5 Основное утверждение

2.6 Однозначность базисного автомата

2.7 Свойство допускающего пути произвольного НКА

2.8 Примеры построения базисного автомата

2.9 Альтернативный алгоритм

3 Свойства базисных автоматов

3.1 Свойства функций разметки

3.2 Варианты алгоритмов объединения состояний

3.3 Примеры применения

3.4 Изменение значений функций разметки

3.5 Свойства входных и выходных языков

3.6 Ещё раз о бинарном отношении #

4 Задачи минимизации

4.1 Блоки и псевдоблоки

4.2 Множество возможных дуг

4.3 Первый алгоритм дуговой минимизации

4.4 Второй алгоритм дуговой минимизации

5 Заключение

Литература

Глава

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

Введение

1.1 Исторический обзор, актуальность и новизна темы

Исторический обзор

Недетерминированные конечные автоматы (ниже - НКА), изучаемые в диссертационной работе, впервые рассматривались в середине прошлого века Ю.Медведевым ([21]), а также М. Рабином и Д.Скоттом ([102]). Позднее, прежде всего - при применении НКА к решению различных прикладных задач, указанные автоматы модифицировались и обобщались многими авторами (см., например [10, 57, 58, 67, 90, 91]). По-видимому, самым важным их обобщением стали недетерминированные автоматы-распознаватели с. магазинной памятью (push-down automata, МП-автоматы), появившиеся как одно из средств автоматического перевода, а также для различных целей программирования, широко используемые в теории трансляции ([1, 2, 3]. Как МП-автоматы, так и НКА служат примером так называемых автоматов-распознавателей - в отличие от конечных автоматов-преобразователей (например, конечных автоматов Мили, Мура), которые в представляемой диссертационной работе не рассматриваются. Конечные автоматы и такие тесно связанные с ними конструкции, как, например, линейные грамматики и регулярные выражения, относятся к основным понятиям информатики.

Теория конечных автоматов Рабина-Скотта активно развивалась в 1960-х годах, по этой тематике в то время было очень много научных публикаций1. Но примерно с начала 1970-х годов, с появлением развитой теории детерминированных конечных автоматов, в научных статьях часто стало прослеживаться мнение, что в теории регулярных языков и конечных автоматов уже решены практически, все возможные задачи. Когда же данная теория стала применяться к различным вопросам смежных наук, оказалось, что остаётся важным способ, которым задаётся регулярный язык, - а не только сам исследуемый язык2.

Актуальность темы

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

Базисный автомат является инвариантом заданного регулярного языка - альтернативным каноническому автомату. Развиваемая в диссертации теория применяется для решения различных задач теории регулярных языков, а также некоторых задач дискретной оптимизации, причём как точными, так и эвристическими методами.

Различные варианты конечных автоматов и близкие им математические объекты служат для описания и анализа технических устройств, различных систем и процессов, программ и. алгоритмов, что отмечается, в частности, в [6]. Эффективность применения имен-

1 Подробные библиографии работ 1960-70-х годов можно найти, например, в следующих монографиях: [17, 19].

2 Наиболее чётко эта мысль отражена в [104].

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

но конечных автоматов в различных задачах теории регулярных языков связана с тем, что, в отличие от других задающих регулярный язык формализмов, конечный автомат является вычислиюпыюп моделью; см. об этом в вышеуказанных монографиях, а также, например, в [6, 77, 78] и др.

Итак, в различных прикладных задачах теории формальных языков желательно получать экономное (с различных точек зрения) представление недетерминированных конечных автоматов. Это обосновано, например, тем, что экономное представление автомата в памяти часто связано с убыстрением работы алгоритмов, моделирующих функционирование автоматов. При разных способах представления автомата в памяти компьютера более важными могут быть либо минимально возможное число вершин, либо минимально возможное число дуг, либо минимальное суммарное число вершин и дуг4. Среди других возможных областей применения можно назвать такие основные, как теория трансляции, теория «естественных» языков, теория искусственного интеллекта, математическое моделирование. Особо отметим возможное применение исследованных автором диссертации функций разметки для создания алгоритмов для ДНК-компьютеров5.

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

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

4См., по этому поводу следующие публикации. [76. 80. 81]

5 Работы в этом направлении только начались. См. [18].

мизации. Недетерминированные конечные автоматы Рабииа-Скотта -наиболее удобный объект для решения самых различных задач теории регулярных языков. Однако в большинстве работ, посвягцённых этим автоматам, либо предполагается, что исходный НКА каким-либо образом задан заранее (часто - как частный случаи, например, как канонический конечный автомат, являющийся инвариантом регулярного языка), либо он получается единственным образом (обычно - по заданному регулярному выражению с помощью теоремы Клини). Но в литературе практически не исследованы многие проблемы, связанные с альтернативными способами получения некоторого НКА специального вида по заданному регулярному языку, причём способ задания языка может быть отличен от регулярного выражения. Проблеме восстановления конечных автоматов по конечным экспериментам, где автоматы заданы в несколько иной, чем в данной диссертации, форме, посвящены, например, работы [5, 57].

Основные задачи исследования

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

Объектом исследования

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

Предметом исследования

являлись алгоритмы работы с недетерминированными конечными автоматами.

Методы исследования

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

Результаты исследования

Результатами диссертационного исследования являются новые утверждения и теоремы теории формальных языков, а также" новые алгоритмы эквивалентного преобразования НКА.

Научная новизна

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

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

Практическая значимость исследования

Полученные результаты могут быть применены при доказательстве теорем, связанных с регулярными языками и недетерминированными конечными автоматами, а также при описании алгоритмов эквивалентного преобразования конечных автоматов ([41]), в том числе -

при построении автоматов, эквивалентных заданному6. Кроме того, результаты диссертации могут быть применены в различных задачах минимизации недетерминированных конечных автоматов - в вершинной7, дуговой (см. работу автора [94]) и т.н. звёздно-высотной минимизации ([4]), а также минимизации по некоторым комбинированным критериям. Для каждой из этих задач может помочь построение т.н. универсального автомата Копвэя - которое также удаётся выполнить на основе базисного автомата ([35]). При этом результаты диссертации могут быть применены и для создания эвристических алгоритмов решения перечисленных задач дискретной оптимизации8. Результаты представляемой диссертации применяются также в смежных областях - а именно, для проверки репрезентативности случайно сгенерированных дискретных структур и описания специальных подходов к кластеризации9 и для описания специальных математических моделей (см. также [16]).

6 Например, схожие конструкции были применены в статье [106], опубликованной через 9 лет после статьи [105] соискателя данной диссертации.

7 Хороший обзор публикаций об эвристических алгоритмах вершинной минимизации НКА приведён в [74, 79]. Кроме того, см. по этому поводу уже упомянутые работы [41, 106], а также, например, [16] и цитируемые ниже статьи [65, 66].

8 Про применение базисных конечных автоматов для эвристических алгоритмов звёздно-высотной минимизации см. вышеуказанную статью [4]. Про применение для эвристических алгоритмов вершинной минимизации см. вышеуказанную диссертацию [16], а также серию статей [65, 66] (см. также другие ссылки, приведённые в этих статьях).

9 См. [40|; стоит специально отметить, что базисные автоматы являются одним из предметов этой статьи - что явно отражено в её названии.

Обоснованность и достоверность

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

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

• Определение функций разметки состояний заданного конечного автомата и формулировка свойств этих функций.

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

• Описание двух алгоритмов построения базисного конечного автомата.

• Формулировка свойств базисного конечного автомата; среди них:

— эквивалентность базисного автомата и канонического;

— однозначность базисного автомата - т.е. единственность последовательности состояний базисного автомата при принятии им некоторого слова рассматриваемого языка;

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

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

• Утверждения о свойствах таблицы состояний конечного авто.ма ы.

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

Апробация работы

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

• Научная конференция «Математическое моделирование физических, экономических, социальных систем и процессов», Ульяновск, УлГУ, 1998 и 1999 г.

• Международная алгебраическая конференция памяти А.Г.Куроша, Москва, МГУ, 1998 г.

• VII Международный семинар «Дискретная математика и её приложения», Москва, МГУ, 2001 г.

• Международная научно-практическая конференция «Методы и алгоритмы прикладной математики в технике, медицине и экономике», Новочеркасск 2001 г.

• Научный семинар для аспирантов кафедры МАТМС (под руководством д.ф.-м.н. В.Буевича и С.Алёшина), Москва, МГУ, 2001 и 2002 г.г.

• Научный семинар (под руководством д.ф.-м.н. Г.Осипова), Переславль-Залесский, НПО РАН, 2001 и 2003 г.г.

• XIII Международная конференция «Проблемы теоретической кибернетики», Казань, 2002 г.

• Международная научно-практическая конференция «Проблемы

математического образования и культуры», Тольятти, ТГУ, 2003 г.

i

• Международная конференция «Общие проблемы управления и их приложения. Проблемы преподавания математики» Тамбов, ТГУ, 2007 и 2009 г.г.

• Научный семинар по математической кибернетике и дискретной математике при Диссертационном совете Д212.081.24, Казань, КГУ (КПФУ), 2009-2014 г.г.

• Научный семинар кафедры математического анализа Ульяновского государственного педагогического университета, 2010 и 2012 г.г.

• Научный семинар по дискретной математике, Димитровград, Филиал УлГУ и ДИТИ - филиал Научно-исследовательского ядерного университета «МИФИ», 1999-2014 г.г.

Публикации

Основные результаты диссертации опубликованы в 21 работе, 7 из которых входят в список изданий, рекомендованных ВАК.

Личный вклад

Изложенные утверждения и теоремы доказаны лично автором, либо совместно с научным руководителем. Результаты, полученные в совместных с научным руководителем работах [34, 36, 37, 38, 94, 95, 96, 100], принадлежат в части, касающейся базисных автоматов, автору диссертации.

1.2 Применяемые обозначения

Итак, в данной диссертационной работе рассматриваются недетерминированные автоматы Рабина-Скотта. Различные варианты изложения теории конечных автоматов (например - варианты обозначений) см., например, в монографиях [6, 19, 64]. В данной диссертации будут применяться обозначения, согласованные с публикациями автора. При этом важно отметить, что они во многом не совпадают с применёнными в [32]: в [32], они были построены на основе некоторого рассматриваемого автомата, а в настоящей диссертации они построены на основе некоторого рассматриваемого регулярного языка.

Определение 1 Недетерминированный конечный автомат -

это пятёрка

К = (1.1)

где:

• Сд - некоторое конечное множество состояний (вершин);

• Е - рассматриваемый алфавит; автомат К вводится для задания некоторого языка над этим алфавитом;

• 6 - функция переходов, функция вида 5 : х (Е и {е}) —> "Р((2) (через V обозначим множество всех подмножеств данного мно-э/сества);

• 5 С - мноэюество стартовых состояний (входов);

• ^ С - множество финальных состояний (выходов).

Отметим, что каждое стартовое состояние может также быть и финальным.

Всюду определённая функция 5: как показывает запись

имеет два аргумента. Первый - одно из состояний множества ф, второй - буква алфавита Е, или пустое слово е. При этом можно избавиться от £-переходов построением формализма (эквивалентного данному) с функцией переходов 5 : х Т, 'Р{0). Один из таких вариантов сведение произвольного недетерминированного конечного автомата к детерминированному. Значениями функции д являются подмножества множества ф (для некоторых пар аргументов значение может быть пустым множеством). ■

Опишем некоторые другие способы задания функции переходов конечного автомата.

Первый способ - с помощью функции

Формально условие а) Э г (здесь д, г е <5, а а € Еи{е}) выполнено тогда и только тогда, когда 7(5, г) Э а. Будем всюду ниже считать, что, задавая функцию 6, мы одновременно задаём и функцию 7.

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

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

В качестве примера рассмотрим запись одного и того же конечного автомата тремя способами. Пусть граф переходов автомата изображён на рис. 1. Его алфавит Е = { а, 6, с, (1}. Согласно изложенному ранее, Я — { 9ь 92 }, £ = { 91 }> Р = { 91, 92 }• Формальные описания функции переходов следующие. Первый способ:

Рис. 1

Кчъ0) = {92}, д{д2,Ь) = {д1} , %2,с) = {д2}, й(д2,<1) = {дх};

второй способ:

7(91,92) = {а}, 7(92,92) = {с}, 7(92,91) ^ {МЬ

Третий способ - см. таблицу 1:

а Ъ с с1

г 91 42

42 41 42 4\

Очевидно, что описанные три способа задания функции переходов эквивалентны: зная задание конкретного автомата одним из этих способов, можно построить другие. Поэтому применительно к конечным автоматам слова «состояние» и «вершина» могут использоваться как синонимы.

Работа НКА состоит в следующем. Получая на вход некоторое слово (последовательность букв), НКА читает его буква за буквой и перемещается из одного состояния в другое по соответствующим дугам. При этом очень важно отметить, что вследствие недетерминированности автомата множество новых состояний может включать более 1 элемента. Выходом является «да» или «нет» - в зависимости от того, допущено ли слово автоматом, то есть принадлежит ли слово языку, определяемому автоматом.

Пусть в том же примере с автоматом, заданным графом на рис. 1, автомат получает на вход слово ассс1. Читая букву а, из входного состояния ql он по дуге с пометкой а переходит в состояние (¡-и читая следующую букву с, по дуге с пометкой с он возвращается в состояние </2; далее повторяет предыдущий шаг; затем, читая букву с/, по дуге с пометкой «с!» автомат переходит в состояние Состояние с[\ - финальное, поэтому на выходе автомат выдаст «да», то есть данное слово допускается автоматом.

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

Итак, НКА служат примером так называемых автоматов-распознавателей (см. [2, 6, 64] и др.) - в отличие от конечных автоматов-преобразователей (например, конечных автоматов Мили и автоматов Мура), которые в данной работе рассматриваться не будут. Можно также рассматривать конечный автомат как формализм, по-

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

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

Определение 3 Конечный автомат

будем называть зеркальным для автомата (1.1)

к = л

и обозначать КЕ, если условие 7^(91,92) Э а выполнено тогда и только тогда, когда 7(^2, Ч\) Э а.

Очевидно, что автомат Кк задаёт зеркальный (инверсный) к Ь язык Ьк.

Через и С к* (я) будем обозначать входной и выходной языки

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

(д.ЕД^М) и .

соответственно.

Уточним понятие и принцип построения канонического автомата, применяемые в настоящей диссертации10. А именно, после получения некоторого детерминированного автомата для заданного языка - пусть автомата

К = (&£,<*,{*}>)

(например - на основе некоторого недетерминированного автомата К (1.1)), мы на множестве, содержащем все неупорядоченные пары раз-

10 Согласно монографиям [24] и [32], мы в данной диссертационной работе приведём модификацию этого алгоритма, которая является более удобной для описания алгоритмов построения базисного конечного автомата. При описании этой модификации использовался алгоритм, рассматривавшийся в [39].

личных элементов Q плюс специальный элемент Т, рассмотрим следующее бинарное отношение >-:

• {<?ъ q2} >~ {дз, qa}, если для некоторого a G Е, имеем ¿(<7ь а) ~ {</3} и d(q2,a) = {qA}.

• {Qi,Q2} J7, если из двух состояний (71,(72 ровно одно финальное.

Далее рассмотрим - транзитивное замыкание отношения При этом C°^\qi) = С°^{с[2) тогда и только тогда, когда не выполнено условие {<71,(72} J7. Если выходные языки состояний q\ и (72 равны (т.е. эти состояния эквивалентны), то можно объединить эти состояния (при этом мы без ограничения общности считаем, что qo -не вход):

• для всех вершин г € Q множество дуг 7(7-, q{) заменяем на множество 7 (г, q{) U 7 (г, <72)

• удаляем д2 и все дуги множеств 7(г, <72) и 7(<72, г).

Задающий язык L канонический автомат L, единственный с точностью до переобозначения состояний, получается из К объединением всех пар эквивалентных состояний. L будет всюду определённым11, если добавить (при необходимости) одно бесполезное состояние N и необходимые дуги (отсутствовавшие для рассматриваемого состояния и некоторой буквы).

1.3 Структура диссертационной работы

Работа состоит из настоящего введения, основной части, содержащей три главы (2, 3 и 4), заключения (глава 5) и списка литературы.

11 Всюду определённый (total) автомат определяется согласно монографии [2]. В наших обозначениях - для каждой пары, состоящей из состояния q Е Q и буквы a G S, множество 5(q, а) непусто. (А поэтому, вследствие детерминированности рассматриваемого автомата это множество состоит ровно из 1 элемента.)

В главе 2 - первой главе основной части - определяется новый объект в теории конечных автоматов Рабина-Скотта - базисный автомат для заданного регулярного языка Ь. Этот автомат является единственным для данного языка Ь, причём является его инвариантом. Исследование базисных автоматов и является предметом представляемой диссертации.

В разделе 2.1 рассматриваются дополнительные определения и обозначения (кроме более «стандартных», приведённых ранее в разделе 1.2), необходимые для введения понятия базисного автомата. Основное из них - бинарное отношение определяемое на множестве пар состояний двух канонических автоматов (т.е. канонических автоматов для заданного языка Ь и для инверсного языка Ьл). В разделе 2.2 приводится основное введённое автором определение - определение базисного автомата. В разделе 2.3 вводятся определения прямой и обратной функций разметки, которые применяются при построении бинарного отношения при построении базисного автомата, а также могут применяться при решении многих других задач. (Впервые эти функции были введены в работе автора [8].)

В разделе 2.4 рассматривается первый подробный пример построения базисного автомата. В разделе 2.5 доказывается основное утверждение о базисном автомате - его эквивалентность определяемому им языку (точнее - эквивалентность каноническому автомату, на основе которого определяется базисный автомат). В разделе 2.6 доказывается однозначность базисного автомата.

В разделе 2.7 доказывается свойство допускающего пути любого автомата для заданного регулярного языка - свойство произвольного автомата К, допускающего рассматриваемый регулярный язык Ь, связывающее его (автомат К) с эквивалентным ему базисным автоматом. В разделе 2.8 рассматриваются ещё два примера построения базисного автомата. Эти примеры демонстрируют выполнение свойств, описанных в предыдущих разделах. В разделе 2.9 приведён ещё один алгоритм построения дуг базисного автомата.

Глава 3 посвящена основным свойствам базисных конечных автоматов и некоторым алгоритмам работы с ними, а также их примене-

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

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

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

В разделе 3.5 описываются свойства входных и выходных языков базисного автомата, которые могут также быть названы свойствами таблицы соответствующих состояний. Это - свойства, связывающие входные и выходные языки базисного автомата с входными и выходными языками состояний канонических автоматов. На основе этих свойств в разделе З.б показано, что при выполнении специальных (достаточно простых) ограничений соответствующий регулярный язык возможен для любой таблицы отношения ф.

Глава 4 посвящена применению базисных автоматов в различных задачах минимизации недетерминированных конечных автоматов, в первую очередь - в «точных», нсэвристических алгоритмах. Конкретные конечные автоматы, получаемые в таких задачах минимизации,

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

Литература

[1] А.Ахо, Р. Сети, Дж. Ульман: Компиляторы: принципы, технологии, инструменты. М.-СПб-Киев, Вильяме, 2003.

[2] А. Ахо, Дж. Ульман: Теория синтаксического анализа, перевода и компиляции. Т. 1. М., Мир, 1978.

[3] А. Ахо, Дж. Хопкрофт, Дж. Ульман : Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

[4] С.Баумгертнер, Б.Мельников: Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов - Вестник Воронеэюского государственного университета, «Системы управления и информационные технологии», №1 (2010) 5-7.

[5] С. Богомолов: О восстановлении автомата по экспериментам -Дискретная математика, №1 (1989) 135-146.

[6] В.Брауэр: Введение в теорию конечных автоматов. М., Радио и связь, 1987.

[7] А. Вахитова: Базисный конечный автомат Рабина-Скотта как инвариант регулярного языка - В кн.: «Труды научной конференции "Математическое моделирование физических, экономических, социальных систем и процессов"», Изд-во Ульяновского ун-та, 1998, 13-14.

[8] А. Вахитова: Об одном алгоритме построения функции разметки конечного автомата - В кн.: «Тезисы докладов на Международной

алгебраической конференции памяти А.Г. Куроша 1998 г.», Изд-во МГУ, 1998, 152-154.

[9] Н. Вирт: Алгоритмы + структуры данных = программы. М., Мир, 1985.

[10] А. Гилл: Линейные последователъност'ные машины. М., Наука, 1974.

[11] С.Гинзбург: Математическая теория контекстно-свободных языков. М., Мир, 1970.

[12] Р. Грэхем, Д. Кнут, О. Паташник: Конкретная Мателштика. Основание информатики. М., Мир, 1998.

[13] И. Грунский: Анализ поведения конечных автоматов. Луганск, Изд-во НПУ им. Т.Шевченко, 2003.

[14] И.Грунский, В.Козловский: Синтез и идентификация автоматов. Киев, Наукова думка, 2004.

[15] О.Дубасова, Б.Мельников: Об одном расширении класса контекстно-свободных языков - Программирование (РАН), № 6 (1995) 46-58.

[16] М. Зузанова: Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов. Дисс____канд. физ.-мат. наук: 05.13.18, Тольяттинский государственный университет, Д 212.264.03, защищена 01.07.10.

[17] Н.Иванов, Г.Михайлов, В.Руднев, А.Таль: Конечные автоматы: эквивалентность и поведение. М., Наука, 1984.

[18] Н. Крайнюков, Б. Мельников: Функция разметки состояний и базисные слова для конечных автоматов - В кн.: «Мео1сд. конф. «Совр. проблемы математики, информатики и биоинформатики», посвященная 100-летию А. А. Ляпунова», Изд-во Новосибирского государственного университета, 2010, 65-66

[19] В.В.Кудрявцев, С.В.Алёшин, A.C. Подколзин : Введение в теорию автоматов. М., Наука, 1985.

[20] Математическая энциклопедия.. Изд-во «Советская энциклопедия», М., 1979.

[21] Ю. Медведев : О классе событий, допускающих представление в конечном автомате - В кн.: «Автоматы», М., Иностранная Литература, 1956, 385-401.

[22] Б. Мельников : Некоторые следствия условия эквивалентности однозначных скобочных грамматик - Вестник Моск. ун-та, сер. Вы-числ. матем. и киб-ка, 3 (1991) 51-53.

[23] Б.Мельников: Об одной классификации последовательностных контекстно-свободных языков и грамматик - Вестник Моск. унта, сер. Вычисл. матем. и киб-ка, 3 (1993) 64-69.

[24] Б. Мельников : Подклассы класса коитекстую-свободных языков. М., Изд-во МГУ, 1995.

[25] Б.Мельников: Ещё раз о конечных автоматах - В кн.: «Учёные записки Ульяновского государственного университета. Фундаментальные проблемы математики и механики. Вып. 1, ч. 2», Изд-во Ульяновского ун-та, 1996, 13-23.

[26] Б.Мельников: Ещё раз об объединении состояний недетерминированного конечного автомата - В кн.: «Тезисы докладов XIмеэю-дународной научной конференции по проблемам теоретической кибернетики», М., Изд-во РГГУ, 1996, 139-141.

[27] Б. Мельников : Важный пример к задачам минимизации недетерминированных конечных автоматов - В кн.: «Тезисы докладов XII меоюдународной научной конференции "Проблемы теоретической кибернетики"», М., Изд-во МГУ, 1999, с. 153.

[28] Б.Мельников: Эвристики в программировании недетерминированных игр - Программирование (РАН), 5 (2001), 63-80.

[29] Б. Мельников: Однозначные конечные автоматы — Известия ВУЗов, серия «Технические науки» (Поволжский регион), № 2 (2002).

[30] Б. Мельников: Расширенный базисный конечный автомат для заданного регулярного языка - В кн.: «Тезисы докладов Х1У Межд. науч. конф. "Проблемы теоретической кибернетики"», М., Изд-во МГУ, 2005, с. 124.

[31] Б. Мельников: Мультиэвристический подход к задачам дискретной оптимизации - Кибернетика и системный анализ (HAH Украины), № 3 (2006) 32-42.

[32] Б. Мельников: Недетерминированные конечные автоматы. Тольятти, Изд-во ТГУ, 2009.

[33] Б.Мельников, А.Бросалина: Сведение задач минимизации конечных автоматов к работе с орграфами - В кн.: «Труды научной конференции "Математическое моделирование физических, экономических, социальных систем и процессов"», Изд-во Ульяновского ун-та, 1998, с. 15.

[34] Б.Мельников, А.Вахитова: Звёздная высота конечного автомата- В кн.: «Учёные записки УлГУ. Фундаментальные проблемы математики и механики. Вып. 3», Изд-во Ульяновского ун-та, 1997, 51-57.

[35] Б. Мельников, А. Зубова: Построение автомата СОМ на основе базисного автомата - Вектор науки Тольяттинского государственного университета, 2010. - №4. - 30-32.

[36] Б. A4 ельников, А.Мельникова: Новый алгоритм построения базисных конечных автоматов - В кн.: «Тезисы докладов XIII Меэ/сд. науч. конф. "Проблемы теоретической кибернетики"», М., Изд-во МГУ, 2002, с. 124.

[37] Б.Мельников, А.Мельникова: Многоаспектная минимизация недетерминированных конечных автоматов. Часть I. Вспомога-

тельные факты и алгоритмы - Известия вузов. Поволоюский регион. Физико-математические науки, 2011. - №4 (20). - 59-69. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[38] Б.Мельников, А.Мельникова: Многоаспектная минимизация недетерминированных конечных автоматов. Часть II. Оснорв-ные алгоритмы - Известия вузов. Поволэюский регион. Физико-математические науки, 2012. - №1 (21). - 31-43. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[39] Б.Мельников, И.Муллина: Об одном «быстром» алгоритме построения регулярного выражения по заданному НРС-автомату -В кн.: «Учёные записки Ульяновского государственного университета. Фундаментальные проблемы математики и механики. Вып. 3», Изд-во Ульяновского ун-та, 1997, 58-63.

[40] Б. Мельников, С. Пивнева, О. Рогова: Репрезентативность случайно сгенерированных конечных автоматов с точки зрения базисных автоматов - Стохастическая оптимизация в информатике (изд-во СПбГУ), 2010. - Том 6. - 74-82.

[41] Б.Мельников, М.Сайфуллина: О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов - Известия ВУЗов, Математика, 2009, К2 4,-67-71

[42] А. Мельникова: Свойства базисных конечных автоматов - В кн.: «Труды второй научной конференции "Математическое моделирование физических, экономических, социальных систем и процессов"», Изд-во Ульяновского ун-та, 1999, с. 11.

[43] А. Мельникова: Базисные конечные автоматы Рабина-Скотта -В кн.: «Материалы VII международного семинара "Дискретная математика и её прилоэюения". Часть II», М., Изд-во МГУ, 2001, 170-172.

[44] А. Мельникова: Свойства базисного конечного автомата как инварианта регулярного языка - В кн.: «Тезисы докладов Меэ/сд.

научно-практ. конф. "Методы и алгоритмы прикладной математики в технике, медицине и экономике"», Новочеркасск, Изд-во ЮРГТУ (НПИ), 2001, с. 49.

[45] А. Мельникова: Варианты некоторых вспомогательных функций для эвристических алгоритмов - В кн.: «Материалы I меоюду-пародной научной конференции "Проблемы математического образования и культуры". Часть 2», Тольятти, Изд-во ТГУ, 2004, 132-135.

[46] А. Мельникова: Базисные автоматы в решении проблемы оптимизации - Вестник Тамбовского государственного университета, сер. Естественные и тех науки, Тамбов, 2007. Т. 12. Выи.4. 492-494. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[47] А. Мельникова: Применение свойств конечных автоматов в алгоритмах вершинной минимизации - Вестник Тамбовского государственного университета, сер. Естественные и тех науки, Тамбов, 2009. Т. 14. Вып.4, 763-765. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[48] А. Мельникова: К вопросу о сходимости значении динамических функций риска - Вестник транспорта Поволоюья, Т. 24. - Вып.4.

- Самара: Изд-во СамГУПС. - 2010. - 11-15. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[49] А. Мельникова: Пример использования базисных конечных автоматов - Развитие и перспективы вузовской наукой и образования в современных условиях. Сборник научных статей: в 2-х частях.

— 1 часть. — Димитровград: ДИТИ., 2012. - 110-114.

[50] А. Мельникова: Некоторые свойства базисного автомата - Вестник Вороиео1сского государственного университета. Серия «Физика. Математика», № 2. - 2012. - 184-189. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[51] Ф. Новиков : Дискретная математика для программистов. СПб, Изд-во «Питер», 2002.

[52] Общая алгебра. Т. 1. М., Наука, 1990.

[53] Общая алгебра. Т. 2. М., Наука, 1991.

[54] А. Оллонгрен : Определение языков программирования интерпретирующими автоматами. М., Мир, 1977.

[55] О.Ope: Теория графов. М., Наука, 1980.

[56] А. Саломаа: Жемчуэюины теории формальных языков. М., Мир, 1986.

[57] В. Твердохлебов : Логические эксперименты с автоматами. Изд-во Саратовского государственного университета, 1988.

[58] В. Твердохлебов : Геометрические образы законов функционирования автоматов. Саратов: ООО Издательский Центр «Научная книга», 2008.

[59] Б. Трахтенброт, Я. Бардзинь: Конечные автоматы: поведение и синтез. М., Наука, 1970.

[60] В. Уфнаровский : Комбинаторные и асимптотические методы в алгебре - Сер. «Современные проблемы математики». Итоги науки и техники, М., Изд-во ВИНИТИ, 57 (1990).

[61] С. Фитиалов : Формальные грамматики. Изд-во ЛГУ, 1984.

[62] Ф.Харари: Теория графов. М., Мир, 1973.

[63] Ф.Харари, Э.Палмер: Перечисление графов. М., Мир, 1977.

[64] Дж. Хопкрофт, Р. Мотвани, Дж. Ульман : Введение в. теорию автоматов, языков и вычислений. М., «Вильяме», 2002.

[65] А.Цыганов, О.Булычов: НеО: библиотека метаэврпстик для задач дискретной оптимизации - Программные продукты и системы, 2009. - Ш. - 148-151.

[66] А.Цыганов, О.Булычов: Параллельные эвристические алгоритмы для задачи вершинной минимизации недетерминированных конечных автоматов - Вестник Воронео1сского государственного университета, «Системы управления и информационные технологии», 2010. - №1. - 60-63.

[67] М.Чирков: Основы общей теории конечных автоматов. JL, Изд-во ЛГУ, 1975.

[68] С.Яблонский: Дискретная математика. М., Наука, 1979.

[69] Языки и автоматы. М., Мир, 1975.

[70] R. Cohen, Y. Gold: Theory of w-Languages. I: Characterizations of cu-Context-Free Languages - J. Сотр. and System Sci., 15 (1977), 169-184.

[71] R. Cohen, Y. Gold: Theory of cu-Languages. II: A Study of Various Models of w-Type Generation and Recognition - J. Сотр. and System Sci, 15 (1977), 185-208.

[72] S.Eilenberg: Automata, Languages and Machines. Vol. A. N.Y., Academic Press, 1974.

[73] L. Eggan: Transitions graphs and the star height of regular events -Michigan Math. J., 10 (1963) 385-397.

[74] J. Geldenhuys, B. van der Merwe, L.van Zijl: Reducing nondeterministic finite automata with SAT solvers - Finite-state methods and natural language processing, Lecture Notes in Сотр. Sci., Vol.6062 (2010) 81-92.

[75] KHashiguchi: Algorithms for determining relative star height and star height - Inform. Comput., 78 (1988) 124-169.

[76] K. Hashiguchi: Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language - 1С A LP, 1991.

[77] J. Hroinkovic : Algorithmics for Hard Problems. Introduction to Combinatorial Optimazation, Randomization, Approximation, and Heuristics. Springer, 2003. - 544 p.

[78] J. Hromkovic : Theoretical Computer Science. Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer, 2004. - 313 p. (Имеется русский перевод: Ю.Громкович. «Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию слоэюности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. СПб, изд-во БХВ, 2010.)

[79] L. Ilie, G. Navarro, Sheng Yu: On NFA Reductions - Theory is forever, Lecture Notes in Сотр. Sci., Vol.3113 (2004) 112-124.

[80] T. Jiang, B. Ravikumar: Minimal NFA problems are hard - SI AM J. Comput., V.22, No.6 (1993) 1117-1141

[81] T. Kameda, P. Weiner: On the state minimization of nondeterministic finite automata - IEEE Trans, on Computers, C-19 (1970) 617-627.

[82] D. Kirsten: Distance desert automata and the star height problem -Theoret. Informatics' Appl., 39 (2005) 455-509.

[83] S. Lombardy, J. Sakarovitch: Star Height of Reversible Languages and Universal Automata - 5th Latin American Theoretical Informatics Symposium, LNCS, Vol.2286 (2002).

[84] S. Lombardy, J. Sakarovitch: The Universal Automaton - Logic and Automata, Texts in Logic and Games, Amsterdam Univ. Press, Vol. 2 (2008) 457-504.

[85] B. Melnikov: The equality condition for infinite catenations of two sets of finite words - Int. J. of Found, of Сотр. Sci., Vol. 4, No. 3 (1993) 267-274.

[86] B. Melnikov: A new algorithm of the state-minimization for the nondeterministic finite automata - The Korean Journal of

Computational and Applied Mathematics, Vol. 6, No. 2 (1999) 277290.

[87] B. Melnikov: 2u-finite automata and sets of obstructions of their languages - The Korean Journal of Computational and Applied Mathematics, Vol. 6, No. 3 (1999) 565-574.

[88] B.Melnikov: Once more about the state-minimization of the nondeterministic finite automata - The Korean Journal of Computational and Applied Mathematics, Vol. 7, No. 3 (2000) 655662.

[89] B.Melnikov: Discrete optimization problems - some new heuristic approaches - 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, 2005. - 73-80.

[90] B. Melnikov: On an axpansion of nondeterministic finite automata - J. of Applied Mathematics and Computing, Springer Berlin/Heidelberg, Vol. 24, No. 1-2 (2007) 155-165.

[91] B.Melnikov: Extended nondeterministic finite automata -Fundamenta Informaticae, Vol. 104, No. 3 (2010) 255-265.

[92] B.Melnikov: Once more on the edge-minimization of nondeterministic finite automata and the connected problems -Fundamenta Informaticae, Vol. 104, No. 3 (2010) 267-283.

[93] B. Melnikov, E. Kashlakova: Some grammatical structures of programming languages as simple bracketed languages - Informática (Lithuania), Vol. 11, No. 4 (2000) 441-454.

[94] B. Melnikov, A. Melnikova: Edge-minimization of non-deterministic finite automata - The Korean Journal of Computational and Applied Mathematics, Vol. 8, No. 3 (2001) 469-479.

[95] B. Melnikov, A. Melnikova: A new algorithm of constructing the basis finite automaton - Informática (Lithuania), Vol. 13, No. 3 (2002) 299-310. (Публикация автора в рецензируемом журнале, рекомендуемом ВАК.)

[96] В. Meliiikov, A. Melnikova: Some properties of the basis finite automaton - The Korean Journal of Computational and Applied Mathematics, Vol. 9, No. 1 (2002) 135-150.

[97] B. Melnikov, A. Melnikova: Some more on the basis finite automaton

- Acta Universitatis Sapientiae. Informática, Vol. 5, No. 2 (2013) 227-244.

[98] B. Melnikov, A. Radionov, V. Gumayunov: Some special heuristics for discrete optimization problems - The 8th International Conference on Enterprise of Information Systems (ICEIS-2006), Pathos (Cyprus), 91-95.

[99] B. Melnikov, N. Sciarini-Guryanova: Possible edges of a finite automaton defining the given regular language - The Korean Journal of Computational and Applied Mathematics, Vol. 9, No. 2 (2002) 475-485.

[100] B. Melnikov, A. Vakhitova: Some more on the finite automata - The Korean Journal of Computational and Applied Mathematics, Vol. 5, No. 3 (1998) 495-506.

[101] D. Perrin: Finite Automata. Handbook of Theoret. Comput. Sci., Vol. A. Elsevier Sci. Publ., 1990.

[102] M. Rabin, D. Scott: Finite automata and their decision problems -IBM J. Research and Development, Vol. 3 (1959) 114-125. (Имеется русский перевод в кн.: «Кибернетический сборник, вып. 4», М., Иностранная Литература, 1962, 58-91.)

[103] J. Sakarovitch: Elements of Automata Theory. Cambridge university press, 2009.

[104] Sheng Yu: A renaissance of automata theory? - Bulletin of the Ear. Assoc. Theor. Comput Sci, 72 (2000), 270-272

[105] A. Vakhitova: The basis automaton for the given regular language

- The Korean Journal of Computational and Applied Mathematics, Vol. 6, No. 3 (1999) 617-624.

[106] R. van Glabbeek, B. Ploeger: Five determinisation algorithms - B kh.: «Implementation and Applications of Automata. - O.Ibarra and B. Ravikumar, editors.», Springer, LNCS. - 2008. - V-;5148. - 161170.

[107] D. Wood: Gramm,ar and L Forms: an Introduction. Berlin, Springer, 1980.