1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 33
Текст из файла (страница 33)
рис. 7.10). Боли Х вЂ” множество переменных, а Р— множество предикатных символов, то черве К (Х, Р) будем обовначать множество э 1 рао. 7ЛО. Пример оовооождеввв л-фрагмента 15г всех сетей в), в которых для любого элемента с выполнено %' (с) ~ Х [) Р ( [ (О, 1). Если Х, Р— конечные множества, то (К (Х, Р), /~) — конечная полурешетка. Определим преобрааователь сетей (ЗАБЫТБ), ноторый произвольную сеть в с:— М' преобразует в сеть в' = (ЗАБЫТЬ) ь. ка К (Х, Р) следующим образом: 1) если «=1, то в'=1; 3) если в чь 1, то пусть сеть в1 получается из в удалением всех элементов с, для которых Ч' (с)»." — Я; в' = ге»[ (в1).
Содержательно, преобразователь (ЗАБЫТЬ) удаляет из .аэзег1 (в) все утверждения, кроме равенств х = у с х, у ~ Ю н равенств Л = р (х) с Л ~ (О, Ц, р е= З», х»=Я". Условие распознавателя А обозначается ннже ол. Т е о р е и а 7.7. Всякую сквозную схему Я можно преобраао«отпь в акен«оленя»ную свободную сквозную схему.
Д о к а з а т е л ь с т в о. Как уже отмечалось, для докааателъства достаточно преобразовать всякий максимальный связный л-фрагмент приведенной схемы 8 в свободный. Пусть б— такой фрагмент. Если он не содержит распознавателей, то ои уже свободен н ничего делать не нужно. Пусть в б имеется й. :1 распознавателей, к которым ведут входы фрагмента б. Применяя при к ) 1 правило копирования, ааменим 6 на й его копий 6» (1 -":; ~( 1 ~~ к) так, чтобы л-фрагмент 6» имел ровно один распознаватель А», к которому ведут входы этого фрагмента.
Еще раэ применяя правило копирования, преобразуем 6» во фрагмент 6;. Прн описании фрагмента б; будем обозначать копни вершины А иэ 6» через А[4, где в ~ К(Ха, Рв). Все входы фрагмента б; направим к вершние А, [О[. Если А — распознаватель фрагмента 6», Л-дуга которого ведет к вершине Вь, то Л-дугу распознавателя А[в[ в 6» направим к вершине Вь [(Л = ол) в[; если А — опера-тор присваивания х:= т, выходная дуга которого ведет к вершине В, то выходную дугу оператора присваивания А[в[ направим к вершине В [(ЗАБЫТЬ) (х:= т) 4. Иа построения фрагмента б; следует, что для стационарной ,разметки р этого фрагмента, для всякой вершины А Ы и любой .ведущей к ней дуги е справедливо р (е) ° в. Покажем, что если условие ол распознавателя А Ы Л-избьпочио иа некотором пути ю, ведущем к А [4, то А [4 — формально Л-избыточный распознаватель.
Действительно, Л-избыточность оа на пути ю оаначает, что ю = ю» В [в'[»оа для некоторого распознавателя В [в'[, причем»оа начинается Л-дугой н $ (ю, о„) = — ов. Следовательно, (Л = оя) в = в, т. е. распознаватель А Ы является формально Л-избыточным. Таким образом, для освобождения фрагмента б' достаточно удалить каждый распознаватель А Ы, который является формально Л-избыточным с некоторым Л к= (О, 1). Пока° ) Если ве оговор«во противное, под сетно в дальнейшем будет ооввяаться правээольэзя обобщеэиая сеть (обь»чзо врээедеввая). 1б2 жем, как это сделать.
Прежде всего, можно предполагать, что дуги такого распоэиавателя А (е) ведут к другим вершинам фрагмента, вставляя в противном случае подходящую вырождеииую пересылку х:= х иа вти дуги. Далее, применением правила копировакия соэдадим копии вершины А Ы таким обравом, чтобы и каждой иа копий вела ровно одна дуга. Раэумеется, все копии по-прежкему будут формальио д-иэбыточкыми распоаиавателями.
Примекеиием правила Ф1 (удалевие иэбыточиого теста) мы сможем иэбавиться от всех только что соадаияых копий распоэиавателя А (е). После удалеиия всех формально Л-иэбыточвых с некоторыми Л ~ (О, Ц распоэвавателей и последующего приведения мы получим свободный л-фрагмект. Д На рис. 7АО покаааи пример, иллюстрирующий переход к свободвому л-фрагмевту. Для описаиия алгоритма расповпавапия вквивалеятиоста двух приведеивых свободных сквовкых схем дт и Яз вам потребуется еще, чтобы выполнялось следующее условие разделенности переменных схем 8 и Яз: если некоторая неременнал х встречается е каждой ив схем 8ю Яз, то ети схемы не содержат операторов присваивания с реаулыпатом х.
Выполиекие этого условия достигается совершевко акалогичко тому, как это сделана в п. 3.2 гл. 6. Сначала применением ЛТ7 каждый иэ вачалькых операторов старт (х„..., х„) эамекяется па луч старт(х,,...,х„) х;. х, х,:=х, "-.. ~х: хД- Затем все вхождения каждой иэ перемеивых у, встречающихся . в схеме (кроме реаультатов вачальвого оператора и аргументов вставлеииых пересылок), примевеиием ЛТ4 эамевяются новой переменной х, которая еще ве встречается пи в Яз, ки в 8 . В реэультате условие раэделеииоств перемеявых схем 8 и Я окажется выполкевкым. 3 а д а к и о 7А. Докажите, что для каждой стандартной схомм, удовлетворяющей условиям Ш и приведоккому виже более слабому, чем ))2, условию 02', по-прежнему можио аффективно построить эквввалоитаую саободиую схему.
(зз2 ) Для всякого распознавателя А тз, у зи арз (Л) (тГм зп И' Г (и, Я) = Ф (и, У)) ~/ (тм зи И'л З (и, а) ~ З (и, У)), гДс (Ул — множество асса путей, ведущих к л от входа стоим. 3 а д а и и о 7.5. Докажвтс, что повятия ссдержатсльиой и формальиой Ь-азбмточиости распознавателей совпадают для фрагментов, в котормх к каждой коржике падет ровно <щна дуга. 2.4. Алгермтм распоэиаваивв эквивалеитпоств сквоэиых схем. Идея расповиающего алгоритма т( состоит в том, что по двум приведеквым свободным сквоввым схемам 8з, Ю„удовлетворяющим условию раэделеииости переменных, мы строим граф О (дт, Ят), который можно рассматривать как иедетермииировавиую схему, моделирующую синхронные вычисления обеих схем. Пусть Хо Р» — множества переменных и предпкатпых символов соответственно, встречающихся в схеме Я», » = 1, 2; Х = = Х» [) Хз, Р = Р» [ ) Рз, К = К (Х, Р).
Вершины схем Ям 8, отличные от операторов присваивания, будем называть ключеаими. Если А,  — распознаватели схем 8, 8, у»-= арг(В), лба М', з чь 1, то положим »уз (А, В, з) = ('с [(у = т)»"=:— авзег» (з) и терм т содержит вхождения переменних только той из схем 8», Юз, е котпарой находится вершина А), 1е (А, В, з) =- ( — заключительный оператор или оператор пет ш, а А — распознавал»ель) ~/ (А,  — распознаватели) 8» (ч»у»." — арг (В) 3 тз е= »уз(А, В, з) чх»== арг (А) х ( -~ ав [тз/у [ у б= арг (В))), еа (А, В, з) = 1е (А, В, з)»х 1е (В, А, з). Веря»ивами графа О (8» 8з) будут служить тройки [А, В, з), где А,  — ключевые вершины схем Ю, 8, соответственно, а з Е= »== У', з ~ 1. Ив каждой вершины в О (В» Яз) будет выходить пе более четырех дуг, среди которых будут различаться 8»-дуги и Я -дуги, причем капп»яя из пих может быть либо О-, либо 1-дугой. Вершину [А, В, з) графа О (Я„уз) можно интерпретировать как состояние синхронных вычислений схем 8» и Я„которое означает, что 8»-вычисление достигло вершины А, а Я -вычисление достигло вершииы В, причем в атом состоянии истнкиы все утверждеиия, содержащиеся в аззвгФ (з).
Истинность предиката 1е (А, В, з) па таком состоякки оапачает при атом, что 8 -вычисление ие опережает 8 -вычисления. Точками синхронизации будут служить состояния, в которых истинно условие е»1(А, В, з): Я; и Я -вычисления пе опережают друг друга. Заметим сразу,что благодаря ацикличпости сетей из М' условие е»1 (А, В, з) равпосильио условию Ухб= арг (А) 3у Е арг (В) (х = у) Е= азвегй (з) б» 8»»ту»-= арг (В) 3х ~ арг (А) (х = у) Е= аззегз (з). Для описания алгоритма з( понадобится вспомогательная память — трехмерная таблица ТТ, в которой для всякой тройки [А, В, з[ такой, что А,  — ключевые вершины схем 8„8з, а з »= К и е»1 (А, В, з), будет храниться некоторый злемент ТТ [А, В, з) — сеть из Я'.
Алгоритм %. Первый этап — инициализация. Пусть ю» (» = 1, 2) — путь в схеме 8», пачикающийся ее входом, содержащий только опера"торы присваивания и заканчивающийся дугой, которая ведет к ключевой вершине А„з = у, (у,„(6)). Напомним (см. п. 2.2), что функция у представляет собой суперпозицию преобразователей сетей, соответствующих проходимым вдоль пути ю вершинам. Граф О (Вм 8,) будет иметь ровно один вход е, который направим к вершине гз = [А», Аз, зз). Варшаву ге объявим достизсил»ой и необработанной Все влемепты таблицы ТТ инициализируются значением 1.
Если е»1 (Ам Аз, зз), то положим ТТ [А», Аз, (ВАВЫТБ) з,) = зз. 454 Второй этап алгоритма состоит в повторении трех описанных ниже шагов до тех пор, пока не будут исчерпаны достижимые необработанные вершины графа О (8, Зг). Пусть о = [А, В, г$ какая-нибудь достижимая необработанная вершина. Шаг 1. [Проееоение 8;дуг!. Если ~1е(А, В, г) бс 1е(В, А, «), то никаких З,-дуг иа опроводнться не будет. В противном случае пусть юд (Л = О, 1)— путь в схеме З„начинающийся Л-дугой распознавателя А, содержащий только операторы присваивания н заканчивающийся дугой, которая ведет к ключевой вершине Сд в 3 . Построим сети гд = у„((Л = ад) г) для Л = О, 1.
Если гд = 1, то Л-дуга иэ о проводиться не будет. Если же гд -ь 1, то при ~ еп (Сд, В, гд) проводим Л-дугу от о к вершине од — — [Сд, В, гд), а при еп (Сд, В, гд) построим сети уд — — (ЗАБЫТЬ) гд и гд = '1 Р [Сд, В, гд! /~ гд, положим [Т [Сд, В, гд! = = гд и проведем Л-дугу вершины о к вершине од = [Сзд, В, гд!. Проводимые на этом шаге дуги называются З,-дугами графа 0 (Зп Зг). Вновь создаваемые на этом шаге новые вершины объявляются достижимыми и необработанными.
)Наг 2. [Проееоение Я -дуг!. Если ~ 1е (В, А, г) А 1е (А, В, г), то никаких 8-дуг из о проводиться ие будет. В противном случае пусть юд (Л = О, 1)— путь в схеме Я„начинающийся Л-дугой распоанавателя В, содержащий только операторы присваивания и заканчивающийся: дугой, которая ведет к ключевой вершине Юд в Яг. Построим сети гд=уд((Л=ав)г) для Л=О, 1. Если гд = 1, то Л-дуга из о проводиться не будет. Если же гд ~ 1, то прн ! еп (А, Юд, гд) проводим Л-дугу от о к вершине од — — [А, Юд, гд), а при ец (А, Юд, гд) построим сети Уд — — (ЗАБЫТЬ) гд и гд = 'ХТ [А, Юд, гд! /~ гд, положим ТТ [А, Юд гд! = гд и проведем Л-дугу вершины о к вершине од = [А, Юд, гд!. Проводимые на атом шаге дуги называются 3;дугами графа 0 (Зп Яг).
Создаваемые на этом шаге новые вершины объявляются достижимыми и необработанными. Пзаг 3. [Проверка на безуспешное окончание!. Алгоритм заканчивается беэ успеха, если для вершины о = =- [А, В, г! выполнено хотя бы одно из следующих трех условий. (За) А — ааключптелькый оператор стоп (г„..., к ), В— заключительный оператор стоп (у, ..., у„) с некоторыми гм ... ..., к, у,..., у„Е= Х, причем и Ф л или 31(1 ~(1~~; л). (к, = у;) Ю аззегь (г).
(36) Одна из вершин А,  — заключительный оператор, а другая — оператор петли. Рв) СУществУет пУть оп ..., ог в гРафе 0 (Зд, 8 ) такой, что "г=о> и ) 1' ~1(1~([~~я) гч = [А» В» э[бс ! еп (А»В„г), А =А,В =В. Если условия (За), (36) н (Зв) ложны, то вершина о объявляется обработанной и алгоритм продолжается применением шагов. 1$ь ! — 3 к другим достижимы!! необработанным вершинам графа О (Я», Вг).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
