余 寒
南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106
在模型檢測領(lǐng)域,時間自動機(jī)[1]、加權(quán)自動機(jī)[2]和加權(quán)時間自動機(jī)[3]用于建模和分析數(shù)量層面的系統(tǒng)性質(zhì)。進(jìn)程代數(shù)用來模擬模塊化的性質(zhì),但它無法表達(dá)基本布爾操作符,達(dá)不到系統(tǒng)規(guī)范[4]要求。像空間邏輯[5-6]、分離邏輯[7-8]、概率邏輯[9]這類模塊化邏輯對于處理并發(fā)非確定性系統(tǒng)很有效,但在反映系統(tǒng)數(shù)量層面的各種性質(zhì)上還有欠缺。
為了集中處理這些問題,Larsen等人提出了并發(fā)加權(quán)邏輯[10](concurrent weighted logic,CWL),這種多模態(tài)的邏輯中包含了反映給定狀態(tài)的資源總量和限制轉(zhuǎn)移過程的模態(tài)詞,以及能夠應(yīng)對組合性系統(tǒng)的二元模態(tài)詞,它可以表達(dá)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)(label weighted transition system,LWS)的質(zhì)化、量化和模塊化的性質(zhì)。基于此,本文將不動點(diǎn)算子加入CWL,擴(kuò)充后得到并發(fā)加權(quán)μ-演算(concurrentweightedμ-calculus,CWC),并給出了輪替樹自動機(jī)[11-12]與CWC間的內(nèi)在聯(lián)系,借此證明了CWC的可判定性、小模型性。
本文組織結(jié)構(gòu)如下:第2章介紹相關(guān)術(shù)語以及LWS;第3章提出CWC并給出其在LWS上的語義解釋;第4章引入輪替樹自動機(jī),并闡述了輪替樹自動機(jī)與CWC公式間的內(nèi)在聯(lián)系;第5章根據(jù)第4章的研究得出CWC的相關(guān)性質(zhì);第6章總結(jié)全文。
本文采用如下一些記號:?表示實(shí)數(shù)集合;?表示有理數(shù)集合;采用集合論方式定義自然數(shù),令n為任意自然數(shù),則n={0,1,…,n-1},ω表示自然數(shù)集合;Q={p,q,r…}表示命題變元的集合;M×S表示集合M和集合S的笛卡爾積;|S|表示集合S的基數(shù);|?|表示公式?的子公式集合的大小。
集合M上的有限序列是函數(shù)n→M,其中n為一個自然數(shù);集合M上的無限序列是函數(shù)ω→M;一個序列π是有限序列或者無限序列,其長度記作|π|。樹是一個二元組 (V,E),V是節(jié)點(diǎn)的集合,E是V×V的子集。樹中任意節(jié)點(diǎn)v∈V的后繼節(jié)點(diǎn)的集合記作Scc(v),如果樹中某節(jié)點(diǎn)v∈V滿足Scc(v)=?,則該節(jié)點(diǎn)稱為死點(diǎn)。
樹T=(V,E)上的一條路徑是V上的一個序列π,該序列滿足如下條件:對于任意的i+1< |π|,(π(i),π(i+1))∈E。樹T的一個分支是從根節(jié)點(diǎn)開始的最大的路徑,則一個分支是始于根節(jié)點(diǎn)終于某死點(diǎn)的有限路徑或者是始于根節(jié)點(diǎn)的無限路徑。T↓v表示以v為根節(jié)點(diǎn)T的子樹。
定義1[10,13](標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng))LWS是一個五元組W=(M,Σ,θ,l,ρ),其中:
(1)M是一個非空的狀態(tài)集。
(2)Σ是一個非空動作集。
(3)θ:M×(Σ×?)→2M是一個狀態(tài)轉(zhuǎn)移函數(shù)。
(4)l:M→?是一個滿足下列條件的函數(shù):如果m′∈θ(m,a,x),則l(m′)=l(m)+x。一般稱函數(shù)狀態(tài)l為標(biāo)記函數(shù)。
(5)ρ:Q→2M是一個解釋函數(shù)。對于p∈Q,N?M,解釋函數(shù)ρ[p?N]滿足下列條件:如果p′=p,則ρ[p?N](p′)=N;如 果p′≠p,則ρ[p?N](p′)=ρ(p′)。
對于任意LWSW=(M,Σ,θ,l,ρ),p∈Q,N?M,W[p?N]表示這樣的標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng):W[p?N]=(M,Σ,θ,l,ρ[p?N])。而定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)是一個二元組(W,m),其中W是LWS,m是W中的一個狀態(tài),稱作定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)的標(biāo)識狀態(tài)。對于一個定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)(W,m),W↓m表示限制在狀態(tài)m上的W 的子模型。令W1和W2為任意 LWS,W1? W2表示 W1和 W2做不相交的并所得模型。
定義2[10,14](加權(quán)互模擬)給定一個LWSW=(M,Σ,θ,l,ρ),一個加權(quán)互模擬是一個等價關(guān)系R?M×M,使得對于任意(m,m′)∈R,如下條件成立:
(1)l(m)=l(m′);
(4)對于任意q∈Q,m∈ρ(q)當(dāng)且僅當(dāng)m′∈ρ(q)。
如果存在一個加權(quán)互模擬關(guān)系R使得(m,m′)∈R,則稱m和m′是互模擬的,記作m~m′??梢詫⒋硕x擴(kuò)展為不同LWSs間的加權(quán)互模擬:若Wi=(Mi,Σi,θi,li,ρi),mi∈Mi,i=0,1且m0和m1互模擬,則 (W0,m0)~(W1,m1)。
定義3[10](LWS乘積)給定一個同步函數(shù)[15]?:Σ×Σ→Σ以及兩個 LWSWi=(Mi,Σi,θi,li,ρi),i=0,1 。 W=(M,Σ,θ,l,ρ)是 W0和 W1的乘積,記作 W=W0?W1,其中:
(1)M=M0×M1。
(2)Σ=Σ0?Σ1={a0?a1|a0∈Σ0,a1∈Σ1}。
(3)l:M→?是滿足下列條件的函數(shù):如果(m0,m1)∈M,則l((m0,m1))=l0(m0)+l1(m1)。
(4)θ:M×(Σ×?)→2M是滿足下列條件的函數(shù):如果 (m0,m1)∈M,a∈Σ,并且x∈ ?,則θ(m,a,x)={(m0′,
(5)ρ:Q→2M是滿足下列條件的函數(shù):如果q∈Q,則ρ(q)={(m0,m1)∈M|m0∈ρ0(q),m1∈ρ1(q)}。
易證W0?W1是LWS。
例1圖1中展 示的是 LWSW1和 W2和其乘積W0?W1。假設(shè)a*c,a*d,b*c在同步函數(shù)中已有合法定義(b*d不合法)。狀態(tài)(m0,n0)的實(shí)數(shù)標(biāo)記是m0和n0的實(shí)數(shù)標(biāo)記之和。m0經(jīng)動作a轉(zhuǎn)移到m2,n0經(jīng)動作c轉(zhuǎn)移到n1,而a*c是轉(zhuǎn)移過程的同步,故(m0,n0)到(m2,n1)的轉(zhuǎn)移帶動作標(biāo)記a*c,并且?guī)?shí)數(shù)標(biāo)記2,此實(shí)數(shù)標(biāo)記是兩個子轉(zhuǎn)移過程的代價之和。p在m0,m1上成立,q在m0,n0上成立,r在m2,n0上成立,則在W0?W1中,q在(m0,n0)上成立。
Fig.1 LWSs and their products圖1 LWS和其乘積
CWC能夠反映LWS的特點(diǎn),并包含了不動點(diǎn)算子,相較CWL具有更強(qiáng)的表達(dá)能力。
定義4(基本公式)CWC的公式由以下BNF范式定義:
其中r∈?,a∈Σ,p∈Q,?∈{≤,≥}。在形如μp?、νp?這樣的公式中,要求變元p在?中正出現(xiàn)(也即,?p不出現(xiàn))。
Fμ指以μ開頭的不動點(diǎn)公式集合,F(xiàn)ν則是以ν開頭的不動點(diǎn)公式集合。Fη是不動點(diǎn)公式集合,由Fμ和Fν組成。在CWC公式中,不動點(diǎn)操作符優(yōu)先級高于組合模態(tài)詞“|”,組合模態(tài)詞優(yōu)先級高于一元模態(tài)詞 [?r]a,?ra。當(dāng)一個CWC公式?中的每個命題變元p最多只被限制一次并且每個p在其限制量詞的轄域內(nèi),則?是范式形式。對于一個出現(xiàn)在范式形式CWC公式?中的受限變元p,?的唯一的子公式ηpφ(η∈{μ,ν})記作?p。顯然,每個CWC公式可以通過在必要時重命名受限變元形成等價的范式形式。下文中的CWC公式均指其范式形式。
將CWC公式在LWS上進(jìn)行解釋,對于給定LWS W=(M,Σ,θ,l,ρ)和CWC公式?,集合 ||?||W?M按歸納方式定義,見圖2。
Fig.2 LWS semantics of CWC圖2 CWC的LWS語義解釋
例2對于公式?=μq(p|(≥ 2)∨[≤ 5]aq),在LWS W 中,||?||W表示這樣的狀態(tài)的集合,從該狀態(tài)出發(fā),在有限步內(nèi)(可能是0步),可以到達(dá)一個使得公式p|(≥2)成立的狀態(tài)。
能夠滿足公式?的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)集合,記作||?||,則:
對于每一個CWC上的模態(tài)操作符及不動點(diǎn)操作符,其在||?||上的相關(guān)操作見圖3。
首先對于連接符,易知,對于任意CWC公式φ、ψ:
另外,據(jù)圖3易知,對于任意CWC公式φ、ψ:
Fig.3 Some operations on||?||圖3 ||?||上相關(guān)操作
定義5[12](輪替樹自動機(jī))輪替樹自動機(jī)是一個四元組 A=(S,s0,δ,Ω),其中:
(1)S是一個有限的狀態(tài)集合。
(2)s0∈S是一個初始狀態(tài)。
(3)Ω:S→ω是一個優(yōu)先級函數(shù),為每個狀態(tài)指派一個自然數(shù)優(yōu)先級標(biāo)記。
(4)δ:S→TC是轉(zhuǎn)移函數(shù),將每個狀態(tài)映射到集合TC上,集合TC是滿足下列條件的最小的集合:0,1 ∈TC;如果r∈ ? ,則r∈ ?,(?r),?(?r)∈TC;如果q∈Q,則q,?q∈TC;如果s∈S,則s,?ras,[?r]as∈TC;如果s,s′∈S,則s∧s′,s∧s′,s|s′∈TC。
輪替樹自動機(jī)的計(jì)算行為用執(zhí)行(run)[12]的概念來解釋。令 A=(S,s0,δ,Ω)為一個輪替樹自動機(jī),(W,m0)是個定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng),其中W=(M,Σ,θ,l,ρ)。 A在(W,m0)上的一次執(zhí)行是樹R=(V,E,λ),其中(V,E)是定義樹的二元組,而λ:V→M×S是一個雙標(biāo)記函數(shù)。該樹的根節(jié)點(diǎn)標(biāo)記為(m0,s0),并且每個帶有雙標(biāo)記(m,s)的節(jié)點(diǎn)v滿足下列條件:
(1)δ(s)≠ 0 。
(2)如果δ(s)=q,則m∈ρ(q);如果δ(s)≠q,則m?ρ(q)。
(3)如果δ(s)=(?r),則l(m)?r;如果δ(s)= ?(?r),則l(m)?r。
(4)如果δ(s)=s′,則存在v′∈Scc(v),使得λ(v′)=(m,s′)。
(5)如果δ(s)= ?ras,則存在v′∈Scc(v),m′∈M并且使得λ(v′)=(m′,s′)。
(6)如果δ(s)=[?r]as,則對于所有x?r,存在v′∈Scc(v),使得λ(v′)=(m′,s′)。
(7)如 果δ(s)=s′∨s″,則 存 在v′∈Scc(v) 使 得λ(v′)=(m,s′)或者λ(v″)=(m,s″)。
(8)如果δ(s)=s′∧s″,則存在v′,v″∈Scc(v)使得λ(v′)=(m,s′)并且λ(v″)=(m,s″)。
(9)如果δ(s)=s′|s″,則存在v′,v″∈Scc(v)和m′,m″∈M使得λ(v′)=(m′,s′)并且λ(v″)=(m″,s″)。
當(dāng)一次執(zhí)行R的每一個無限分支上的狀態(tài)優(yōu)先級標(biāo)記滿足由Ω確定的奇偶接收條件,這個執(zhí)行R能夠被接收。確切地說,對于每一個R的無限分支π,將優(yōu)先級函數(shù)Ω應(yīng)用到每個節(jié)點(diǎn)上,對于所得到的自然數(shù)序列,當(dāng)其中無限次出現(xiàn)的最大自然數(shù)是偶數(shù),這個分支能夠被接收。如果R的每個無限分支是可接收的,則R是可接收的。
當(dāng)一個定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)上存在一個關(guān)于A可接收的執(zhí)行,則這個系統(tǒng)是能夠被A接收的。能夠被A接收的語言,記作||A||,它包含了所有能夠被A接收的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)。
接下來為每個CWC公式構(gòu)建一個輪替樹自動機(jī)用以接收此公式定義的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)。這種從CWC到輪替樹自動機(jī)的翻譯過程容易創(chuàng)建,關(guān)鍵是其正確性的證明。
令?為一個CWC公式,輪替樹自動機(jī)A(?)=(S,s0,δ,Ω),其中:
(1)S是個包含?的所有子公式φ(記作φ)的集合。
(2)s0=?是初始狀態(tài)。
(3)δ是轉(zhuǎn)移函數(shù),具體定義見圖4。
(4)Ω是優(yōu)先級函數(shù),定義方式同文獻(xiàn)[16]。
Fig.4 Definition of transform functionδ圖4 轉(zhuǎn)移函數(shù)δ定義
例3對于例2公式?=μq(p|(≥ 2)∨[≤ 5]aq),構(gòu)建其輪替樹自動機(jī) A(?),初始狀態(tài)為μq(p|(≥2)∨[≤5]aq),轉(zhuǎn)移函數(shù)如下:
按照文獻(xiàn)[16]中優(yōu)先級定義方式,除了狀態(tài)μq(r∨ [≤ 3]aq|(≤ 5)的優(yōu)先級為1,其余狀態(tài)優(yōu)先級均為0。
下面證明幾個定理,用以說明CWC的操作符和連接詞是如何用自動機(jī)來建模的。
定理1[12]令A(yù)和A′為兩個輪替樹自動機(jī),則:
定理2[12]令A(yù)為一個輪替樹自動機(jī),則:
定理3[12]令p為命題變元,A是輪替樹自動機(jī),則:
定理1~3中涉及的自動機(jī) A+A′,A?A′和 ?raA(φ),[?r]aA(φ)以及μpA,νpA的定義見文獻(xiàn)[12]。
定義6令A(yù)和A′為兩個輪替樹自動機(jī),s0為某個新的狀態(tài),則A|A′定義為:
令φ和ψ為CWC公式,則容易看出A(φ|ψ)=A(φ)|A(ψ)。
基于定義6,可以得到定理4。
定理4令A(yù)和A′為兩個輪替樹自動機(jī),則:
其中,M′是W′的狀態(tài)集,另一方面:
其中,M是W的狀態(tài)集。
證明對于任意兩個自動機(jī)A和A′,令A(yù)=(SA,首先證明本定理第一部分,假設(shè) (W,m)∈ ||A|||||A′||,則存在 LWSs Wi=(Mi,Σi,θi,li,ρi),mi∈Mi,i=1,2使得 (W,m)~ (W1? W2,(m1,m2))并且以下條件成立:(W1,m1)∈||A||,(W2,m2)∈||A′||。令R1為A在(W1,m1)上的一次可接收執(zhí)行,R2為A′在(W2,m2)上的一次可接收執(zhí)行??紤]這樣的樹,它的根節(jié)點(diǎn)標(biāo)記為(m,s0)(s0為某個新狀態(tài))且恰有兩個后繼v1和v2,以v1為根節(jié)點(diǎn)的子樹與R1相同,以v2為根節(jié)點(diǎn)的子樹與R2相同,則這棵樹是 A|A′在(W?W1?W2,m)上的可接收執(zhí)行。此時,(W?W1?W2,m)∈ ||A|A′||。
接著證明本定理第二部分。假設(shè)(W,m)∈||A|A′||,則A|A′在(W,m)上存在一個可接收執(zhí)行R,且R的根節(jié)點(diǎn)有且僅有兩個后繼節(jié)點(diǎn)v1和v2,標(biāo)記分別為。顯然,R↓v1和R↓v2分別是A和 A′在定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)(W↓m1,m1),(W↓m2,m2)上的可接收執(zhí)行。那么(W↓m1,m1)∈||A||且 (W↓m2,m2)∈ A′。令 (W′,m′)=(W↓m1? W↓m2,(m1,m2)),則有 (W′,m′)∈ ||A|||||A′||。 □
當(dāng) |A||||A′||與 ||A|||||A′||間具有定理 4 所述關(guān)系,則||A|A′||? ||A|||||A′||,稱二者互模擬等價。
這一章主要的定理是正確性的證明,即滿足?的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)與自動機(jī) A(?)能接收的語言是互模擬等價的。
定理5令?為任意CWC公式,則當(dāng)?中包含模態(tài)詞 |時,||?||? ||A(?)||,否則 ||?||=||A(?)||。
證明按照公式?的復(fù)雜度歸納證明。當(dāng)?為p,?p,(?r),?(?r)時,顯然 ||?||=||A(?)||成立。否則分情況討論,若?的最外層連接詞是析取和合取,定理1說明此情況成立;若最外層操作符是一元模態(tài)詞[?r]a和 ?ra,定理2說明此情況成立;若最外層操作符是不動點(diǎn)操作符,定理3說明此情況成立;若最外層操作符是二元模態(tài)詞|,定理4說明此情況成立?!?/p>
有了上一章的等價性,關(guān)于CWC的可滿足性判定可歸結(jié)到自動機(jī)的非空問題上。
定理6[12,16]輪替樹自動機(jī)的非空問題在指數(shù)時間內(nèi)可判定。
根據(jù)定理5和定理6可直接得出定理7。
定理7CWC的可滿足性問題在指數(shù)時間內(nèi)可判定。
CWC的小模型性也可以利用上一章的等價性來證明。
定理8[17]如果一個輪替樹自動機(jī)A=(S,s0,δ,Ω)所接收的語言非空,那么它可以接收一個狀態(tài)集不超過2Ο(|S|4lg|S|)的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)。
定理9一個CWC公式?能夠被某些定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)滿足,則存在一個狀態(tài)集不超過2Ο(|?|4lg|?|)的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)滿足它。
證明根據(jù)定理5和定理8可知,對于一個CWC公式?,如果 A(?)=(S,s0,δ,Ω)所接收的語言非空,那么它可以接收一個狀態(tài)集不超過2Ο(|S|4lg|S|)的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng),由A(?)的構(gòu)造過程可知,該定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)的狀態(tài)集不超過 2Ο(|?|4lg|?|)。根據(jù)定理 5可知,若公式?中不包含組合模態(tài)詞 |,則存在一個狀態(tài)集不超過 2Ο(|?|4lg|?|)的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)滿足它。否則,根據(jù)定理4,令L(?)表示公式?的長度,可得到結(jié)論,存在一個狀態(tài)集不超過 (2Ο(|?|4lg|?|))L(?)(i.e.2Ο(|?|4lg|?|))的定點(diǎn)標(biāo)記加權(quán)轉(zhuǎn)移系統(tǒng)滿足?。 □
本文在CWL的基礎(chǔ)上,提出了CWC,給出了它在LWS上的語義,并闡述了輪替樹自動機(jī)與CWC之間內(nèi)在的聯(lián)系。這種聯(lián)系在探討CWC的可滿足性及小模型性等問題上起到重要作用。而如何使用輪替樹自動機(jī)探索CWC的公理系統(tǒng),驗(yàn)證其可靠性和完備性還有待進(jìn)一步研究。