Лекция 5. Model Checking для CTL. BDD - двоичные разрешающие диаграммы (1185527), страница 5
Текст из файла (страница 5)
Graph-based algorithms for boolean functionmanipulation. IEEE Transactions on Computers, 35(8):677691,1986.1) â êàæäîì ïóòè èç êîðíÿ â òåðìèíàëüíóþ âåðøèíóïåðåìåííûå äîëæíû ñëåäîâàòü â îäíîì è òîì æå ïîðÿäêå.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÁðèàí ïîêàçàë, êàê ïîñòðîèòü êàíîíè÷åñêèå ïðåäñòàâëåíèÿáóëåâûõ ôóíêöèé, íàëàãàÿ äâà îãðàíè÷åíèÿ íà ñòðóêòóðóäâîè÷íûõ ðàçðåøàþùèõ äèàãðàìì.R.
Bryant. Graph-based algorithms for boolean functionmanipulation. IEEE Transactions on Computers, 35(8):677691,1986.1) â êàæäîì ïóòè èç êîðíÿ â òåðìèíàëüíóþ âåðøèíóïåðåìåííûå äîëæíû ñëåäîâàòü â îäíîì è òîì æå ïîðÿäêå.2) â äèàãðàììå íå äîëæíî áûòü èçîìîðôíûõ ïîääåðåâüåâ èëèèçáûòî÷íûõ âåðøèí.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÁðèàí ïîêàçàë, êàê ïîñòðîèòü êàíîíè÷åñêèå ïðåäñòàâëåíèÿáóëåâûõ ôóíêöèé, íàëàãàÿ äâà îãðàíè÷åíèÿ íà ñòðóêòóðóäâîè÷íûõ ðàçðåøàþùèõ äèàãðàìì.R. Bryant. Graph-based algorithms for boolean functionmanipulation. IEEE Transactions on Computers, 35(8):677691,1986.1) â êàæäîì ïóòè èç êîðíÿ â òåðìèíàëüíóþ âåðøèíóïåðåìåííûå äîëæíû ñëåäîâàòü â îäíîì è òîì æå ïîðÿäêå.2) â äèàãðàììå íå äîëæíî áûòü èçîìîðôíûõ ïîääåðåâüåâ èëèèçáûòî÷íûõ âåðøèí.Ïåðâîå òðåáîâàíèå ìîæíî âûïîëíèòü, çàäàâ ëèíåéíûé ïîðÿäîê< íà ìíîæåñòâå ïåðåìåííûõ è îáúÿâèâ, ÷òî åñëè âåðøèíà uèìååò íåòåðìèíàëüíóþ âåðøèíóïîñëåäîâàòåëÿ v , òîvar (u) < var (v ) .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÁðèàí ïîêàçàë, êàê ïîñòðîèòü êàíîíè÷åñêèå ïðåäñòàâëåíèÿáóëåâûõ ôóíêöèé, íàëàãàÿ äâà îãðàíè÷åíèÿ íà ñòðóêòóðóäâîè÷íûõ ðàçðåøàþùèõ äèàãðàìì.R.
Bryant. Graph-based algorithms for boolean functionmanipulation. IEEE Transactions on Computers, 35(8):677691,1986.1) â êàæäîì ïóòè èç êîðíÿ â òåðìèíàëüíóþ âåðøèíóïåðåìåííûå äîëæíû ñëåäîâàòü â îäíîì è òîì æå ïîðÿäêå.2) â äèàãðàììå íå äîëæíî áûòü èçîìîðôíûõ ïîääåðåâüåâ èëèèçáûòî÷íûõ âåðøèí.Ïåðâîå òðåáîâàíèå ìîæíî âûïîëíèòü, çàäàâ ëèíåéíûé ïîðÿäîê< íà ìíîæåñòâå ïåðåìåííûõ è îáúÿâèâ, ÷òî åñëè âåðøèíà uèìååò íåòåðìèíàëüíóþ âåðøèíóïîñëåäîâàòåëÿ v , òîvar (u) < var (v ) .Âòîðîå òðåáîâàíèå ìîæíî âûïîëíèòü, ïîñëåäîâàòåëüíîïðèìåíÿÿ ñëåäóþùèå òðè ïðàâèëà ïðåîáðàçîâàíèÿ BDDs.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÓäàëÿþòñÿ âñåêðîìå îäíîé òåðìèíàëüíûå âåðøèíû, èìåþùèåçàäàííóþ ïîìåòêó; âñå äóãè, êîòîðûå ðàíåå âåëè âèçúÿòûå òåðìèíàëüíûå âåðøèíû, íàïðàâëÿþòñÿòåïåðü â îñòàâøóþñÿ òåðìèíàëüíóþ âåðøèíó.Óäàëåíèå ïîâòîðíûõ âõîæäåíèé òåðìèíàëîâ.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÓäàëÿþòñÿ âñåêðîìå îäíîé òåðìèíàëüíûå âåðøèíû, èìåþùèåçàäàííóþ ïîìåòêó; âñå äóãè, êîòîðûå ðàíåå âåëè âèçúÿòûå òåðìèíàëüíûå âåðøèíû, íàïðàâëÿþòñÿòåïåðü â îñòàâøóþñÿ òåðìèíàëüíóþ âåðøèíó.Óäàëåíèå ïîâòîðíûõ âõîæäåíèé òåðìèíàëîâ.Åñëè äëÿ äâóõíåòåðìèíàëüíûõ âåðøèí u è v âåðíû ðàâåíñòâàvar (u) = var (v ) , low (u) = low (v ) èhigh(u) = high(v ) , òî îäíà èç íèõ óäàëÿåòñÿ, à âñåâåäóùèå â íåå äóãè íàïðàâëÿþòñÿ â îñòàâøóþñÿâåðøèíó.Óäàëåíèå ïîâòîðíûõ âõîæäåíèé íåòåðìèíàëîâ.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÓäàëÿþòñÿ âñåêðîìå îäíîé òåðìèíàëüíûå âåðøèíû, èìåþùèåçàäàííóþ ïîìåòêó; âñå äóãè, êîòîðûå ðàíåå âåëè âèçúÿòûå òåðìèíàëüíûå âåðøèíû, íàïðàâëÿþòñÿòåïåðü â îñòàâøóþñÿ òåðìèíàëüíóþ âåðøèíó.Óäàëåíèå ïîâòîðíûõ âõîæäåíèé òåðìèíàëîâ.Åñëè äëÿ äâóõíåòåðìèíàëüíûõ âåðøèí u è v âåðíû ðàâåíñòâàvar (u) = var (v ) , low (u) = low (v ) èhigh(u) = high(v ) , òî îäíà èç íèõ óäàëÿåòñÿ, à âñåâåäóùèå â íåå äóãè íàïðàâëÿþòñÿ â îñòàâøóþñÿâåðøèíó.Óäàëåíèå ïîâòîðíûõ âõîæäåíèé íåòåðìèíàëîâ.Åñëè äëÿ íåòåðìèíàëüíîéâåðøèíû v âåðíî ðàâåíñòâî low (v ) = high(v ) , òîîíà óäàëÿåòñÿ, à âñå âåäóùèå â íåå äóãèíàïðàâëÿþòñÿ â low (v ) .Óäàëåíèå èçáûòî÷íûõ ïðîâåðîêÏîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÊàíîíè÷åñêóþ ôîðìó ìîæíî ïîëó÷èòü èç ëþáîé BDD,îáëàäàþùåé ñâîéñòâîì óïîðÿäî÷åííîñòè; â õîäå ïîñòðîåíèÿïðàâèëà ïðåîáðàçîâàíèÿ ïðèìåíÿþòñÿ äî òåõ ïîð, ïîêà îíèïðèìåíèìû.BDD íàçûâàåòñÿ ðåäóöèðîâàííîé óïîðÿäî÷åííîé äâîè÷íîéðàçðåøàþùåé äèàãðàììîé (ROBDD), åñëè íè îäíî èçóêàçàííûõ ïðàâèë ê íåé íå ïðèìåíèìî.Áðèàí ïîêàçàë, êàê ïîñòðîèòü ROBDD, ïðîâîäÿïðåîáðàçîâàíèÿ ïðîèçâîëüíîé BDD ñíèçó ââåðõ ïðè ïîìîùèïðîöåäóðû Reduce çà âðåìÿ ïðîïîðöèîíàëüíîå ðàçìåðóèñõîäíîé äâîè÷íîé ðàçðåøàþùåé äèàãðàììû.Íàïðèìåð, åñëè èñïîëüçóåòñÿ óïîðÿäî÷åíèå a1 < b1 < a2 < b2äëÿ äâóõáèòîâîé ôóíêöèè ñðàâíåíèÿ, òî â ðåçóëüòàòå áóäåòïîëó÷åíà âîò òàêàÿ OBDD. a1HH0H 1HH Hb1b1@0@1@@ @0@1@@ a2a2a2a2 B B B B0B10B10B10B1BBBBBBBB b2b2b2b2b2b2b2b2CCCCCCCC0 C1 0 C1 0 C1 0 C1 0 C1 0 C1 0 C1 0 C1 C C C C C C C C CCC CC CC C100100000000 1001 a1@1@ 0b1b10110 a2@@01@ @b2b2@@01 1@ 0@10Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÅñëè èñïîëüçîâàòü ROBDD â êà÷åñòâå êàíîíè÷åñêîé ôîðìûäëÿ ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé, òî ïðîâåðêàýêâèâàëåíòíîñòè ñâîäèòñÿ ê ïðîâåðêå èçîìîðôèçìà ìåæäóäâîè÷íûìè ðàçðåøàþùèìè äèàãðàììàìè.Ýòî îçíà÷àåò, ÷òî âûïîëíèìîñòü ìîæåò áûòü óñòàíîâëåíàïóòåì ïðîâåðêè ýêâèâàëåíòíîñòè èññëåäóåìîé ROBDD èâûðîæäåííîé ROBDD, ñîñòîÿùåé èç åäèíñòâåííîéòåðìèíàëüíîé âåðøèíû, ïîìå÷åííîé 0 .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÅñëè èñïîëüçîâàòü ROBDD â êà÷åñòâå êàíîíè÷åñêîé ôîðìûäëÿ ïðåäñòàâëåíèÿ áóëåâûõ ôóíêöèé, òî ïðîâåðêàýêâèâàëåíòíîñòè ñâîäèòñÿ ê ïðîâåðêå èçîìîðôèçìà ìåæäóäâîè÷íûìè ðàçðåøàþùèìè äèàãðàììàìè.Ýòî îçíà÷àåò, ÷òî âûïîëíèìîñòü ìîæåò áûòü óñòàíîâëåíàïóòåì ïðîâåðêè ýêâèâàëåíòíîñòè èññëåäóåìîé ROBDD èâûðîæäåííîé ROBDD, ñîñòîÿùåé èç åäèíñòâåííîéòåðìèíàëüíîé âåðøèíû, ïîìå÷åííîé 0 .Ðàçìåð OBDD î÷åíü ñèëüíî çàâèñèò îò óïîðÿäî÷åíèÿïåðåìåííûõ.Íàïðèìåð, åñëè ìû óïîðÿäî÷èì ïåðåìåííûå a1 < a2 < b1 < b2äëÿ äâóõáèòîâîé ôóíêöèè ñðàâíåíèÿ, òî â ðåçóëüòàòå áóäåòïîëó÷åíà âîò òàêàÿ ROBDD. a1HHHH 1 H0a2a2@1@10 @@0b1b1b1b101XXXX@X@XB X1@ 01@ 0X @ B XX XX @XX@B 1 0b2b2@B00PP@ B PP @ B 11PPP@B 10á) a1 < a2 < b1 < b2 a1a1@1@ HHHH 1 H0b1b1a20110 a2b2@@01 1@ 0@10a) a1 < b1 < a2 < b2a2@1@10 @@0b1@@01@ @b20b1b1b101XXXX@X@XB X1@ 01@ 0X @ B XX XX @XX@B 1 0b2b2@B00PP@ B PP @ B 11PPP@B 10á) a1 < a2 < b1 < b2Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàìì îáùåì ñëó÷àå, êîãäà ðå÷ü èäåò î n -áèòîâîì êîìïàðàòîðå,âûáðàâ óïîðÿäî÷åíèå ïåðåìåííûõ a1 < b1 < · · · < an < bn , ìûïîëó÷èì ROBDD, èìåþùóþ 3n + 2 âåðøèí.Íî åñëè âûáðàòü óïîðÿäî÷åíèå a1 < · · · < an < b1 · · · < bn , òîROBDD áóäåò èìåòü 3 · 2n − 1 âåðøèí.Âîîáùå ãîâîðÿ, ïðîâåðêà òîãî, áóäåò ëè ïðåäëîæåííûé ïîðÿäîêîïòèìàëüíûì, ÿâëÿåòñÿ-ïîëíîé çàäà÷åé.NPÁîëåå òîãî, ñóùåñòâóþò ïîñëåäîâàòåëüíîñòè áóëåâûõ ôóíêöèé,ðàçìåð OBDD äëÿ êîòîðûõ ðàñòåò ýêñïîíåíöèàëüíî ñóâåëè÷åíèåì ÷èñëà ïåðåìåííûõ íåçàâèñèìî îò ïîðÿäêà èõðàñïîëîæåíèÿ.Ïðèìåðîì ìîæåò ñëóæèòü ôóíêöèÿ, âû÷èñëÿþùàÿ n -é áèòïðîèçâåäåíèÿ äâîè÷íûõ öåëûõ ÷èñåë.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÄàëåå âûÿñíèì, êàê âûïîëíÿòü ðàçëè÷íûå ëîãè÷åñêèå îïåðàöèèäëÿ áóëåâûõ ôóíêöèé, ïðåäñòàâëåííûõ â âèäå OBDD.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÄàëåå âûÿñíèì, êàê âûïîëíÿòü ðàçëè÷íûå ëîãè÷åñêèå îïåðàöèèäëÿ áóëåâûõ ôóíêöèé, ïðåäñòàâëåííûõ â âèäå OBDD.Íà÷íåì ñ îïåðàöèè ïîäñòàíîâêè êîíñòàíòû b âìåñòî çàäàííîéïåðåìåííîé xi â çàäàííîé áóëåâîé ôóíêöèè f .
Ïîëó÷åííàÿ âðåçóëüòàòå ôóíêöèÿ îáîçíà÷àåòñÿ f |xi ←b è îïðåäåëÿåòñÿñëåäóþùèì ñîîòíîøåíèåì:f (x1 , . . . , xn ) = f (x1 , . . . , xi−1 , b, xi+1 , . . . , xn ) .Åñëè èìååòñÿ ROBDD äëÿ f , òî ROBDD äëÿ f |xi ←b ìîæíîïîñòðîèòü ïóòåì îáõîäà èñõîäíîé OBDD.Åñëè èç âåðøèíû v äóãà âåäåò â òàêóþ âåðøèíó w , ÷òîvar (w ) = xi , òî ïåðåíàïðàâèì ýòó äóãó â âåðøèíó low (w ) âñëó÷àå b = 0 , è â high(w ) â ñëó÷àå b = 1 .Ò.ê.
ïîëó÷åííàÿ OBDD ìîæåò îêàçàòüñÿ íåêàíîíè÷åñêîé,ïðèìåíèì ïðîöåäóðó Reduce äëÿ ïîëó÷åíèÿ ROBDD,ïðåäñòàâëÿþùóþ f |xi ←b . a1@1f (a1 , a2 , b1 , b2 )@ 0b1b10110 a2@@01@ @b2b2@@01 1@ 0@10 a1@1f (a1 , a2 , b1 , b2 )@ 0b1b1À êàê âûãëÿäèò ROBDD äëÿ f |b1 ←0 (a1 , a2 , b1 , b2 ) ?0110 a2@@01@ @b2b2@@01 1@ 0@10 a10 1f |b1 ←0 (a1 , a2 , b1 , b2 ) a2@@01@ @b2b2@@01 1@ 0@10Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÄëÿ áóëåâûõ ôóíêöèé, ïðåäñòàâëåííûõ ROBDD, âñåøåñòíàäöàòü äâóìåñòíûõ áóëåâûõ îïåðàöèé ìîãóò áûòüýôôåêòèâíî ðåàëèçîâàíû.Ñëîæíîñòü âû÷èñëåíèÿ ýòèõ îïåðàöèé ëèíåéíà îòíîñèòåëüíîïðîèçâåäåíèÿ ðàçìåðîâ èñõîäíûõ ÎBDD.Êëþ÷îì ê èõ ðåàëèçàöèè ñëóæèò ðàçëîæåíèå Øåííîíàf = (¬x ∧ f |x←0) ∨ (x ∧ f |x←1)Áðèàí ïðåäëîæèë åäèíûé àëãîðèòì Apply äëÿ âû÷èñëåíèÿ âñåõøåñòíàäöàòè îïåðàöèé.Àëãîðèòì ñòðîèòñÿ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.Ïîÿñíèì âêðàòöå, êàê îí ðàáîòàåò.Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÎáîçíà÷èì ñèìâîëîì ∗ ïðîèçâîëüíóþ äâóõìåñòíóþ ëîãè÷åñêóþîïåðàöèþ è ðàññìîòðèì ïàðó áóëåâûõ ôóíêöèé f è f 0 .Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:Iv è v 0 êîðíåâûå âåðøèíû OBDD äëÿ f è f 0 ;Ix = var (v ) è x 0 = var (v 0 ) .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÂîçìîæíû íåñêîëüêî âàðèàíòîâ â çàâèñèìîñòè îò ñîîòíîøåíèéìåæäó v è v 0 .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÂîçìîæíû íåñêîëüêî âàðèàíòîâ â çàâèñèìîñòè îò ñîîòíîøåíèéìåæäó v è v 0 .IÅñëè îáå âåðøèíû v è v 0 òåðìèíàëüíûå, òîf ∗ f 0 = value(v ) ∗ value(v 0 ) .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììÂîçìîæíû íåñêîëüêî âàðèàíòîâ â çàâèñèìîñòè îò ñîîòíîøåíèéìåæäó v è v 0 .IÅñëè îáå âåðøèíû v è v 0 òåðìèíàëüíûå, òîf ∗ f 0 = value(v ) ∗ value(v 0 ) .IÅñëè x = x 0 , òî ìû âîñïîëüçóåìñÿ ðàçëîæåíèåì Øåííîíàf ∗ f 0 = (¬x ∧ (f |x←0 ∗ f 0 |x←0 )) ∨ (x ∧ (f |x←1 ∗ f 0 |x←1 ))äëÿ ðàçáèåíèÿ çàäà÷è íà äâå ïîäçàäà÷è, êîòîðûåðåøàþòñÿ ðåêóðñèâíî.Êîðíåâîé âåðøèíîé ðåçóëüòèðóþùåé ROBDD áóäåò íîâàÿâåðøèíà w , äëÿ êîòîðîé var (w ) = x;ïðè ýòîì low (w ) ýòî êîðíåâàÿ âåðøèíà ROBDD äëÿf |x←0 ∗ f 0 |x←0 , à high(w ) ýòî êîðíåâàÿ âåðøèíîéROBDD äëÿ f |x←1 ∗ f 0 |x←1 .Ïîñòðîåíèå ðàçðåøàþùèõ äèàãðàììIÅñëè x < x 0 , òî f 0 |x←0 = f 0 |x←1 = f 0 , ïîñêîëüêó f 0 íåçàâèñèò îò x .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
