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

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

СЕМЫНИНА Татьяна Валерьевна

РАЗРАБОТКА КАТЕГОРНЫХ СРЕДСТВ АНАЛИЗА ФОРМАЛЬНЫХ ЯЗЫКОВ НА ОСНОВЕ ТЕОРИИ КОНИЧЕСКИХ ТИПОВ

Специальность 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Воронеж - 2005

Работа выполнена в Воронежском государственном техническом университете

Научный руководитель доктор технических наук, профессор

Юрасов Владислав Георгиевич Официальные оппоненты: доктор технических наук, профессор

Ведущая организация Липецкий государственный технический университет

Зашита состоится 28 апреля 2005 г. в 1200 часов в конференц-зале

на заседании диссертационного совета Д 212 037.01 Воронежского государственного технического университета по адресу: 394026, г. Воронеж, Московский просп., 14.

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

Автореферат разослан «28» марта 2005 г.

Кравец Олег Яковлевич;

кандидат технических наук

Комарчук Сергей Анатольевич

Ученый секретарь

диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Диссертационная работа выполнена в рамках основного направления ВГТУ «Вычислительные системы и программно-аппаратные комплексы»

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

Для достижения поставленной цели необходимо решить следующие задачи

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

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

3 Применить комбинаторную топологию к исследованию лексической структуры формального языка

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

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

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

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

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

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

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

Практическая значимость и результаты внедрения основные теоретические и практические результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки высокоэффективных инструментальных средств программирования специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы»

Апробация работы Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах Международном семинаре «Компьютерное моделирование

электромагнитных процессов в физических, химических и технических системах» (Воронеж, 2004), Международном семинаре «Физико-математическое моделирование систем» (Воронеж, 2004), Всероссийской конференции «Интеллектуализация управления в социальных и экономических системах» (Воронеж, 2004)

Публикации Основное содержание диссертационной работы изложено в 10 печатных работах В работах, опубликованных в соавторстве, лично соискателю принадлежат в [1,2,3] разработка математической модели поиска гомоморфизмов и изоморфизмов между группами при разработки синтаксиса и семантики формальных языков, [8] оценка семантической сложности входного потока в процессе функционирования транслятора, в [9] возможность применения теорий категорий к множеств) конического типа для повышения эффективности процедур лексического анализа

Автор благодарит ФО Порпера за консультации в области структурной лингвистики

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, изложенных на 140 страницах машинописного текста, списка литературы из 84 наименований, содержит 40 рисунков

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы исследования, определены цели и задачи исследования, научная новизна и практическая значимость полученных результатов, приведены сведения о внедрении результатов работы

Первая глава посвящена исследованию современных тенденций создания средств программирования, в частности системному анализу логических конструкций формальных языков и лингвистической формализации процессов проектирования компиляторов Рассматривается классификация языков в соответствии с типом машин, способных узнавать их, так как в настоящее время существует потребность стандартизованного семантического интерфейса к программам на том или ином языке программирования Дело в том, что для реализации практически полезного интерфейса доступа к программам, особенно многомодульных (рис 1), необходимо учитывать взаимодействие основных фаз транслятора,

несогласованность в работе которых приводит к нарушению процесса трансляции

Рис 1 Структурная схема процесса подготовки исполняемой многомодульной программы

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

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

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

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

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

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

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

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

помощи конечных автоматов и каждому групповому элементу может быть сопоставлено единственное слово Это дает возможность производить быстрые и более точные вычисления объектов инвариантных по отношению к группе

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

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

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

Определение 2 Пусть О является группой, а А алфавит, и р А-»О - это отображение, которое не обязательно инъективно Продолжим g до потугруппового гомоморфизма л А —>С Если этот гомоморфизм является съюрективным, то есть, если образует О, как полугруппу, будем

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

Если дан язык Ь над А, мы будем также использовать л для обозначения сужения л А*—»О на Ь (те часть л) Наиболее интересны случаи, когда л Ь—>0 является съюрективным, то есть когда каждый элемент группы представпен, по меньшей мере, одной строкой в Ь Мы будем предполагать, что элементы языка, дают нормальную или стандартную форму элементов группы В лучшем случае, нормальная форма является единственной, те л 1,-->0 является взаимно однозначным, тогда будем говорить, что Ь имеет свойство единственности Но мы также будем рассматривать языки, которые не обладают этими свойствами Нормальные формы обычно ведут к решению проблемы слов для в, которую мы сейчас определим

Определение 3 Пусть А является алфавитом Образуем алфавит А/=АиА 1 замкнутый по отношению к обращению, следующим образом А 1 просто является множеством той же координальности что и А и не пересекающиеся с А, и ) А —>А - это инволюция переставляющая А и А 1 (то есть меняющая местами) Слово над А - это строчка над А',

Слово является сокращенным, если оно не содержит подстроки вида хх ' Множество Р(А) редуцированных слов над А, имеет естественную групповую структуру Произведение двух слов получается с помощью их

соединения и вычеркивания пар вида а обращение к слову получается путем замены каждой буквы его обращением и последующим прочтением в обратном направлении всей строки. Мы будем называть F(A) свободной группой над А. Сформулирована и доказана теорема:

Теорема 1. Пусть А является алфавитом и RcF(A) является множеством слов над А. Наименьшая нормальная подгруппа из F(A) , содержащая Ы состоит из всех слов вида:

(1)

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

Если дана группа О, такая что А является множеством групповых образующих для О, то мы распространим это выражение р до АиА"1, полагая и таким образом мы получим групповой гомоморфизм Если ядро этого гомоморфизма является наименьшей нормальной подгруппой из F(A), содержащей R, то будем говорить, что R является множеством отношений для G. И что А и R вместе образуют групповое представление для G Проблема слов в G состоит в нахождении алгоритма, который имеет на входе слово со над А и отвечает «Да» или «Нет», в зависимости от того представляет ли со тождественный элемент в G или нет.

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

является съюрективным, и такого, что обратный образ тождественного элемента под действием тоже является регулярным языком. Тогда проблема слов в G разрешима.

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

/ 'V

■•г I-*-

Рис.2. Язык регулярных выражений в абелевой группе с тремя образующими

Этот автомат допускает язык , где х является

образующей группой Z целых чисел и X является его обращением. С этим языком Z регулярно-образована, но не является группой автоматов.

Выбор множества групповых или полугрупповых образующих А для группы О дает понятие расстояния в О, где два различных элемента находятся на расстоянии единица, если они могут быть получены один из другого правым умножением на образующую Объединяя такие соседние элементы, мы получаем так называемый «граф Кэли» для О Рисунок 3 иллюстрирует это для симметричной группы с тремя элементами

(132) у (13)

О х (12)

Рис 3 Граф Кэли симметричной группы Здесь образующими являются х=(12)иу=(23)

Более обще пусть О является группой и пусть Н является подгруппой О Обозначим через Н\О множество правых подмножеств вида Щ из Н, где g обходит О Группа О действует на Н\О справа

А - множество полугрупповых образующих и Н Граф Кэли Т(И\ОД) для О по отношению к А и Н - это ориентированный, отмеченный граф, определенный следующим образом множеством вершин является Н\О, а множеством ярлыков является А Можно ввести различные ориентации графа Кэли Существует ориентированное ребро или стрелка с ярлыком х, исходящая из Щ и кончающаяся в Щ2, тогда и только тогда, когда Иногда мы будем обозначать такую стрелку следующим образом Граф Кэли Т(О,А) для О по отношению к А, тот же самый, что и граф Кэли по отношению к А и к тривиальной (нулевой) подгруппе Базовой точкой графа Кэли является комножество тождественного элемента

Если А замкнуто, по отношению к обращению, то две стрелки (Щ, х, и рассматриваются обычно, как одно ребро, обозначающее

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

которые являются гомоморфизмами Таким образом, имеется являющиеся однородным, то есть, любые две

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

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

Определение 4 Пусть G является группой и пусть А не пустое конечное множество образующих для G Мы будем предполагать, что А является замкнутым по инверсии так, что iеодезические строчки являются эффективно кратчайшими путями в графе Кэли. Для любой строки а, конический тип С (а) определяется, как множество таких строк у, что ау является геодезической Очевидно, С(а) не пусто, тогда и только тогда, когда а является геодезической, так как в этом случае оно должно включать в себя нулевую строку Кроме того, если а является геодезической, то С(а) зависит только от а, Поэтому мы можем определить конический тип C(g) элемента geG в виде Cíg) -Cía), где а является геодезической строкой, представляющей g. Все негеодезические строки-а определяют один и тот же конический тип, a именно нулевое множество, которое мы будем называть типом недостатка.

Сформируем автомат, множество состояний которого является множеством конического типа. Если число конических типов конечно, это и будет автомат с конечным числом состояний. Пусь X является коническим типом и х е А. Будем предполагать, что Х=С(а), для некоторой строки а ,и определим fj{X ,х) = С(ах ). Чтобы увидеть, что это определение является корректным, заметим, что у^С(ах), тогда и только тогда, когда аху являются геодезической строкой, а это случается тогда и только тогда когда хуеХ. Таким образом ц(Х,х)={у|хуеХ}, что не зависит от выбора а,

определяющего X. Начальное состояние автомата это С(е) то есть конический тип единичного элемента (тождественного преобразования). Каждый конический тип, кроме типа неудачи, по определению, является допустимым состоянием. Язык, допустимый этим автоматом очевидно является множеством всех геодезических представлений в А* элементов G. Для многих групп автомат, который мы сконструировали, является бесконечным. Если иметь только конечное число конических типов, то проблема слов разрешима.

В случае свободной абелевой группы с двумя образующими мы получаем автомат с конечным числом состояний, а именно с десятью состояниями (если включить состояние недостатка). Однако этот автомат не является частью автоматической структуры, так как две геодезические из базовой точки к другой вершине графа Кэли могут быть произвольно далеки друг от друга, что противоречит неравенству Липшица (см рис 4)

Рис.4. Автомат для свободной абелевой группы

Этот автомат является частным автоматом для свободной абелевой группы с образующими х и у с обратными X и У соответственно. Автомат допускает все строки, которые являются кратчайшими представлениями некоторого группового элемента. Каждый групповой элемент g представлен некоторым конечным числом различных строк, но не существует верхней границы для этого числа, когда g меняется. Состояние неудачи в этом автомате опущено.

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

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

является шаром радиуса г с центром в точке х. Другими словами, каждая

точка из А находится на расстоянии не более г от некоторой точки из А' и наоборот.

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

Предположение, что число к>1, такое, что для любых двух геодезических строк и и V над А, их образы при преобразовании я:А*-+0 находятся на расстоянии не более единицы друг от друга. Для любых двух таких геодезических строк имеем, что расстояние Хаусдорфа между путями

и и V в графе Кэли

Г(0,А)<к (2)

Пусть существует число к с такими свойствами. Пусть Ь0 является языком над данным множеством геодезических строк над А. Тогда (А,Ь0) является автоматической структурой для в. В работе доказано следующее утверждение.

Теорема 2. Пусть а и р являются двумя элементами из Ц

порождающие геодезические а и р в Г, начинающиеся в отмеченной точке

и заканчивающиеся на расстоянии не больше единицы, тогда акр равномерно удалены дру[ от друга на расстоянии не больше 2к.

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

¡а|> / >0 (3)

По предположению, существует 5 такое, что

|/?|>*>0 (4)

и такое что

(¡{а{1)М))<к (5)

Тогда

,*-1\<к (6)

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

й{а(1)М))<2к (7)

для всех I.

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

Пусть V - является автоматом, допускающим Ь. Пусть N является шаром радиуса 2к в в, с центром в единичном элементе. Мы построим

стандартные автоматы , для хе А j \е\, основанных на (V,N). Язык = е L : {со,со') е L(Mt)=> \т\ < |®'|| (8)

является регулярным.

Аналогично

¿' = (U Lxxyj{s})nL (9)

тоже регулярен.

Обозначим через L" наибольшее префиксно - замкнутое подмножество из L ' .L" тоже является регулярным. Мы утверждаем, что L" совпадает с языком L„ геодезических строк L. Нулевая строка является геодезической и содержится в L, так как L является префиксно замкнутым. Поэтому s е Lu и seL". Возьмём теперь со е L", которое jft>|>0 и предположим, что со~ш

для некоторых хеА. Тогда usL'' так как L" является префиксно замкнутым, и по индукции и является геодезической строкой в L. Пусть v е L является

геодезической строкой с v = их . По предположению и и v равномерно удалены на расстояние не более чем 2к друг от друга. Так как и и v обе принадлежат L, то определение М, показывает, что (u,v) допустима М,.

По определению L", мы имеем uxeL' и таким образом, и е /. , , откуда следует что v строго длиннее, чем и. Отсюда следует, что й) = ш тоже является геодезической.

Обратно, предположим, что со является геодезической в L. Мы должны показать, что шеЬ'. Мы покажем, путём индукции по длине, что любой префикс и для о) е /,'.

Случай нулевого префикса является тривиальным. Допустим, что u-vх для некоторого хе А. Так как L является префиксно замкнутым, то veL . Мы должны показать, что v € Lx. Другими словами, что если пара (vj v') допустима для М,, то v' длиннее, чем v . Но и - является геодезической, представляющей тот же элемент из G, что и v'. Отсюда |v'|>H>jv!. (10)

Пусть п>0 - целое число, Пусть B-является замкнутым шаром радиуса п в графе Кэли для G, с центром в единичном элементе, п-уровнем элемента geG мы будем называть множество элементов heB, таких, что d{gh,e)<d{g,e), где е - это единичный элемент G. Заметим, что п-уровень элемента g пуст, тогда и только тогда когда g=e.

Применим теорию категорий Люстерника-Шнирельмана к множествам конического типа для оценки сложности входного потока символов в терминах топологических инвариантов.

Сформулируем понятие категории для семейства кривых на поверхности рода 0; оно является обобщением понятия категории на функциональное пространство: Будем называть нормальное семейство линий

на поверхности 8 семейством категории 1 в Ь, если оно сводимо путем нормальной деформации к нулевому гтеченту функционального пространства Ь , Нормальное семейство А называется семейством категории к в Ь, если оно может быть разбито на к семейств категории 1 и не может быгь разбито на меньшее число таких семейств Будем обозначать са^А^к

Например, нормальное семейство, не покрывающее поверхности, 8 обладает категорией 1 в Ь В самом деле, всякая часть поверхности сводима к точке Следовательно, часть поверхности, покрытая нашим семейством, сводима вместе с ним к точке

Семейство кривых называется 1 раз покрывающим поверхность, если через каждые 1 точек поверхности проходит хотя бы одна кривая семейства

Замкнутое семейство, покрывающее поверхность не более чем к раз, имеет категорию в Ь не более к+1

Действительно, пусть А есть такое семейство Можно указать группу из к+1 точек а ,а2, ,акч нашей поверхности, через которые не проходит ни одна кривая семейства Расстояние любой кривой семейства от совокупности точек (аьа2, ,ак»0 не равна нутю, и нижняя грань £ этих расстояний оттична от н/1я (мы предполагаем, что наше семейство замкнуто) Обозначим через А совокупность кривых, расстояние которых от гочки а не меньше, чем £ Всякая кривая входит хотя бы в одно из А , так как в противоположном случае расстояние этой кривой от совокупности (аьа-., а Л было бы меньше е При этом имеем А, А2, |

са|А,-1, что доказывает наше предположение 1аким образом доказана возможность установления формального соо[ветс1вия между автоматическими группами и квазигеодезическими, основанная на использовании 1 опологических свойств квазигеодезических и позволяющая применять методы комбинаторной топологии к лексическому анализу

Четвертая глава посвящена приложению результатов теоретического исследования к решению задач лексического анализа в процессе компиляции программ

Значение лексемы сопровождает ее на этапе синтаксического анализа (рис 5) где лексема выступает как терминальный симвоп и передается далее фазе семантического анализа В процессе синтаксического анализа, при "свертывании" правила, в котором в качестве терминалов фигурируют имена, вызывается семантическая процедура, соответствующая этому правилу Она должна потучить ссылки на эти имена из соответствующих лексем,

Исходная программа

Синтаксическим анализатор

Сканер Лексический анализатор) \ 1 Обращение за 1 очередным с ювом ' (лексемой)

1 - - « И -

Рис 5 Работа лексического и синтаксического анализаторов

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

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

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

Рис б Структурная схема алгоритма работы сканера

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

ОСНОВНЫЕ РЕЗУЛЬ ГА ГЫ РАБОТЫ

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

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

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

4 Разработан метод определения автоматичности формальной системы, отличающийся использованием свойств близости геодезических в

метрике Хаусдорфа, и позволяющий устанавливать применимость развитой теории к анализу формальных языков.

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

6. Основные теоретические и практические результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки инструментальных средств программирования микропроцессоров специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».

Основные результаты диссертации опубликованы в следующих работах:

1. Семынина Т.В. Оценка числа стационарных точек для функций, заданных на конечных автоматах // Физико-математическое моделирование систем: Материалы Междунар. семинара. Воронеж, 2004. С. 34-39.

2. Агранович Ю.Я., Семынина Т.В. О вероятностном смысле геометрической информации // Вестник Воронеж, гос. техн. ун-та. Сер. Радиоэлектроника и системы связи. 2001. Вып. 4. С. 92-95.

3. Семынина Т.В., Юрасов ВГ. К теории регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах: Математический 3-й Междунар. семинар. Воронеж, 2004. С. 254-257.

4. Юрасов В.Г., Агранович Ю.Я., Семынина Т.В. Методы метризации информационного пространства на основе конечных геометрий // Интеллектуализация управления в социальных и экономических системах: Тр. Всерос. конф. Воронеж, 2004. С. 266-268.

5. Агранович Ю.Я., Семынина Т.В., Юрасов В.Г. Обзор методов абстрактной теории автоматов в разработке конечных геометрий информационного пространства // Интеллектуализация управления в социальных и экономических системах: Тр. Всерос. конф. Воронеж, 2004. С.275-277.

6. Семынина Т.В. О возможности применения теорий категорий к множеству конического типа // Физико-математическое моделирование систем: Математический Междунар. семинар. Воронеж, 2004. С 144-161.

7. Агранович Ю.Я., Семынина Т.В. Определение геометрической информации и энтропии // Некоторые аспекты экономики, методики обучения, истории кооперации, права и товароведения современной России: Межвуз. сб. научн. тр. Воронеж: БУПК, 2001. С.172-179.

8. Семынина Т.В. Основные свойства регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах: Материалы 3-го Междунар. семинара. Воронеж, 2004. С. 307-311.

9. Семынина Т.В., Агранович Ю.Я. О геометрической структуре информационного пространства // Обеспечение прогрессивного развития хозяйственных структур в транзитивной экономике: Межвуз. сб. научн. тр. Воронеж: БУПК, 2002. С. 205-215.

10. Семынина Т.В., Юрасов В.Г. Проектирование обобщённых конечных автоматов // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах: Материалы 3-го Междунар. семинара. Воронеж, 2004. С.:

Подписано в печать 25.03.2005. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ № 4Z6.

Воронежский государственный технический университет 394026 Воронеж, Московский просп., 14

OïM - os. #

/* / с *

f í<

V * »

2 2 АПР1Й5

j-

272

Введение.

1 Анализ логических конструкций формальных языков.

1.1 Исследование алгоритмов формирования многомодульных программ.

1.2 Языки и регулярные языки.

1.2.1 Алфавиты и языки.

1.2.2 Регулярные выражения.

1.3 Автомат с конечным числом состояний.

1.3.1 Проектирование автомата с конечным числом состояний.

1.3.2 Гипотеза отождествления.

1.3.3 Префиксное замыкание.

1.4 Просто звёздные языки.

1.4.1 Ограничения размера языка.

1.4.2 Однобуквенный автомат.

1.4.3 Условия полиномиального роста.

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

1.5.1 Регулярные предикаты.

1.5.2 Языки со многими переменными.

1.5.3 Исчисление и замкнутость предикатов.

Цель и задачи исследования.

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

2.1 Группы, как языки.

2.1.1 Структура автоматов для групп.

2.1.2 Построение алгоритма для решения проблемы слов.

2.2 Графы Кэли и изометрические неравенства.

2.2.1 Граф Кэли для различных групп.

2.2.2 Превращение графа Кэли в метрическое пространство.

2.2.3 Ограничение длин.

2.3. Группы автоматов.

2.3.1 Свойство Липшица для групп автоматов.

2.3.2 Стандартные автоматы.

2.3.3 Ограничение длин.

2.4. Инвариантность при замене образующих.

2.4.1 Изменение образующих.

2.4.2 Улучшение автоматической структуры.

2.4.3 Биавтоматичность.

2.4.4 Префиксное замыкание групп автоматов.

Выводы.

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

3.1 Квазигеодезические, псевдоизометрия, поочередная комбинация.

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

3.3 Кратчайшие строки.

3.3.1 Множества конического типа.

3.3.2 Нахождение уровня элемента группы.

3.3.3 Применение теории Люстерника - Шнирельмана к множествам конического типа.

3.4 Псевдоизометрии.

3.4.1 Псевдоотображения.

3.4.2 Равносильность группы и действующего пространства.

3.4.3 Оценки числа стационарных точек.

Выводы.

4 Определение оценки сложности символьного текста в терминах топологических инвариантов.

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

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

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

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

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

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

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

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

- метод категорного' анализа, позволяющий повысить эффективность процедур лексического анализа в сканерах входного потока, основанный на применении теории конических типов для вычисления уровня элемента группы;

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

- метод определения автоматичности формальной системы, отличающийся использованием свойств близости геодезических в метрике Ха-усдорфа, и позволяющий устанавливать применимость категорных методов к анализу формальных языков программирования;

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

Практическая значимость и результаты внедрения: основные теоретические и практические' результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки высокоэффективных инструментальных средств программирования специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международном семинаре «Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах» (Воронеж, 2004), Международном семинаре «Физико-математическое моделирование систем» (Воронеж, 2004), Всероссийской конференции «Интеллектуализация управления в социальных и экономических системах» (Воронеж, 2004).

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

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

4.4 Выводы

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

Заключение

Задачи о способе представления информации в памяти компьютера остаются особенно важными и актуальными в развитии информационных технологий в целом. Современный информационный рынок характеризуется быстрым появлением новых микропроцессоров и микроконтроллеров. Ожидать предоставления аппаратного прототипа перед началом разработки программного обеспечения в настоящее время означает рисковать своим проектом. Ликвидировать постоянное отставание процессов создания программного обеспечения от появления технических средств позволяет одновременная разработка программного и аппаратного обеспечения, что в результате приводит к повышению эффективности проектных работ и ускорению выхода нового изделия на рынок. Сложность рассматриваемой проблемы приводит к необходимости развития исследований в области математической теории программирования в направлении разработки и внедрения новых методов синтаксиса и семантики языков программирования и их оптимизации, отражающих современные комбинаторно-геометрические методы анализа. Корректная постановка соответствующих задач требует глубокого изучения содержания понятия «формальный язык». Специфика проектируемых объектов определяет особенности разработки алгоритмов, в основе которых лежит синтез современных результатов теории автоматов - конечные автоматы и семантического решения различного рода алгоритмических задач. В рамках исследования этих проблем были получены следующие результаты:

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

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

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

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

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

6. Основные теоретические и практические результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки инструментальных средств программирования микропроцессоров специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».

1. Автоматизация проектирования сложных логических структур/ В.А. Горбатов, В.Ф.Демьяник, Г.Б.Кулиев и др. Под ред В.А.Горбатова. — М.: Энергия, 1978. —

2. Агранович Ю.А. Геометрическое моделирование структуры информационного пространства // серия «Моделирование, оптимизация и компьютеризация с ложных системах», книга 13 — Воронеж: ВГТУ, 2000.

3. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. — М.-Л., 1948.

4. Александров П.С. Общая теория гомологии. Уч. зап. МГУ, 1940, вып. 3-7. О гомологических свойствах расположения комплексов и замкнутых множеств. Изв. АН СССР, сер. матем., 1942, 6, № 5.

5. Батыршин И.З. Лексикографические оценки правдоподобности с универсальными границами. II Операции отрицания. Теория и системы управления. Изв. АН РАН. - 1995. - № 5. - с. 133-151.

6. Бишоп Р.Л., Криттенден Р. Дж. Геометрия многообразий. Пер. с англ. -М., 1967.

7. Блисс Г.А. Лекции по вариационному исчислению. — Пер. с англ. — М., 1950.

8. Бураго Ю.Д. Неравенства изопериметрического типа в теории поверхностей ограниченной внешней кривизны. М., 1968.

9. Вишик М. Некоторые вопросы почти-изометрических отображений. Ю.Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическоепроектирование дискретных автоматов. М.: Наука, 1977. —

10. Гекке Е. Теория алгебраических чисел. — М., 1939.

11. Генис А.Л. Метрические свойства эндоморфизмов п-мерного тора // «Доклады АН СССР», т. 138, № 5. М., 1961.

12. Гладкий A.B. Формальные грамматики и языки. -М., 1973.

13. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. -М.: Кибернетика, 1965.

14. Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов. — Изв. АН СССР. Техническая кибернетика, 1970, № 4

15. Горбатов В.А. Проблемы оптимизации сложных систем логического управления. В кн.: Оптимизация дискретных систем управления. -М.: ГВЦ Госплана СССР, 1972.

16. Горбатов В.А. Семантическое эквивалентирование сложных систем. — В кн.: Семиотические методы управления в больших системах. — М.: МДНТП, 1971.

17. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука, 1999. — 544 с.

18. Громов М. Гиперболические группы. М. - Ижевск: 2000. - 159 с.

19. Громов М. Знак и геометрический смысл кривизны. — М.- Ижевск: РХД, 2000.- 160 с.

20. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969. —

21. Ивахненко А.Г. Моделирование сложных систем: информационный подход. — К.: «Наукова думка», 1987. 136 с.

22. Курош А.Г. Общая алгебра (лекции 1969 1970 уч. г.). -М.: Наука, 1974.- 159 с.

23. Курош А.Г. Теория групп,- М.: Наука, 1967. 648 с.

24. Курош А.Г., Лившиц А.Х., Шульгейфер Е.Г. Успехи математических наук. Т. 15.-М., 1960.

25. Лаврентьев М.А., Люстерник Л.А. Курс вариационного исчисления. 2-еизд.-М.-Л., 1950.

26. Ленг С. Введение в теорию дифференцируемых многообразий.- Пер с англ.-М., 1967.

27. Люстерник Л. Пересечения в линейных в малом функциональных пространствах. ДАН XXVII, 1940, № 8.

28. Люстерник Л.А. Замечания к некоторым вариационным задачам. Уч. зап. МГУ, 1934, вып. 2, 17-23

29. Люстерник Л.А. и Щнирельман Л.Г. Топологические методы в вариационных задачах. Труды Научно-исслед. инст. мат. и мех. М., 1930.

30. Люстерник Л.А. и Щнирельман Л.Г. Применение топологии к экстремальным задачам. Труды Второго всес. матсъезда. М., 1935, т.1

31. Люстерник Л.А. Топология функциональх пространств и вариационное исчисление в целом. М.-Ленинград: Издательство АН СССР, 1947.-100 с.

32. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. -2- е изд., перераб. М.: Наука, 1965. - 522 с.

33. Майника Э. Алгоритмы оптимизации на сетях и графах. -М.: Мир, 1981. —

34. Марков A.A. Теория алгоритма. // «Труды математического института АН СССР», т. 42, М.-Л., 1952.

35. Марковский A.B. Анализ структуры знаковых ориентированных графов // Изв. АН. Теория и системы управления,- 1997. № 5. - с. 144149.

36. Мелихов А.Н., Бернщтейн Л.С., Коровин С.Л. Ситуационные советующие системы с нечетко логикой. М.: Наука, 1990. - 272 с.

37. Новиков П.С. Конструктивная математическая логика с точки зрении классической. -М.: Наука, 1977. —

38. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-е изд., перераб. и доп. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 336 с.

39. Общая теория систем. М.: Мир, 1977.

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

41. Поспелов Д.А. Логико-лингвистические модели в системах управления. М.: Энергия, 1981.

42. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. - 128 с.

43. Рохлин В.А. Об энтропии автоморфизма компактной коммутативной группы // «Теория вероятностей и его применения», т. 6, вып. 3 — М., 1961.

44. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

45. Семынина Т.В. Оценка числа стационарных точек для функций, заданных на конечных автоматах // Физико-математическое моделирование систем: Мат. меж. сем. Воронеж: ВГТУ, 2004.С.34-39

46. Семынина Т.В. О возможности применения теорий категорий к множеству конического типа // Физико-математическое моделирование систем: Мат. меж. сем. Воронеж: ВГТУ, 2004.С 144-161.

47. Семынина Т.В., Юрасов В.Г., К теории регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.254-257.

48. Семынина Т.В., Юрасов В.Г., Проектирование обобщённых конечных автоматов // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.311 -318.

49. Семынина Т.В.Основные свойства регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.307-311.

50. Семынина Т.В., Агранович Ю.Я. О вероятностном смысле геометрической информации // Вестник вып. 4. Воронеж.: ВГТУ, 2001. С.92-95.

51. Семынина Т.В., Фурсова С.А., Организация самостоятельной работы студентов в соответствии с требованиями государственных общеобразовательных стандартов // Интеллектуальные информационные ситемы: Всерос. конф. Воронеж ВГТУ, 2000. С. 146147.

52. Семынина Т.В., Агранович Ю.Я. О геометрической структуре информационного пространства // Обеспечение прогрессивного развития хозяйственных структур в транзитивной экономике: Межвуз. сб. научн. тр. Воронеж: БУПК, 2002. С.205-215.

53. Семынина Т.В., Юрасов В.Г., Агранович Ю.Я. Методы метризации информационного пространства на основе конечных геометрий // Интеллектуализация управления в социальных и экономических системах: Тр. Всерос. конф. Воронеж: ВГТУ, 2004. С.266-268.

54. Семынина Т.В., Агранович Ю.Я. Определение геометрической информации и энтропии // Некоторые аспекты экономики, методики обучения, истории кооперации, права и товароведения современной России: Межвуз. сб. научн. тр. Воронеж: БУПК, 2001. С. 172-179.

55. Сигалов А. Почти-изометрические отображения и псевдодифференцируемость. ДАН, 1946, № 1.

56. Синай Я. О понятии энтропии динамической системы. ДАН, т. 124, № 4,-М., 1959.

57. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

58. Хинчин А .Я. Понятие энтропии в теории вероятностей // «Успехи математических наук», Т.8, вып. 3. — М., 1953.

59. Цаленко М.Ш., Шульгейфер Е.Г. Основы теории категорий. М., 1974.

60. Эльсгольц Л.Э. Длина многообразия и ее свойства. Мат сб., 1939, № 3.

61. Эльсгольц Л.Э. Теория вариантов, дающих оценку числа критических точек непрерывной функции, заданной на многообразии. Мат сб., 1939, №5.

62. Alonso J.M. Combings of groups. To appear in MSRI Proceedings of the workshop on algorithms, word problems and classification in combinatorial group theory. 1989. - p.220

63. Anick D.J. On the homology of associative algebras. TAMS. 1986. -p.220.

64. Artin E. Theory of braids. Annals of mathematics, 1947. p.240.

65. Baumslag G., Gersten S.M., Shapiro M., Short H. Automatic groups and amalgams. Unpublished, p.280.

66. Birman J.S. Braids, Links and mapping Class Groups. Princeton Univ.press. - 1975. - p.245.

67. Bowditch B.H. Geometric finiteness for hyperbolic groups. Preprint, originally Warwick Ph.D. thesis, 1988 -p.266.

68. Bowditch B.H. Notes of Gromov's hyperbolicity criterion. In Group theory a geometric viewpoint. World Scientific, Singapore, to appear. Proceedings of the ISTP conference in summer, 1990. p.80.

69. Buchberger B., Loos R. Algebraic simplification. In Buchberger B., Collins G.E., Loos R., editors. Computer Algebra, Simbolic and Algebraic Computation, Second Edition. Springer-Verlag, New-York, 1982.— p. 113.

70. Epstein D.B.A., Cannon J.W., Holt D.F., Levy S.V.F., Paterson M.S, Thurston W.P., Word Processing in Groups, Jones and Bartlett, Boston MA, 1992

71. Jaco W., Shalen P. Seifert fibre spaces in 3-manifolds, 1979. p. 274.

72. Johannson K. Homotopy equivalence of 3-manifolds with boundaries. Springer-Verlag, Berlin, New-York, 1979. p. 274.

73. Kapovich M., Potiagailo L. On the absence of Ahlfors' Finiteness Theorem for Kleinian groups in dimension-3, 1991. p.270.

74. Knuth D.E., Bendix P.B. Simple word problems in universal algebra. In Leech J., editor, Computational problems in abstract algebras. Pergamon Press, 1970.-p. 300.

75. Koebe P. Allgemeine Theorie der Riemannischen Mannigfaltigkeiten, 1927. -p.460.

76. Koebe P. Riemannischen Mannigfaltigkeiten und nichteuklidische Raumformen, 1929. p.460.

77. Lundell A.T., Weingram S. The topology of CW complexes. Van Nostrand. New-York, 1969. - p.250.

78. Macdonald I.D. The theory of groups. Oxford University Press, Oxford, 1968.-200.