簡易檢索 / 詳目顯示
| 研究生： |
曾昭宏 Tseng, Jau-Hung |
|---|---|
| 論文名稱： |
同步選擇派屈網路性質之研究 Some Properties of Synchronized Choice Ordinary Petri Net |
| 指導教授： |
趙玉
Cha, Y. Daniel |
| 學位類別： |
碩士
Master |
| 系所名稱： |
商學院 - 資訊管理學系 Department of Management Information System |
| 論文出版年： | 1998 |
| 畢業學年度： | 86 |
| 語文別： | 英文 |
| 論文頁數： | 83 |
| 中文關鍵詞： | 派屈 、同步選擇 |
| 外文關鍵詞： | Petri, Synchronized choice, SNC, Synthesized net, S-Matrix |
| 相關次數： | 點閱：231 下載：0 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
傳統上，派屈網路分類的方式是依照區域結構分成"簡單網"、"非對稱選擇網"， "擴充自由選擇網"，"自由選擇網"，"標記圖形網"，"狀態機"。最近我們將派屈網路依照全域結構的分類方式分成兩類：同步選擇網及非同步選擇網。 同步選擇網的結構不同於其它的分類方式，不但可以作派屈網的分類，而且可以因此決定網路的性質如：boundedness、liveness、reversibility等。
在一個同步選擇網中，任何一個沒有bridge的handle必定是一個TT-或PP-路徑；同步選擇網也可以分解成許多T-components或P-components；同步選擇網是非常值得研究的題目，如果一個派屈網不屬於同步選擇網，這個派屈網很可能有設計上的錯誤如unbounded或deadlock。
Traditionally Petri nets (PN) are classified, based on local structures (input and output set of transitions or
places), into simple nets, asymmetric choice nets, extended free choice nets, free choice nets, mark graphs and state machines. We categorize ordinary Petri nets into two lasses: SNC and non-SNC based on global structure. Unlike other class of Petri nets, the structure of SNC nets not only classify the nets, but also determine the properties of the nets such as boundedness, liveness, reversibility, …etc.
In an SNC, any prime handle must be either a TT-or PP-path. SNC nets is declared to be largest (than Free Choice) set of nets that are covered by both T-components and P-components. SNC nets is interesting because if a designed PN is not an SNC, then most likely it suffers from design errors of deadlocks or unbounded.
SNC nets is both structurally live and bounded. However, it may not be live or reversible. This thesis presents the conditions of liveness and rsibility. An algorithm is developed to detect SNC nets which based on a useful mechanism called S-Matrix to records the structure relationship between any two PSP's. Further, we will also provide algorithms to check the SNC nets to be live and irreversible.
1. INTRODUCTION -----1
2. PRELIMINARIE -----7
2.1 Petri net definition -----7
2.2 Marked Petri nets -----7
2.3 Petri net firing rules -----8
2.4 Subclass of Petri nets -----9
2.5 Petri net behavior properties -----12
2.6 Incidence Matrix and state equation -----15
2.7 Structural properties of Petri nets -----16
2.8 Synchronic distance and structure synchronic distance -----17
2.9 Pseudo process, generation point, and joint point -----17
2.10 Prime start node and prime end node -----18
2.11 Structural Relationship -----19
2.12 P-invariant, T-invariant -----19
2.13 Conservativeness -----20
2.14 Consistency -----20
2.15 LEX and LCN -----20
3. SYNTHESIZED NET (SN) -----22
3.1 The Synthesis Rules -----22
3.2 Examples of Synthesized Petri Nets -----26
4. SYNCHRONIZED CHOICE NET (SNC) -----33
4.1 Handle -----33
4.2 Bridge -----34
4.3 Prime Handle -----34
4.4 SNC -----35
5. PROPERTIES OF SNC-----38
5.1 Notations -----38
5.2 Relationship between Synchronized Choice Net and TP_Decomposability -----39
5.3 Structure Matrix for Petri Net -----48
5.4 The algorithm for SNC detection -----58
5.5 Reachability -----61
5.6 Livness -----62
5.7 Irreversibility -----72
5.8 The Relationship between Synthesized Net and Synchronized Choice Net -----75
5.9 Duality -----78
6. CONCLUSION
7. REFERECNE
LIST OF FIGURES
Figure 2.1. The typical structure that represents the subclasses of Petri nets.-----11
Figure 2.2. An overview of Petri net subclass classification. -----11
Figure 2.3. Examples of Petri net for all possible combination of three properties. -----14
Figure 2.4. Examples of Incidence Matrix A. -----15
Figure 3.1. An example of a basic process. -----22
Figure 3.2. An example of TT.1 rule and TT.2 rule. -----23
Figure 3.3. An example of a PP.1 rule. -----27
Figure 3.4. An example of interactive TT generation (TT.3 rule). -----28
Figure 3.5. An example of an interactive TT generation (TT.4 rule). -----29
Figure 3.6. An example of an interactive PP generation (PP.2 rule). -----31
Figure 4.1. PT-Handle and TP-Bridge. -----34
Figure 4.2. An example of PT-handle and TP-bridge in a Free Choice Net. -----36
Figure 4.3. An example of Synchronized Choice Net. -----37
Figure 4.4. An asymmetric choice net (AC), but not SNC. -----37
Figure5.1. T-Components of Fig.3.5(b). -----43
Figure 5.2. T-Components of Fig.4.3. -----45
Figure 5.3. T-Components and P-Components of the Petri net in Fig.4.2. -----47
Figure 5.4. An example of PN and its T-Matrix. -----49
Figure 5.5. Illustration of new handle generation. -----51
Figure 5.6. Original Petri Nets and its T-Matrix prior to the pure handle generation. -----52
Figure 5.7. The new Petri Nets and its T-Matrix after a new pure handle generation -----52
Figure 5.8. Illustration of a new bridge generation. -----54
Figure 5.9. The T-Matrix A' after a new bridge generation. -----56
Figure 5.10(a) pspl is exclusive to psp2, but joint at atransition. -----58
Figure 5.10(b) pspl is concurrent to psp2, but joint at a place. -----58
Figure 5.11(a) An example of live & reversible SNC. -----63
Figure 5.11(b) Dual of Fig.5.11(a). -----63
Figure 5.11(c) An example of irreversible SNC. -----64
Figure 5.l1(d) Dual of Fig.5.11(c). -----64
Figure 5.12. Three cases of partially marked TT subnet. -----66
Figure 5.13. The Bridge B and Subhandle H<sub>s</sub> -----67
Figure 5.14. Illustration of LC of case(1). -----68
Figure 5.15. Illustration of LC of case(2). -----68
Figure 5.16. An example of irreversible SNC. -----72
Figure 5.17. Similar to Fig.5.11(c), but is reversible. -----73
Figure 5.18. Similar to Fig.3.5(b), but deadlock SNC. -----77
(限達賢圖書館四樓資訊教室A單機使用)