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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

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

специальность 01.01.09 дискретная математика и математическая кибернетика

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

Хачатрян Владимир Ервандович

Москва 2008



Работа выполнена в Белгородском государственном университете на факультете компьютерных наук и телекоммуникаций

Консультант: доктор физико-математических наук, профессор Подловченко Римма Ивановна

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

член-корреспондент НАНУ, доктор физико-математических наук, профессор Летичевский Александр Адольфович

доктор физико-математических наук, профессор Сапоженко Александр Антонович

доктор физико-математических наук, профессор Ломазова Ирина Александровна

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

Ученый секретарь диссертационного совета профессор Трифонов Н.П.

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

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

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

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

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

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

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

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

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

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

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

Все три задачи объединяет следующее: их решение базируется на

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

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

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

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

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

множества M_n,m, где n, m ? 2;

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

подмножества множества M_n,m, состоящего из однородных автоматов, где n, m ? 2;

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

Из теорем 2.3, 2.5 следует частичная разрешимость проблемы эквивалентности в множестве M_n,m и, соответственно, в множестве автоматов с непересекающимися циклами, принадлежащих M_2,2. Из теоремы 2.7 следует полная разрешимость проблемы эквивалентности в множестве однородных автоматов, принадлежащих M_n,m.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад соискателя. Результаты, изложенные в диссертации, получены автором самостоятельно и опубликованы в работах [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 рисунков.



2. Содержание работы

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

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

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

В разделе 1.1 дается используемое в работе определение конечного детерминированного n-ленточного автомата, n 2, над алфавитом , где

={у₁, у₂ ,…, у_m}, m 2.

Воспроизведем это определение. Автомат состоит из управляющего графа, вершины которого называются его состояниями, и n бесконечных лент, обозначенных символами p₁,…, p_n, n 2, и заполненных символами из ={у₁, у₂ ,…, у_m}, m 2. На каждой ленте имеется считывающая головка, движущаяся вправо. Управляющий граф - это, по определению, конечный ориентированный граф, в котором выделены три различных состояния: инициальное, финальное и мертвое. Из каждого состояния, кроме финального и мертвого, исходят по m дуг, помеченных различными символами у₁, у₂ ,…, у_m; из финального и мертвого нет исходящих дуг. Любое отличное от них состояние помечено символом p_i, i=1,2,…,n и называется p_i-состоянием, i=1,2,…,n.

Функционирование автомата ведется на лентах p₁,…, p_n, которые в общем случае заполнены произвольными символами из . Оно состоит в обходе управляющего графа. Этот обход начинается с инициального состояния в условиях, когда считывающие головки лент стоят на первых позициях.

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

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

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

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

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

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

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

В разделе 1.3. формулируется проблема эквивалентных преобразований в множестве M, где M некоторое множество диаграмм. Она состоит в поиске нетривиальной полной в M, системы эквивалентных преобразований. Отметим, что система T э. п. диаграмм, называется полной в M, если для любых двух эквивалентных диаграмм D', D” из M существует цепочка D₁, D₂,…_, D_k, k 1, такая, что D' = D₁, D” = D_k, и преобразование D_i в D_i+1 принадлежит системе T.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Через M_n,m обозначим множество многоленточных автоматов над алфавитами: P = {p₁, p₂, …, p_n}, n 2 и Q = {₁, ₂,…, _m}, m 2.

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

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

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

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

Теорема 2.2. Система преобразований Т_2,2 является полной в M_2,2.

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

Аксиома C1. Фрагмент F₁, не имеющий входящих дуг и не содержащий входа диаграммы, эквивалентен пустому фрагменту F₂.

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

Аксиома С3. Пусть фрагмент F₁ допускает разбиение множества всех его вершин на непересекающиеся классы V₁, …, V_k такие, что

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

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

Опишем фрагмент F₂, получаемый по фрагменту F₁. Его внутренними вершинами являются v₁', v₂', …, v_k', отличные от вершин фрагмента F₁. Из v_i' в v_j' ведет дуга с меткой , где Q, если дуги с меткой ведут из вершин класса V_i в вершины класса V_j ; если же эти дуги являются выходящими из V_i и оканчиваются в состоянии v, то дуга из v_i' с меткой ведет в v. Если в какую-либо вершину из V_i ведет входящая дуга фрагмента F₁, то она направляется в вершину v_i'.

Фрагменты F₁ и F₂ эквивалентны.

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

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

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

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

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

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

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

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

По фрагменту F₁ построим фрагмент F₂ с теми же внешними входами и внешними выходами, что у фрагмента F₁.

Построим образ u вершины v, полагая, что u - это вход диаграммы, если v - вход диаграммы, и в противном случае - единственный внутренний вход фрагмента F₂; между входящими дугами в F₂ и входящими дугами в F₁ определим взаимно однозначное соответствие, устанавливаемое совпадением их начал. Полагаем, что метка u совпадает с меткой граничных вершин F₁.

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

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

Рис. 1

На рис.1 во фрагменте F₁ выделена граница. Вершины, ее составляющие, имеют метку q. Имеются две дуги, исходящие из граничных вершин и направленные во внутренний вход фрагмента F₁. Он помечен номером 5. Неграничные вершины включены во фрагмент и имеют метку p. Вход фрагмента F₂ выделен и имеет метку q. Согласование внешних выходов фрагментов и с внешними выходами фрагмента F₁ задается совпадением их номеров.

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

Фрагменты F₁ и F₂ эквивалентны.

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

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

Аксиома С5. Пусть F₁ - древовидный фрагмент диаграммы D; (v_i, v_i') - пара эквивалентных вершин фрагмента F₁, i = 1, 2, …, k, где v_i - внутренняя вершина F₁, а v_i' - внешний выход фрагмента F₁, отличный от выхода диаграммы и пустого цикла.

Построим фрагмент F₂. Для этого выходящую дугу фрагмента F₁, направленную во внешний выход v_i', направим на эквивалентную ему вершину v_i, и так для всех i = 1, 2, …, k.

Фрагменты F₁, F₂ эквивалентны.

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

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

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

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

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

В п.2.1.4 приводится обобщение полученного результата для множества M_n,m, n 2, m 2.

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

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

Аксиома С4 n,m. Пусть F₁ - фрагмент с i-границей, i{1, 2, …, n} и F₂ - фрагмент, полученный из F₁ построениями, выполненными в описании аксиомы С4.

Фрагменты F₁, F₂ эквивалентны.

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

Теорема 2.3. Система Т_n,m полна в М_n,m, где n > 2, m 2.

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

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

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

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

Система T₀ задается аксиомами С1, С2, С3, С6, С7.

На рис. 2.а и 2.б схематически описаны пары фрагментов F₁, F₂, задающих аксиому С6. Здесь символами F⁽¹⁾,…, F^(l), l ? 2, обозначены фрагменты, изоморфные фрагменту F и не содержащие p-состояния, а ₁,…, _m, m ? 2, изоморфны фрагменту . Соответствие между некоторыми внешними выходами, указано совпадающими натуральными числами. Возможное наличие нескольких дуг, ведущих в одну и ту же вершину, фиксируется двойной стрелкой.

а б

Рис. 2

Фрагменты F₁ и F₂ эквивалентны.

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

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

Если v₁, v₂ - эквивалентные вершины, то фрагменты ₁, ₂ также эквивалентны.

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

Пусть w путь в некоторой диаграмме, и w проходит по циклу w₀, т. е. w можно записать в виде w₁w₀w₂. Тогда, если w₂ не пуст, и первая его дуга не принадлежит w₀, то говорим, что путь w покидает цикл w₀. Рангом пути w назовем число покинутых им циклов, а рангом диаграммы максимальный ранг маршрутов через нее.

Пусть D₁, D₂ эквивалентные приведенные диаграммы, и ранги их больше 0. Тогда (Лемма 2.8) преобразованиями из T₀ диаграммы D₁, D₂ можно трансформировать в приведенные диаграммы D₁', D₂', соответственно, содержащие такие изоморфные фрагменты со входами F₁, F₂, что

s({D₁,D₂})>s(M(D₁',F₁) M(D₂',F₂)). (1)

Здесь M(D,F) множество диаграмм D(v), где v внешний выход фрагмента F со входом, s(D) число неизбыточных маршрутов, т.е. маршрутов через диаграмму, ранг которых совпадает с рангом диаграмм D₁, D₂ и которые всякий раз проходя по некоторому циклу, содержат не более одного витка этого цикла.

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

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

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

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

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

Аксиома С8. Пара фрагментов F₁, F₂, принадлежащая ей, изображена на рис. 3.

Рис. 3

Овалами очерчены подфрагменты фрагментов F₁ и F₂; каждый из этих подфрагментов имеет в точности одну входящую дугу и все внутренние его вершины помечены общим для него символом; этот символ вписан в овал. Графы, полученные из подфрагментов отбрасыванием входящих в них дуг, изоморфны, когда подфрагментам соответствует один и тот же символ; при этом вершины, в которых оканчиваются отброшенные дуги, изоморфны друг другу. Между дугами, выходящими из подфрагментов F₁₀ и F₂₀, и дугами, выходящими из других подфрагментов, имеется соответствие, устанавливаемое совпадением вершин, в которых оканчиваются выходящие дуги фрагмента F₁ и фрагмента F₂; оно продемонстрировано на рис.3 парой дуг с метками a и b и вершиной n₂.

Фрагменты F₁ и F₂ эквивалентны.

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

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

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

Полученные результаты справедливы и для многоленточных однородных автоматов над алфавитами P = {p₁, p₂, …, p_n}, n 2, Q = {₁, ₂,…, _m}, m 2.

Рассмотрим аксиому С8*, которая отличается от аксиомы С8 только тем, что пара фрагментов F₁, F₂ входит в аксиому С8*, если вершины корня фрагмента F₁ и всех ветвей фрагмента F₂ помечены одним и тем же символом, а вершины корня фрагмента F₂ и всех ветвей фрагмента F₁ этим символом не помечены. Они могут быть помечены любыми другими символами алфавита P = {p₁, p₂, …, p_n}, n 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предписание 1. Процедура должна работать таким образом, чтобы имело место утверждение: графы G₁,G₂ эквивалентны тогда и только тогда, когда не ломается на паре (G₁,G₂), и каждый из построенных потомков вершины (G₁,G₂) состоит из эквивалентных графов.

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

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

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

Пусть (G₁,G₂) вершина дерева T, к которой применяется . Процедура планируется как последовательное выполнение процедур ₁ и ₂.

Предписание 2. Процедура ₁ должна осуществить эквивалентную развертку графа G₁ в граф G₁' и сделать это так, чтобы к G₁' была применима процедура , выполняющая эквивалентную свертку графа G₁' в граф G₁.

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

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

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

2) набор R эквивалентных преобразований, выполнимых в случае, когда удовлетворены условия из Q, и достаточных для трансформации графа G₂ в требуемый граф G₂'.

Тогда действия процедуры ₂ будут состоять в пошаговом построении копии купола F; каждый шаг начинается проверкой условий из Q; если они не выполнены, то построение копии прекращается с заключением: графы (G₁,G₂) неэквивалентны; это событие квалифицируется как поломка процедуры ; если же проверяемые условия удовлетворены, то преобразованиями из R осуществляется очередное приращение уже построенной части купола F и переход к следующему шагу процедуры ₂.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В п.3.2.6. приводится обобщение результата на случай произвольных многоленточных автоматов. Рассмотрим многоленточные автоматы над алфавитами P={p₁,…,p_n}, n 2 и Q={₁,…,_m}, m 1.

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

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

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

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

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

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

Сечение, каждая вершина которого помечена парой графов, совпадающей с парой, метящей одну из вершин дерева T(G₁,G₂), предшествующих данной вершине, назовем -сечением.

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

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

Теорема 3.6. Если G₁, G₂ графы с непересекающимися циклами, то G₁ эквивалентен G₂ тогда и только тогда, когда дерево T(G₁,G₂) заканчивается -сечением, причем высота начального фрагмента не превышает числа n+3, где n ранг сравниваемых графов.

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

если дерево потомков T(G₁,G₂) графов G₁,G₂ обладает -сечением, то графы G₁,G₂ - эквивалентны.

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

Обозначим Re((D₁,D₂)) множество всех меток вершин дерева потомков T(D₁,D₂). Пару диаграмм (D₁,D₂) назовем -ограниченной, если множество Re((D₁,D₂)) конечно.

Теорема 3.8. Если алгоритм (D₁,D₂) не ломается, то дерево потомков T(D₁,D₂) обладает -сечением тогда и только тогда, когда пара (D₁,D₂) является -ограниченной.

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

...