基于擴展Petri網的ECA規則集表示及終止性分析

張立臣，王小明，竇文陽

（陜西師范大學 計算機科學學院，陜西 西安 710062）

1 引言

基于觸發機制的ECA(event-condition-action)規則能夠描述主動知識，是人工智能和知識表示處理領域的研究熱點[1]。應用ECA規則[2,3]和ECA規則集的動態行為特性(如可終止性、匯流性等)分析[4～10]得到研究人員的高度關注。如果從任何初始狀態下開始，ECA規則集的執行過程都會在有限步之內停止，那么稱ECA規則集是可終止的[4]。但是，由于ECA規則集之間存在復雜的規則結構和規則特性，如復合事件(composed event)、復合條件(composed condition)、觸發關系(triggering relation)、活化關系(activating relation)和墮化關系(deactivating relation)等，導致 ECA規則集的可終止性分析問題十分困難，在考慮所有規則特性的情況下，ECA規則集的可終止性分析問題是不可判定的[5]，因此，研究人員通常只考慮部分結構特性。

截至目前，在 ECA規則集可終止性分析方法中，基于圖理論和基于Petri網的分析方法是主要的2類方法。觸發圖(TG, triggering graph)分析方法只考慮了規則間的觸發關系[6]，而活化圖(AG, activating graph)的分析方法針對的是活化關系[7]。Baralis提出了結合TG圖和AG圖的終止性分析方法[8]，在此基礎上，Montesi定義了進化圖[9]，郝忠孝等提出了含環觸發圖的分析方法[10]。在基于圖理論的分析方法中，規則用圖的節點表示，規則間觸發、活化或墮化關系則用圖的有向邊描述。若圖中存在一條回路，則表明所對應的 ECA規則集是不可終止的。但是簡單的圖形并不能體現 ECA規則之間的細粒度規則特性(如復合事件、規則耦合模式等)，導致了基于圖理論的終止性分析方法的分析粒度較粗，準確性較差。

Petri網是動態系統建模和行為分析方面的形式化工具[2,3,11]，被廣泛應用于 ECA規則集的可終止性分析領域[12～15]。Latifa[12]基于 Petri網分析含優先級的 ECA規則集的終止性，但是沒有考慮復合事件和復合條件等結構特性。Bostan-Korpeoglu[14]基于模糊有色Petri網分析模糊ECA規則集的可終止性，但只考慮了復合事件。

綜上所述，現有 ECA規則集的可終止性分析方法只考慮 ECA規則之間的部分結構特性，導致算法判定的準確性較低。為了提高 ECA規則集的可終止性判定算法準確性，筆者首先提出可有效描述 ECA規則各種規則特性的擴展 Petri網(EPN,extended Petri net)模型，然后在充分利用EPN所包含的規則結構信息的基礎上，綜合分析 ECA規則集的可終止性，并提出了相應的可終止性判定算法，最后，通過理論分析和實驗仿真對本文的算法與傳統可終止判定算法進行了比較。

2 ECA規則集的EPN模型

2.1 模型設計

ECA規則的事件分為原子事件和復合事件，條件分為原子條件和復合條件。為簡單起見，本文約定，ECA規則的復合事件只能通過“”∧運算符將原子事件或原子事件的“逆事件”復合起來；復合條件只能通過“”∧運算把原子條件或原子條件的否定復合而來。在此約定下，本文提出了一種可有效表示ECA規則集的擴展Petri網模型——EPN模型。

定義1 描述ECA規則集的EPN是一個9元組，EPN=(P, T, F, C, E, W, G, CF, M0)。

1) P 是庫所的有限集，P=Pe∪Pt∪Pv∪Pn∪Pc，其中，Pe是事件庫所集，Pt是處于觸發態的庫所集，Pv是處于激活態的庫所集，Pn是動作庫所集，Pc是條件庫所集。Pe、Pt、Pv、Pn和Pc兩兩不相交。

2) T是變遷的有限集，Tt?T是觸發變遷集，Tv?T是激活變遷集，Tn?T是執行變遷集。Tt、Tv和Tn兩兩不相交。

3) F是流關系的有限集， F = Fi∪ Fo，其中，Fi? { (p, t)|p ∈ P , t ∈ T }是 輸 入 弧 集 ， Fo?{(t,p)| p∈ P , t ∈ T }是輸出弧集；Fi=Fn∪Fh∪Ft，Fn、Fh和Ft分別是一般弧集(normal arcs)、抑制弧集(inhibitor arcs)和檢測弧集(test arcs)，并且 Fn、Fh和 Ft兩兩不相交。

4) C是顏色的非空有限集；CF： P→CM是顏色映射函數，其中，CM是C上的多重集(multiset)。

5) E： F→ expression 是弧函數；G： T→ bool是變遷門函數(guard function)。

6) W： P→N+是庫所容量函數，對?p∈P, 都有W(p)∈N+，N+是自然數集合，表示庫所p的最大容量。

7) M0： P→CM是初始標記函數，對網中庫所標記。?p∈P，M(p)表示p的標識，p中的token以二元組(p, c)表示，其中，c∈C表示token顏色。

定義2 在EPN中，變遷t 的前集用?t 表示，?t = {p|(p, t)∈F, p∈P}。

1) 若對于?p∈?t，都有 p不包含 token且(p,t)∈Fh，或者p 中至少包含E(p,t)個token，并且(p, t)?Fh，則稱t是激活的(enabled)。

2) 若t 是激活的，且G(t)返回true，則稱t為可發生的(firable)。

3) 若t為可發生的，則t發生后，網中的標識由式(1)確定。

帶檢測弧和抑制弧的有色 Petri網在表達能力上是與傳統有色 Petri網是等價的[16]，因此，檢測弧和抑制弧并沒有降低EPN的分析能力，并且檢測弧和抑制弧使得EPN比標準有色Petri網更為簡潔。

2.2 EPN的描述能力

EPN不僅可以描述復合事件和復合條件，而且可以描述 ECA規則中事件消耗模式(event consumption mode)。

2.2.1 對觸發變遷的描述

ECA規則的每個原子事件在EPN中都對應一個原子事件庫所。普通原子事件在EPN中對應的事件庫所與觸發變遷之間的弧是普通弧，而原子事件的“逆事件”對應的弧則為抑制弧。設一條ECA規則r的事件為e1∧e2∧?e3，變遷t是r在EPN中對應的觸發變遷，庫所p是r處于觸發態的庫所。圖1是觸發變遷t發生過程，圖1(a)是t發生前EPN狀態，圖1(b)是t發生后EPN狀態。t發生后，一個token將流入到庫所p，其含義是規則r被觸發。

圖1 觸發變遷的發生過程

2.2.2 對激活變遷的描述

ECA規則的每個原子條件在EPN中都對應一個條件庫所。普通原子條件所對應的條件庫所與規則的激活變遷之間的弧是檢測弧，而否定形式的原子條件所對應的條件庫所與激活變遷之間的弧是抑制弧。設一條ECA規則r的條件為c1∧?c2，變遷t為激活變遷，庫所p和p'分別為處于觸發態和激活態的庫所。激活變遷t的發生過程如圖2所示，其中，圖2(a)是t發生前的EPN狀態，圖2(b)是t發生后的 EPN狀態。t發生后，p'中將產生一個token，此時規則r被激活。

圖2 激活變遷的發生過程

2.2.3 對執行變遷的描述

通常情況下，一條 ECA規則執行后不會產生事件，也不會改變條件，此時該規則在EPN所對應的執行過程如圖3所示，其中，庫所p和p'分別為處于激活態的庫所和動作庫所。

圖3 執行變遷的發生過程

2.2.4 對規則動作改變條件情形的描述

如果一條ECA規則r改變原子條件，那么EPN中r對應的執行變遷t的發生過程如圖4所示，其中，庫所p和pc分別為處于激活態的庫所和條件c

對應的庫所。

圖4 3種改變條件的情形對應的EPN

1) 情形1：使條件c為真

如圖4(a)所示，在網中添加一個動作庫所p'和一個變遷t'，(pc, t')為抑制弧。t發生后，如果c為真，則t'將不發生，此時c仍為真；否則t'將發生，將c改為真。

2) 情形2：使條件c為假

如圖4(b)所示，在網中添加一個動作庫所p'和一個變遷t'，(pc, t')為一般弧。t發生后，如果c為假，則t'將不發生，此時c仍為假；否則t'將發生，將c改為假。

3) 情形3：使條件c取反

如圖4(c)所示，在網中添加一個動作庫所p'和2個變遷t'和t''，(pc, t')和(pc, t'')分別為一般弧和抑制弧。t發生后，如果c為真，則t'將發生，將c改為假；否則變遷t''將發生，將c改為真。

2.2.5 對事件消耗模式的描述

ECA規則的事件消耗模式包括消耗范圍(記為cs)和消耗時間(記為 ct)2種屬性[17]，其中，消耗范圍表示系統對觸發事件的處理方式，具有3種取值：不消耗(記為0)、局部消耗(記為1)和全局消耗(記為2)；消耗時間屬性有2種取值：條件評價后(記為0)和規則動作執行后(記為1)。若ct=0，則不考慮條件評價的結果，而是根據cs的取值處理觸發事件；若ct=1，則需考慮規則條件評價結果。如果條件評價結果為假，則不處理觸發事件；否則，將根據cs的取值處理觸發事件。為了在EPN中有效描述事件消耗模式，本文約定，對于一個事件庫所 p，其中的token標識(p, c)中c取值為規則標識，含義是該token能夠觸發規則標識為c的ECA規則。針對不同的事件消耗模式，EPN的具體結構如下：(設事件 e是可以觸發規則集{rj, rj+1, …, rk}，p是對應的事件庫所)

1) 消耗范圍是不消耗(cs=0)

此時，p中有一個標記為(p, n)的token，符號n表示 e的事件消耗范圍是不消耗；p到規則集{rj,rj+1,…, rk}所對應的每一個觸發變遷均有一條輸入弧。圖 5是事件消耗時間為“條件評價后”(ct=0)的EPN結構，t2是激活變遷。設r的條件為c1∧?c2。pc1和 pc2分別與變遷 t3和 t4連接，其中，( pc1, t2)和( pc2, t4)為檢測弧，( pc1, t3)和( pc2, t2)為抑制弧。r被觸發后，3個變遷t2、t3和t4中有且僅有一個發生，此時，庫所p中都將產生一個token，其含義是當評估完條件后，觸發事件e都將重新產生，而不論評估結果如何。

圖5 觸發事件的消耗范圍為“不消耗”且ct=0時的EPN

圖 6為事件消耗時間為“執行動作后”(ct=1)的EPN，t2和t3分別是激活變遷和執行變遷。只有當t3發生時，e才會被重新產生，其含義是在條件的評價結果為真時，不會被消耗觸發事件，反之，若條件檢測結果為假，則消耗觸發事件。

圖6 觸發事件的消耗范圍為“不消耗”且ct=1時的EPN

2) 消耗范圍是局部消耗(cs=1)

此時，事件庫所p中有k-j+1個token，標記分別為(p, rj), (p, rj+1), …, (p, rk)。庫所 p到{rj,rj+1, …, rk}所對應的每個觸發變遷均有一條輸入弧，且弧上的表達式為所指向的 ECA規則標識。由于每個token根據其顏色只觸發其中一條規則，因此，局部消耗事件在消耗時間為“條件評價后”與 “執行動作后”的EPN結構相同。圖7為局部消耗模式的EPN，設規則r1的條件為c1?c2, t2和t3分別是激活變遷和執行變遷，不論t2是否發生，觸發事件都將被消耗。

3) 消耗范圍為全局消耗(cs=2)

此時，庫所 p中只有一個標記為(p, g)的token，符號 g 表示事件消耗范圍是全局消耗；p到{rj, rj+1,…, rk}的每個觸發變遷均有一條輸入弧。設e觸發了2條ECA規則r1和r2，其中，r1優先級較高，r1和r2的條件分別為c1和c2。圖8為事件消耗時間為“條件評價后”(ct=0)的 EPN，t2和 t3分別是 r1和r2的激活變遷。t1發生后，r1和r2被觸發。由于(1tp, t3)是抑制弧，故先評價c1。若c1滿足，則消耗2tp中的token，處于觸發態r2被改成未觸發態。

圖7 觸發事件的消耗范圍為“局部消耗”的EPN

圖8 觸發事件的消耗范圍為“全局消耗”且ct=0時的EPN

圖 9為觸發事件的消耗時間為“執行動作后”(ct=1)的EPN。t1發生后，r1和 r2均被觸發，此時(1tp, t3)和(1vp, t3)是抑制弧，因此先對r1進行條件評價，當r1的條件滿足且變遷t4發生時，r2的狀態被改變，被重新轉為未觸發狀態。

圖9 觸發事件的消耗范圍為“全局消耗”且ct=1時的EPN

2.2.6 對規則產生事件的描述

在EPN中，如果執行變遷產生原子事件e(設p為e對應的事件庫所)，那么：1) 如果e的事件消耗模式為不消耗，則所產生 token的標記為(p,n)；2) 如果 e的事件消耗模式為全局消耗，則所產生token的標記為(p, g)；3)如果e的事件消耗模式為局部消耗，設e可觸發規則集{rj, rj+1,…, rk}，則將產生k-j+1個token，其標記依次為(p, rj), (p,rj+1),…, (p, rk)。

2.3 EPN舉例

例1 一條ECA規則r 描述如下。

ON e1?e2??e3

IF c1??c2THEN e2??c1

規則 r 的語義為：當原子事件e1和 e2發生并且e3沒有發生時，r被觸發，然后評價r的條件，如果c1成立且c2不成立，則執行動作，產生e2并使c1不成立。設r觸發事件的消耗模式為局部消耗。圖10是規則r的EPN的初始狀態，e1和e2已發生，e3未發生，此時觸發變遷t1是可發生的。t1發生后，r被觸發，庫所pt中產生一個token。由于條件庫所pc1中有 token(條件 c1成立)且庫所 pc2中沒有token(條件c2不成立)，此時激活變遷t2是可發生的。t2發生后，r被激活，庫所pv中產生一個token。此時，t3可發生。t3發生后，在e3和pn各產生一個token。由于1cp有token，因此變遷t4是可發生的。t4發生后，消耗庫所1cp中的token。此時，完成了規則r 的一次觸發執行過程。

圖10 規則r的EPN

2.4 ECA規則集的EPN等價轉化

為了利用 EPN中的規則結構信息分析規則集的終止性，本文提出了EPN的等價轉化算法，該算法將包含復雜規則特性(如復合事件、復合條件、事件消耗模式、觸發關系、活化關系和墮化關系等)的ECA規則集轉化為等價的EPN。ECA規則集EPN的等價轉化算法如圖11所示。

3 ECA規則集的終止性分析

3.1 理論分析

在ECA規則中，如果存在事件消耗模式為不消耗的事件，那么一旦該事件發生，該規則將不可終止。因此本文假設規則集中不存在事件消耗模式為不消耗的規則。設∑為 ECA規則集R的EPN表示，L是網∑ 中的一個觸發環，L=(r1, r2,…, ri)表示規則 r1觸發 r2, r2觸發 r3,…,且 ri觸發 r1。

圖11 ECA規則集EPN的等價轉化算法

定義3 設L是網∑的一個觸發環，如果從任意初始標識出發，L中的規則都將在執行有限次后永遠不會被觸發，那么稱L為一個假觸發環，否則，L為一個真觸發環。

定義4 設L是網∑的一個觸發環。對于L中的一條規則r和一個庫所p，如果規則r在網∑中對應的事件庫所集合、條件庫所集合和動作庫所集合包含p，則稱p屬于觸發環L，記p∈L。

定義5 設L是網∑的一個觸發環，如果存在庫所p和p'，滿足p∈∑，p'∈L，并且從庫所p'到庫所p有一條通路，則稱p是觸發環L可達的。

定理1 設L是網∑中一個觸發環，存在一條規則r∈L，構成規則r的原子事件設為e，并設e在∑中對應的庫所為p，t為規則r的觸發變遷。如果(p,t)為一般弧，滿足要么p的前集為空，要么p不由任何觸發環可達，那么L是一個假觸發環。

證明 設網∑的一個觸發環L=(r1, r2, …, ri)且規則r∈L，e是r的原子事件，p為e對應的事件庫所，t為r的觸發變遷，(p, t)為一般弧，n為∑的初始標識下p中所包含token的數目，n是自然數。1)如果 p的前集為空，那么∑中任何變遷的發生只可能消耗p的token，而不會在p中產生token。消耗完所有p中的token以后，規則r 將不可能被再一次觸發和執行。由于初始狀態下p中的token的數目是有限的(數目為n)，因此，r 最大觸發次數不會超過n，在此之后，r 將不能再被觸發，從而L為一個假觸發環。2) 如果p不被任何觸發環可達，此時進入p中的token數目是有限的，不妨設為m，從而當消耗完p中所有token時，r被觸發執行的次數不會超過n+m。此后規則r將不能再被觸發，從而L終止。

因此，觸發環L是一個假觸發環，命題得證。

推論1 設L是網∑中一個觸發環，一條ECA規則r∈L，e為r的原子事件，p為e對應庫所，t為r對應的觸發變遷，弧(p, t)為一般弧。如果p的前集為空或僅由假觸發環可達，則L是一個假觸發環。

定理2 設L是網∑中一個觸發環。如果存在一條ECA規則r∈L，其原子條件為c，滿足以下3個條件：1) (c, t)是一般弧，其中，t是r的激活變遷；2) c被改為假或取反；3)改變c 的規則只有一條，設為r'，且r'∈L，那么L為一個假觸發環。

證明 采用反證法。假設觸發環L不是假觸發環。此時，從∑中任何狀態出發，r' 可以被無限次執行。規則 r'改變了規則 r的條件 c，使其為假或取反，但是r被激活的前提是條件評估必須為真。由于改變規則r條件的規則只能是規則r'，因此當r'執行后，導致規則r的條件評價為假，從而使得r不能被激活和執行，從而使得L不能永遠執行下去，與假設矛盾。命題得證。

定理3 設L是網∑中一個觸發環，如果存在一條ECA規則r∈L，r的原子條件為c，并且1) (c, t)是抑制弧，其中，t是r的激活變遷；2) c被改為假或取反；3) 改變c的規則只有一條，設為r'，且r'∈L，那么L為一個假觸發環。

證明 與定理2類似。

定理4 設ECA規則集R的等價EPN為∑，如果∑中不存在任何觸發環或者所有的觸發環都是假觸發環，那么，ECA規則集R是可終止的。

證明 如果網∑中不包含任何觸發環，則命題顯然成立。設L是∑的一個假觸發環，那么對于任意ECA規則r∈L，由定義3可知，r在觸發有限次后將不能被再次觸發，導致規則r是可終止的。由于∑中所有觸發環都是假觸發環，因此，規則集 R中的所有假觸發環中的規則都是可終止的，從而R是可終止的。命題得證。

3.2 終止性判定算法

基于ECA規則集的等價EPN，本文提出了相應的終止性判定算法。該算法充分利用EPN所包含的規則信息，通過化簡EPN來判定規則集的可終止性。算法具體描述如圖12所示。

圖12 ECA規則集的可終止性判定算法

本質上講，基于圖理論的 ECA規則集終止性分析方法是通過構造規則集的觸發關系矩陣(或活化關系矩陣等)，并依據該矩陣元素的可達性判定原規則集是否存在環(回路)。一般地，設A為規則集的觸發關系矩陣，元素aij=1表示ECA規則i觸發ECA規則j。矩陣M=Ak中的元素mij的值表示從規則i到規則j的長度為k的觸發鏈路條數，而其對角線上的元素aii不為0則表示存在觸發環或回路。在極端情況下，規則集不存在任何觸發環或存在一個包含大部分或所有規則的觸發環時，矩陣的乘法運算需要進行到An，這是判定算法的最壞情況。因此，現有基于觸發圖等圖理論的判定算法的時間復雜度為O(n4)[8,9,14]，其中，n為ECA規則條數。

本文提出的規則集判定算法不同于傳統基于圖理論的規則集可終止性判定算法，它基于ECA規則集的等價EPN，而EPN中包含了ECA規則的豐富規則信息，如復合事件、復合條件、事件消耗模式等，通過在EPN來判定定理1、定理2和定理 3，從而不斷消除所有能終止的規則和所有假觸發環，達到化簡 EPN的目的。如果最終EPN的所有元素均被刪除，則表示原ECA規則集不包含任何觸發環或所有的觸發環都是假觸發環，從而原ECA規則集是可終止的，否則，原規則集不可終止。

在算法2中，2)基于定理1和推論1對EPN進行化簡，時間復雜度為O(m2)，其中，m為ECA規則集中所有不同的原子事件個數。3)基于定理2和定理3對EPN再次化簡，時間復雜度為O(kn)，其中，k為規則中所有原子條件的個數，n為規則條數。通常在ECA規則集合中，k<

3.3 終止性判定舉例

例2 設有ECA規則集R={ r1, r2, r3, r4}，其中，

r1： ON e1?e2IF c1THEN e3

r2： ON e3?e4IF c2THEN e1

r3： ON e4IF c3?c2THEN ?c2?e5

r4： ON e5IF c3THEN e4

ECA規則r1, r2, r3和r4中各元素的含義與例1中的 ECA規則相同，設所有規則的事件消耗模式為局部消耗。圖13是規則集R的等價EPN∑。對規則集R的終止性分析過程如下所述。

圖13 規則集的EPN

執行算法2的2)后，網∑被化簡，如圖14所示。在3)中，由于原子條件c2及改變該條件的唯一一條ECA規則r3使c2為假，從而定理2成立，進而刪除相關元素后，EPN被再次化簡為只剩下規則r1。由于flag的取值為true，轉至2)，EPN被再次化簡為空，從而得出結論：規則集R是可終止的。目前，采用已有方法均不能得出與筆者相同的終止性分析結論。

圖14 化簡后的EPN

4 實驗分析

針對不同的ECA規則集和終止性判定算法，本文設計了相應的仿真實驗以驗證各判定算法的正確性和效率。實驗環境如下：CPU Intel 雙核1.86 GHz，內存 1GB，Windows XP專業版，Microsoft Visual Studio 2005平臺。參與對比的判定算法有3種TG、BK和PN算法，其中，TG(基于觸發圖的判定)算法是依據規則集的觸發關系矩陣及其乘法運算計算是否存在回路，BK 算法是 Bostan-Korpeoglu[14]等人的算法，PN是本文所使用的算法。

4.1 實驗1

待測試ECA規則集R只包含一個觸發環L，L= {r1, r2, …, rn}，n為規則條數。r1的事件為 e1?e2，rn產生事件e1、事件e2是獨立事件，它不被任何規則產生。實驗中n取值范圍(100, 1 000)。表1記錄了規則集在不同算法下的運行時間。結果表明本文提出算法(PN)的效率最高，且算法PN和BK得出了正確結論(規則集是可終止的)，而算法 TG的判定結果出錯(規則集不可終止)。

表1 含一個觸發環時算法的運行時間(單位：s)

4.2 實驗2

待測試ECA規則集R含有3個觸發環，分別為 L1、L2和 L3，其中，L1=( r1, r2,…, rn/2)，L2=( rn/2+1,rn/2+2,…, rn)和 L3=(rn/4, rn/4+1,…, rn/2, rn/4×3, rn/4×3+1,…,rn)。規則 r1的事件為 e1?e2，其中，e2不被任何規則動作產生。表2記錄了規則集在不同算法下的運行時間，結果表明本文提出算法(PN)的運行時間仍然最短，并且得出了正確結論，而TG算法的判定結果仍然是錯誤的。

表2 含3個觸發環時算法的運行時間(單位：s)

4.3 實驗3

隨機生成待測試ECA規則集R。表3記錄了不同算法的運行時間。所有算法的判定結果是規則集保證終止，即規則集不含任何觸發環，但本文算法PN的運行時間仍遠低于其他算法。

表3 不同算法對隨機生成的規則集判定的運行時間(單位：s)

5 結束語

ECA規則具有復雜的結構特性，這些結構特性使得 ECA規則集的可終止性判定十分困難。針對目前 ECA規則集的終止性判定算法只考慮部分結構特性而導致算法準確性差的缺點，本文提出了可有效表示ECA規則集的擴展Petri網模型(EPN)，并在此基礎上綜合分析了 ECA規則的各種結構特性對終止性的影響，提出了基于EPN的可終止性判定算法。該算法通過化簡EPN來直接刪除ECA規則間的假觸發環，從而提高了判定準確性，并在一定程度上降低了傳統圖理論判定算法的時間復雜度。理論分析和實驗結果表明，本文提出的 ECA規則集可終止性判定算法具有更高的準確性和更低的時間復雜度。

[1] PATON N, DIAZ O. Active database systems[J]. ACM Computing Surveys, 1999, 31(1)：63-103.

[2] 盧捍華, 閔麗娟, 王亞石. 工作流主從實例處理方法及其Petri網建模[J]. 通信學報, 2010, 31(1)：92-99.LU T H, MIN L J, WANG Y S. Approach to master-slave workflow system and its Petri-net modeling[J]. Journal on Communications,2010, 31(1)：92-99.

[3] 郭迎九, 林闖, 尹浩等. 基于Petri網的數字媒體分發協議的安全性證明[J].電子學報,2009,37(5)：1031-1036.GUO Y J, LIN C, YIN H, et al. Proof of the security of digital media distributing protocol based on Petri net models[J]. Acta Electronica Sinica, 2009, 37(5)：1031-1036.

[4] AIKEN A, WIDOM J, HELLERSTEIN J M. Behavior of database production rules： termination, confluence, and observable determinism[J]. SIGMOD, 1992, 21(2)：59-68.

[5] BAILEY J, DONG G, RAMAMOHANARAO K. Decidability and undecidability results for the termination problem of active database rules[A]. PODS'98[C]. New York, USA, 1998. 264-273.

[6] MURATA T. Petri nets： properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4)：541-580.

[7] BARALIS E, CERI S, WIDOM J. Better termination analysis for active databases[A]. RIDS '93[C]. Edinburgh, Scotland, 1993.163-179.

[8] BARALIS E, CERI S, PARABOSCHI S. Improved rule analysis by means of triggering and activation graphs[A]. RIDS'95[C]. Greece：Springer-Verlag, 1995. 165-181.

[9] MONTESI D, BAGNATO M, DALLERA C. Termination analysis in active databases[A]. IDEAS'99[C]. Montreal, Canada, 1999. 288-297.

[10] 郝忠孝, 任超, 趙齡強. 含環觸發圖對應的主動規則集可終止性分析[J]. 計算機研究與發展, 2005, 42(12)：2199-2205.HAO Z X, REN C, ZHAO L Q. Termination analysis of active rule based on dependency set[J]. Journal of Computer Research and Development, 2005, 42(12)：2199-2205.

[11] 熊曾剛, 楊揚, 曾明. 基于Petri網的兩階段網格任務調度模型與分析[J]. 通信學報, 2009, 30(8)：69-77.XIONG C G, YANG Y, ZENG M. Research on two-phase grid task scheduling based on Petri nets[J]. Journal on Communications, 2009,30(8)：69-77.

[12] LATIFA B, HAFIDA B. The priority of rules and the termination analysis using Petri nets[J]. The International Arab Journal of Information Technology, 2007, 4(2)：177-183.

[13] MEDINA-MARIN J, PEREZ-LECHUGA G, LI X. ECA rule analysis in a distributed active database[A]. ICCTD'09[C]. Kinabalu, Malaysia,2009.113-116.

[14] BOSTAN-KORPEOGLU B, YAZICI A. A fuzzy Petri net model for intelligent databases[J]. Data & Knowledge Engineering, 2007, 62(2)：219-247.

[15] 張立臣.面向普適計算的主動訪問控制模型研究[D].西安：陜西師范大學,2011.ZHANG L C. Research on Active Access Control Model for Pervasive Computing[D]. Xian： Shaanxi Normal University,2011.

[16] CHRISTENSEN S, HANSEN N. Coloured Petri nets extended with place capacities, test arcs and inhibitor arcs[J]. Lecture Notes in Computer Science, 1993, 691(1)：186-205.

[17] FRATERNALI P, TANCA L. A structured approach for the definition of the semantics of active databases[J]. ACM Trans on Database Systems, 1995, 20(4)：414-471.