2. Проблемы ограниченности и безопасности для обыкновенных сетей Петри. Деревья покрытия разметок сетей Петри (Лекция), страница 3

Êàê áûëî óñòàíîâëåí â ëåììå 3, Dmaxt (π) êîíå÷íî.2). Ïîêàæåì, ÷òî Dt (π) = {M : ∃M 0 : M 0 ∈ Dmaxt (π) ∧ M M 0}Ïðåäïîëîæèì ïðîòèâíîå: ñóùåñòâóåò ðàçìåòêà M èç ìíîæåñòâàDt (π) , êîòîðàÿ íåñðàâíèìà íè ñ îäíîé ðàçìåòêîé èç Dmaxt (π)Ðàññìîòðèì îäíó èç òàêèõ ðàçìåòîê M0 , ó êîòîðîé M0(p) = ∞äëÿ íàèáîëüøåãî ÷èñëà ïîçèöèé p .Äîêàçàòåëüñòâî ëåììû 4.Òàê êàê M0 ∈ Dt (π) \ Dmaxt (π) , äîëæíà òàêæå ñóùåñòâîâàòüáåñêîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ðàçìåòîêα = M0 ≺ M1 ≺ M2 ≺ . . .

èç ìíîæåñòâà Dt (π) \ Dmaxt (π) .Íî òîãäà ïî ëåììå 2 ñóùåñòâóåò ðàçìåòêà M 0 = sup(α) ,êîòîðàÿI ïðèíàäëåæèò ìíîæåñòâó Dt (π) ;I íå ñðàâíèìà íè ñ îäíîé ðàçìåòêîé èç Dmaxt (π) ;I ïðèíèìàåò çíà÷åíèå ∞ â áîëüøåì ÷èñëå ïîçèöèé, íåæåëèðàçìåòêà M0 (âîïðåêè óñëîâèþ âûáîðà ðàçìåòêè M0 ).Ïîëó÷åííîå ïðîòèâîðå÷èå ñâèäåòåëüñòâóåò î òîì, ÷òî êàæäàÿðàçìåòêà èç ìíîæåñòâà Dt (π) ñðàâíèìà ñ îäíîé èç ðàçìåòîêìíîæåñòâà Dmaxt (π) .Äîêàçàòåëüñòâî ëåììû 4.3).

Ìíîæåñòâî ðàçìåòîê Dmaxt (π) ìîæíî ïîñòðîèòü ýôôåêòèâíî â äâà ýòàïà ïóòåì ïîñëåäîâàòåëüíûõ ïðèáëèæåíèé ñíèçó.Âíà÷àëå çàäà÷à âû÷èñëåíèÿ ìàêñèìàëüíûõ t -òóïèêîâûõðàçìåòîê ðåøàåòñÿ òîëüêî íà êîíå÷íîì ìíîæåñòâå ðàçìåòîê,ïðåäñòàâëåííûõ íàáîðàìè èç ìíîæåñòâà {0, ∞}n .Ðåøåíèå ýòîé çàäà÷è ïðîâîäèòñÿ ïðè ïîìîùè ïîëíûõ äåðåâüåâïîêðûòèé ðàçìåòîê è íà îñíîâàíèè òåîðåìû î ìåðòâûõïåðåõîäàõ:1. äëÿ êàæäîé ðàçìåòêè M, M ∈ {0, ∞}n , íóæíî ïîñòðîèòüïîëíîå äåðåâî ïîêðûòèé ðàçìåòîê ñ êîðíåì M è âûäåëèòüòîëüêî òàêèå ðàçìåòêè, äëÿ êîòîðûõ â ñîîòâåòñòâóþùåìäåðåâå íåò äóã ñ ïîìåòêîé t ;2.

ñðåäè âûäåëåííûõ ïîìåòîê íóæíî âûáðàòü ìàêñèìàëüíûå.Äîêàçàòåëüñòâî ëåììû 4.Íà âòîðîì ýòàïå äëÿ êàæäîé èç âûäåëåííûõ t -òóïèêîâûõðàçìåòîê M, M ∈ {0, ∞}n íåîáõîäèìî íàéòè âñå òàêèå ìàêñèìàëüíûå êîíå÷íûå ðàçìåòêè K , ÷òîáû M + K ∈ Dmax (π) .Ýòîò ïîèñê ìîæíî ïðîâîäèòü òàê:I ïðîâîäèòñÿ ïåðåáîð âñåõ íàáîðîâ K , K ∈ Nn ,I äëÿ êàæäîãî èç íèõ ñòðîèòñÿ ïîëíîå äåðåâî ïîêðûòèéðàçìåòîê ñ êîðíåì M + K ,I â ïîñòðîåííîì êîíå÷íîì äåðåâå ïðîâîäèòñÿ ïîèñê äóãè ñïîìåòêîé t .Ïî òåîðåìå î ìåðòâûõ ïåðåõîäàõ îòñóòñòâèå òàêîé äóãè ýòîïðèçíàê t -òóïèêîâîñòè ðàçìåòêè M + K .t -òóïèêîâàÿ ðàçìåòêà M + K çàíîñèòñÿ â ìíîæåñòâî Dmax (π)òîãäà è òîëüêî òîãäà, êîãäà ëþáàÿ èç íåïîñðåäñòâåííîñëåäóþùèõ çà íåé (ïî îòíîøåíèþ ) ðàçìåòîê M + K 0 íåÿâëÿåòñÿ t -òóïèêîâîé.Ïðîáëåìû æèâîñòè è äîñòèæèìîñòèÒåîðåìà î ñâîäèìîñòè ïðîáëåìû æèâîñòè êïðîáëåìå äîñòèæèìîñòèÄëÿ îáûêíîâåííûõ ñåòåé Ïåòðè ïðîáëåìà æèâîñòè ñåòèàëãîðèòìè÷åñêè ñâîäèìà ê ïðîáëåìå äîñòèæèìîñòè ðàçìåòêè.Äîêàçàòåëüñòâî.Êàê ñëåäóåò èç ëåììû 4, ñóùåñòâóåò àëãîðèòì, êîòîðûé äëÿêàæäîé ñåòè Ïåòðè π è äëÿ êàæäîãî ïåðåõîäà t â ýòîé ñåòèâû÷èñëÿåò òàêîå êîíå÷íîå ìíîæåñòâî ðàçìåòîê Dmaxt (π) , ÷òîM ∈ Dt (π) ⇔ ∃ M 0 : (M 0 ∈ Dmaxt (π) ∧ M M 0 )Ïîýòîìó ñåòü π íå ÿâëÿåòñÿ æèâîé òîãäà è òîëüêî òîãäà, êîãäàâ íåé äîñòèæèìà õîòü îäíà ðàçìåòêà M , ïîêðûâàåìàÿ õîòÿ áûîäíîé ðàçìåòêîé èç ìíîæåñòâà S Dmaxt (π) .t∈TÏðîáëåìû æèâîñòè è äîñòèæèìîñòèÄîêàçàòåëüñòâî òåîðåìû.Òàêèì îáðàçîì, çàäà÷à ïðîâåðêè æèâîñòè ñåòè Ïåòðè ñâîäèìàê çàäà÷å ïðîâåðêè äîñòèæèìîñòè ïðîèçâîëüíîé ðàçìåòêè M ,ïîêðûâàåìîé çàäàííûì íàáîðîì M 0 , êîòîðàÿ ñîãëàñíî òåîðåìåîá îãðàíè÷åííîé äîñòèæèìîñòè ñâîäèìà ê ïðîáëåìåäîñòèæèìîñòè.Ïðîáëåìó äîñòèæèìîñòè ðàçìåòîê äëÿ îáûêíîâåííûõ ñåòåéÏåòðè èññëåäîâàëè ïî÷òè 20 ëåò.Âíà÷àëå áûëî óñòàíîâëåíî, ÷òî ýòà çàäà÷à ExpSPACE-òðóäíà, àçàòåì ïîñëå íåñêîëüêèõ ïîïûòîê â 1981 ã.

Ý. Ìàéð (E. Mayr)ïðåäëîæèë äëÿ íåå ðàçðåøàþùèé àëãîðèòì.Ëþáîé èç èçâåñòíûõ â íàñòîÿùåå âðåìÿ àëãîðèòìîâ ðåøåíèÿïðîáëåìû äîñòèæèìîñòè äëÿ ñåòåé Ïåòðè íå ÿâëÿåòñÿïðèìèòèâíî ðåêóðñèâíûì.Ïðîáëåìû æèâîñòè è äîñòèæèìîñòèÌû èçó÷èëè íåêîòîðûå çàäà÷è àíàëèçà ïîâåäåíèÿîáûêíîâåííûõ ñåòåé Ïåòðè, äëÿ êîòîðûõ ñóùåñòâóþòàëãîðèòìû èõ ðåøåíèÿ.Íî â òåîðèè ñåòåé Ïåòðè åñòü òàêæå è àëãîðèòìè÷åñêèåíåðàçðåøèìûå çàäà÷è.Ê èõ ÷èñëó îòíîñèòñÿ ïðîáëåìà R-ýêâèâàëåíòíîñòè ïðîâåðêèòîãî, ìîãóò ëè â äâóõ ðàçíûõ ñåòÿõ Ïåòðè áûòü äîñòèæèìûîäíè è òå æå ðàçìåòêè.ÊÎÍÅÖ ËÅÊÖÈÈ 2.