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

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

005002539

Великая Яна Геннадьевна

/Г

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

Специальность 05.13.17 - Теоретические основы информатики (технические науки)

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 7 НОЯ 2011

Белгород - 2011

005002539

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), факультет компьютерных наук и телекоммуникаций, кафедра математического и программного обеспечения информационных систем.

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

доктор физико-математических наук, доцент [Хачатрян Владимир Ервандович|

Официальные оппоненты

доктор технических наук, профессор, заслуженный деятель науки РФ, Корсунов Николай Иванович

доктор технических наук, профессор Константинов Игорь Сергеевич

Ведущая организация

кандидат технических наук, доцент Коробкова Елена Николаевна

Московский государственный университет имени М.В. Ломоносова

Защита состоится 24 ноября 2011 года в 15 часов на заседании диссертационного совета Д 212.015.10 при ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ») по адресу: 308015, г. Белгород, ул. Победы, д. 85, корпус 15, ауд.3-8.

С диссертацией можно ознакомиться в библиотеке ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ).

Автореферат разослан октября 2011 года

Ученый секретарь диссертационного совета Д 212.015.10

кандидат технических наук, старший научный сотрудник ' Белов С.П.

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

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

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

Весомый вклад в развитие теории конечных автоматов внесли Глушков В.М., Бернштейн Л.С., Скляров В.А., Баранов С.И., Трахтенброт Б.А., Бауэр В., Мили Г., Мур Э., Гилл А., Хаффмен Д., Хопкрофт Д., Рабин М., Скотт Д. и др. В исследованиях учёных решены вопросы, связанные с проблемой минимизации, проблемой эквивалентности и эквивалентных преобразований конечных автоматов. В работе В.М. Глушкова разработана теоретическая база для решения задач, возникающих при синтезе цифровых автоматов. Кроме конечного автомата известна модель многоленточного автомата, которая является расширением обычного конечного автомата. В многоленточном автомате в отличие от конечного автомата работа производится на нескольких лентах. Теория многоленточных автоматов развивалась отечественными и зарубежными учёными Подловченко Р.И., Хачатряном В.Е., Летичевским А.А, Бёрдом Р., Гриффитсом Т., Харью Т., Кархумяки Дж., Тамм X. и др.

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

Известны реализации специализированных языков, в которых многоленточный автомат используется, в качестве модели для обработки строк. Запрос, написанный на специализированном декларативном языке, представляет собой пользовательскую функцию для обработки строк базы данных, которая преобразуется в многоленточный автомат. Полученный по функции многоленточный автомат хранится в виде объектного кода и используется при вызове функции. Данный подход позволяет расширять реализованный в СУБД язык, вызывая из него функции, написанные на специализированном декларативном языке. Следовательно, многоленточный автомат даёт возможность использовать его в качестве модели представления программ специализированных языков, работающих со строками. Однако, недостаточная проработка теории многоленточных автоматов, не позволяет

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

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

Работа связана с развитием общенаучных направлений РФ и поддержана грантом ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», ГК №16.740.11.0045 от 01.09.2010 г.; грантом РФФИ, проект 09-01-00277, «Обобщенная проблема минимизации многоленточных автоматов при моделировании управляющих систем», 2009-2011 гг.

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

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

• разработать систему эквивалентных фрагментных преобразований в подклассе многоленточных автоматов и доказать её полноту;

• обобщить трансформационный метод решения проблемы эквивалентности для подклассов многоленточных автоматов;

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

• разработать алгоритмы и программы минимизации многоленточных автоматов;

• исследовать временную сложность полученных алгоритмов.

Объектом исследования диссертационной работы являются

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

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

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

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

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

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

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

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

Научная новизна состоит в:

1) разработке новой системы эквивалентных преобразований для подкласса многоленточных автоматов;

2) формулировке и доказательстве теоремы о полноте предложенной системы эквивалентных преобразований;

3) модификации трансформационного метода для решения проблемы эквивалентности в подклассах многоленточных автоматов;

4) разработке алгоритмов минимизации для подкласса многоленточных автоматов.

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

1)в реализации результатов диссертации при проектировании интерпретатора специализированного языка запросов автоматизированной системы дистанционной передачи радиолокационных измерений с приёмного устройства на спецвычислитель, внедрённой в ООО «Научно-производственное предприятие «Энергетические и информационные технологии» Белгородского государственного университета».

2) разработаны алгоритмы процедуры минимизации для подмножества многоленточных автоматов, использованные при выполнении фундаментальных исследований, выполненных в рамках тематического плана НИР ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), проект «Методы и алгоритмы преобразования структурированного представления модели управления последовательностью процессов, наделенных частично-коммутативными свойствами», 2010-2012 гг.

3)в использовании результатов диссертационной работы в учебном процессе кафедры математического и программного обеспечения информационных систем ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), при подготовке студентов по специальности 010503 «Математическое обеспечение и администрирование информационных систем», в дисциплине «Теория вычислительных процессов и структур», при обучении студентов по направлению подготовки 010300.68 «Математика. Компьютерные науки», в дисциплине «Теоретическая информатика».

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

международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ, 2009), Первой международной научно-технической конференции «Компьютерные науки и технологии» (Белгород, БелГУ, 2009), Десятом международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ, 2010), Десятой международной научно-технической конференции «Проблемы информатики и моделирования» (Харьков, Национальный технический университет «ХПИ», 2010), на международной научно-технической конференции «Информационные системы и технологии» (Орел, ОрелГТУ, 2010), на международной научно-технической интернет-конференции «Информационные системы и технологии» (Орел, ОрелГТУ, 2011), Девятнадцатой международной научно-практической конференции «Информационные технологии: наука, техника, технология, образование, здоровье» (Харьков, Национальный технический университет «ХПИ», 2011).

По результатам исследований опубликовано 16 печатных работ (из них 6 в изданиях из списка ВАК РФ), а так же получены акт о внедрении результатов диссертационной работы, свидетельства об официальной государственной регистрации программ для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа изложена на 125 страницах основного текста, включающего 65 рисунков, список литературных источников из 87 наименований и приложения, содержащего акт о реализации результатов диссертационной работы, свидетельства о государственной регистрации программ для ЭВМ, комплекс программ.

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

ПЕРВАЯ ГЛАВА посвящена рассмотрению областей информатики, в которых нашли своё применение конечные и многоленточные автоматы.

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

В связи с развитием сети Интернет актуальны задачи автоматической обработки естественных языков. Такие задачи встречаются в системах

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

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

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

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

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

• представлять многоленточный автомат в виде ориентированного размеченного графа;

• разработать полную систему фрагментных эквивалентных преобразований;

• использовать эквивалентные фрагментные преобразования для решения проблемы минимизации;

• использовать эквивалентные фрагментные преобразования для решения проблемы эквивалентности.

ВТОРАЯ ГЛАВА посвящена разработке полной системы эквивалентных преобразований многоленточных автоматов из подкласса Ь.

Многоленточный автомат будем задавать в виде размеченного ориентированного графа 0=(У,Е), где V - множество вершин, помеченных символами алфавита Р={ри р2,...,р„}, а Е - множество ребер, помеченных символами алфавита <2={0,1}. Многоленточный автомат изображён на рис. 1.

Конечный ориентированный путь ж в многоленточном автомате В задается последовательностью рёбер. Он описывается историей Ь(ц>), где Ь(м>) = (а1,Ь1)(а2,Ь2)...(ак,Ьк), где ц-это метка вершины, из которой исходиту-ое ребро пути, а - метка этого ребра,у = 1, 2, ..., к.

р,- проекцией, г = 1, 2, ..., п пути м> называется слово, полученное из Цм>) удалением всех пар, не содержащих символа р,. Два пути многоленточных автоматов являются эквивалентными, если все р-проекции, /' = 1, 2, ..., п, этих путей совпадают. Многоленточные автоматы I)/ и /)?, по определению, эквивалентны, если для любого пути, ведущего из входа в выход автомата £>/, существует эквивалентный ему путь, ведущий из входа в выход в автомате 02 и наоборот.

Классом эквивалентности называется множество эквивалентных между собой многоленточных автоматов.

Многоленточный автомат О принадлежит классу Ь, если он задается графом, вершины которого помечены символами алфавита Р={р,ць...,ц„_1}, а рёбра символами алфавита ()={0,1}. Из вершин, помеченных символами <7/,...,<7„_/, может выходить только одно ребро с меткой 0. Вершины, помеченные символом ¡=1,...,п, назовем простыми. Вершины,

помеченные символом р, назовем сложными. На рис. 1 приведен автомат из подмножества Ь. Черным кружком отмечен вход автомата (начальное состояние), перечеркнутым кружком отмечен выход автомата (финальное состояние). Рёбра, несущие метку 1, имеют жирную точку у основания.

Фрагмент многоленточного автомата б задается некоторым подмножеством вершин Кь которое включено или совпадает с V, и содержит в себе все инцидентные этим вершинам рёбра, помеченными теми же метками, что и в графе Б.

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

Фрагментным преобразованием многоленточного автомата С называют замену в автомате б фрагмента С, на фрагмент С} или наоборот, при этом многоленточный автомат С преобразуется в многоленточный автомат 5. Фрагментное преобразование задается фрагментами О/ и , участвующими в преобразовании. Фрагментное преобразование является эквивалентным, если в результате его применения к многоленточному автомату Б получим многоленточный автомат 3, такой что, многоленточные автоматы й и ¿"являются эквивалентными.

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

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

Первое эквивалентное фрагментное преобразование системы задается парой фрагментов С1 и С2. Фрагмент Су удовлетворяет следующим требованиям:

• множество его вершин может быть разбито на непересекающиеся классы: В1,В2,...,В„;

• все вершины, принадлежащие классу 5,, где 1=1,...,п, помечены одним и тем же символом;

• пусть вершины V,- и у'; , принадлежат классу В„ г'=7,...,/?, а вершины V] и V;, принадлежат классу ]=1,...,п, тогда если из у, выходит ребро, ведущее в Уу, то и из у) выходит ребро с той же меткой, ведущее в V

• пусть вершины и у',, принадлежат классу В„ 1=1,...,«, тогда если из V, выходит ребро, являющееся выходящим из фрагмента Оь то и из V'; выходит ребро с той же меткой, ведущее в ту же вершину, что и исходное ребро.

Фрагмент 02 может быть получен из следующим образом. В качестве вершин фрагмента С2 возьмем по одной вершине из каждого класса В1,В2,...,В„. Множество вершин фрагмента обозначим {Ь],Ь2,...,Ь„}, где й, принадлежит классу В-,. Если из вершин класса В1 , /=/,...,я, выходило

ребро, ведущее в вершину класса В], ]=1.....и, то строим ребро с той же

меткой, ведущее из Ь, в />у. Если в вершины класса /=/,...,«, вело ребро, входящее во фрагмент й,, то строим ребро с той же меткой и с тем же

началом, направленное в вершину ¿>;. Если из вершин класса В^, 1=1.....и,

вело ребро, выходящее из фрагмента <3/, тот строим ребро с той же меткой и с тем же концом, ведущее из вершины Л, . На рис. 2 приведён пример

Рис. 2

Второе эквивалентное фрагментное преобразование системы задается парой фрагментов С/ и С2, изображенных на рис 3. Двойными стрелками обозначено непустое множество рёбер. Фрагмент получают из фрагмента С; следующим образом. Пусть существует входящее во фрагмент б, ребро Для каждого такого ребра проделаем следующее: удалим его, а ребра, направленные в вершину г), направим в вершину гр а вершину г} удалим. Пополним фрагмент г вершинами, помеченными символом (¡¡, обозначим их <,, 5=7, ...,г, где г - это количество внешних выходов фрагмента вь Для каждого выходящего из фрагмента ребра (&„о,), где 1>=г, проделаем следующее: заменим ребро (/г„о,) на рёбра и {¡„о). Полученный фрагмент является фрагментом 02.

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

Утверждение 2.1. Фрагментное преобразование является

эквивалентным.

Утверждение 2.2. Фрагментное преобразование •^2=(С1,С2) является эквивалентным.

Рис. 3

Полнота введенной системы эквивалентных преобразований подтверждается доказательством теоремы:

Теорема 2.1. Система преобразований Г является полной для многоленточных автоматов из подкласса Ь.

ТРЕТЬЯ ГЛАВА посвящена решению проблемы эквивалентности в некоторых подклассах многоленточных автоматов с использованием трансформационного метода, который предназначен для решения проблемы эквивалентности многоленточных автоматов. Метод основан на использовании фрагментных эквивалентных преобразований многоленточных автоматов.

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

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

Подавтоматом автомата С?, обозначим его й(с), где с — вершина автомата б, называют автомат, удовлетворяющий условиям: вход автомата С(с) - это вершина с; выход автомата О(с) совпадает с выходом автомата С; ребро автомата (? принадлежит автомату С (с), если оно принадлежит пути, ведущему из вершины с в выход автомата.

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

Приведём известные шаги процесса сравнения на эквивалентность автоматов £); и й2, основанного на трансформационном методе:

1. Добавим в дерево потомков новый лист с меткой (О/ ,02).

2. Построим покрытие диаграммы и определим список пар эквивалентных вершин 5=/^/,.$';,),...,

3. Трансформируем диаграмму В2, используя эквивалентные преобразования, в диаграмму Б3, начинающуюся куполом, изоморфным

11

Рф,). Если такое преобразование невозможно, то ОиВ2 не являются эквивалентными. Для полученного купола строим список пар вершин К={(г1,г',), ...,(г„,г'Г1)}, каждый элемент которого является изоморфным образом вершин списка 5.

4. Выполним шаги 1-3 для каждой пары автоматов, входы которых заданы вершинами списка Я: ф3(г,), Б3(г',)),..., (В3(г,), Б^г'^).

В ходе сравнения на эквивалентность строится дерево потомков Т(БиБ2). Меткой корня дерева служит пара сравниваемых автоматов (БиБ2), а метками вершин - пары сравниваемых подавтоматов. Непосредственными потомками корня дерева будут вершины, помеченные парами (Б3(г/),

Оз&',)).....(Б3(Гп), Я/гУА У пар диаграмм (Б3(п), О ¡(г',)).....(Б3(г„), Б3(г'^)

будут свои потомки и т.д.

Сечение дерева Т(БиБ2), каждая вершина которого помечена парой изоморфных автоматов, называют «-сечением.

Алгоритм разрешения эквивалентности, обозначим его р, основанный на трансформационном методе, распадается на шаги. Отдельный шаг описывается процедурой г, назначение которой найти потомков для данной вершины дерева потомков с меткой (Б1,Б2)- Для этого процедура выполняет шаги 1-3 процесса сравнения на эквивалентность, описанного ранее. Если на шаге 2 процедуре не удается выполнить построение купола, то алгоритм останавливает свою работу с утверждением, что сравниваемые автоматы 01,02 не являются эквивалентными. Если при построении дерева потомков алгоритм находит а-сечение, то он может остановить свою работу с утверждением: исходные автоматы эквивалентны.

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

Автомат является автоматом с не пересекающимися циклами, если его циклы не имеют общих вершин.

Покрытием автомата Б называют дерево, все вершины и рёбра которого являются образами вершин и рёбер автомата Б с их метками. Корнем является образ входа автомата Б.

Существуют автоматы, для которых можно построить несколько покрытий. На рисунке 4.а) приведен неоднозначный автомат вместе с покрытиями, которые можно по нему построить 4.6) и 4.в).

в)

а)

6)

Рис.4 12

Автомат называют однозначным, если он обладает единственным покрытием.

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

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

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

Теорема 3.6. Алгоритм 5 является алгоритмом разрешения проблемы

эквивалентности для конечных детерминированных автоматов.

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

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

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

Теорема 3.7. Алгоритм со является алгоритмом разрешения проблемы

эквивалентности однородных автоматов.

Доказательство теоремы следует из справедливости следующих лемм.

Лемма 3.3. Если автоматы - однородные и эквивалентные, то в

дереве потомков Т(01,02) непременно имеется а-сечение.

Лемма 3.4. а-сечение в дереве потомков Т(01,02), где £); и В2 _ однородные автоматы, строится за конечное число шагов, которое задается только количеством вершин в автоматах Б/ и В2.

В ЧЕТВЕРТОЙ ГЛАВЕ решается проблема минимизации для подкласса многоленточных автоматов Ь и разрабатываются алгоритмы, реализующие процедуру минимизации.

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

Классом эквивалентности называют подмножество всех эквивалентных между собой автоматов.

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

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

Процедура минимизации состоит в следующем:

1) минимизация сложных элементов многоленточного автомата;

2) минимизация простых элементов многоленточного автомата;

3) окончательная минимизация многоленточного автомата;

4) нахождение всех минимальных многоленточных автоматов.

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

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

комбинацию эквивалентных преобразований системы Т. Для этого в многоленточном автомате отыскиваются фрагменты, применение к которым последовательности преобразований ¡=1,...,п-1, заменяет исходный

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

фрагментов, уменьшается число простых состояний в многоленточном автомате.

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

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

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

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

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

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

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

р

фф

Рис. 5

Автоматы, полученные, путём применения к автомату (рис. 5), известного алгоритма минимизации и предложенных алгоритмов минимизации, изображены соответственно на рис. 6а и 66.

Полученные автоматы имеют одинаковое количество вершин.

Известный алгоритм имеет верхнюю асимптотическую оценку временной сложности 0(п3*^* г4), где п - количество лент автомата, 5 -количество символов алфавита, г - количество вершин автомата.

Предложенные в работе алгоритмы минимизации имеют верхнюю асимптотическую оценку временной сложности 0(п*г4*т2), где п -количество лент автомата, г - количество вершин автомата, а т - количество дуг автомата.

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

Р

а

б

Рис.6

Несмотря на равное число вершин в автоматах, изображенных на рисунках 6а и 66, второй автомат (рис 66) позволяет повысить быстродействие выполнения информационных преобразований в трансляторе, системах баз данных и т.д. Это даёт наибольший эффект при использовании многопроцессорных систем за счёт повышения коэффициента загрузки процессоров, если один из процессоров с очередью команд используется для реализации операторов q и к процессоров, выбираемых из соотношения Т2=к*Т,, используется в конвейерной обработке операторов, определяемых р вершинами. Здесь 7} - время обработки операторов для q вершин, Т2 - время обработки операторов для р вершин.

В ПРИЛОЖЕНИИ помещены акт о реализации результатов диссертационной работы, свидетельства о государственной регистрации программ для ЭВМ, комплекс программ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Предложена модификация трансформационного метода, нацеленного на решение проблемы эквивалентности многоленточных автоматов.

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

5. Предложена процедура нахождения всех минимальных автоматов в классе эквивалентности для подкласса многоленточных автоматов Ь .

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах из перечня ВАК

1. Хачатрян В.Е., Великая Я.Г. Модели вычислений с однозначным покрытием // Научные ведомости БелГУ. Серия «История. Политология. Экономика. Информатика». 2009. № 7(62). Вып. 10/1. С.116-121.

2. Хачатрян В.Е., Великая Я.Г., Несвитайло A.A. Представление и обработка структурированной информации // Вопросы радиоэлектроники. Серия «Электронная вычислительная техника (ЭВТ)». 2010. Вып. 1. С. 38-44.

3. Хачатрян В.Е., Великая Я.Г., Сунцова А.И. О преобразовании модели вычислений к однозначному виду // Информационные системы и технологии. 2010. №3(59). С.45-49.

4. Великая Я.Г. Обобщенный трансформационный метод и конечные детерминированные автоматы // Научные ведомости БелГУ. Серия «История. Политология. Экономика. Информатика». 2010. №19(90). Вып 16/1 С.93-103.

5. Хачатрян В.Е., Великая Я.Г., Сунцова А.И., Несвитайло A.A. Проблема сравнения моделей представления структурированной информации // Вопросы радиоэлектроники. Серия «Электронная вычислительная техника (ЭВТ)». 2011. Вып. 1. С. 41-50.

6. Хачатрян В.Е., Великая Я.Г., Сунцова А.И. Минимизация информационных структур с почти коммутативными свойствами // Научные ведомости БелГУ. Серия «История. Политология. Экономика. Информатика». 2011. №7(102). Вып. 18/1. С.94-101.

Статьи в научных журналах

7. Великая Я.Г. Проблема эквивалентности в структурированных моделях вычислений // Вестник национального технического университета «ХПИ». 2011. № 17. С.10-15.

Публикации в сборниках научных трудов и конференций

8. Хачатрян В.Е. Великая Я.Г. О трансформационном методе распознавания эквивалентности // Дискретные модели в теории управляющих систем: сб. науч. тр. / МГУ. М: Издательство механико-математического факультета, 2009. С. 320-324.

9. Великая Я.Г., Хачатрян В.Е. Трансформационный метод и конечные детерминированные автоматы // Компьютерные науки и технологии: сб. науч. тр. / БелГУ. Белгород: ГиК, 2008. Ч. 1. С. 33-37.

10. Великая Я.Г., Хачатрян В.Е. Модификация трансформационного метода // Дискретная математика и ее приложения: сб. науч. тр. / М.: Изд-во механико-математического факультета МГУ, 2010. С.447-450.

11. Великая Я.Г. Проблема эквивалентности в структурированных моделях вычислений // Проблемы информатики и моделирования: тезисы / НТУ «ХПИ». Харьков: Изд-во НТУ «ХПИ», 2010. С. 5.

12. Хачатрян В.Е., Великая Я.Г., Сунцова А.И. Информационные структуры с почти коммутативными свойствами // Информационные

системы и технологии: материалы / ФГОУ ВПО «Госуниверситет-УНК». Орёл: ФГОУ ВПО «Госуниверситет-УНК», 2011. С. 100-104.

13. Великая Я.Г., Проблема эквивалентности в структурированных моделях вычислений // Информационные технологии: наука, техника, технология, образование, здоровье: тезисы / НТУ «ХПИ». Харьков: Изд-во НТУ «ХПИ», 2011. 4.4. С. 13.

Свидетельства о государственной регистрации программ для ЭВМ

14. Великая Я.Г. Программа построения графа с однозначным покрытием / Хачатрян В.Е., Сунцова А.И. // Программа для ЭВМ. Свидетельство о государственной регистрации программ для ЭВМ, № 2010617196 от 28 октября 2010 года.

15. Великая Я.Г. Программа выделения древовидного покрытия графа / Хачатрян В.Е., Сунцова А.И. // Программа для ЭВМ. Свидетельство о государственной регистрации программ для ЭВМ, № 2011611294 от 9 февраля 2011 года.

16. Великая Я.Г. \УеЬ-приложение для учета, контроля процесса выдачи и выполнения студентами курсовых работ / Михелёв В.М., Хачатрян В.Е. // Программа для ЭВМ. Свидетельство о государственной регистрации программ для ЭВМ, № 2010610443 от 11 января 2010 года.

Подписано в печать 19.10.2011. Формат 60x84/16. Гарнитура Times. Усл. п. л. 1,0. Тираж 100 экз. Заказ 233. Оригинал-макет подготовлен и тиражирован в ИПК НИУ «БеЛУ» 308015, г. Белгород, ул. Победы, 85

Введение.

Глава 1. Основные понятия и постановка задач.

1.1 Многоленточные автоматы.

1.2 Фундаментальные проблемы многоленточных автоматов.

1.3 Область применения автоматов.

1.3.1 Формальное проектирование программного обеспечения.

1.3.2 Разработка цифровых устройств.

1.3.3 Лексический анализ.

1.3.4 Компьютерная лингвистика.

1.3.5 8\укс11-технология.

1.3.6 Специализированные языки программирования.

1.4 Единый подход решения фундаментальных проблем.

Глава 2. Фрагментные преобразования.

2.1 Основные понятия.

2.2 Система преобразований Т.

2.3 Полнота системы Т.

Глава 3. Проблема эквивалентности многоленточных автоматов.

3.1 Трансформационный метод.

3.2 Модификация трансформационного метода.

3.3 Решение проблемы эквивалентности многоленточных автоматов, модифицированным трансформационным методом.

3.3.1 Конечные автоматы.

3.3.2 Однородные автоматы.

Глава 4. Проблема минимизации и её решение для некоторых множеств многоленточных автоматов.

4.1 Общее описание процедуры минимизации.

4.2 Минимизация по сложным элементам.

4.3 Минимизация по простым элементам.

4.4 Окончательная минимизация.

4.5 Алгоритмы минимизации.

4.6 Сравнение алгоритмов минимизации.

4.7 Применение многоленточных автоматов в многопроцессорных системах.

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

Для реализации отдельных фаз трансляции программы используют известные модели: формальные грамматики, конечные автоматы Мура и Мили, автоматы с магазинной памятью и т.д. Данные модели являются хорошо изученными и применяемыми в области информатики, связанной с теорией обработки формальных языков[1].

Весомый вклад в развитие теории конечных автоматов внесли Глушков В.М., Бернштейн Л.С.,Скляров В.А.,Баранов С.И.Драхтенброт Б. А., Бауэр В., Мили Г., Мур Э., Гилл А., Хаффмен Д., Ауфенкамп Д., Шеннон К. и др. В исследованиях ученых решены вопросы, связанные с проблемой минимизации, проблемой эквивалентности и эквивалентных преобразований конечных автоматов. В работе В.М.Глушкова разработаны теоретическая база для решения задач, возникающих при синтезе цифровых автоматов [2]. Кроме конечного автомата известна модель многоленточного автомата, которая является расширением обычного конечного автомата. В многоленточном автомате в отличие от конечного автомата работа производится на нескольких лентах. Теория многоленточных автоматов развивалась отечественными и зарубежными учёными Подловченко Р.И., Хачатряном В.Е., Летичевским А.А, Бёрдом Р., Гриффитсом Т., Харыо Т., Кархумаки Дж., Тамм X. и др.

Для многоленточных автоматов решены проблемы эквивалентности [3] и эквивалентных преобразований [4]. Однако, при решении конкретных практических задач, требуется рассмотрение лишь определенных подклассов многоленточных автоматов, следовательно, актуальной остается задача разработки систем эквивалентных преобразований для подклассов многоленточных автоматов. Проблема минимизации многоленточных автоматов остаётся открытой. Существуют решения этой проблемы для отдельных подклассов многоленточных автоматов. Из литературных источников известно применение многоленточных автоматов для реализации специализированного языка запросов к базам данных [5].

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

Работа связана с развитием общенаучных направлений РФ и поддержана грантом ФЦП "Научные и научно-педагогические кадры инновационной России на 2009-2013 годы", ГК №16.740.11.0045 от 01.09.2010 г.

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

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

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

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

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

4. разработать алгоритмы и программы минимизации многоленточных автоматов;

5. исследовать временную сложность полученных алгоритмов.

Объектом исследования диссертационной работы являются трансляторы специализированных языков запросов к базам данных.

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

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

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

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

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

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

Научная новизна состоит в:

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

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

3. модификации трансформационного метода для решения проблемы эквивалентности в подклассах многоленточных автоматов;

4. разработке алгоритмов минимизации для подкласса многоленточных автоматов.

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

1. в реализации результатов диссертации при проектировании интерпретатора специализированного языка запросов автоматизированной системы дистанционной передачи радиолокационных измерений с приёмного устройства на спецвычислитель, внедрённой в ООО «Научно-производственное предприятие «Энергетические и информационные технологии» Белгородского государственного университета».

2. разработаны алгоритмы процедуры минимизации для подмножества многоленточных автоматов, использованные при выполнении фундаментальных исследований, выполненных в рамках тематического плана НИР ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), проект «Методы и алгоритмы преобразования структурированного представления модели управления последовательностью процессов, наделенных частично-коммутативными свойствами», 2010-2012 гг.

3. в использовании результатов диссертационной работы в учебном процессе кафедры математического и программного обеспечения информационных систем ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), при подготовке студентов по специальности 010503 «Математическое обеспечение и администрирование информационных систем», в дисциплине «Теория вычислительных процессов и структур», при обучении студентов по направлению подготовки 010300.68 «Математика. Компьютерные науки», в дисциплине «Теоретическая информатика».

ПЕРВАЯ ГЛАВА посвящена рассмотрению областей информатики, в которых нашли своё применение конечные и многоленточные автоматы. Освещаются фундаментальные достижения и проблемы теории автоматов. Обоснована потребность развития теории многоленточных автоматов в целях их применения при реализации специализированных языков запросов к базам данных.

ВТОРАЯ ГЛАВА посвящена разработке полной системы эквивалентных фрагментных преобразований для подкласса многоленточных автоматов Ь.

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

Многоленточный автомат (7 принадлежит подкласса Ь, если он задается графом, вершины которого помечены символами алфавита Р={р,Ц1,.^п.1}, а рёбра символами алфавита ()={0,1}. Из вершин, помеченных символами Чь—^п-и может выходить только одно ребро с меткой 0. Предложенная система эквивалентных преобразований содержит два преобразования, доказана полнота системы в подклассе многоленточных автоматов Ь.

ТРЕТЬЯ ГЛАВА посвящена решению проблемы эквивалентности в некоторых подмножествах многоленточных автоматов с использованием трансформационного метода, который предназначен для решения проблемы эквивалентности многоленточных автоматов. Метод основан на использовании фрагментных эквивалентных преобразований многоленточных автоматов.

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

Нами предложена модификация трансформационного метода.

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

В ЧЕТВЕРТОЙ ГЛАВЕ решается проблема минимизации для подкласса многоленточных автоматов Ь и разработке алгоритмов, реализующих процедуру минимизации.

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

Классом эквивалентности называют подмножество всех эквивалентных между собой автоматов.

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

Для многоленточных автоматов из подкласса Ь предлагается процедура минимизация, которая по данной многоленточному автомату находит все минимальные в одном классе эквивалентности. Разработаны алгоритмы , реализующие процедуру минимизации. Проведено сравнение разработанных алгоритмов с известными алгоритмами [47]. Отметим, что идея и технология решения проблемы минимизации почерпнута из литературных источников[46;64], в которых предложена процедура минимизации для подкласса двухленточных автоматов (алфавит Р={р,ц}). В работе предлагается процедура минимизации для подкласса многоленточных автоматов Ь (алфавит Р={р>Чь—>с1п-1})' Для предоженной процедуры разработаны алгоритмы и комплекс программ. Показан пример применения многоленточных автоматов в многопроцессорных системах.

Заключение

Перечислим основные результаты и выводы, полученные в диссертации:

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

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

3. Предложена модификация трансформационного метода, нацеленного на решение проблемы эквивалентности многоленточных автоматов.

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

5. Предложена процедура нахождения всех минимальных автоматов в классе эквивалентности для подкласса многоленточных автоматов Ь .

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

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

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

1. Хантер Р. Основные концепции компиляторов. Москва: Издательский дом «Вильямс».2002. с.256.

2. Глушков В.М. Синтез цифровых автоматов.- М.:Физматгиз, 1962.-476 с.

3. Хачатрян B.E. Полная система эквивалентных преобразований для многоленточных автоматов // Программирование. 2003. №1. С.62-77.

4. Hakli, R., Nykanen, М., and Tamm, Н. A declarative programming system for manipulating strings. In Sixth Fenno-Ugric Symposium on Software Technology, Sagadi, Estonia, 1999, 29-40.

5. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314

6. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159.

7. Rabin М.О., Scott D. Finite automata and their decision problems // IBM J. of Research and Development, 1959, 3, № 2. p. 114125 (Русский перевод: Кибернетический сборник, 1962, № 4, с. 5891)

8. Champarnaud, J.-M., and Coulon, F. NFA reduction algorithms by means of regular inequalities. In Proceedings of DLT 2003, Lecture Notes in Computer Science 2710, Springer, 2003,194-205.

9. Elgot C.C. and Mezei J.E. On relations defined by generalized finite automata. IBM J. Res. Develop. 9, (1965), 47-68.

10. Fischer P.C., and Rosenberg, A.L. Multitape one-way nonwriting automata. J. Comput. System Sci. 2, (1968), 88-101.

11. Rabin M.O., Scott D. Finite automata and their decision problems // IBM J. of Research and Development, 1959, 3, № 2. p. 114125.

12. Griffiths T.V. The insolvability of the equivalence problem for D-free nondeterministic generalized machines. J. ACM, 15,3 (1968), 409413.

13. М.Подловченко Р.И. Алгоритм канонизации пар схем программ сперестановочными операторами // Программирование, 1997, № 6,с.316.

14. Подловченко Р.И. К вопросу об эквивалентных преобразованиях алгоритмов и программ // Математические вопросы кибернетики, М., Физматлит, 2000, вып. 9, с. 2536.

15. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314

16. Подловченко Р.И. Проблема эквивалентных преобразований в модели программ с перестановочными и монотонными операторами // Программирование, 2002, №6, с. 117.

17. Подловченко Р.И. О построении полных систем эквивалентных преобразований схем программ // Труды XII Международн. конф.

18. Дискретные модели в теории управляющих систем», М., Диалог-МГУ, 1997, с. 4647.

19. Подловченко Р.И. Система преобразований, полная в классе схем программ с перестановочными операторами // Программирование. 1998. № 2. С. 5867.

20. Подловченко Р.И., Айрапетян М.Г. О построении полных систем эквивалентных преобразований схем программ // Программирование, 1996. № I.e. 329.

21. Хачатрян В.Е. Однородные логические графы // Прикладная математика, изд-во Ереванского гос. университета. Ереван. 1981. с. 6780.

22. Подловченко Р. И., Хачатрян В. Е., Чашин Ю. Г. Полная система эквивалентных преобразований для двухленточных автоматов с непересекающимися циклами // Программирование. 2000. №5. с.119.

23. Яблонский C.B. «Эквивалентные преобразования управляющих систем», Методическая разработка по курсу «Элементы кибернетики», МГУ, ВМК, 1986, с. 140.

24. Айзерман М.А., Гусев JI.A., Розоноэр Л.И., Смирнова И.М., Таль A.A. Логика, автоматы, алгоритмы. М.: ГИФМЛ, 1963.-556 с.

25. ГлушковВ.М. Синтез цифровых автоматов.- М.:Физматгиз, 1962.-476 с.

26. Кобринский H. Е., Трахтенброт Б. А. Введение в теорию конечных автоматов. —М.: Физматгиз, 1962. —404 с.

27. Гилл А. «Введение в теорию конечных автоматов», М., Наука, 1970.-272 с.

28. Kinber E. The inclusion problem for some classes of deterministic multitape automata, Theoret.Comput.Sci. 26 (1983), 124.

29. Bird R. The equivalence problem for deterministic two-tape automata // J. of Computer and System Science, 1973, 7, № 4. p. 218236.

30. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности// Программирование. 2004. № 3. С. 117.

31. Хачатрян В.Е. О применении трансформационного метода для распознавания эквивалентности многоленточных автоматов. // VI межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2004. С. 148-150.

32. Хачатрян В.Е. Трансформационные методы сравнения моделей на эквивалентность // Научные ведомости. Серия: информатика, прикладная математика, управление. Белгород. БелГУ. 2004. с. 4051

33. Хачатрян В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4. с. 5255.

34. Подловченко Р.И., Хачатрян В.Е. Алгоритм распознаванияэквивалентности многоленточных автоматов без пересекающихся циклов

35. Труды 5-межд. конф. Дискретные модели в теории управления систем. Ратмино-Москва. 2003. с. 6770.

36. Хачатрян В.Е. Трансформационный метод в моделях вычислений // Вестник компьютерных и информационных технологий. 2008. № 4. с. 5255.

37. Хачатрян В.Е., Щербинина Н.В. К вопросу о минимизации в моделях вычислений. // Научные ведомости. БелГУ. Сер. Информатика и прикладная математика, №2(31), вып.З,. 2006. с. 4259.

38. Шишков Д.Б. Минимизация конечных автоматов//Кибернетика. 1972. Том 8. Выпуск 4.с. 297-316.

39. Carrez, С.; On the minimalization of non-deterministic automaton, Laboratoire de Calcul de la Facult.e des Sciences de l'Universit.e de Lille, 1970

40. Champarnaud, J.-M., and Coulon, F. NFA reduction algorithms by means of regular inequalities. In Proceedings of DLT 2003, Lecture Notes in Computer Science 2710, Springer, 2003, 194-205.

41. Jiang T.and Ravikumar В. Minimal NFA problems are hard. SIAM J.Comput. Vol 22, No 6, pages 1117-1141, 1993

42. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159)

43. Носков A.A., Пескова O.B., Ягунова E.B., Большакова Е.И., Клышинский Э.С., Ландэ Д.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистика : учеб. пособие. М:МИЭМ. С.272.

44. Гильмуллин Р.А. Модуль обучающейся модели татарско-турецкого машинного переводчика // Вестник Казанского государственного технического университета им. А.Н.Туполева. 2007, № 2(46) - С. 65-67.

45. André Kempe NLP Applications Based onWeightedMulti-Tape Automata. TALN 2004, Session Poster, Fès, 19-21 avril 2004.

46. Туккель H. И., Шалыто A. A. SWITCH-технология автоматный подход к созданию программного обеспечения «реактивных» систем //Программирование. 2001. № 5, с.45-62.

47. Hakli, R., Nykanen, M., and Tamm, H. A declarative programming system for manipulating strings. In Sixth Fenno-Ugric Symposium on Software Technology, Sagadi, Estonia, 1999, 29-40.

48. Свердлов С.З. Языки программирования и методы трансляции.СПб.: Питер.2007.63 8 с.

49. Хачатрян В.Е., Великая Я.Г. Подход к решению фундаментальных проблем моделей вычислений на примере многоленточных автоматов //Научные ведомости БелГУ. 2009. № 9(64). с. 108-111.

50. Хачатрян В.Е. Об отношениях перестановочности в схемах Янова. // Программирование. 1976. № 4. с. 312.

51. Подловченко Р.И., Айрапетян М.Г. О построении полных систем эквивалентных преобразований схем программ // Программирование, 1996. № I.e. 329.

52. Хачатрян В.Е., Великая Я.Г., Сунцова А.И. Структурные преобразования модели вычислений // Информационные системы и технологии, №3. -2010 г.-с. 45-49.

53. Подловченко Р.И. О проблеме эквивалентных преобразований программ // Программирование, 1986, №6, с. 314.

54. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов (учебное пособие для студентов) М.: Издательский отдел ф-та ВМиК МГУ, 2000 г. - 58 с.

55. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-429 с.

56. Подловченко Р.И, Хачатрян В. Е. Минимальность и тупиковость многоленточных автоматов // Дискретная математика. 2008. № 2. с. 92120.

57. Подловченко Р.И., Хачатрян В.Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд. сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 3843

58. Хачатрян В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН. 2006. том 411. № 3. с. 314318.

59. Великая Я.Г., Хачатрян В.Е. Модификация трансформационного метода//Десятый международный семинар "Дискретная математика и ее приложения". Москва, МГУ. с.447-450.

60. Великая Я.Г. Обобщенный трансформационный метод и конечные детерминированные автоматы // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. №19(90), вып. 16/1, 2010. с.93-103.

61. Хачатрян В.Е. О перестановочности логических графов // Кибернетика. 1976. №3. с. 33-43.

62. Подловченко Р.И., Хачатрян В.Е. Метод трансформацинного распознавания эквивалентности в моделях вычислений // 8-ой межд. сем. Дискретная математика и ее приложения. Москва, МГУ. 2004. С. 38-43.

63. Подловченко Р.И., Хачатрян В.Е. Об одном подходе к разрешению проблемы эквивалентности// Программирование. 2004. № 3. С. 117.

64. Хачатрян В.Е. Проблема эквивалентных преобразований для однородных многоленточных автоматов // Программирование. 2008. №3. с. 7780.

65. Sengoku Н. Minimization of nondeterministic finite automata. Master's thesis, Kyoto University, 1992.

66. Watson B.-W. and Daciuk. J. An efficient incremental DFA minimization algorithm. Natural Language Engineering, 9(l):49-64, march 2003.

67. Jiang T.and Ravikumar В. Minimal NFA problems are hard. SIAM J.Comput. Vol 22, No 6, pages 1117-1141, 1993.

68. Kameda Т., Weiner R On the state minimization of nondeterministic automata. IEEE Trans. Comput.c-19, 7(1970),617-627.

69. Hopcroft J. An n log n algorithm for minimizing states in a finite automaton. Technical Report CS-190, Stanford University, 1971.

70. Hopcroft J. E., Motwani R. and Ullman J.D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 2001.

71. Carrez, C.; On the minimalization of non-deterministic automaton, Laboratoire de Calcul de la Facult.e des Sciences de l'Universit.e de Lille, 1970

72. Champarnaud, J.-M., and Coulon, F. NFA reduction algorithms by means of regular inequalities. In Proceedings of DLT 2003, Lecture Notes in Computer Science 2710, Springer, 2003, 194-205.

73. Подловченко Р.И., Хачатрян В.Е.Полное решение проблемы минимизации для одного множества бинарных двухленточных автоматов//Дискретная математика. 2010. Том 22. Выпуск 3. С. 146-159.

74. Бауэр В. Введение в теорию конечных автоматов, под ред. Ю.И. Журавлева М.: Радио и связь, 1987. 392 с.

75. Свидетельство о государственной регистрации программы для ЭВМ