版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
顯式狀態(tài)遷移模型中國科學(xué)院軟件研究所張文輝/~zwh/pv顯式狀態(tài)遷移模型中國科學(xué)院軟件研究所2互斥協(xié)議：衛(wèi)式遷移模型初始狀態(tài)：遷移集合：互斥協(xié)議：衛(wèi)式遷移模型初始狀態(tài)：遷移集合：3互斥協(xié)議：示意圖x==0||t==0t0x=1,t=0t1t2y==0||t==1t3x=0s0y=1,t=1s1s2s3y=0初始狀態(tài)s0t0x=0y=0t=0互斥協(xié)議：示意圖x==0||t==0t0x=1,t=0t1t4系統(tǒng)狀態(tài)及狀態(tài)變化關(guān)系系統(tǒng)狀態(tài)有5個(gè)分量用五元組(a,b,x,y,t)表示進(jìn)程A執(zhí)行位置變量x的值進(jìn)程B執(zhí)行位置變量t的值變量y的值系統(tǒng)狀態(tài)及狀態(tài)變化關(guān)系系統(tǒng)狀態(tài)有5個(gè)分量用五元組(a,b,x5運(yùn)行：狀態(tài)變化序列s0,t0,0,0,0s1,t0,0,1,1s1,t1,1,1,0s2,t1,1,1,0s3,t1,1,0,0s3,t2,1,0,0s3,t3,1,0,0s0,t1,1,0,0s1,t1,1,1,1s1,t2,1,1,1運(yùn)行：狀態(tài)變化序列s0,t0,0,0,06s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1狀態(tài)變化圖:s2,t1,1,1,0s1,t2,1,1,1s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1s2,t1,1,1,0s1,t2,1,1,1s3,t1,1,0,0s1,t3,0,1,1s3,t2,1,0,0s3,t3,0,0,01096s2,t3,0,1,1s3,t3,0,0,1513121312569101213s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,8z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55z0z12z35z67z97z46z20z24z47抽象狀態(tài)z0z12z35z67z97z46z20z24z47z78z55z108z59z116z1201096z91z121513121312569101213z0z12z35z67z97z46z20z24z47z78zz0z12z35z67z97z46z20z24z47z78z55z108z59z116z120z55z78z47z91z121z46z59z108z59z108z0z12z35z67z97z46z20z24z47z78z11Kripke模型Kripke模型12Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)抽象狀態(tài)二元組狀態(tài)集合Kripke模型Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)Kripke模13Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：{
z0,
z1,
z2,
z3,…,
z127}{
(z0,z35),
(z0,z12),
…
}{
z0
}Kripke模型：例子狀態(tài)集合：{z0,z1,z2,14Kripke模型：例子z0,…,z127代表根據(jù)字母順序排列的128個(gè)(a,b,x,y,t)狀態(tài)zi代表(a,b,x,y,t)?i=32*a+8*b+4*x+2*y+t定義 a(i)=i/32 b(i)=(i%32)/8 x(i)=(i%8)/4 y(i)=(i%4)/2 t(i)=(i%2)Kripke模型：例子z0,…,z12715Kripke模型：例子互斥協(xié)議的衛(wèi)式遷移模型表示的8條遷移對應(yīng):Kripke模型：例子互斥協(xié)議的衛(wèi)式遷移模型表示的8條遷移對16Kripke模型：可達(dá)狀態(tài)的遷移遷移關(guān)系包括能到可達(dá)狀態(tài)的遷移26個(gè):Kripke模型：可達(dá)狀態(tài)的遷移遷移關(guān)系包括能到可達(dá)狀態(tài)的遷17Kripke模型：可達(dá)狀態(tài)可達(dá)狀態(tài)17個(gè):Kripke模型：可達(dá)狀態(tài)可達(dá)狀態(tài)17個(gè):18Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)19Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不滿足)Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不20標(biāo)號Kripke模型標(biāo)號Kripke模型21s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1狀態(tài)變化圖:s2,t1,1,1,0s1,t2,1,1,1s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,22z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55a=s0:{z0,z12,…}b=t0:{z0,z35,…}z0z12z35z67z97z46z20z24z47抽象狀態(tài)23z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55p,q,rp:a=s0q:b=t0r:t=0s:a=s0b=t0ppp,rqqqrrz0z12z35z67z97z46z20z24z47抽象狀態(tài)24標(biāo)號Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)狀態(tài)信息抽象狀態(tài)二元組狀態(tài)集合命題標(biāo)號Kripke模型標(biāo)號Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)標(biāo)號Kripke模型25標(biāo)號Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：標(biāo)號函數(shù)：{
z0,
z1,
z2,
z3,…
}{
(z0,z35),
(z0,z12),
…
}{
z0
}L:L(z0)={p,q,r},L(z12)={p},…命題集合{p,q,r}的子集
標(biāo)號Kripke模型：例子狀態(tài)集合：{z0,z1,z226標(biāo)號Kripke模型：命題定義命題:標(biāo)號Kripke模型：命題定義命題:27標(biāo)號Kripke模型：標(biāo)號函數(shù)可達(dá)狀態(tài)的標(biāo)號:狀態(tài)的標(biāo)號:標(biāo)號Kripke模型：標(biāo)號函數(shù)可達(dá)狀態(tài)的標(biāo)號:狀態(tài)的標(biāo)號:28標(biāo)號Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)標(biāo)號Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)29標(biāo)號Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不滿足)標(biāo)號Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)30擴(kuò)展標(biāo)號Kripke模型擴(kuò)展標(biāo)號Kripke模型31z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55p,q,rp:a=s0q:b=t0r:t=0s:a=s0b=t0ppp,rqqqrrz0z12z35z67z97z46z20z24z47抽象狀態(tài)32z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55pqrp:a=s0q:b=t0r:t=0s:a=s0b=t0pqrpqrpqrpqrpqrpqrpqrpqrpqrpqrz0z12z35z67z97z46z20z24z47抽象狀態(tài)33z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55pqrp:a=s0q:b=t0r:t=0s:a=s0b=t0pqrpqrpqrpqrpqrpqrpqrpqrpqz0z12z35z67z97z46z20z24z47抽象狀態(tài)34擴(kuò)展標(biāo)號Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)狀態(tài)信息抽象狀態(tài)二元組狀態(tài)集合公式擴(kuò)展標(biāo)號Kripke模型擴(kuò)展標(biāo)號Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)擴(kuò)展標(biāo)號Kripke35擴(kuò)展標(biāo)號Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：標(biāo)號函數(shù)：{
z0,
z1,
z2,
z3,…
}{
(z0,z35),
(z0,z12),
…
}{
z0
}L:L(z0)=pqr,…命題公式擴(kuò)展標(biāo)號Kripke模型：例子狀態(tài)集合：{z0,z1,36s01s0s1s2s11s02s12p,qppqpq擴(kuò)展標(biāo)號Kripke模型：例2p,qqs2p,qs01s0s1s2s11s02s12p,qppqpq擴(kuò)展標(biāo)37擴(kuò)展標(biāo)號Kripke模型：例2狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：標(biāo)號函數(shù)：{
s0,
s1,s2}{(s0,s1),(s1,s1),(s1,s2),(s2,s2)}{
s0
}L:L(s0)=p,L(s1)=q,L(s2)=pq擴(kuò)展標(biāo)號Kripke模型：例2狀態(tài)集合：{s0,s1,38公平Kripke模型公平Kripke模型39z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55z0z12z35z67z97z46z20z24z47抽象狀態(tài)40z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55進(jìn)程A的運(yùn)行進(jìn)程B的運(yùn)行z0z12z35z67z97z46z20z24z47抽象狀態(tài)41公平Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)公平性約束抽象狀態(tài)二元組狀態(tài)集合狀態(tài)集合的集合公平Kripke模型公平Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)公平Kripke模型42公平Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：公平性約束：{
z0,
z1,
z2,
z3,…
}{
(z0,z35),
(z0,z12),
…
}{
z0
}{{z35,z67,…
},
{z12,z20,…}}公平Kripke模型：例子狀態(tài)集合：{z0,z1,z43Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)44Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不滿足)Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不顯式狀態(tài)遷移模型中國科學(xué)院軟件研究所張文輝/~zwh/pv顯式狀態(tài)遷移模型中國科學(xué)院軟件研究所46互斥協(xié)議：衛(wèi)式遷移模型初始狀態(tài)：遷移集合：互斥協(xié)議：衛(wèi)式遷移模型初始狀態(tài)：遷移集合：47互斥協(xié)議：示意圖x==0||t==0t0x=1,t=0t1t2y==0||t==1t3x=0s0y=1,t=1s1s2s3y=0初始狀態(tài)s0t0x=0y=0t=0互斥協(xié)議：示意圖x==0||t==0t0x=1,t=0t1t48系統(tǒng)狀態(tài)及狀態(tài)變化關(guān)系系統(tǒng)狀態(tài)有5個(gè)分量用五元組(a,b,x,y,t)表示進(jìn)程A執(zhí)行位置變量x的值進(jìn)程B執(zhí)行位置變量t的值變量y的值系統(tǒng)狀態(tài)及狀態(tài)變化關(guān)系系統(tǒng)狀態(tài)有5個(gè)分量用五元組(a,b,x49運(yùn)行：狀態(tài)變化序列s0,t0,0,0,0s1,t0,0,1,1s1,t1,1,1,0s2,t1,1,1,0s3,t1,1,0,0s3,t2,1,0,0s3,t3,1,0,0s0,t1,1,0,0s1,t1,1,1,1s1,t2,1,1,1運(yùn)行：狀態(tài)變化序列s0,t0,0,0,050s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1狀態(tài)變化圖:s2,t1,1,1,0s1,t2,1,1,1s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1s2,t1,1,1,0s1,t2,1,1,1s3,t1,1,0,0s1,t3,0,1,1s3,t2,1,0,0s3,t3,0,0,01096s2,t3,0,1,1s3,t3,0,0,1513121312569101213s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,52z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55z0z12z35z67z97z46z20z24z47抽象狀態(tài)z0z12z35z67z97z46z20z24z47z78z55z108z59z116z1201096z91z121513121312569101213z0z12z35z67z97z46z20z24z47z78zz0z12z35z67z97z46z20z24z47z78z55z108z59z116z120z55z78z47z91z121z46z59z108z59z108z0z12z35z67z97z46z20z24z47z78z55Kripke模型Kripke模型56Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)抽象狀態(tài)二元組狀態(tài)集合Kripke模型Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)Kripke模57Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：{
z0,
z1,
z2,
z3,…,
z127}{
(z0,z35),
(z0,z12),
…
}{
z0
}Kripke模型：例子狀態(tài)集合：{z0,z1,z2,58Kripke模型：例子z0,…,z127代表根據(jù)字母順序排列的128個(gè)(a,b,x,y,t)狀態(tài)zi代表(a,b,x,y,t)?i=32*a+8*b+4*x+2*y+t定義 a(i)=i/32 b(i)=(i%32)/8 x(i)=(i%8)/4 y(i)=(i%4)/2 t(i)=(i%2)Kripke模型：例子z0,…,z12759Kripke模型：例子互斥協(xié)議的衛(wèi)式遷移模型表示的8條遷移對應(yīng):Kripke模型：例子互斥協(xié)議的衛(wèi)式遷移模型表示的8條遷移對60Kripke模型：可達(dá)狀態(tài)的遷移遷移關(guān)系包括能到可達(dá)狀態(tài)的遷移26個(gè):Kripke模型：可達(dá)狀態(tài)的遷移遷移關(guān)系包括能到可達(dá)狀態(tài)的遷61Kripke模型：可達(dá)狀態(tài)可達(dá)狀態(tài)17個(gè):Kripke模型：可達(dá)狀態(tài)可達(dá)狀態(tài)17個(gè):62Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)63Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不滿足)Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不64標(biāo)號Kripke模型標(biāo)號Kripke模型65s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,1,1s2,t0,0,1,1s3,t0,0,0,1s1,t1,1,1,0s0,t2,1,0,0s0,t3,0,0,0s1,t1,1,1,1狀態(tài)變化圖:s2,t1,1,1,0s1,t2,1,1,1s0,t0,0,0,0s0,t1,1,0,0s1,t0,0,66z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55a=s0:{z0,z12,…}b=t0:{z0,z35,…}z0z12z35z67z97z46z20z24z47抽象狀態(tài)67z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55p,q,rp:a=s0q:b=t0r:t=0s:a=s0b=t0ppp,rqqqrrz0z12z35z67z97z46z20z24z47抽象狀態(tài)68標(biāo)號Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)狀態(tài)信息抽象狀態(tài)二元組狀態(tài)集合命題標(biāo)號Kripke模型標(biāo)號Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)標(biāo)號Kripke模型69標(biāo)號Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：標(biāo)號函數(shù)：{
z0,
z1,
z2,
z3,…
}{
(z0,z35),
(z0,z12),
…
}{
z0
}L:L(z0)={p,q,r},L(z12)={p},…命題集合{p,q,r}的子集
標(biāo)號Kripke模型：例子狀態(tài)集合：{z0,z1,z270標(biāo)號Kripke模型：命題定義命題:標(biāo)號Kripke模型：命題定義命題:71標(biāo)號Kripke模型：標(biāo)號函數(shù)可達(dá)狀態(tài)的標(biāo)號:狀態(tài)的標(biāo)號:標(biāo)號Kripke模型：標(biāo)號函數(shù)可達(dá)狀態(tài)的標(biāo)號:狀態(tài)的標(biāo)號:72標(biāo)號Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)標(biāo)號Kripke模型：安全性質(zhì)系統(tǒng)的互斥性質(zhì)表示為安全性質(zhì)73標(biāo)號Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)(不滿足)標(biāo)號Kripke模型：響應(yīng)性質(zhì)系統(tǒng)具備的部分性質(zhì)包括響應(yīng)性質(zhì)74擴(kuò)展標(biāo)號Kripke模型擴(kuò)展標(biāo)號Kripke模型75z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55p,q,rp:a=s0q:b=t0r:t=0s:a=s0b=t0ppp,rqqqrrz0z12z35z67z97z46z20z24z47抽象狀態(tài)76z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55pqrp:a=s0q:b=t0r:t=0s:a=s0b=t0pqrpqrpqrpqrpqrpqrpqrpqrpqrpqrz0z12z35z67z97z46z20z24z47抽象狀態(tài)77z0z12z35z67z97z46z20z24z47抽象狀態(tài)變化圖:z78z55pqrp:a=s0q:b=t0r:t=0s:a=s0b=t0pqrpqrpqrpqrpqrpqrpqrpqrpqz0z12z35z67z97z46z20z24z47抽象狀態(tài)78擴(kuò)展標(biāo)號Kripke模型系統(tǒng)狀態(tài)狀態(tài)變化初始狀態(tài)狀態(tài)信息抽象狀態(tài)二元組狀態(tài)集合公式擴(kuò)展標(biāo)號Kripke模型擴(kuò)展標(biāo)號Kripke模型系統(tǒng)狀態(tài)抽象狀態(tài)擴(kuò)展標(biāo)號Kripke79擴(kuò)展標(biāo)號Kripke模型：例子狀態(tài)集合：遷移關(guān)系：初始狀態(tài)集：標(biāo)號函數(shù)：{
z0,
z1,
z2,
z3,…
}{
(z0,z35),
(z0,z12),
…
}{
z0
}
溫馨提示
- 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度養(yǎng)老產(chǎn)業(yè)PPP項(xiàng)目合同風(fēng)險(xiǎn)分析與風(fēng)險(xiǎn)防范3篇
- 二零二五年度丙方維護(hù)服務(wù)合同2篇
- 2024年中國火車組合床市場調(diào)查研究報(bào)告
- 很有工作述職報(bào)告范本
- 2024年中國演示直尺市場調(diào)查研究報(bào)告
- 2024年模擬操作器項(xiàng)目可行性研究報(bào)告
- 2024年中國景泰藍(lán)鋼筆市場調(diào)查研究報(bào)告
- 電商經(jīng)理周工作總結(jié)
- 2024年收音機(jī)電筒項(xiàng)目可行性研究報(bào)告
- 2024年搓泥刀盤項(xiàng)目可行性研究報(bào)告
- 心衰患者的容量管理中國專家共識-共識解讀
- 山東省濟(jì)南市2023-2024學(xué)年高一上學(xué)期1月期末考試數(shù)學(xué)試題（解析版）
- 文字學(xué)概要完整版本
- 手術(shù)室搶救工作制度
- ce自我聲明模板
- 鋼閘門監(jiān)理評估報(bào)告
- 高檔養(yǎng)老社區(qū)項(xiàng)目計(jì)劃書
- 蛇年銷售年會發(fā)言稿范文
- 國管局住房制度改革相關(guān)政策解答
- 無縫鋼管服務(wù)方案
- 排澇泵站養(yǎng)護(hù)方案范本
評論
0/150
提交評論