Почти однородные информационные модели

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

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

Почти однородные информационные модели

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

Information model - logic structure of circuits of programs with the relation rearrangement [1]. The investigated model is adequate to multitape automats [2]. The basic result consists in construction of complete system of equivalent transformations for some subclasses of information models. The last are set by logic graphs with disjoint loops, each of which is equivalent to some homogeneous logic the graph.

однородный информационный модель

Рассматриваются модели, определяемые над двухбуквенными алфавитами. Пусть R={p,q} и S={+,-}. Логическим графом назовем конечный ориентированный граф, в котором выделена одна вершина, называемая входом; существует единственная вершина (несовпадающая со входом), из которой не исходит ни одной дуги, такая вершина называется выходом; из всякой вершины, отличной от выхода, исходят две дуги; все дуги помечены символами "+", "-", причем дуги, выходящие из одной вершины помечены различными символами; каждой вершине, за исключением выхода, приписан некоторый символ из алфавита R.

Каждому пути l, ведущему из некоторой вершины a логического графа в вершину b, сопоставим слово L в алфавите RS, называемое историей пути. Слово L получается последовательным выписыванием меток вершин и дуг пути l.

Проекцией слова L на символ r, rR, назовем последовательность, полученную из L вычеркиванием всех таких пар, первый символ которых не есть r. Проекцию слова L на символ r будем обозначать через прL.

Будем говорить, что пути L₁, L₂ эквивалентны (LL), если, каким бы ни был символ rR, проекции историй этих путей на r совпадают.

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

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

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

Легко убедиться в справедливости.

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

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

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

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

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

Всякая аксиома A.I: вместе с правилом вывода определяет преобразование информационной модели в или наоборот.

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

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

Рассмотрим систему преобразований Т, состоящую из аксиом A.0 - A.3.

Аксиома A.0, FF.

Аксиома A.1. Называется аксиомой расклейки [1], хотя позволяет как расклеивать, так и склеивать вершины. По этой аксиоме фрагмент, состоящий из одной вершины, можно заменить на две с теми же самыми выходящими дугами. Приходящими же дугами этих вершин являются все приходящие дуги исходной, причем на одну из них направлена лишь одна дуга, а все остальные направлены во вторую вершину.

Для описания аксиомы A.2 введем дополнительные определения и обозначения. Пусть S - некоторое множество вершин фрагмента F; через F(S) обозначим подфрагмент фрагмента F, порожденный множеством S и рассматриваемый с приписанными его вершинам и дугам меткам.

Максимальный подграф фрагмента F(S) назовем его телом.

Фрагмент, имеющий единственный вход, назовем d-фрагментом.

Фрагмент, в котором из любой его вершины достижима любая вершина этого же фрагмента, назовем макровершиной.

Пусть S - множество всех вершин d-фрагмнета. Разбиение S на попарно непересекающиеся и непустые подмножества S,...,S назовем рассечением фрагмента, если для всякого i под фрагмент F(S) является d-фрагментом; приходящими дугами d-фрагментов являются все исходные дуги фрагмента F(S) и только они; кроме того, тела фрагментов F(S),...,F(S) изоморфны друг другу с сохранением их входов.

Зададимся бесконечным алфавитом X={u,...,u,...}.Соответствие, при котором каждой исходящей дуге фрагмента приписывается символ u_i, назовем правильным, если одинаковые символы приписаны только дугам с одинаковыми метками, причем эти дуги исходят из изоморфных тел d-фрагментов и начала дуг соответствуют друг другу при этом изоморфизме.

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

1) корень одного из них и ветви другого изоморфны с сохранением их входов;

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

Аксиома A2. Если F и F сопряженные, то .

Последнюю из рассматриваемых нами аксиом, аксиому A.3, назовем склейкой однородных циклов.

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

Теорема 2. Система преобразований T является полной в классе почти однородных информационных моделей с непересекающимися циклами.

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

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

Лемма 1. По любой информационной модели из класса K(R,S) преобразованиями A.0 и A.1 можно построить модель, принадлежащую классу K(R,S).

Лемма 2. Пусть A K(R,S) и его вход помечен меткой p. Тогда существует однородная информационная модель, которая эквивалентна A, вход которой не принадлежит циклу и помечен меткой p.

Действительно, пусть B однородная информационная модель, которая эквивалентна A.

Если её вход помечен меткой p и принадлежит циклу, то, используя лишь преобразования A.1, легко получить необходимую информационную модель. Если же вход B помечен меткой q, то проделаем следующее. На каждом пути, ведущем из входа B в его выход, отметим ближайшие вершины, помеченные меткой p. Наличие таких вершин гарантируется эквивалентностью исходных информационных моделей. Преобразованием A.1 добьемся, чтобы все эти вершины не принадлежали циклам. Затем, применяя преобразование A.2, получим информационную модель, удовлетворяющую условию леммы.

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

Лемма 3. Если A - почти однородная информационная модель, то A(a) также является таковой.

Действительно. Рассмотрим путь L, ведущий из входа A в вершину a, и пусть B-однородная информационная модель, эквивалентная A. Преобразуем B в B' так, чтобы в B' существовал путь L, исходящий из входа. Возможность такого преобразования обеспечивается справедливостью леммы 2. Если b вершина, в которой завершается путь L, то B'(b) A(a). Поскольку B'(b) однороден, то A(a) почти однороден.

Проведем доказательство теоремы 2. Его достаточно провести лишь для информационных моделей класса K(R,S) (см. лемму 1). Доказательство проведем методом математической индукции по числу неоднородных макровершин.

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

Пусть k=1, B - однородный, BA и BK(R,S). Рассмотрим все пути, ведущие из входа A во входы макровершин и не проходящие через них. Обозначим через l и l соответственно наибольшее вхождение символов p и q в таких путях.

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

Используя A.1, преобразуем макровершину, содержащую вход A, в макровершину, содержащую rn+rm вершин, причем rn-вершины с меткой p и rm - с q. Обозначим полученную информационную модель через A'. Используя преобразования системы T, проделаем следующее: если входы a и b A' и B одинаково помечены, то перейдем в этих информационных моделях по дугам, оставляющим нас в неоднородном цикле A. Обозначим через вершины, в которые осуществлен переход. Понятно, что .

Если же входы помечены различными символами, то, преобразуя A' с помощью преобразований A.1, A.2, добьемся, чтобы входы были одинаково помечены, и лишь затем проделаем выше указанный переход.

Такой одновременный переход по логическим графам будем осуществлять до тех пор, пока в B не встретится вершина b_t, принадлежащая макровершине. Понятно, что trn+rm. Но тогда вершины а_tи b_tодновременно принадлежат макровершинам. Используя A.1, преобразуем A' в A'' так, чтобы вершина aстала входом A''.

Предположим, макровершина, содержащая вершину b_t, состоит из v вершин, имеющих метку p и u=нок(v,rn). Преобразуем макровершину содержащую a_t, преобразованием A.1 так, чтобы в ней стало u вершин с меткой p и добьемся, чтобы все вершины с меткой p предшествовали в этой макровершине вершинам с меткой q.

Это возможно, ибо A(a) B(b) и B(b) - однороден.

Тогда путь, ведущий из вершины a_n в нее же, будет иметь вид L'L'', где L'=(Lb - путь, ведущий из b_n в b_n, а L''= .

Обозначим через c вершину A, в которую ведет путь L'. Понятно, что A(c) A(a_n). Но тогда макровершину, содержащую a_n, можно получить из однородных макровершин, задаваемых путями L' и L'' с использованием преобразования A.3.

Таким образом, неоднородная макровершина «получается» из однородных, а для однородных информационных моделей A.0, A.1, A.2 образуют полную систему преобразований [4].

Предположим, теорема верна для k=m. Докажем ее для k=m+1. Рассмотрим некоторую вершину a, такую, что A(a) содержит не более чем m неоднородных макровершин. Тогда предположение проходит для информационной модели A, в которой вместо A(a) подставлена однородная информационная модель B(b). Наличие последней следует из справедливости лемм 2 и 3.

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

Литература

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

2. Bird, M. The equivalence problem determenistic two tape automata [Text] / M. Bird // YCSS.1973. - Vol. 7. - №2. - p. 218-236.

3. Хачатрян, В.Е. Однородные логические графы. Прикладная математика [Текст] / В.Е. Хачатрян. - Ереван; Изд. ЕГУ, 1981. - с. 68-80.

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

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