Использование преобразований для сравнения моделей на эквивалентность

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

Белгородский филиал Московского государственного университета экономики, статистики и информатики

Белгородский государственный технологический университет им. В.Г. Шухова Россия, г. Белгород,

Использование преобразований для сравнения моделей на эквивалентность

Хачатрян В.Е., Чашин Ю.Г.

Annotatіon

The new approach is offered at construction algorithms of decidable the equivalence problem based on equivalent transformations. Resolvability of equivalence in a class of regular diagrams is proved.

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

AB(AB)(BA),

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

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

* не учитывающий проблему включения;

* использующий систему эквивалентный преобразований.

1. Исследуемые объекты и отношения

Рассматриваемые модели, - детерминированные конечные автоматы Рабина и Скотта и многоленточные автоматы [1] - изображаются в виде диаграмм переходов

[2] и называться диаграммами [3].

Диаграммы строятся над двумя конечными алфавитами:

P={p1,p2,…,pn}, n 2, и Q={0,1}.

Пусть D диаграмма над P и Q. Конечный ориентированный путь w в диаграмме D задается последовательностью дуг. Он описывается историей l(w), где

l(w)=(a1,1), (a2,2),…,(an,n),

aj - метка вершины, из которой исходит j - ая дуга пути, а j - метка этой дуги, j=1,2,…,n.

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

Диаграммы D1, D2, по определению, строго эквивалентны (D1D2) тогда и только тогда, когда для любого маршрута через Dj, j=1, 2, существует маршрут через D3-j, имеющий ту же историю.

pi-проекцией, i=1,2,…., n, пути w, называется слово, полученное из l(w) удалением всех пар, не содержащих символа pi.

Диаграммы D1, D2, по определению, эквивалентны (D1D2) тогда и только тогда, когда для любого маршрута через Dj, j=1, 2, существует маршрут через D3-j, все pi - проекции которого i=1,2,…n, совпадают с pi - проекциями первого маршрута.

В работе [4] рассматривается алгоритм разрешения для строгой эквивалентности.

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

Формально преобразования диаграмм определяются заданием взаимозаменяемых фрагментов.

Фрагмент диаграммы - это ее часть, задаваемая множеством V вершин диаграммы и содержащая вместе с этими вершинами все их инцидентные дуги.

Преобразование диаграмм осуществляется путем замены в диаграмме какого-либо ее фрагмента другим фрагментом. Такие пары взаимозаменяемых фрагментов и определяют систему преобразований, которая обычно задается набором аксиом [3].

Рис. 1

2. Распознавание строгой эквивалентности

Под разверткой диаграммы D будем понимать диаграмму, обозначим ее у1(D), состоящую из древовидного фрагмента, полученную преобразованиями «склейка-расклейка» [3] и содержащую все дуги диаграммы D ровно один раз. На концах этого дерева расположены поддиаграммы диаграммы D.

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

Через 2(у1(D1),D2) обозначим процедуру, которая по древовидному началу Fу1(D1) диаграммы у1(D1) в диаграмме D2 «выделяет» фрагмент F, изоморфный Fу1(D1), и выдает значение «да», если его можно построить, и «нет», в противном случае. Алгоритм выделения изоморфного фрагмента зависит от рассматриваемого отношения эквивалентности. При таком выделении диаграмма D2 преобразуется в эквивалентную ей диаграмму. Это достигается за счет применения преобразований сохраняющих используемое отношение эквивалентности. Для строгой эквивалентности достаточно воспользоваться преобразованиями типа «склейка-расклейка» [3].

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

S1=(s11, s12, .,s1k), -

вершины-листья соответствующего древовидного фрагмента.

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

3. Распознавание эквивалентности

Алгоритм с распознавания строгой эквивалентности [4] может быть обобщен, в частности, на эквивалентность, которая определена в данной работе.

Рис. 2

При этом алгоритм модифицируется за счёт замены процедуры ф2 на ф2*. В последней процедуре происходит выделение необходимой границы и перенос её в выравниваемое место древовидного фрагмента [5]. Обозначим полученный алгоритм через *. В процедуре ф2* используется преобразование, позволяющее менять порядок символов, используемых в диаграммах. Это осуществляется за счет применения преобразования, приведенного на рис.2. Данное преобразование сохраняет эквивалентность преобразуемых диаграмм.

Фрагмент F1 этого рисунка содержит подфрагмент Ф, не содержащий вершин помеченных символом p. Все выходящие из фрагмента Ф дуги направлены в вершины помеченные символом p. Последние составляют p-границу. Во фрагменте F2 эта граница находится в начале фрагмента и состоит лишь из одной вершины. На дугах этой вершины находятся фрагменты Ф(0) и Ф(1), изоморфные фрагменту Ф.

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

Можно показать, что для заданной пары сравниваемых на эквивалентность диаграмм D1,D2, множество пар диаграмм, создаваемых алгоритмом с*- конечно, если D1,D2 однородные диаграммы.

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

-алгоритм с*- ломается; D1/D2;

-алгоритм с* останавливается только за счет изоморфизма проверяемых на эквивалентность поддиаграмм; D1D2;

-алгоритм с* не останавливается, но появляются повторяющиеся пары. Этот факт фиксируется через определённое конечное число шагов; D1D2.

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

Покажем, что для любой проверяемой пары (d,d'):

d'- является диаграммой некоторого конечного множества W;

d- диаграмма, структура которой состоит:

- из древовидного фрагмента, высота которого ограничена для исходной пары диаграмм D1,D2;

- на листьях этого древовидного фрагмента расположены диаграммы из того же множества.W

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

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

Трассу А назовём подобной трассе В, если А можно получить из В, быть может, удалив из В некоторые вершины и макровершины и, быть может, заменив некоторые макровершины родственными.

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

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

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

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

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

- входящие дуги с образов перебросить на копии;

- перенести полученную границу во вход диаграммы, воспользовавшись заменой фрагмента F1 на фрагмент F2 (см. рис.1.).

Утверждение 1. Если D - однородная диаграмма, то поддиаграммы D1,D2 в которые направлены дуги вершины вынесенной из D - подобны D.

Утверждение 2. Множество диаграмм подобных D - конечно.

Обозначим через D1', D2' диаграммы, полученные после 1-го шага алгоритма *. Т.е. D1'является разверткой [5] диаграммы, D2'= ф2*(D1', D2).

Через W - обозначим множество всех диаграмм, подобных поддиаграммам D2'(di'), i=1,..,k, а через N(D1, D2) максимальную высоту древовидных покрытий всех диаграмм из W. Под высотой дерева понимается максимальная длина его ветвей.

Утверждение 3. Любая пара поддиаграмм алгоритма с*(D1,D2), задаваемая вершинами (r,r'), и предназначенная для сравнения, удовлетворяет условиям:

поддиаграмма с входом r' принадлежит W;

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

Следствие утверждения 3. Число пар диаграмм, возникающих в алгоритме с*(D1,D2) и предназначенных для сравнения на эквивалентность, ограничено.

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

Теорема 4. Алгоритм * является алгоритмом разрешения эквивалентности в классе однородных диаграмм.

Литература

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

2. Bird R. The equivalence problem for deterministic two tape automata // Journal of Computer and System Science. 1973. V. 7. № 4. P. 218-236.

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

4. Хачатрян В.Е., Рязанов Ю.Д. Структурный метод распознавания автоматной эквивалентности. Международный конгресс «Современные технологии в промышленности строительных материалов и стройиндустрии». 2003 г.

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

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

Размещено на Allbest.ru