1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 26
Текст из файла (страница 26)
Понятие влияния понадобится нам для формулировки преоб. рааования удаленвя неиспользуемых преобрааователев. 3 з д а к н е 6Л. Сформулкручы задачу глобального анализа слекы л, решение которой ноззоляет ваходвть все вгршввы компоненты связноегв ааформзцнонноге графа схемы 8, содержащей выделенный результат т выделенного операторе й. Полурепмтке свойств: Ь вЂ” множество подмножеств двухзлеиентвого множества (х (, х $ ), оиерзцая полурыпеткп — объедвненпе подмныкестз.
Преобрззозатела свойств: зсе днстрнбутвввые функции пз Ь. Семевткческая фувкцвя: (~~ (ж) — -- (х ( ( (х ( «в и) «% (т «я рез (вач (е))) 6«(нзч (е) = кон (х'))) «««' ( 1 (х ( ( (х ) «в з«) 6«(х ш роз (коа (х))) 6«(ков (х) = нзч (е'))) () ( «(х ( ) (х ( «н и«) 8«(х «в рез (вач (ей) 6«(нзч (х) = вач (х'))) О (( (х ) ) (х ( ж з«) 6«(х «н арг (кон (х))) 6«(кон (х) = ков (х 3). Начальная разметке: (хЦ, если х — выходная дуга выделенного оператора 3, р«(~) д е остальных случаях. Докзжкте, что здесь сформулпроззпа задача глобального звзлпзз с днстрвбутязкыма преобрззовзтелямп свойств н что аргумент х (результзт х) вершным г будет стносвться к яскопой компоненте сеязвостн пвформзппоп«- пото графа схемы 6 тогда н только тогда, когда пра стацпонарной разметке р (т) — — (х), х () для катя бы одной нз дуг х, зедущвз к зершяяе г (соствештвевно, выходящкх нз еершвны г), Кзк нужно кзмевять гткзптеческу«с фувкцнз«(, чтобы мо«као быпо сгронть компоненты связвоств нвформацвоннего графа провзвольпсго фраг маета"г 3 а д а н п е 6.2.
Построате алгорптм рззжхкв дзя нахождення отно. кыпкя ззцеплепв«ктн переменных е заданном фрагменте. 3 а д а в а е 6.3. Постройте алгоритм разметка для взтожденая откошевая ялияння вершка н результзтоз входов нз вершввы а выходы в задав. пом фрагменте. 4.3. Формальные пргобрвэоваыия. Вхозгдемиел( (йраанеми(а Р ео ())разя(хит С называется такая часть Р' фрагмента 6, котораы вместе с каждой нерпщвов содержит и все внцндентиые ей дуги ,' я для которой существует правильная нумерация свободных дуг, , ы также прнпнсываемые этим дугам множества результатов входа н аргументов выхода, удовлетворяющие следующим требованиям: >) прн атой нумерации к расстановке множеств переменных Р' образует фрагмент, совпадающий с Р; 2) если свободная в Р' дуга свободна н в 6, то ее номер н приписываемые множества переменных совпадают с соответствующими в 6; 3) все выходы в Р', которые были внутренними в 6, получают : номера.
отличные от номеров всех выходов в 6; 4) еслн внутренняя дуга е фрагмента 6 является входом в Р', то в качестве результатов входа ей првпнсывак>тся все перемен.' ные, которые заданы для е в 6; 5) если внутренняя дуга е фрагмента 6 является выходом ;". в Р', то в качестве аргументов выхода ей приписываются все пере, менные, маршруты которых проходят по дуге е в 6; 6) все выходы в Р', которые являются внутреннимн в б н ; амеют одннаиовые номера, ведут к одной н той >ко вершине во ~- фрагменте б. Заменой вхождения Фрагмента Р во фрагмент 6 фрагментом Р ,. называется следующая операция: нз 6 удаляется вхожденне Р>„ ,'я каждая свободная дуга фрагмента Р (т.
е. ее начало, если она 'входная, н/илн ее конец, если она выходнан) присоединяется :и той вершине оставшейся части фрагмента б, к которой была ;-прнсоедннена дуга вхождения Р> с тем же номером. Системы преобразований, которые строятся в етой главе, бу" дут описаны с помощью конечных наборов схам аравия. Каждая :схема правил представляет собой описание некоторого (вообще заваря, бесконечного) множества пар фрагментов, называемых '„равноснльнымн. Чтобы получить одну нз таких пар, нужно взять :два правильных фрагмента, удовлетворяющих посылке такой схе;мы правил. Прн этом фиксируется какая-нибудь правильная ну, мерация свободных дуг так, чтобы номер каждого из входов фрагментов отличался ог номеров всех выходов зтих фрагментов.
Правило>з системы преобразований называется всякая пара .: фрагментов, которая порождается схемамн правил атой системы. ; Правило (б, бз) будет записываться также в внде 6, бз. При.:' менением правила (6, бз) к фрагменту б называется замена вхож: деннв одного нз фрагментов пары 6>, 6, во фрагмент б другнм фрагментом атой пары.
Прнмененне схемы правил состоит в прнмепеннн любого нз правил, порождаемых этой схемой правил. х Выводом равносильности 6 бз в системе Х называется последовательность фрагментов Р = 6„Р,..., Р„= бз такая, что фрагмент Роч получается иа фрагмента Р> (> =- Ф, ..., и — 1) применением некоторой схемы правил нз Х. Отношение равносильности будет записываться также в внде б, б, если ясно, о какой системе идет речь, Это отношение является, очевндко, рефлексивным, снмметрнчным н транзнтивным.
ИЬ Система преобрааований Х называется полной для отношения Е-вквивалентнооти в классе схем К„если всякие Е-эквивалентные схемы класса К являются Х-равноснлышми. $2. Инварианты и нх представление в ввце сетей 2.1. Функциональные сети. С каждым аутем ю, кончающимся некоторой дугой е во фрагменте С, можно связать множество с . отношений равенства тернов уеп (С, ю) =-.= (л =- т ~ Ф(и>, е) =- 8 (ю, т) н переменная х задана для цуги е) Мы будем говорить, что путь и яороледае>п множество реп (С, ю). Тогда со всякой дугой е в С ассоциируется множество сост яошевий равенства 1птаг(С,е) = П нее(С,и>), »н>т где пересечение берется по всем путям и>„начинающимся входами фрагмента С и кончающимся дугой е. Это множество равенств будет называться илларион>лозе дуги е в С.
Например, яавариантом 1-дуги распознавателя в схеме Юа > на рис. 6.3 является множество е т (х = х, у =- у, х =- у, у =.= х). Наша ближайшая цель состоит л я Р построении алгоритма разметив для нахождения ннвариаятов дуг г:-е>е> в стандартвык схемах. Для етого л>х> мы опишем пол у решетку сетей с для представления январвантов. ж-ц т Фушщионаеьыо>1 сетью (ялн етьл вьет просто сетью) будет называться тройка е = (У, Ч', Г), содержащая конечное множество вершин У =- (»), каждая иь которых, в свою очередь, содержит конечное множество элементов о =- (е).
Каждому элементу с припасен некоторый символ Ч' (е) бБ Ю () Я", от него ведет И ()Р (е)) аронумерованных дуг к верн1внам сети; Г (е, 1) означает вершину, к которой ведет с-я дуга влемевта е. Мы будем предполагать выполненными три следующих условия правильности сети. 1. Каждая верпшна содержит не более одного элемента, которому приписан функциональный символ. 2. В сети нет элементов-дублей, т. е. таких различных зле. ментов ем е„, для которых Ч'(ет) = Ч'(ет) дс У) (1:~ Ф ~ Ю(Ч'(е,))) Г [ем 1) = Г(ел, $). нв 3. В сети нет контуров, т. е. Ч«н ~ О «З«и„..., и„б= У Ч«с«,..., е„У/«, .
* ., /„ («т«(4 < «а: я) е, «х: и««Ь (1 < /« ~~ ««(Ч' (е,)))) =о =+(3«Г (е«./«) Ф и« ~/Г(е„. /„) ть и«). ( На рисунках с примерами сетей ыы изображаем вершины овала; :ыи, а их элементы — прямоугольниками, размещенными внутри ', овалов. Для вершины и н элементов е сети е определим множества тврмов 3«по«е, (и) и 3«пои, (с): ( (у). если Ч«(е) = уй«Ю (у) =- О, Ьпоте«(с) =- ~ (/(т«,..., т„)~ т«(«ь «к п) т««:=)«пом (Г(с, «))), если Ч'(с) =-/ и й(/) =-л»О , .Зспов«, (и) = Ц )«пов«, (е).
«ыь ! Будем говорить, что элемент е (вершина и) сети е знает терм т, ! если с е= 3«вон, (е) (соответственно т ~ )«««о«е, (и)). Например, ! в сети, изображенной на рис. 6.4, вершина о«знает термы з, ( / (х, Ь) и / (у, Ь). Будем говорить, что сеть е вреде«лаеллел« .в««охееетео разе««ел«е аззег«(е) == () (х =т((хб=Ю)д«(х,т~х)«поз«,(и))). ««вг Сеть на рис. 6„4 представляет, например, множество равенств.
(х = х, у = у, х = у, у = х, з = / (х, Ь), з = х, з == / (у, Ь)). Назовем вершину о сети з забытой, если она не аявет ни од- ного герма, т. е. Йпои«, (««) =- Я. Раве елее«еыз«а определим сле: ду«ощнм образом: ( Ое если й(Ч«(с)) = О, "-"'"'=1='" -* "~'~- ' -- «»== >' ьс з«евг<ь и !' Ранг вершкны равен. максимальному рангу содержащихся в вер- ~: тине элементов. В сетя иа рис.
6.4 ранг (и«) = 1 и ранг (и«) .=- « = ранг(из) = О. Для уда.'„: ления забытых вершин будем использовать следу«оп«у«о оне- Я г рацшо. « Ояеракыл удаленил забмвы«й вершины. Пусть вершина и сети з не имеет нн одного элемента. Удалим тогда из з е«Я Пу Е3 всякий элемент, от которого хотя бы одна дута ведет к и, после него удалим к вер. Рве. б.4. Првмер Фуввавввзлыоа сета н«нку о. Легко видеть, ито если з' — результат применения к сети з оиервции удаления забытой вершины, то взвеси (е) = аззегб (е'). Ит Кроме того, из определения забытой вершины вытекает„что если сеть содержит забытые вершины, то среди них есть хотя бы одна ранга О.
Это оаначает, что последовательным.применением операции удаления забытых вершин можно удалить все забытые зерпншы сети с сохранением представляемого множества равенств. Пусть теперь сеть г не содержит забытых вершин. Вершвну и сети в назовем доступной, если з г имеется путь к и от некоторой вершины и' с элементом с', для которого Ч' (с') ~ Я. Все остальные вершины нааыэаются недостумнымм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
