Структурный анализ многоленточных автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

08-3 1929

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

ХАЧАТРЯН Владимир Ервандович

Структурный анализ многоленточных автоматов

01.01.09 -дискретная математика и математическая кибернетика

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

Москва 2008

Работа выполнена в Беягородсжом государственном университете

Консультант

профессор Постшшип Ниш Имютя»

Официальные опповягш:

таингоррссповднаегНАНУ,

доююр фвдоо-додоахяпеспосвдо,

профессор ЛишкжииШ Адгагтняр Адояьфомч

jjfUgTpp- ^||ПЯ1ВНШШИ|1НН!иД Biytj цофбнорСипншв Ajrxcshrp Акгавопрг

профессор Ломям»» Ирква Александровна

Ведущая организация Институт системного програмсвровяакя РАН

Защита состоит« "17" октябре 2008 года в 11 часов ва •и^у^тн диссертационного совета Д 501.001.44 при Московском государством» университете им. М В. Ломоносом во адеесу: 119991 Москва, ГСП-1, Ленинские горы, МГУ, факультет ВМиК, ауд, 6X5.

С диссертацией можно ознакомиться ■ научной бнбиютавеМГУ.

Автореферат разослан

ы

L& cjkvcJlP

Трифонов Н. П.

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

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

Многоленточные автоматы, как самостоятельная модель вычислений, введена в 1959 г. М. Рабином и Д. Скоттом. Эта модель обобщает конечные автоматы путем перехода от одной ленты, с которой работает конечный автомат, к нескольким лентам.

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

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

Развитие теории многоленточных автоматов, в основном, направлено на изучение детерминированных автоматов. Основная часть исследований, проведенных в рамках теории, посвящена проблеме эквивалентности детерминированных автоматов. Из многочисленных полученных здесь результатов, несомненно, фундаментальными являются два, а именно: разрешимость эквивалентности в множестве всех двухленточных автоматов, установленная Р.Бердом в 1973 году, и разрешимость эквивалентности в множестве автоматов с любым числом лент, установленная Т.Харью и Ю.Кархумяки в 1991году. При этом важным является следующее: оба результата получены сведением проблемы

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

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

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

1) построение полных систем э. п. в различных множествах детерминированных многоленточных автоматов;

2) исследование проблемы минимизации для последних;

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

Все три задачи объединяет следующее: их решение базируется на анализе структуры эквивалентных автоматов; именно это и дает название самому направлению исследований.

Результаты исследований. В работе рассматриваются только детерминированные многоленточные автоматы. Они берутся в определении, данном Р.Бердом, и по выразительной мощности адекватны автоматам, введенным М. Рабином и Д. Скоттом.

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

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

Обозначим М^п, множество всех автоматов, использующих п бесконечных лент, которые заполняются символами алфавита, содержащего т символов; здесь п, т > 2. В работе для каждого из следующих множеств:

- множества М„1т, где п, т > 2;

- подмножества множества М^, состоящего из автоматов с непересекающимися циклами;

- подмножества множества М^,, состоящего из однородных автоматов, где п, т > 2;

построена полная в нем система э. п. автоматов (теоремы 2.3, 2.5, 2.7). Здесь непересекаемость циклов в автомате трактуется обычным образом, а однородность автомата - требованием: если состояния автомата принадлежат одному и тому же циклу, то в них считывается одна и та же лента.

Из теорем 23, 2.5 следует частичная разрешимость проблемы эквивалентности в множестве М^ и, соответственно, в множестве автоматов с непересекающимися циклами, принадлежащих Мг> Из теоремы 2.7 следует полная разрешимость проблемы эквивалентности в множестве однородных автоматов, принадлежащих Нм„.

При построении полных систем э. п. автоматов применены следующие новые подходы:

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

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

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

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

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

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

Доказывается, что выполнимость условия а влечет за собой эквивалентность исходных автоматов (лемма 3.3).

Трансформационный метод апробирован на некоторых множествах автоматов.

Для автоматов с непересекающимися циклами, принадлежащих множеству Им« п, т > 2, получен следующий результат: для двух произвольных автоматов, поступивших на вход метода, дана оценка глубины выполняемого методом процесса развертки, достаточной, чтобы установить либо их неэквивалентность путем нарушения признака 6, либо выполнимость условия а, гарантирующего их эквивалентность (теорема 3.4). Таким образом, получен алгоритм, разрешающий эквивалентность в данном множестве.

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

Показано, что среди выделенных множеств находятся однородные автоматы, принадлежащие множеству М^, где п, т > 2 (утверждение 3.20).

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

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

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

Поставленная задача решена (теоремы 4.2, 4.4). Искомым оказалось множество двухленточных бинарных автоматов (обозначим его М), фактически самое близкое к обычным конечным автоматам: из двух лент, с которыми работает автомат из М, одна имеет произвольное заполнение над алфавитом {0,1}, а вторая всегда заполняется одним и тем же символом, скажем, символом 0.

Установлено, что М является нетривиальным (пример на рис. 4.1 и утверждение 4.2), а также то, что минимальные автоматы в классах эквивалентности в М являются тупиковыми (лемма 4.3).

Решение проблемы минимизации в М осуществлено следующим образом:

1) построена система Т э. п. автоматов, полная в М (теорема 4.1), при этом доказательство полноты проведено традиционным образом: трансформацией средствами системы каждого автомата из М в канонический; таким образом, построен алгоритм, разрешающий эквивалентность в М (утверждение 4. Г);

2) проблема минимизации в М сведена к проблеме минимизации в М, где М с М (теорема 4.2); М состоит из автоматов, непременно работающих с обеими лентами;

3) любой класс эквивалентности из М разбит на подклассы, называемые срезами; построена система Т0 э. п., полная в каждом срезе (утверждение 4.8);

4) построена алгоритмизуемая процедура отыскания всех минимальных автоматов в срезе, содержащем канонический автомат (теорема 4.3); процедура использует преобразования из Т0; исследованный срез назван главным;

5) показано, что преобразованием системы Т из главного среза можно попасть в любой (утверждение 4.16), и выявлено конечное множество срезов, в которых и только в них могут находиться минимальные автоматы в рассматриваемом классе эквивалентности (лемма 4.6); назовем эти срезы допустимыми; в их множестве - главный срез;

6) построена алгоритмизуемая процедура отыскания минимальных автоматов в любом допустимом срезе, отличном от главного {лемма 4.5); процедурой применяются преобразования из То;

7) описана алгоритмизуемая и оптимальная по быстродействию процедура построения всех минимальных автоматов в произвольном классе эквивалентности из М {теорема 4.4).

Таким образом, теоремами 42 и 4.4 дано решение проблемы минимизации в М.

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

Цели исследований диссертационной работы достигнуты.

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

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

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

Личный вклад соискателя. Результаты, изложенные в диссертации, получены автором самостоятельно и опубликованы в работах [1-20]. В коллективных публикациях автору принадлежат те их части, которые составляют основу диссертации.

Апробация работы и публикации. Основные результаты работы докладывались на научных конференциях и семинарах. В том числе: на семинаре по теоретическим вопросам программирования кафедры Математической кибернетики МГУ (2002-2007), на Международных конференциях «Дискретные модели в теории управляющих систем» (май 2002, декабрь 2004, март 2006), на VII Международном семинаре «Дискретная математика и ее приложения» (февраль 2004), на научном семинаре в Институте прикладной математики им. М.В.Келдыша (октябрь 2002, ноябрь 2004), на Международной конференции ((Проблемы теоретической кибернетики» (май 2006), на Ломоносовских чтениях (апрель 2007), на IX Международном семинаре «Дискретная математика и ее приложения» (июнь 2007), на научно-исследовательском семинаре

«Дискретная математика и математическая кибернетика» (МГУ ВМиК, май 2008), на Международной научной конференции «Космос, астрономия и программирование» (Лавровские чтения, май 2008).

Работа поддерживалась следующими грантами: грант РФФИ 03-01-00132а, грант РФФИ 06-01-00106, внутренними фантами Белгородского государственного университета В КГ 031-06 и В КГ 183-07.

Основные результаты работы отражены в 20 публикациях, полностью отражающих основные научные результаты работы, в том числе 9 в рецензируемых научных изданиях по списку ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографического списка (121 наименование). Объем работы - 201 страница, включая 68 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Глава 1 состоит из пяти разделов.

В разделе 1.1 дается используемое в работе определение конечного детерминированного n-ленточного автомата, n ¿ 2, над алфавитом где £={oi, <*г.....am}, т £ 2.

Воспроизведем это определение. Автомат состоит из управляющего графа, вершины которого называются его состояниями, и п бесконечных лент, обозначенных символами р,,..., р„, n¿ 2, и заполненных символами из Е={оь а2,..., (!„,}, m 2: 2. На каждой ленте имеется считывающая головка, движущаяся вправо. Управляющий граф - это, по определению, конечный ориентированный граф, в котором выделены три различных состояния: инициальное, финальное и мертвое. Из каждого состояния, кроме финального и мертвого, исходят по m дуг, помеченных различными символами а и о2 ,..., аю; из финального и мертвого нет исходящих дуг. Любое отличное от них состояние помечено символом p¡, i = 1,2,...,п и называется pj-состоянием, i = 1Д,...,п.

Функционирование автомата ведется на лентах Pi,..., р„ которые в общем случае заполнены произвольными символами из I. Оно состоит в обходе управляющего графа. Этот обход начинается с инициального состояния в условиях, когда считывающие головки лент стоят на первых позициях. Общий шаг такого обхода совершается в условиях, когда достигнуто некоторое состояние v автомата, и каждая головка обозревает некоторый символ на своей ленте. Шаг состоит в считывании обозреваемого символа с ленты p¡, если v - это p¡-coстояние, при этом сработавшая головка сдвигается на одну позицию вправо, а автомат

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

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

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

Для каждого автомата можно построить вспомогательный конечный автомат, спустив на дуги, исходящие из каждого состояния, метку этого состояния в качестве первой добавочной к уже имеющейся. Так мы получим конечный автомат над алфавитом РхХ, где Р={рь..., р,}, п 2; 2. Сильно эквивалентными назовем такие п-ленточные автоматы, для которых построенные вспомогательные конечные автоматы эквивалентны в обычном понимании этого отношения.

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

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

В разделе 1.2. дается общее описание рассматриваемых проблем: эквивалентности и включения, эквивалентных преобразований, минимизации. Формальное определение этих проблем дается в разделах 1.3-1.5.

В разделе 1.3. формулируется проблема эквивалентных преобразований в множестве М, где М - некоторое множество диаграмм. Она состоит в поиске нетривиальной полной в М системы эквивалентных преобразований. Отметим, что система Т э. п. диаграмм называется полной в М, если для любых двух эквивалентных диаграмм Б', О" из М существует цепочка О,, Бь к £ 1 такая, что Б' = Бь О" = Эь н

преобразование О* в принадлежит системе Т.

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

Раздел 1.4. посвящен краткому обзору исследований в теории многоленточных автоматов. В частности, отмечается, что неразрешимость проблемы включения была установлена М. Рабином и Д. Скопом в 1959 году, а разрешимость проблемы эквивалентности для автоматов с

произвольным числом лент была доказана лишь в 1991 году Т. Харью и Ю. Кархумаки.

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

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

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

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

Диаграмма является частным случаем ее фрагмента, все вершины которого являются внутренними.

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

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

Вхождением фрагмента Б в диаграмму Б называется любой ее фрагмент, изоморфный фрагменту Б.

Под согласованием двух фрагментов понимается установление такого соответствия между внешними входами и отдельно между внешними выходами этих фрагментов, которое:

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

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

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

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

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

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

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

Через Мо^ш обозначим множество многоленточных автоматов над алфавитами Р = {р[( рг.....р,}, п £ 2 и <3 = {аь а*..., с^}, т £ 2.

В данной главе дня каждого п и т (п, т £ 2) приводится система э. ги, являющаяся полной в множестве М^.

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

Глава 2 состоит из четырех разделов.

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

Теорема 2.2. Система преобразований Ту является полной в М2-2.

Система Т2-2 состоит из аксиом С1 - С5.

Аксиома С1. Фрагмент Рь не имеющий входящих дуг и не содержащий входа диаграммы, эквивалентен пустому фрагменту Р2.

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

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

• всем вершинам одного класса сопоставлен общий символ из Р;

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

Опишем фрагмент Р2, получаемый по фрагменту Рь Его внутренними вершинами являются VI', у2', ..., ук', отличные от вершин фрагмента Р1р Из у/ в у/ ведет дуга с меткой а, где стер, если дуги с меткой а ведут из вершин класса V; в вершины класса V,; если же эти дуги являются выходящими из V; и оканчиваются в состоянии V, то дуга из у/ с меткой о ведет в V. Если в какую-либо вершину из V; ведет входящая дуга фрагмента Рь то она направляется в вершину

Фрагменты Р] и Р2 эквивалентны.

Аксиоме С4 предпошлем дополнительные понятия.

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

• V не является внутренним выходом фрагмента Р;

• выход диаграммы не является внутренней вершиной Б;

• внутренние выходы фрагмента Р составляют непустое множество, все они имеют общую метку, которая отлична от меток остальных внутренних вершин фрагмента И;

• если из внутреннего выхода исходит дуга, не являющаяся выходящей дугой фрагмента Р, то эта дуга ведет в V.

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

Аксиома С4. Пусть Р) - фрагмент с границей, и V - его заглавная вершина.

Обозначим Ф фрагмент, индуцированный неграничными внутренними вершинами фрагмента Р|.

По фрагменту Р) построим фрагмент Р2 с теми же внешними входами и внешними выходами, что у фрагмента Р[.

Построим образ и вершины V, полагая, что и - это вход диаграммы, если V - вход диаграммы, и в противном случае - единственный внутренний вход фрагмента Р2; между входящими дугами в Р2 и входящими дугами в Р, определим взаимно однозначное соответствие, устанавливаемое совпадением их начал. Полагаем, что метка и совпадает с меткой граничных вершин Р].

Создадим фрагменты Ф+, Ф~, изоморфные фрагменту Ф, и направим дугу с меткой 1 из и в ту вершину фрагмента Ф+, которая является образом вершины V, дугу с меткой 0 из и - в образ вершины V во фрагменте Ф~. Устраним из Ф+ и Ф" все выходящие дуги.

На примере фрагментов, изображенных на рис.1, показано, в какие вершины пойдут дуги, выходящие из принадлежащих Ф+, Ф~ - образов внутренних выходов фрагмента Ф. Заметим, что дуги, помеченные жирной

На рис.1 во фрагменте выделена граница. Вершины, ее составляющие, имеют метку q. Имеются две дуги, исходящие из граничных вершин и направленные во внутренний вход фрагмента Р|. Он помечен номером 5. Неграничные вершины включены во фрагмент Ф и имеют метку р. Вход фрагмента Р2 выделен и имеет метку ц. Согласование внешних выходов фрагментов Ф* и Ф'с внешними выходами фрагмента Р| задается совпадением их номеров.

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

Фрагменты ?! и Р2 эквивалентны.

Аксиоме С5 предпошлем понятие древовидного фрагмента.

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

Аксиома С5. Пусть - древовидный фрагмент диаграммы О; (чъ -пара эквивалентных вершин фрагмента Рь 1 = 1, 2, ..., к, где у* -внутренняя вершина а у^ - внешний выход фрагмента Рь отличный от выхода диаграммы и пустого цикла.

Построим фрагмент Р2. Для этого выходящую дугу фрагмента Рь направленную во внешний выход V)', направим на эквивалентную ему вершину и так -для всех 1 = 1,2,..., к.

Фрагменты Рь Р2 эквивалентны.

Доказательство теоремы 2.2 проводится следующим образом. Доказывается (теорема 2.1), что э. п. системы Тгд любую диаграмму из множества Му можно преобразовать к виду, удовлетворяющему двум условиям:

1) любая вершина диаграммы, за исключением пустого цикла, лежит на пути из входа в выход;

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

Диаграммы, удовлетворяющие условию 1), назовем очищенными, а

условиям 1) и 2) - приведенными и обозначим последние .

Доказывается, что для любых двух эквивалентных диаграмм из М1Л одну из них можно перестроить в другую, используя лишь преобразования системы Т2д(лелша 2.4).

В п.2.1.4 приводится обобщение полученного результата для множества Мп ш, п > 2, ш 2:2.

Предлагается использовать систему Тпт, состоящую из ранее описанных аксиом С1, С2, С3, С5 и новой аксиомы С4п,т. Последняя является обобщением аксиомы С4.

Определение фрагмента с границей естественным образом обобщается до определения фрагмента с ¡-границей, ¡е{1, 2, ..., п}, в котором все внутренние выходы фрагмента помечены символом р), а остальные внутренние вершины - символами

Аксиома С4 п,т. Пусть ?! - фрагмент с ¡-границей, ¡е {1, 2,..., п} и Р2 - фрагмент, полученный из Р] построениями, выполненными в описании аксиомы С4.

Фрагменты Р|, Р2 эквивалентны.

Утверждения и леммы, на которые опирается теорема 22, доказываются аналогично и для случая п ¡> 2, т > 2. Поэтому справедлива

Теорема 2.3. Система Т^ полна в М^, где п й: 2, т £ 2.

Приводится пример использования преобразований системы Т3>2 для эквивалентных диаграмм, взятых из статьи Р.Бер'да, эквивалентность которых не распознается алгоритмом, приведенным в этой работе.

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

Предлагаемая система э. п. отличается от системы э. п., которую можно было бы получить из уже предложенной системы Т^ при п=2, т=2.

Теорема 2.5. Система Т0 полна для множества бинарных двухленточных автоматов с непересекающимися циклами.

Система Т0 задается аксиомами С1, С2, СЗ, С6, С7.

На рис. 2а и 26 схематически описаны пары фрагментов Рь Р2, задающих аксиому Сб. Здесь символами Р<1),. -, Р0'. 1 ^ 2 обозначены фрагменты, изоморфные фрагменту И и не содержащие р-состояния, а Яш, т > 2 изоморфны фрагменту п. Соответствие между некоторыми внешними выходами указано совпадающими натуральными числами. Возможное наличие нескольких дуг, ведущих в одну и ту же вершину, фиксируется двойной стрелкой.

1 2

з

а

б

Рис. 2

Фрагменты Р) и Р2 эквивалентны.

Аксиома С7. Пусть щ - цикловой фрагмент с одной входящей дугой и V] - его внутренний вход, а у2 - какая-либо вершина цикла.

Обозначим я2 цикловый фрагмент, полученный из я\ переводом дуги, ведущей (в цикле) в вершину у2, в вершину V, и устранением всех вершин цикла, начиная с у2 и кончая вершиной, предшествующей вершине VI, если идти в направлении дуг цикла.

Если V,, у2 - эквивалентные вершины, то фрагменты л,, к^ также эквивалентны.

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

Пусть \¥ - путь в некоторой диаграмме, и проходит по циклу т.е. можно записать в виде \у1\у0мг2. Тогда, если w2 не пуст и первая его дуга не принадлежит \у0, то говорим, что путь w покидает цикл у/о. Рангам пути \у назови« число покинутых им циклов, а рангам диаграммы -максимальный ранг маршрутов через нее.

Пусть Од, Б2 - эквивалентные приведенные диаграммы, и ранги их больше 0. Тогда (лемма 2.8) преобразованиями из То диаграммы 0|, ЕЪ можно трансформировать соответственно в приведенные диаграммы О,', 02' содержащие такие изоморфные фрагменты со входами Рь Р2) что 5({0,Д)2})>5(М(В1^1)^М(В2|,Р2)). (1)

Здесь М(Б,Р) - множество диаграмм Э(у), где V - внешний выход фрагмента Р со входом, вф) - число неизбыточных маршрутов, т.е. маршрутов через диаграмму, ранг которых совпадает с рангом диаграмм Оь Б2 и которые, всякий раз проходя по некоторому циклу, содержат не более одного витка этого цикла.

Многократное применение предлагаемой стратегии трансформации диаграмм Э2 в диаграммы Б/, Б2' позволяет пару эквивалентных приведенных диаграмм с непересекающимися циклами привести к общему виду. Условие (1) гарантирует конечность такого процесса.

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

Строится полная система э. п. для бинарных однородных двухленточных автоматов, а затем приводится обобщение на случай п ленточных автоматов, п > 2 с числом символов, используемых для записи на лентах, равным т, т>2.

Теорема 2.6. Т, является полной системой э. п. в множестве всех однородных бинарных двухленточных автоматов.

Система э. п. Т1 состоит из ранее введенных аксиом С1, С2, СЗ и новой аксиомы С8.

Аксиома С8. Пара фрагментов Р2, принадлежащая ей, изображена на рис. 3. Овалами очерчены подфрагменты фрагментов Р] И р2) КЯЖДЫЙ

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

Графы, полученные из подфрагментов отбрасыванием входящих в них дуг, изоморфны, когда подфрагментам соответствует один и тот же символ; при этом вершины, в которых оканчиваются отброшенные дуги, изоморфны друг другу. Между дугами, выходящими из подфрагментов Р10 и Изо, и дугами, выходящими из других подфрагментов, имеется соответствие, устанавливаемое совпадением вершин, в которых оканчиваются выходящие дуги фрагмента Р| и фрагмента оно продемонстрировано на рис. 3 парой дуг с метками а и Ь и вершиной п2.

Фрагменты Р) и Р2 эквивалентны.

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

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

Следствие теоремы 2.6. Проблема эквивалентности в множестве всех однородных бинарных двухленгочных автоматов разрешима.

Полученные результаты справедливы и для многоленточных однородных автоматов над алфавитами Р = {р,, рг, ..., р„}, п £ 2, 0 = {а1,а2,...,ав},т2:2.

Рассмотрим аксиому С8Ф, которая отличается от аксиомы С8 только тем, что пара фрагментов Р], Р2 входит в аксиому С8*, если вершины корня фрагмента и всех ветвей фрагмента Р2 помечены одним и тем же символом, а вершины корня фрагмента Р2 и всех ветвей фрагмента Р| этим символом не помечены. Они могут бьггь помечены любыми другими символами алфавита Р = {р(, рг,..., р„}, 2.

Обозначим Т1* систему преобразований, состоящую из аксиом С1, С2, СЗ и аксиомы С8*.

Рис. 3

Теорема 2.7. Т1* является полной системой э. п. в множестве всех однородных автоматов над алфавитами Р,

Следствие теоремы 2.7. Проблема эквивалентности в множестве всех однородных автоматов над алфавитами Р, <3 разрешима.

Доказательства полностью повторяют доказательство теоремы 2.6 и - следствия теоремы 2.6.

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

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

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

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

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

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

Глава 3 состоит из пяти разделов.

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

Метод предписывает построение алгоритма (обозначим его р) с заранее очерченной задачей. Она состоит в построении дерева Т, вершинами которого являются пары графов из взятой модели. Его корнем служит пара сравниваемых графов, которые назовем исходными.

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

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

Предписание I. Процедура т должна работать таким образом, чтобы имело место утверждение: графы 0ь02 эквивалентны тогда и только тогда, когда т не ломается на паре (вьСг), и каждый из построенных потомков вершины (01,62) состоит из эквивалентных графов.

Если предписание 1 реализовано, то справедлива

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

Уточним требования к процедуре т, при выполнении которых будет удовлетворено предписание 1.

Пусть (С|,02) - вершина дерева Т, к которой применяется т. Процедура т планируется как последовательное выполнение процедур т, и т2.

Предписание 2. Процедура Г] должна осуществить эквивалентную развертку графа О! в граф в/ и сделать это так, чтобы к О,' была применима процедура 5, выполняющая эквивалентную свертку графа в граф С|.

Предписание 3. Процедура т2 должна попытаться эквивалентными преобразованиями трансформировать граф 02 в граф 02', который начинается копией купола Р. Здесь под куполом графа О понимается древовидный фрагмент, полученный копированием его структуры, при котором с каждого цикла снимается лишь по одному випсу. Неудачность этой попытки должна приводить к заключению: графы в, и неэквивалентны.

Чтобы реализовать предписание 3, рекомендуется следующее. Для рассматриваемой модели определить:

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

2) набор Я эквивалентных преобразований, выполнимых в случае, когда удовлетворены условия из С?, и достаточных для трансформации графа 02 в требуемый граф 02'.

Тогда действия процедуры т2 будут состоять в пошаговом построении копии купола Р; каждый шаг начинается проверкой условий из <3; если они не выполнены, то построение копии прекращается с заключением: графы (0ь02) неэквивалентны; это событие квалифицируется как поломка процедуры т; если же проверяемые условия удовлетворены, то преобразованиями из Я осуществляется очередное приращение уже построенной части купола Р и переход к следующему шагу процедуры т2.

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

Доказывается, что достаточно предложенную задачу рассмотреть лишь для диаграмм из а/о - приведенных диаграмм, к которым применен алгоритм разметки вершин рангами.

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

Корнем дерева Т назначается пара исходных диаграмм.

1. Предпринимается попытка построения потомков данной вершины (с тем, чтобы дополнить ими уже построенную часть Т). Это выполняет алгоритм т, который завершается благополучно, если попытка удалась, и неблагополучно (ломается) в противном случае. Если т ломается, то алгоритм р останавливается с ответом «снег», квалифицируемым как заключение: исходные диаграммы неэквивалентны. Иначе р переходит к следующему действию.

2. Каждый из построенных потомков подвергается проверке, не является ли он листом. Здесь под листом понимается вершина, метка которой состоит из изоморфных диаграмм. Если имеются нелистовые потомки, то к ним применяется 1.

Теорема 3.3. Алгоритм р распознает эквивалентность диаграмм из класса Л/о.

Перечислим факты, на которых базируется доказательство теоремы 3.3. Сначала устанавливаются свойства алгоритма т, т.е. изучается один шаг работы алгоритма р. Эти свойства фиксируются леммами 3.1 - 3.3.

Лемма 3.1. Если вершина (Di,Di) дерева Т, к которой применяется алгоритм т, состоит из эквивалентных диаграмм, то т благополучно завершает свою работу.

Лемма 3.2. Если верна предпосылка леммы 3.1, то построенные алгоритмом т потомки вершины (DbD2) таковы, что каждый из них состоит из эквивалентных диаграмм.

Лемма 3.3. Если алгоритмом т построены потомки вершины (D,,D2) дерева Т и оказалось, что каждый из них состоит из эквивалентных диаграмм, то Db D2 эквивалентны.

Из лемм 3.1 и 3.2 вытекают два следствия.

Следствие 3.1. Если алгоритм р останавливается с ответом «нет», то поступившие на его вход диаграммы неэквивалентны.

Следствие 3.2. Если поступившие на вход алгоритма р диаграммы эквивалентны, то р никогда не останавливается с ответом «нет».

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

Лемма 3.4. Если алгоритм р никогда не останавливается с ответом «нет», то он строит конечное дерево Т, т.е. останавливается с ответом «да».

И так как каждый лист дерева Т состоит из эквивалентных диаграмм, то из лемм 3.3 и 3.4 вытекает

Следствие 3.3. Если алгоритм р останавливается с ответом «да», то диаграммы, к которым он применялся, эквивалентны.

П.п.3.2.2 - 3.2.5 посвящены описанию составляющих алгоритма т и доказательству того, что они сохраняют отношение эквивалентности между преобразуемыми диаграммами (утверждения 3.4 - 3.8, леммы 3.5-3.6).

В п.3.2.6. приводится обобщение результата на случай произвольных многоленточных автоматов. Рассмотрим многоленточные автоматы над алфавитами Р={р1,...,ро},пг2и0={а!.....а,,,},1.

Справедливы все утверждения и леммы, подобные тем, что доказаны в пл. 3.2.1 - 325, а значит и теорема 3.4.

Теорема 3.4. Алгоритм р' распознает эквивалентность диаграмм из класса м«-

Здесь м» подкласс приведенных диаграмм с непересекающимися циклами над алфавитами Р и <3, к которым применен алгоритм разметки вершин рангами.

Пример распознавания эквивалентности трехленточных автоматов рассмотрен в п. 3.2.7.

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

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

Сечение дерева Т^ьОг), каждая вершина которого помечена парой графов, совпадающей с парой, метящей одну из вершин предшествующих данной вершине, назовем /3-сечением.

Отметим, что частным случаем ^-сечения является случай, когда каждая вершина сечения содержит метку, состоящую из изоморфных графов. Назовем такое сечение - а-сечением.

Основное утверждение, доказанное в параграфе 32, можно сформулировать в виде теоремы.

Теорема 3.6. Если С], С2 графы с непересекающимися циклами, то в] эквивалентен 02 тогда и только тогда, когда дерево Т^^) заканчивается а-сечением, причем высота начального фрагмента не превышает числа п+3, где п - ранг сравниваемых графов.

Сформулируем гипотезу о достаточном признаке эквивалентности:

если дерево потомков Т(0Ь02) графов 0Ь02 обладает р-сечением, то графы 0|,С2 эквивалентны.

В подтверждение гипотезы доказывается теорема 3.8.

Обозначим Яе(р(В1102)) множество всех меток вершин дерева потомков Т(Вь02). Пару диаграмм (0,,02) назовем р-ограниченной, если множество Яе(р(ОьВ2)) конечно.

Теорема 3.8. Если алгоритм рфьГ^) не ломается, то дерево потомков Т(ОьВ2) обладает Р-сечением тогда и только тогда, когда пара (О^г) является р-ограниченной.

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

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

Утверждение 3.16. Число различных диаграмм дерева Т конечно тогда и только тогда, когда высота диаграмм дерева Т ограничена некоторым числом.

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

Теорема 3.10. Если диаграммы 01, удовлетворяют условию у и алгоритм р, на вход которого поданы эти диаграммы, не ломается, то высота диаграмм дерева ТфьОг) ограничена числом, которое определяется по диаграммам Оь 02.

Доказательство основано на утверждениях (утверждения 3.15-3.17), которые позволяют за счет структурных особенностей диаграмм, удовлетворяющих условию у, получить оценку высоты диаграмм дерева Т(Б,Д)2).

Если любая пара диаграмм Оь 02 множества М удовлетворяет условию у, то такое множество обозначим М(у) и будем говорить, что оно удовлетворяет условию у.

Отметим, что если будет справедлива выдвинутая нами гипотеза, то алгоритм р будет алгоритмом разрешения эквивалентности для диаграмм множества М(у).

Обозначим М) класс однородных диаграмм.

Утверждение 3.20. М^М^у).

Следствие 3.5 теоремы 3.10. Алгоритм р распознает 0-сечение однородных диаграмм.

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

Следствие 3.6 теоремы 3.10. Алгоритм р распознает Р-сечение конечно-автоматных диаграмм.

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

При применении трансформационного метода к эквивалентным конечным автоматам мы можем получить либо а, либо р-сечение и ничего другого. Доказано, что тип сечения зависит от порядка автоматов в паре (утверждение 3.21). Приводится достаточное условие, налагаемое на структуру графов, при которых сравниваемые эквивалентные автоматы непременно определяются а-сечением (теорема 3.11).

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

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

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

Большинство моделей вычислений обладает некоторой структурой, и минимизация определяете* как уменьшение объема этой структуры.

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

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

Задачу минимизации сформулируем следующим образом. Пусть М - некоторое множество многоленточных автоматов:

1) по заданному автомату из М найти в классе его эквивалентности тупиковый автомат,

2) описать процедуру, посредством которой по найденному автомату конструируется любой минимальный автомат в том же классе эквивалентности.

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

Глава 4 состоит из восьми разделов.

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

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

Разделы 4.2 и 4.3 посвящены построению системы Т э. п. автоматов, доказательству ее полноты в М, а также сводимости проблемы минимизации в М к одноименной проблеме в подмножестве М множества М.

Система Т использует аксиомы В1 и В2. В качестве аксиомы В1 рассматривается аксиома СЗ, описанная в разделе 2.1.

Аксиома В2 индуцирует преобразования, которые задаются парами фрагментов, тип которых изображен на рис. 5.

Двойные стрелки на рисунке обозначают непустое множество дуг, приходящих в указанное состояние. Совпадение меток, приписанных этим стрелкам (в качестве меток используются символы аире индексами), означает наличие взаимно однозначного соответствия между дугами помеченных множеств, сохраняющего метки дуг и состояния, из которых исходят эти дуги. Через Рр обозначены изоморфные подфрагменты фрагментов Р] и Р2. Они очерчены на рис. 5 овалами.

Достаточно описать лишь фрагмент Р). Он имеет ш, т £ О внутренних входов, все они являются я-состояниями, дуги из которых ведут в состояния аь а2,..., а„ подфрагмента Рр и не принадлежат этому подфрагменту; приходящие в ц-состояния непустые множества дуг обозначены ои,..., ат. Фрагмент ?! имеет п внешних выходов. Последние

Рис.4

Рис. 5

помечены символами bb b2,..., Ь„, а приходящие в них множества дуг обозначены Pi,..., Р„.

Фрагменты Fi и F2 эквивалентны.

Теорема 4.1. Система Т полна в М.

Доказательство следует из возможности трансформирования преобразованиями В1 и В2 автомата в канонический и утверждения 4.5.

Приписыванием к наименованию аксиомы 4 обозначим преобразование, индуцированное аксиомой, в котором фрагмент Fi заменяется на фрагмент F2 и -1 при замене фрагмента F2 на Рь

Автомат из М, к которому неприменимы преобразования В2Т, а к q-состояниям - В1-1-, назовем q-упорядоченным.

Справедлива

Лемма 4.1. Из эквивалентности состояний в q-упорядоченном автомате множества М следует их сильная эквивалентность.

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

Утверждение 4.5. В каждом классе эквивалентных автоматов из М имеется канонический автомат, он - тупиковый и единственен с точностью до изоморфизма в своем классе.

Следствие теоремы 4.1. В множестве М разрешима проблема эквивалентности.

Автоматом смешанного типа назовем автомат, содержащий как р-, так и q-состояния.

Обозначим М подмножество множества М, состоящее из всех автоматов смешанного типа. Доказывается

Теорема 4.2. Проблема минимизации в М сводится к одноименной проблеме в М.

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

Раздел 4.4 начинается с того, что произвольный класс эквивалентности К, принадлежащий множеству М, разбивается на подклассы, называемые срезами класса К;

р-проекцией автомата D назовем автомат, полученный из D корректным устранением q-состояний: если преемником р-состояния является q-состояние, то преемник последнего объявляется преемником первого; это правило используется до тех пор, пока из D не устраняются все q-состояния.

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

Утверждение 4.13. Автоматы из главного среза класса К имеют минимальную р-проекцию среди всех срезов класса К.

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

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

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

Утверждение 4.8. Система То, индуцируемая аксиомами ВО и В2, полна в любом срезе класса К.

Действительно, преобразованиями по аксиомам ВО и В2 любой автомат из среза трансформируется в я-упорядоченный, а он -единственный в срезе.

«Рабочим» преобразованием при осуществлении стратегии является так называемое <р-преобразование. Опишем его.

На вход (^-преобразования поступает фрагмент Р] из описания аксиомы В2. Он представлен на рис. 5.

Выполняется В24-преобразование, заменяющее фрагмент Р[ фрагментом Р2. Во фрагменте Р2 (см. рис. 6.) его внешние выходы ЬЬ...,Ь.

разбиваются на две группы: С!,...,«* и с^.....ф, где к+1=п, к>0, 1>0. В

каждое состояние С!,...,^ приходит дуга из д-состояния, не входящего во фрагмент Р2, а всякое из состояний не обладают этим свойством.

На рис. 6 представлена данная ситуация. Фрагмент Р2 подвергается В01-преобразованиям, склеивающим я-состояния, и трансформируется во фрагмент, изображенный на рис. 7, который и объявляется результатом данного ф-преобразования.

Рис. 6

Рис. 7

Раздел 4.5 посвящен реализации первого этапа. Основной в данном разделе является

Лемма 4.2. Любая конечная цепочка ((^преобразований трансформирует канонический в К автомат в тупиковый.

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

Теорема 4.3. Существует процедура построения всех минимальных автоматов в главном срезе класса К.

Предъявляется требуемая алгоритмизуемая процедура.

Разделы 4.6-4.8 посвящены реализации второго этапа. Устанавливается, что предположение стратегии действительно выполняется. Более того, предлагаемая процедура не только алгоритмизуема, но и является оптимальной по быстродействию.

Теорема 4.4. Каким бы ни был класс эквивалентности К из множества М, существует процедура построения всех минимальных автоматов в К.

Но тогда из теоремы 4.4 и того факта, что рассматриваются лишь допустимые срезы, а также из теоремы 4.2 о сводимости проблемы минимизации из М в М следует, что проблема минимизации в множестве М решена.

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

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

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

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

- для множества М,у„, где п, т > 2;

— для подмножества автоматов с непересекающимися циклами, принадлежащих множеству М^;

- для подмножества однородных автоматов, принадлежащих множеству М^в, где п, т > 2.

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

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

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

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

Найдены два достаточных условия благополучного завершения метода - условия аир.

Использованием условия а установлена разрешимость эквивалентности для автоматов с непересекающимися циклами, принадлежащих множеству М^,,, п, т > 2.

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

Установлено, что среди выделенных множеств находятся однородные автоматы, принадлежащие множеству М,^ п, т > 2.

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

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

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

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

Доказано, что искомым является множество двухленточных бинарных автоматов, работающих с лентами, одна из которых всегда заполнена одним и тем же символом из двух возможных:

- показана нетривиальность этого множества;

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

4. Очерчена область применимости трансформационного метода для моделей вычислений, отличных от многоленточных автоматов.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Хачатрян Bü, О перестановочности логических графов // Кибернетика. -1976.-№3.-С. 33-43.

2. Хачатрян В.Е. Однородные логические графы // Прикладная математика. - Ереван: Изд-во Ереванского гос. ун-та, 1981. -С. 67-80.

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

4. Хачатрян В. Е., Чашин Ю. Г. Преобразование программ микропроцессорных систем управления // Известия высших учебных заведений,-2000.-№ 10.-С. 135-139.

5. Подловченко Р.И., Хачатрян В.Е. Алгоритм распознавания эквивалентности многоленточных автоматов без пересекающихся циклов // Дискретные модели в теории управления систем: тр. V Междунар. конф. -Ратмино; М., 2003. -С. 67-70.

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

7. Хачатрян В. Е., Рязанов Ю.Д. Структурный метод распознавания автоматной эквивалентности // Вестник БГТУ. - 2003. - № 6. - 4.3. -С. 236-239.

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

9. Хачатрян В. Е., Чашин. Ю.Г. Использование преобразований для сравнения моделей на эквивалентность // Информационные технологии в

науке, образовании и производстве. Междунар. научно-практ. конф. // Известия ОГТУ. 2004. - № 2(3). - С. 53-57.

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

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

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

13. Хачатрян В.Е. О минимизации многоленточных автоматов. // Проблемы теоретической кибернетики: материалы XIV Междунар. конф. -Пенза, 2005.-С. 161-162.

14. Хачатрян В.Е., Щербинина Н.В. К вопросу о минимизации в моделях вычислений // Научные ведомости. Серия: информатика, прикладная математика, управление. - Белгород: БелГУ, 2006. - С. 34-51.

15. Хачатрян В.Е. Минимизация двухленточных автоматов // Дискретные модели в теории управляющих систем: тр. VII Междунар. конф. - М.: МГУ, 2006. - С. 379-386.

16. Хачатрян В.Е. Решение обобщенной проблемы минимизации для двухленточных автоматов с одной фиксированной лентой // ДАН. -2006. -Т. 411,№ З.-С. 314-318.

17. Подловченко Р.И., Хачатрян В.Е. О построении минимальных по размеру двухленточных автоматов // Дискретные модели в теории управляющих систем: тр. IX Междунар. конф. - М.: МГУ, 2007. -С. 348-351.

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

19. Хачатрян В. Е. Проблема эквивалентных преобразований для однородных многоленточных автоматов // Программирование. - 2008. -№3.-С. 77-80.

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

Подписано | печш 15.08.2008. Формат 60x84/16. Гарнитура Типе*. Усл. а л. 1,74. Тираж 110 экз. Заказ 166. Оригинал-макет подготовлен н тиражирован > издательстве Белгородского государственного университета 308015 г. Белгород ул. Победы, 85

Введение.

1. Основные понятия, постановка рассматриваемых задач и средства их решения.

1.1 Определение многоленточного автомата.

1.2 Рассматриваемые проблемы в теории многоленточных автоматов.

1.3 Проблема эквивалентных преобразований.

1.4 Проблема эквивалентности и включения.

1.5 Проблема минимизации и поиска всех минимальных форм.

1.6 Фрагментные преобразования. Общий подход к решению проблем.

2.Частичная разрешимость проблемы эквивалентности в множестве всех детерминированных бинарных многоленточных автоматов и в двух его подмножествах (построение полных систем э. п.).

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

2.2 Полная система для автоматов с непересекающимися циклами.

2.3. Полная система для однородных автоматов.

3. Трансформационный метод анализа структуры многоленточных автоматов.

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

3.2 Применение трансформационного метода для случая автоматов с непересекающимися циклами.

3.3Достаточное условие применимости трансформационного метода и его использование.

3.4 Классификация сечений для конечных автоматов.

3.5 Использование трансформационного метода для случая с неразрешимой проблемой включения.

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

4.1. Множество М детерминированных бинарных двухленточных автоматов и некоторые их свойства.

4.2. Система Т эквивалентных преобразований автоматов и сведение обобщенной проблемы минимизации из М в М.

4.3 Срезы класса эквивалентности и стратегия поиска минимальных автоматов в классе эквивалентности.

4.4 Главный срез и минимальные в нем автоматы.

4.5 Допустимые срезы класса эквивалентности и построение минимальных автоматов в них.

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

Классическими моделями вычислений являются алгебраические выражения, формулы логики, конечные автоматы, абстрактные вычислительные машины, схемы программ и другие [2,4,5,9,11,13,23,72,84,102,110]. Исследование моделей вычислений позволяет, с одной стороны, заняться только изучением тех конкретных свойств, которые заложены в данную модель вычислений, абстрагируясь от всех остальных, что позволяет обычно добиться положительного результата ввиду упрощения исходной задачи. С другой стороны, полученные результаты обычно переносимы на более сложные реальные объекты. Это достигается путем наложения на последние дополнительных ограничений, нацеленных на возможность использования исследованной модели вычислений.

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

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

Предлагаемая работа посвящена решению фундаментальных проблем классической модели вычислений - многоленточных автоматов, введенной М. Рабином и Д. Скоттом в 1959 году в их классической статье [110]. Эта модель является естественным обобщением конечных детерминированных автоматов, состоящим в переходе от одной ленты, несущей информацию для работы автомата, к нескольким лентам. Последнее означает, что это модель многозадачного процесса вычислений, поскольку работа на одной ленте может восприниматься как работа, выполненная одной задачей обладающей возможностью коммутировать с остальными. При этом в каждой цепочке задач, начинающихся во входе и заканчивающихся в выходе число выполнений каждой задачи данной разновидности, должно сохраняться. Исследуемая модель не является универсальной моделью вычислений. В [110] установлено принципиальное отличие функциональных свойств многоленточных автоматов от одно ленточных, а именно:

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

Установлено также [110], что в отличие от обыкновенного (одноленточного) конечного автомата, недетерминированные многоленточные автоматы более мощные, чем детерминированные. Это утверждение справедливо и для случая двухленточного автомата.

Для недетерминированных многоленточных автоматов (даже для двухленточных автоматов, которые обычно называются конечными преобразователями) проблема эквивалентности является стандартным примером неразрешимой проблемы [67]. Этот результат неразрешимости был впервые доказан Т.Гриффитсом в 1968 г. [77].

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

Не останавливаясь на всех полученных результатах, отметим те, что являются в известном смысле заключительными. М.Бердом в 1973 [65] показана разрешимость проблемы эквивалентности для двухленточных автоматов. Альтернативное решение для случая двухленточного автомата было дано в [118]. Многочисленные попытки [103,98,71,54,8,7] решить главную проблему привели только к очень скромному успеху, и лишь Т.

Харью и Дж. Кархумяки в 1991 [87] доказали разрешимость в случае любого количества лент.

Особо отметим, что результаты, полученные в [65,118,87], связаны с рассмотрением моделей более широкого толкования, чем многоленточные автоматы. Так М.Бердом исследовались недетерминированные диаграммы , а Т. Харью и Дж. Кархумяки воспользовались Теоремой Равенства Айленберга (Eilenbergs Equality Theorem) [72] для решения множественной эквивалентности для недетерминированных многоленточных автоматов, к которым сводится эквивалентность многоленточных автоматов.

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

- установление частичной разрешимости автоматов путем построения полной системы их э. п.;

- исследования, связанные с использованием достаточных условий эквивалентности;

- построение минимальных по размеру автоматов в классе их эквивалентности.

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

Достиэ/сение цели связывается с решением следующих задач:

• расширение понятия допустимого фрагментного преобразования;

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

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

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

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

При разработке фрагментных преобразований используется опыт предшествующих исследований автора [49 - 53].

Основной результат. Разработан и обоснован новый аппарат (структурный анализ) решения фундаментальных проблем для модели вычислений - многоленточные автоматы, основанный на использовании систем фрагментных преобразований:

В главе 1 дается классическое [9], а также используемое в работе [102] определение многоленточного автомата. Формулируется исследуемая проблематика теории многоленточных автоматов и стратегия их решения [38, 34, 43, 14]. Предлагается решение проблем осуществлять для бинарных многоленточных автоматов с последующим переносом полученных результатов на произвольные многоленточные автоматы [102]. Описывается применяемый при исследованиях аппарат [14,15,41,42,47]. Определяются понятия фрагмента, допустимого преобразования, контекстно-зависимого преобразования [38], исчисления фрагментных преобразований и полных систем [15,16].

Формулируются основные проблемы, решаемые в главах 2 - 4 и общие подходы к их решению.

В главе 2 для каждого п, ш, (п, ш > 2) приводится система э. п., являющаяся полной в множестве М„,т [38]. Здесь через Мп>т обозначено множество п-ленточных автоматов над ш-символьным алфавитом. Разработка э. п. основана на структурно-семантическом анализе рассматриваемого отношения эквивалентности и не предполагает наличия алгоритма разрешения эквивалентности, а значит и его использования.

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

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

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

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

Глава 3 посвящена рассмотрению задачи построения разрешающего алгоритма в моделях вычислений, объекты которых представлены конечными ориентированными графами с разметкой. Предлагаемый подход отличается от изложенного в [87] и назван трансформационным [34], поскольку для распознавания эквивалентности объектов применяет эквивалентные их преобразования.

Отметим, что близким по идейному замыслу, но выводящим из класса детерминированных объектов в класс недетерминированных, является алгоритм разрешения эквивалентности двухленточных автоматов, предложенный Р. Бердом в [65].

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

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

Проводится апробация метода [35] на конечных детерминированных многоленточных автоматах с непересекающимися циклами.

Приводится алгоритм, применяемый к паре многоленточных автоматов, и формулируется гипотеза о достаточном признаке, при наличии которого в классе многоленточных автоматов приведенный алгоритм является алгоритмом разрешения эквивалентности [41].

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

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

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

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

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

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

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

В заключение вынесены наиболее важные результаты, полученные в диссертации.

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

Работа поддерживалась следующими грантами: грант РФФИ 03-01-00132а, грант РФФИ 06-01-00106, внутренними грантами Белгородского государственного университета ВКГ 031-06 и ВКГ 176-07. и

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

Заключение

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

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

2. Расширено понятие фрагментного преобразования, что позволило:

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

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

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

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

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

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

•описаны достаточные условия для проведения классификации по характеристикам сечений как для классов многоленточных, так и конечных автоматов;

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

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

•описан алгоритм минимизации для автоматов этого класса.

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

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

3. Ершов А.П. Об операторных схемах Янова, сб., Проблемы кибернетики, вып.20, М., Наука, 1967.

4. Ершов А.П. Смешанные вычисления // В мире науки. 1984. № 6. с. 2842

5. Журавлёв Ю.И., Флёров Ю.А. Дискретный анализ. 4.1: Учебное пособие. М.: Изд-во МФТИ, 1999.

6. Журавлев. Ю.И., Гуревич И.Б. Минимизация булевых функций и эффективные алгоритмы распознавания // Кибернетика, 1974, № З.с. 1620.

7. Калис A.A. О проблеме эквивалентности многоленточных автоматов, один из которых произвольный. ВЦ ЛГУ

8. Кинбер Е.Б. Об одном классе многоленточных автоматов с разрешимой проблемой эквивалентности // Программирование, 1983, №3, с. 3-16

9. Котов В.Е., Сабельфельд В.К. Теория схем программ. Москва: Наука. 1991. с. 248

10. Летичевский A.A. Практические методы распознавания эквивалентности дискретных преобразователей и схем программ// Кибернетика, 1973, № 4, с. 15-26.

11. Летичевский A.A. Функциональная эквивалентность дискретных преобразователей//Кибернетика, №2, 1969, с. 15-17; №2,1970, с. 14-29; №1, 1972, с. 1-5.

12. Лупанов О. Б. Об одном подходе к синтезу управляющих систем -принципе локального кодирования. Проблемы кибернетики, вып. 14, М., Наука, 1965, с. 31-110.

13. Ляпунов A.A. О логических схемах программ // Проблемы кибернетики, вып. 1, М.: Физматгиз, 1958, с. 46-74.

14. Подловченко Р.И., Хачатрян В.Е. О построении минимальных по размеру двухленточных автоматов // IX межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ. 2007.С. 348-351.

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

16. Подловченко Р.И., Айрапетян М.Г. О построении полных систем эквивалентных преобразований схем программ // Программирование,1996. № 1. с. 3-29.

17. Подловченко Р.И., Полная система подобных преобразований R-схем, сб., Проблемы кибернетики, вып.27, М., Наука, 1973.

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

19. Подловченко Р.И. О построении полных систем эквивалентных преобразований схем программ // Труды XII Международн. конф. «Дискретные модели в теории управляющих систем», М., Диалог-МГУ,1997, с. 46-47.

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

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

22. Подловченко Р.И. От схем Янова к теории схем программ // Математические вопросы кибернетики, М., Физматлит, 1998, вып. 7, с.281-302.

23. Подловченко Р.И. Об одном семействе полных систем эквивалентных преобразований схем программ // Тезисы докл. XII Международной конф. «Проблемы теоретической кибернетики», (Нижний Новгород, 1722 мая 1999), М., изд. мех.-мат. ф-таМГУ, 1999, ч. 2, с. 187.

24. Подловченко Р.И. Об одном массовом решении проблемы эквивалентных преобразований схем программ. I //Программирование, 2000, №1, с. 64-77.

25. Подловченко Р.И. Об одном массовом решении проблемы эквивалентных преобразований схем программ. II //Программирование, 2000, №2, с. 3-11.

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

27. Подловченко Р.И. Алгебраические модели программ и автоматы // Математические вопросы кибернетики, М., Физматлит, 2007

28. Подловченко Р.И. Иерархия моделей программ //Программирование, 1981, №2, с.3-13.

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

30. Подловченко Р.И. Эквивалентные преобразования схем программ для «запутывания» самих программ // Программирование, 2002, №2, с. 66-80.

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

32. Подловченко Р.И., Хачатрян В.Е. Алгоритм распознавания эквивалентности многоленточных автоматов без пересекающихся циклов // Труды 5-межд. конф. Дискретные модели в теории управления систем. Ратмино-Москва. 2003. С. 67-70.

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

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

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

36. Сабельфельд В. К. О преобразовании унарных линейных рекурсивных схем // Кибернетика, 1975, № 5, с. 56-66

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

38. Хачатрян В.Е., Рязанов Ю.Д. Структурный метод распознавания автоматной эквивалентности // Вестник БГТУ. 2003. №6. ч.З. С. 236239.

39. Хачатрян В.Е., Чашин. Ю.Г. Использование преобразований для сравнения моделей на эквивалентность // Межд.научно-практ.конф. Информационные технологии в науке, образовании и производстве. Известия ОГТУ. 2004. №2(3). С. 53-57.

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

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

42. Хачатрян В.Е. О минимизации многоленточных автоматов. XIV межд. конф. Проблемы теоретической кибернетики. Пенза. 2005. С. 161-162.

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

44. Хачатрян В.Е. Минимизация двухленточных автоматов // Труды VII межд. конф. Дискретные модели в теории управляющих систем. Москва, МГУ.2006. С. 379-386.

45. Хачатрян В.Е. Чашин Ю. Г. Преобразование программ микропроцессорных систем управления// Известия высших учебных заведений. 2000. № 10. С. 135-139.

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

47. Хачатрян В.Е. Системы преобразований, сохраняющих различные отношения эквивалентности схем программ. Диссертация на с.у.с.канд. физ-мат наук. Ереван 1979 г.

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

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

50. Хачатрян В.Е. Логико-термальная эквивалентность в классе схем над сильно-невырожденным базисом //Программирование. 1977.№ З.С.20-27.

51. Хачатрян В.Е. Полные системы D-эквивалентных преобразований схем Янова//Программирование. 1978. № 3. С. 16-27.

52. Хачатрян В.Е. Преобразования сохраняющие D-эквивалентность схем Янова (общий случай) // Программирование. 1979. № 1. С. 3-10.

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

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

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

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

57. Яблонский С. В. Элементы математической кибернетики-. М.: Высшая школа, 2007, 191 с.

58. Янов Ю.И. Проблемы кибернетики, вып. I , М: Физматгиз, 1958, с.75-127.

59. Янов Ю.И. Несколько теорем о свертках, АН СССР, ИПМ им. М.В.Келдыша, Москва. 1978. С. 1-73.

60. Янов Ю.И. О локальных преобразованиях схем алгоритмов // Проблемы кибернетики, вып. 20, -М.: Наука, 1968, с. 201-216

61. Aho, А.V., Sethi, R., and Ullman, J.D. Compilers: Principles, Techniques, and Tools. Addison-Wesley 1986

62. Angluin, D. Inference of reversible languages. Journal of the ACM 29, (1982), 741-765.

63. Arnold, A., Dicky, A., and Ni vat, M. A note about minimal nondeterministicautomata. Bull. European Assoc. Theoret. Comput. Sci. 47 (1992), 166-169.

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

65. Berstel J. Trasductions and Context-Free Languages (B.G.Teubner, Stuttgart, 1977).

66. Berstel J. and Reutenauer C. Rational series and Their Languages (Springer, erlin, 1988).

67. 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.

68. Cohn P.M. Free Rings and their Relations,2nd edn. (Academic Press. New York, 1985)

69. Culik K. 11 and Karhumaki J. HDTOL matching of computations of multitape automata, Acta Inform. 27 (1989) 179-191.

70. Eilenberg S. Automata, Lnguages, and Macines, Vol. A (Academic Press, New York, 1974).

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

72. Fisher P. Multi-tape and infinite-state automata. Communications of the ACM, 1965,8:799-805.

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

74. Fuchs L. Partially Ordered Algebraic Systems (Pergamon Press, Oxford, 1963).

75. Griffiths T.V. The insolvability of the equivalence problem for X-free nondeterministic generalized machines. J. ACM, 15,3 (1968), 409-413.

76. Grigorieff S. Modelization of deterministic rational relations. Theoretical Computer Science, 281, (2002), 423D453.

77. Glaister, I., and Shallit, J. A lower bound technique for the size of nondeterministic finite automata. Inform. Proc. Letters 59, (1996), 75-77.

78. Grahne, G., Hakli, R., Nyk'anen, M., Tamm, H., and Ukkonen, E.

79. Design and implementation of a string database query language. Information Systems 28, (2003), 311-337.

80. Grahne, G., Nyk'anen, M., and Ukkonen, E. Reasoning about strings in databases. J. Comput. System Sci. 59, (1999), 116-162.

81. Grigorieff S. Modelization of deterministic rational relations. Theoretical Computer Science, 281, (2002), 423-453.

82. Harju T. and Karkumaki J. Decidability of the multiplicity eguivalence problem of multitape finite automata, in: Proc. 22nd STOC (1990) 477-481.

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

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

85. Harju T., Karhumaki J. The equivalence of multitape finite automata // Theoret. Computer Sci., 1991, 78, p. 347-355.

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

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

88. Hopcroft J.E., and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 1979.

89. Ilie L., and Yu S. Algorithms for computing small NFAs. In Proceedingsof MFCS 2002, Lecture Notes in Computer Science 2420, Springer, 2002, 328-340.

90. Ilie L., and Yu S. Reducing NFAs by invariant equivalences. Theoretical Computer Science, 306, 2003, 373-390.

91. Ilie L., Navarro G., and Yu, S. On NFA reductions. In Theory is forever, Lecture Notes in Computer Science 3113, Springer, 2004, 112-124.

92. Jacobson N. Lectures in Abstract Algebra, Vol. 11 (Van Nostrand, New York, 1953).

93. Jiang Т., and Ravikumar B. Minimal NFA problems are hard. SIAM J. Comput. 22, 6 (1993), 1117-1141.

94. Karhumaki J. On Recent Trends in Formal Language Theory, Lecture Notes in Computer Science 267 (Springer, Berlin, 1983) 136-162.

95. Kinber E. The inclusion problem for some classes of deterministic multitape automata, Theoret.Comput.Sci. 26 (1983) 1-24.

96. Kameda T. and Weiner P. On the state minimization of nondeterministic automata. IEEE Trans. Comput. C-19, 7 (1970), 617-627.

97. Karhurrfaki J. Applications of finite automata. In Proceedings of FCS 2002, Lecture Notes in Computer Science 2420, Springer, 2002, 40-58.

98. Khachatryan V.E. Complete system of equivalent transformations for multitape automata. Programming and Computer Software 29, 1, (2003), 43-54

99. Luckham D.C. Park D.M., Paterson M.S. On formalized computer programs// JCSS, 1970. 4, № 3, p. 220-249. (Русский перевод:

100. Кибернетический сборник. Новая серия, М: Мир, 1975. № 12, с. 78-114).

101. Lewis Н.Р. A new desidable problem, with application. Proc. 18 Ann. Symp. On Foundation of Сотр. Sci. 1979. P. 62-73.

102. Matz O. and Potthoff, A. Computing small nondeterministic finite automata. In Proceedings of the Workshop on Tools and Algorithms

103. Muder D.J. Minimal trellises for block codes. IEEE Trans. Inform.

104. Neumann B.N. On orderd division rings, Trans. Amer. Math. Soc. 66 (1949) 202-252.

105. Passman D.S. The Algebraic Structure of Group Rings (Wiley, New York, 1977).

106. Pin J.-E. On reversible automata. In Proceedings of the first LATIN conference, Lecture Notes in Computer Science 583, Springer, 1992, 401-416.

107. Post E. A variant of recursively unsolvable problem, Bull. Amer. Math. Soc., 52(1946), p. 264 268.

108. Rabin M.O., Scott D. Finite automata and their decision problems // IBM J.of Research and Development, 1959, 3, № 2. p. 114-125 (Русский перевод: Кибернетический сборник, 1962, № 4, с. 58-91)

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

110. Salomaa A. On sentential forms of contexs-free grammars, Acta Inform. 2 (1973)40-49.

111. Shankar P., Dasgupta A., Deshmukh K. and Rajan B.S. On viewing block codes as finite automata. Theoretical Computer Science, 290, 3 (2003), 1775-1797.

112. Tamm H. On Minimality and Size Reduction of One-Tape and Multitape Finite Automata// University of Helsinki, Helsinki, 2004.heory 34, 5 (1988), 1049-1053.

113. Tamm H. and Ukkonen. E. Bideterministic automata and minimalrepresentations of regular languages. In Proceedings of the CIAA 2003, Lecture Notes in Computer Science 2759, Springer, 2003, 61-71.

114. Tamm H. and Ukkonen. E. Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science, 328, 1-2(2004), 135-149.

115. Tamm, H., Nykanen M. and Ukkonen, E. Size Reduction of Multitape Automata . In Proceedings of the CIAA 2005, Lecture Notes in Computer Science, Springer, 2005, 236-244.

116. L.G.Valiant, The equivalence problem for deterministic finite-turn pushdawn automata, Inform, and Control. 25 (1974) 123-133.

117. Watson, B.W. Taxonomies and toolkits of regular language algorithms. PhD dissertation, Faculty of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, The Netherlands,

118. Yamasaki, On multitape automata. In Proceedings of MFCS'79, Lecture Notes in Computer Science 74, Springer, 1979, 533-541.

119. Zakharov V., Zakharyaschev I. On the equivalence-checking problem for a model of programs related with multi-tape automata // Lecture Notes in Computer Science, v. 3317, 2005, p. 293-304.of Mathematics and Computing Science,