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