1. NCCU Academic Hub
  2. 學術產出
  3. College of Commerce
  4. Theses
  5. Item

學術產出-Theses

Article View/Open

Publication Export

Google ScholarTM

政大圖書館

Citation Infomation

  • No doi shows Citation Infomation
題名 派翠網路的基本架構
Fundamental Structures in Petri Nets
作者 廖扶西
Nicdao, Jose Marcelino Arrozal
貢獻者 趙玉
Daniel Chao, Y.
廖扶西
Jose Marcelino Arrozal Nicdao
關鍵詞 派翠
網路
基本架構
Petri Nets
Synchronized Choice Nets
Liveness
Boundedness
First-order structures
Second-order structures
TP and PT Handles
Bridges
Siphons
Traps
Deadlocks
日期 2000
上傳時間 31-Mar-2016 15:44:01 (UTC+8)
摘要 The thesis contributes to the theoretical study of Petri net theory. We conduct boundedness and liveness structural analysis of Synchronized Choice nets (SNC) based on fundamental structures in Petri nets and identified as first-order structures. By studying these structures, the study proposes two ways of preserving good properties: addition of second-order structures or other asymmetric structures. Liveness of these new SNC nets is studied based on the concept of siphons and traps. We prove that SNC nets thus formed are structurally bounded and live. The thesis extends this class of nets to those with pure TP and PT first-order structures and explores its structural and marking conditions. Based on this, we introduce a new class of Synchronized Choice nets called Expanded Synchronized Choice nets.
參考文獻 [1] Agerwala, T. and Y. Choed-Amphai, “A Synthesis Rule for Concurrent Systems,” Proc. of Design Automation Conf., 1978, pp. 305-311.
     [2] Arnold, A., “Synchronized Products of Transition Systems and Their Analysis,” Advances in Petri Nets, Lecture Notes in Computer Science, 1995, Springer Verlag, pp. 26-27.
     [3] Barkaoui, K. and M. Minoux, “A Polynomial-time Graph Algorithm to Decide Liveness of Some Basic Classes of Bounded Petri Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1992, Springer Verlag, pp. 62-75.
     [4] Barkaoui, K., J.M. Couvreur, and C. Dutheillet, “On Liveness in Extended Non Self-Controlling Nets,” Application and Theory of Petri Nets, 16th International Conference, Turin, Italy, June 26-30 1995 Proceedings, G. De Michelis and M. Diaz eds., Springer Verlag, pp. 25-44.
     [5] Berthelot, G., “Checking Properties of Nets Using Transformations,” Advances in Petri Nets, G. Rozenberg ed., 1985, Springer Verlag, pp. 19-40.
     [6] Best, E., “Structure Theory of Petri Nets: the Free Choice Hiatus,” Advanced Course in Petri Nets, Bad Hannef, Lectures Notes on Computer Science Vol. 254, Springer Verlag, 1987, pp. 168-205.
     [7] Brams, G.W., “Reseaus de Petri,” Theoretical Computer Science, Springer Verlag, 1985.
     [8] Brauer, W., R. Gold, and W. Volger, “A Survey of Behavior and Equivalence Preserving Refinements of Petri Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1990, Springer Verlag, pp. 1-46.
     [9] Chao, D.Y., “A CAD Tool for Constructing Large Petri Nets,” revised for IEEE Trans. SMC.
     [10] Chao, D.Y., “Application of a Synthesis Algorithm to Flexible Manufacturing System,” Journal of Information Science and Engineering, Vol. 14, No. 2, June 1998, pp. 409-447.
     [11] Chao, D.Y., “Equivalence of Temporal and Structural Relationships of Synthesized Nets using Knitting Technique,” invited paper 1997 Proc. IEEE Int’l Conf. SMC, Orlando, Florida, USA, October 13-15, 1997.
     [12] Chao, D.Y., “Extending a CAD Tool to Synthesize FMS Modeled by General Petri Nets,” 1998 International Mechtronics, Hsinchu, Taiwan, December, pp. 379-384.
     [13] Chao, D.Y., “Extending Knitting Algorithm to Synthesize Resource Sharing FMS,” invited paper in Proc. 1998 Int’l Conf. SMC, San Diego, CA, USA, October 12-16, 1998.
     [14] Chao, D.Y., “Knitting Technique and Structural Matrix for Deadlock Analysis and Synthesis of Petri Nets with Sequential Exclusion,” MIS Review, Vol. 7, December 1997, pp. 45-85.
     [15] Chao, D.Y, “Linear Algebra Based Verification of Well-Behaved Properties and S-invariants of Petri Nets Synthesized Using Knitting Technique,” MIS Review, Vol. 5, December 1995, pp. 27-48.
     [16] Chao, D.Y., “Petri Net Synthesis and Synchronization Using Knitting Technique,” Journal of Information Science and Engineering, Vol. 18, No. 5, 1999.
     [17] Chao, D.Y., “The Algorithm for Checking Liveness in Synchronized Choice Net,” (invited) Proc. 1999 IEEE Int’l Conf. SMC, Beijing, China, July 5-9, 1999.
     [18] Chao, D.Y., “The Algorithm for Synchronized Choice Net Detection,” Proceedings of 1999 Workshop on Distributed System Technologies & Applications, Tainan, Taiwan, May 13-14, 1999, pp. 276-284.
     [19] Chao, D.Y, “X-Window Implementation of an Algorithm to Synthesize Ordinary Petri Nets,” Journal of National Cheng-Chi University, Vol. 73, Oct, 1996, pp.451-496.
     [20] Chao, D.Y. and D.T. Wang, “A Reduction Algorithm of Petri Net,” Proc. Int`l Comp Symp, Taichung, Taiwan, Dec. 1992, pp. 16-23.
     [21] Chao, D.Y. and D.T. Wang, “A Synthesis Technique for General Petri Nets,” Journal of Systems Integration, Vol.4, No.1, 1994, pp.67-102.
     [22] Chao, D.Y. and D.T. Wang, “An Interactive Tool for Design, Simulation, Verification, and Synthesis of Protocols,” Software Practice and Experience, an International Journal, Vol. 24, No. 8, August 1994, pp. 747-783 and to appear in Software Practice and Experience, an International Journal
     [23] Chao, D.Y. and D.T. Wang, “Knitting Technique and Structural Matrix for Deadlock Analysis and Synthesis of Petri Nets with Sequential Exclusion,” International Conference on System, Man, and Cybernetics, San Antonio, Texas, Oct. 1994, pp. 1332-1339.
     [24] Chao, D.Y. and D.T. Wang, “Knitting Technique with TP-PT Generations for Petri Net Synthesis,” invited paper, Proc. 1995 IEEE Int’l Conf. SMC, Vancouver, Canada, October 22-25, 1995, pp. 1454-1459.
     [25] Chao, D.Y. and D.T. Wang, “Petri Net Synthesis and Synchronization using Knitting Technique,” International Conference on System, Man, and Cybernetics, San Antonio, Texas, Oct. 1994, pp. 652-657.
     [26] Chao, D.Y. and D.T. Wang, “Synchronized Choice Ordinary Petri Nets,” invited paper, Proc. 1995 IEEE Int’l Conf. SMC, Vancouver, Canada, October 22-25, 1995, pp. 1442-1447.
     [27] Chao, D.Y. and D.T. Wang, “The Knitting Technique and its Application to Communication Protocol Synthesis,” MASCOTS ‘94, Durham, NC, pp. 234-238.
     [28] Chao, D.Y. and D.T. Wang, “Two Theoretical and Practical Aspects of Knitting Technique—Invariants and A New Class of Petri Net,” IEEE Transactions on System, Man, and Cybernetics, Vol. 27, No.6, 1997, pp.962-937.
     [29] Chao, D.Y. and D.T. Wang, “XPN-FMS: A Modeling and Simulation Software for FMS using Petri Nets and X-Window,” International Journal of Flexible Manufacturing Systems, Vol. 7, No. 4, October 1995, pp. 339-360.
     [30] Chao, D.Y. and Jau-Hung Tseng “Some Properties of Synchronized Choice Ordinary Petri Net,” Invited Session paper, 1999 IFAC, Beijing China, July 5-9, 1999, pp.193-197.
     [31] Chao, D.Y., J.H. Tseng, J.H. Tang, J.A. Nicdao, and Y.K. Chen, “The Algorithm for Checking Liveness in Synchronized Choice Nets,” IEEE Conference on Systems, Man, and Cybernetics ’99, Tokyo, Japan, October 12 – 15, 1999, p. 277.
     [32] Chao, D.Y., Jose A. Nicdao, Jih-Hsin Tang and Yi-Kung Chen, “Second Order Structures for Synchronized Choice Ordinary Petri Nets,” the Third World Multiconference on Systemics, Cybernetics and Informatics (SCI`99) and the Fifth International Conference on Information Systems Analysis and Synthesis (ISAS`99), Orlando, USA, July 31-August 4, 1999, Proceedings Volume 5 Computer Science and Engineering, pp. 336-343.
     [33] Chao, D.Y., M.C. Zhou, and D.T. Wang, “Extending Knitting Technique to Petri Net Synthesis of Automated Manufacturing Systems,” Computer Journal (British Computer Society), Oxford University Press, Vol. 37, No. 1-2, pp. 1-10.
     [34] Chen, Y., W.T. Tsai, and D.Y. Chao, “Dependency Analysis—A Compositional Technique for Building Large Petri Nets,” IEEE Transactions On Parallel and Distributed Systems, Vol.4, No.4, 1993, pp. 414-426.
     [35] Commoner, E., “Deadlocks in Petri Nets,” Applied Data Res. Inc., Wakefield, MA, 1972.
     [36] Datta, A., “Modular Synthesis of Deadlock-Free Control Structures,” Foundations of Software Technology and Theoretical Computer Science, Vol. 241, G. Goos and J. Hartmanis ed., 1986, Springer Verlag, pp. 288-318.
     [37] Datta, A. and S. Ghosh, “Synthesis of a Class of Deadlock-Free Petri Nets,” Journal of ACM, Vol. 31, No. 3, 1984, pp. 486-506.
     [38] Desel, J. and J. Esparza, Free Choice Petri Nets, Cambridge University Press, 1995.
     [39] DiCesare, F., G. Harhalakis, J.M. Proth, M. Silva, and F.B. Vernadat, Practice of Petri Nets in Manufacturing, Chapman & Hall, London, 1993.
     [40] Esparza, J. and M. Silva, “Circuits, Handles, Bridges, and Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1991, Springer Verlag, pp. 210-242.
     [41] Esparza, J. and M. Silva, “Top-Down Synthesis of Live and Bounded Choice Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1991, G. Rozenberg ed., Springer Verlag, pp. 118-139.
     [42] Ezpeleta, J., J.M. Colom, and J. Martinez, “A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 2, April 1995, pp. 173-184.
     [43] Hack, M.H.T. “Analysis of Production Schemata by Petri Nets,” Cambridge Mass, MIT, Dept. Electrical Engineering, MS Thesis (1972), corrected June 1974.
     [44] Jeng, M.D. and F. DiCesare, “A Modular Synthesis Techniques for Petri Nets,” Japan-USA Sym. on Flexible Automation, 1992, pp. 1163-1170.
     [45] Jeng, M.D. and F. DiCesare, “A Review of Synthesis Techniques for Petri Nets with Application to Automated Manufacturing Systems,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 1, January/February 1993, pp. 301-312.
     [46] Jeng, M.D. and F. DiCesare, “Synthesis Using Resource Control Nets for Modeling Shared-Resource Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 3, June 1993, pp. 317-327.
     [47] Kemper, P. and F. Bause, “An Efficient Polynomial-Time Algorithm to Decide Liveness and Boundedness of Free-Choice Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1992, G. Rozenberg ed., Springer Verlag, pp. 263-278.
     [48] Koh, I. and F. DiCesare, “Transformation Methods for Generalized Petri Nets and their Applications in Flexible Manufacturing Systems,” IEEE Trans System, Man, and Cybernetics, Vol. 21(6), 1991, pp. 963-973.
     [49] Krogh, B.H. and C.L. Beck, “Synthesis of Place/Transition Net for Simulation and Control of Manufacturing System,” Proc. IFIP Symp. Large Scale Systems, Zurich, Aug. 1986.
     [50] Landweber, L.H. and E.L. Robertson, “Properties of Conflict-Free and Persistent Petri Nets," Journal Of ACM, Vol. 25, No 3, 1978, pp. 352-364.
     [51] Lautenbach, K. and H. Ridder, “Liveness in Bounded Petri Nets which are Covered by T-Invariants,” Application and Theory of Petri Nets, Zaragoza, Spain, June 1994, LNCS, No. 815, R. Valette ed., Springer-Verlag, 1994, pp. 358-378.
     [52] Lee, Dong-Ik, Sadatoshi Kumagai, and Shinzo Kodama, “Complete Structural Characterization of State Machine Allocatable Nets,” IEICE Transactions, Vol. E74, No. 10, pp.3115-3123, October 1991.
     [53] Lee, Dong-Ik, Sadatoshi Kumagai, and Shinzo Kodama, “Handles and Reachability Analysis of Free choice Nets,” Application and Theory of Petri Nets, LNCS, No. 935, Springer-Verlag, 1995, pp. 298-316.
     [54] Lee, K. H. and J. Favrel, “Hierarchical Reduction Method for Analysis and Decomposition of Petri Nets,” IEEE Trans. Systems, Man, and Cybernetics, SMC-15, 2, 1985, pp. 272-280.
     [55] Lien, Y.L., “Termination Properties of Generalized Petri Nets,” SIAM Journal On Computing, Vol. 5, No. 2, 1976.
     [56] Lipton, R.J., “The Reachability Problem Requires Exponential Space,” New Haven, CT, Yale University, Dept. of Computer Science, Res. Rep. 62, 1976.
     [57] Murata, T., “Circuit Theoretic Analysis and Synthesis of Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-24, No. 7, 1977, pp. 400-405.
     [58] Murata, T., “Petri Nets: Properties, Analysis and Applications,” IEEE Proceedings, Vol. 77, No. 4, April 1989, pp. 541-580.
     [59] Murata, T., “Synthesis of Decision-Free Concurrent Systems for Prescribed Resources and Performance,” IEEE Trans. Software Engineering, SE-6, NO. 6, pp. 525-530.
     [60] Murata, T. and J. Y. Koh, “Reduction and Expansion of Live and Safe Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-27, 1980, pp. 68-70.
     [61] Murata, T. and Z. Wu, ”Fair Relation and Modified Synchronic Distances in a Petri Net,” Journal of the Franklin Institute, Vol. 320, No. 2, August 1985, pp. 83-82.
     [62] Narahari, Y. and N. Viswanadham, “A Petri Net Approach to the Modeling and Analysis Manufacturing System,” Annals of Operations Research, Vol. 3, 1985, pp. 449-472.
     [63] Peterson, J.L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1981.
     [64] Pouyan, Ali Akbar, “A Computer-Based Petri Net Approach to Modeling Automated Manufacturing Systems,” Swinburne University of Technology, Australia, PhD Thesis, November 1997.
     [65] Ramamoorthy, C.V., S.T. Dong, and Y. Usuda, “The Implementation of an Automated Protocol Synthesizer (APS) and its Application to the X.21 Protocol,” IEEE Trans. on Software Engineering, No. 9, September 1985, pp. 886-908.
     [66] Ramamoorthy, C.V., Y. Yaw, and W.T. Tsai, “A Petri Net Reduction Algorithm for Protocol Analysis,” Computer Communication Review (USA), Vol. 16, No. 3, Aug. 1986, pp. 157-166.
     [67] Ramamoorthy, C.V., Y. Yaw, and W.T. Tsai, “Synthesis Rules for Cyclic Interactions Among Processes in Concurrent Systems,” Proc. COMPSAC, 1988, pp. 497-504.
     [68] Ramamoorthy, C.V., Y. Yaw, W.T. Tsai, R. Aggarwal, and J. Song, “Synthesis and Performance Evaluation of Two-Party Error-Recoverable Protocols,” COMSAC Symp., Oct. 1986, pp.214-220.
     [69] Ramamoorthy, C.V., Y. Yaw, W.T. Tsai, R. Aggarwal, and J. Song, “Synthesis of Two-Party Error Recoverable Protocols,” Computer Communication Review (USA), Vol. 16, No. 3, Aug. 1986, pp. 227-235.
     [70] Reisig, W., Petri Nets, EATCS Monographs on Theoretical Computer Science, Vol. 4, New York, Springer Verlag, 1985.
     [71] Savi, V.M. and X. Xie, “Liveness and Boundedness Analysis for Petri Nets with Event Graph Modules,” Advances in Petri Nets, Lecture Notes in Computer Science, G. Rozenberg ed., 1992, Springer Verlag, pp. 328-347.
     [72] Sifakis, J., “Structural Properties of Petri Nets,” Math. Fund. of Comp. Sci., Lecture Notes in Comp. Sci., Vol. 64, Springer Verlag, NY 1978, pp. 474-483
     [73] Suzuki, I., and T. Murata, “A Method for Hierarchically Representing Large Scale Petri Nets,” Proceedings, IEEE International Conference on Circuits and Computers, ICCC80, pp. 620-623.
     [74] Suzuki, I., and T. Murata, “A Method of Stepwise Refinement and Abstraction of Petri Nets,” Journal of Computer and System Sciences, Vol. 27, 1983, pp.51-76.
     [75] Teruel, E., P. Chrzastowski-Watchel, J.M. Colom, M. Silva, “On Weighted T-systems,” Research Report GISI-RR-92-04. Dpto. Ing. Electrica e Informatia, Universidad de Zaragoza, January, 1992 and in Application and Theory of Petri Nets, Lecture Notes In Computer Science, Jensen, K. ed., Springer-Verlag, 1992, pp. 348-367.
     [76] Valette, R., “Analysis of Petri Nets by Stepwise Refinement,” Journal of Computer & System Sciences, Vol. 18, 1979, pp.35-46.
     [77] Valvanis, K. S., “On the Hierarchical Analysis and Simulation of Flexible Manufacturing Systems with Extended Petri Nets,” IEEE Trans. of System, Man, and Cybernetics, SMC-20, 1, 1990, pp. 94-100.
     [78] Varpaaniemi, K., “On Stubborn Sets in the Verification of Linear Time Temporal Properties,” Application and Theory of Petri Nets, 19th International Conference ICATPN `98, Lisbon, Portugal, June 22-26 1998: proceedings, J. Desel and M. Silva eds., pp. 124-143.
     [79] Wang, D.T. and D.Y. Chao, “Enhanced Knitting Technique to Petri Net Synthesis,” Proc. 1994 IEEE Int`l Conf SMC, San Antonio, Texas, October 2-5, 1994, pp. 658-663.
     [80] Wang, D.T. and D.Y. Chao, “Extension of Knitting Technique to Petri Net Synthesis and Application to Flexible Manufacturing System Cell Preserving Well-Behaved Properties,” Research Report CIS-94-38, New Jersey Institute of Technology, July 1994.
     [81] Wang, D.T. and D.Y. Chao, “New Knitting Technique for Large Petri Net Synthesis with Automatic Preservation of Liveness, Boundedness and Reversibility,” Research Report CIS-94-41, New Jersey Institute of Technology, July 1994. Also in 1995 Proc. IEEE Int’l Conf SMC, Vancouver, Canada, October 22-25, 1995.
     [82] Yaw, Y., “Analysis and Synthesis of Distributed Systems and Protocols,” Ph.D. Dissertation, Dept. of EECS, U.C. Berkeley, 1987.
     [83] Yaw, Y. and F.L. Foun, “The Algorithm of a Synthesis Technique for Concurrent Systems,” 1989 IEEE Int. Workshop on Petri Nets and Performance Models, Dec. 1989, pp. 266-276.
     [84] Yaw, Y., C.V. Ramamoorthy, and W.T. Tsai, “A Synthesis Technique for Designing Concurrent Systems,” Proc. Second Parallel Processing Symposium, April 1988, pp. 143-166.
     [85] Zhou, M.C. and F. DiCesare, “Adaptive Design of Petri Net Controllers for Error Recovery in Automated Manufacturing Systems,” IEEE Trans. SMC, SMC-19, 5, 1989, pp. 963-973.
     [86] Zhou, M.C. and F. DiCesare, “Parallel and Sequential Mutual Exclusions for Petri Net Modelling of Manufacturing Systems with Shared Resources,” IEEE Transactions on Robotics and Automation, Vol. 7. No. 4, August 1991, pp. 515-527.
     [87] Zhou, M.C., F. DiCesare, and A.A. Desrochers, “A Hybrid Methodology for Petri Net Synthesis of Manufacturing Systems,” IEEE Trans. on Robotics and Automation, Vol. 8 No. 3, 1992, pp. 350-361.
     [88] Zhou, M.C., F. DiCesare, and D. Rudolph, “Design and Implementation of a Petri Net Based Supervisor for a Flexible Manufacturing System,” Automatica, Vol. 28, No. 6, 1992, pp. 1199-1208.
     [89] Zhou, M.C., K. McDermott, and A. Patel, “Petri Net Synthesis and Analysis of a Flexible Manufacturing Systems Cell,” IEEE Trans. SMC, Vol. 23, No.1, March 1993, pp. 524-531.
描述 碩士
國立政治大學
資訊管理學系
86356030
資料來源 http://thesis.lib.nccu.edu.tw/record/#A2002002181
資料類型 thesis
dc.contributor.advisor 趙玉zh_TW
dc.contributor.advisor Daniel Chao, Y.en_US
dc.contributor.author (Authors) 廖扶西zh_TW
dc.contributor.author (Authors) Jose Marcelino Arrozal Nicdaoen_US
dc.creator (作者) 廖扶西zh_TW
dc.creator (作者) Nicdao, Jose Marcelino Arrozalen_US
dc.date (日期) 2000en_US
dc.date.accessioned 31-Mar-2016 15:44:01 (UTC+8)-
dc.date.available 31-Mar-2016 15:44:01 (UTC+8)-
dc.date.issued (上傳時間) 31-Mar-2016 15:44:01 (UTC+8)-
dc.identifier (Other Identifiers) A2002002181en_US
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/83318-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 資訊管理學系zh_TW
dc.description (描述) 86356030zh_TW
dc.description.abstract (摘要) The thesis contributes to the theoretical study of Petri net theory. We conduct boundedness and liveness structural analysis of Synchronized Choice nets (SNC) based on fundamental structures in Petri nets and identified as first-order structures. By studying these structures, the study proposes two ways of preserving good properties: addition of second-order structures or other asymmetric structures. Liveness of these new SNC nets is studied based on the concept of siphons and traps. We prove that SNC nets thus formed are structurally bounded and live. The thesis extends this class of nets to those with pure TP and PT first-order structures and explores its structural and marking conditions. Based on this, we introduce a new class of Synchronized Choice nets called Expanded Synchronized Choice nets.en_US
dc.description.tableofcontents 封面頁
     證明書
     致謝詞
     論文摘要
     目錄
     圖目錄
     表目錄
     Chapter 1 Introduction
     A. Overview
     B. History and applications
     C. Strengths
     D. Formalism
     E. Limitations
     1. Analytical complexity
     2. Non-deterministic
     F. Suggestions to overcome limitations
     G. Analysis
     H. Research Scope
     1. Second-order structures
     2. First-order structures
     Chapter 2 Fundamentals of Petri nets
     A. Overview
     B. Basic elements
     C. Input and output functions
     1. Marking of a Petri net
     2. Node, elementary path, and virtual path
     3. Terminal node
     4. Source transition
     5. Sink transition
     6. Infinite and finite capacity net
     7. Graphical representation
     D. Execution of a Petri net
     1. Enabled transitions
     2. Firing rules
     3. Home place
     4. Iteration
     5. Conflict
     6. Mutually exclusive
     E. Modeling framework
     F. Behavioral properties
     1. Liveness
     2. Safeness
     3. Reachability
     4. Boundedness
     5. Reversibility and Home state
     6. Well-behaved Petri Net
     7. Coverability
     8. Persistence
     9. Synchronic Distance
     G. Analytical techniques
     1. Algebraic-based analytical methods
     2. Reduction
     3. Structural
     H. Structural properties
     1. S and T invariants
     2. P-semiflow and T-semiflow
     3. T-condition
     4. P and T components
     5. Controllability
     6. Structural boundedness (SB)
     7. Structural liveness (SL)
     8. Conservativeness (Cv)
     9. Consistency (Ct)
     10. Repetitiveness
     11. Structure synchronic distance
     12. Language of a Petri Net
     I. Subclasses of Petri nets
     1. Ordinary Petri nets (OPN)
     2. State Machine (SM)
     3. Marked Graph (MG)
     4. Free Choice Net (FC)
     5. Extended Free-Choice Net (EFC)
     6. Asymmetric Choice Net (AC)
     J. Other structures
     1. Siphons and traps
     2. Handles, bridges, and first-order structures
     3. Composite first-order structure
     Chapter 3 Second-order structures
     A. Overview
     B. Inconsistent pair and liveness conditions
     1. Inconsistent Pair
     2. Liveness Conditions (LC)
     C. P-components and two types of minimal siphons
     D. Formal proof of liveness condition
     1. Algorithms for verification of SNC and liveness
     2. Algorithm for constructing an S-Matrix
     3. Time complexity
     E. Application to a Flexible Manufacturing System model
     F. Discussion
     Chapter 4 First-order structures
     A. Overview
     B. Structural constraints
     1. Case (1): Single token in RC
     2. Case (2): Multiple tokens in RC
     C. Marking constraints
     D. Enhancements
     E. Discussion
     Chapter 5 Conclusion and Future Work
     Bibliography
     Appendix
     Appendix A Procedure of Converting P-Semiflow z in WSNC into an S-invariant in ESNC
     Appendix B Di computation for RC with multiple tokens		zh_TW
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2002002181en_US
dc.subject (關鍵詞) 派翠zh_TW
dc.subject (關鍵詞) 網路zh_TW
dc.subject (關鍵詞) 基本架構zh_TW
dc.subject (關鍵詞) Petri Netsen_US
dc.subject (關鍵詞) Synchronized Choice Netsen_US
dc.subject (關鍵詞) Livenessen_US
dc.subject (關鍵詞) Boundednessen_US
dc.subject (關鍵詞) First-order structuresen_US
dc.subject (關鍵詞) Second-order structuresen_US
dc.subject (關鍵詞) TP and PT Handlesen_US
dc.subject (關鍵詞) Bridgesen_US
dc.subject (關鍵詞) Siphonsen_US
dc.subject (關鍵詞) Trapsen_US
dc.subject (關鍵詞) Deadlocksen_US
dc.title (題名) 派翠網路的基本架構zh_TW
dc.title (題名) Fundamental Structures in Petri Netsen_US
dc.type (資料類型) thesisen_US
dc.relation.reference (參考文獻) [1] Agerwala, T. and Y. Choed-Amphai, “A Synthesis Rule for Concurrent Systems,” Proc. of Design Automation Conf., 1978, pp. 305-311.
     [2] Arnold, A., “Synchronized Products of Transition Systems and Their Analysis,” Advances in Petri Nets, Lecture Notes in Computer Science, 1995, Springer Verlag, pp. 26-27.
     [3] Barkaoui, K. and M. Minoux, “A Polynomial-time Graph Algorithm to Decide Liveness of Some Basic Classes of Bounded Petri Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1992, Springer Verlag, pp. 62-75.
     [4] Barkaoui, K., J.M. Couvreur, and C. Dutheillet, “On Liveness in Extended Non Self-Controlling Nets,” Application and Theory of Petri Nets, 16th International Conference, Turin, Italy, June 26-30 1995 Proceedings, G. De Michelis and M. Diaz eds., Springer Verlag, pp. 25-44.
     [5] Berthelot, G., “Checking Properties of Nets Using Transformations,” Advances in Petri Nets, G. Rozenberg ed., 1985, Springer Verlag, pp. 19-40.
     [6] Best, E., “Structure Theory of Petri Nets: the Free Choice Hiatus,” Advanced Course in Petri Nets, Bad Hannef, Lectures Notes on Computer Science Vol. 254, Springer Verlag, 1987, pp. 168-205.
     [7] Brams, G.W., “Reseaus de Petri,” Theoretical Computer Science, Springer Verlag, 1985.
     [8] Brauer, W., R. Gold, and W. Volger, “A Survey of Behavior and Equivalence Preserving Refinements of Petri Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1990, Springer Verlag, pp. 1-46.
     [9] Chao, D.Y., “A CAD Tool for Constructing Large Petri Nets,” revised for IEEE Trans. SMC.
     [10] Chao, D.Y., “Application of a Synthesis Algorithm to Flexible Manufacturing System,” Journal of Information Science and Engineering, Vol. 14, No. 2, June 1998, pp. 409-447.
     [11] Chao, D.Y., “Equivalence of Temporal and Structural Relationships of Synthesized Nets using Knitting Technique,” invited paper 1997 Proc. IEEE Int’l Conf. SMC, Orlando, Florida, USA, October 13-15, 1997.
     [12] Chao, D.Y., “Extending a CAD Tool to Synthesize FMS Modeled by General Petri Nets,” 1998 International Mechtronics, Hsinchu, Taiwan, December, pp. 379-384.
     [13] Chao, D.Y., “Extending Knitting Algorithm to Synthesize Resource Sharing FMS,” invited paper in Proc. 1998 Int’l Conf. SMC, San Diego, CA, USA, October 12-16, 1998.
     [14] Chao, D.Y., “Knitting Technique and Structural Matrix for Deadlock Analysis and Synthesis of Petri Nets with Sequential Exclusion,” MIS Review, Vol. 7, December 1997, pp. 45-85.
     [15] Chao, D.Y, “Linear Algebra Based Verification of Well-Behaved Properties and S-invariants of Petri Nets Synthesized Using Knitting Technique,” MIS Review, Vol. 5, December 1995, pp. 27-48.
     [16] Chao, D.Y., “Petri Net Synthesis and Synchronization Using Knitting Technique,” Journal of Information Science and Engineering, Vol. 18, No. 5, 1999.
     [17] Chao, D.Y., “The Algorithm for Checking Liveness in Synchronized Choice Net,” (invited) Proc. 1999 IEEE Int’l Conf. SMC, Beijing, China, July 5-9, 1999.
     [18] Chao, D.Y., “The Algorithm for Synchronized Choice Net Detection,” Proceedings of 1999 Workshop on Distributed System Technologies & Applications, Tainan, Taiwan, May 13-14, 1999, pp. 276-284.
     [19] Chao, D.Y, “X-Window Implementation of an Algorithm to Synthesize Ordinary Petri Nets,” Journal of National Cheng-Chi University, Vol. 73, Oct, 1996, pp.451-496.
     [20] Chao, D.Y. and D.T. Wang, “A Reduction Algorithm of Petri Net,” Proc. Int`l Comp Symp, Taichung, Taiwan, Dec. 1992, pp. 16-23.
     [21] Chao, D.Y. and D.T. Wang, “A Synthesis Technique for General Petri Nets,” Journal of Systems Integration, Vol.4, No.1, 1994, pp.67-102.
     [22] Chao, D.Y. and D.T. Wang, “An Interactive Tool for Design, Simulation, Verification, and Synthesis of Protocols,” Software Practice and Experience, an International Journal, Vol. 24, No. 8, August 1994, pp. 747-783 and to appear in Software Practice and Experience, an International Journal
     [23] Chao, D.Y. and D.T. Wang, “Knitting Technique and Structural Matrix for Deadlock Analysis and Synthesis of Petri Nets with Sequential Exclusion,” International Conference on System, Man, and Cybernetics, San Antonio, Texas, Oct. 1994, pp. 1332-1339.
     [24] Chao, D.Y. and D.T. Wang, “Knitting Technique with TP-PT Generations for Petri Net Synthesis,” invited paper, Proc. 1995 IEEE Int’l Conf. SMC, Vancouver, Canada, October 22-25, 1995, pp. 1454-1459.
     [25] Chao, D.Y. and D.T. Wang, “Petri Net Synthesis and Synchronization using Knitting Technique,” International Conference on System, Man, and Cybernetics, San Antonio, Texas, Oct. 1994, pp. 652-657.
     [26] Chao, D.Y. and D.T. Wang, “Synchronized Choice Ordinary Petri Nets,” invited paper, Proc. 1995 IEEE Int’l Conf. SMC, Vancouver, Canada, October 22-25, 1995, pp. 1442-1447.
     [27] Chao, D.Y. and D.T. Wang, “The Knitting Technique and its Application to Communication Protocol Synthesis,” MASCOTS ‘94, Durham, NC, pp. 234-238.
     [28] Chao, D.Y. and D.T. Wang, “Two Theoretical and Practical Aspects of Knitting Technique—Invariants and A New Class of Petri Net,” IEEE Transactions on System, Man, and Cybernetics, Vol. 27, No.6, 1997, pp.962-937.
     [29] Chao, D.Y. and D.T. Wang, “XPN-FMS: A Modeling and Simulation Software for FMS using Petri Nets and X-Window,” International Journal of Flexible Manufacturing Systems, Vol. 7, No. 4, October 1995, pp. 339-360.
     [30] Chao, D.Y. and Jau-Hung Tseng “Some Properties of Synchronized Choice Ordinary Petri Net,” Invited Session paper, 1999 IFAC, Beijing China, July 5-9, 1999, pp.193-197.
     [31] Chao, D.Y., J.H. Tseng, J.H. Tang, J.A. Nicdao, and Y.K. Chen, “The Algorithm for Checking Liveness in Synchronized Choice Nets,” IEEE Conference on Systems, Man, and Cybernetics ’99, Tokyo, Japan, October 12 – 15, 1999, p. 277.
     [32] Chao, D.Y., Jose A. Nicdao, Jih-Hsin Tang and Yi-Kung Chen, “Second Order Structures for Synchronized Choice Ordinary Petri Nets,” the Third World Multiconference on Systemics, Cybernetics and Informatics (SCI`99) and the Fifth International Conference on Information Systems Analysis and Synthesis (ISAS`99), Orlando, USA, July 31-August 4, 1999, Proceedings Volume 5 Computer Science and Engineering, pp. 336-343.
     [33] Chao, D.Y., M.C. Zhou, and D.T. Wang, “Extending Knitting Technique to Petri Net Synthesis of Automated Manufacturing Systems,” Computer Journal (British Computer Society), Oxford University Press, Vol. 37, No. 1-2, pp. 1-10.
     [34] Chen, Y., W.T. Tsai, and D.Y. Chao, “Dependency Analysis—A Compositional Technique for Building Large Petri Nets,” IEEE Transactions On Parallel and Distributed Systems, Vol.4, No.4, 1993, pp. 414-426.
     [35] Commoner, E., “Deadlocks in Petri Nets,” Applied Data Res. Inc., Wakefield, MA, 1972.
     [36] Datta, A., “Modular Synthesis of Deadlock-Free Control Structures,” Foundations of Software Technology and Theoretical Computer Science, Vol. 241, G. Goos and J. Hartmanis ed., 1986, Springer Verlag, pp. 288-318.
     [37] Datta, A. and S. Ghosh, “Synthesis of a Class of Deadlock-Free Petri Nets,” Journal of ACM, Vol. 31, No. 3, 1984, pp. 486-506.
     [38] Desel, J. and J. Esparza, Free Choice Petri Nets, Cambridge University Press, 1995.
     [39] DiCesare, F., G. Harhalakis, J.M. Proth, M. Silva, and F.B. Vernadat, Practice of Petri Nets in Manufacturing, Chapman & Hall, London, 1993.
     [40] Esparza, J. and M. Silva, “Circuits, Handles, Bridges, and Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1991, Springer Verlag, pp. 210-242.
     [41] Esparza, J. and M. Silva, “Top-Down Synthesis of Live and Bounded Choice Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1991, G. Rozenberg ed., Springer Verlag, pp. 118-139.
     [42] Ezpeleta, J., J.M. Colom, and J. Martinez, “A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 2, April 1995, pp. 173-184.
     [43] Hack, M.H.T. “Analysis of Production Schemata by Petri Nets,” Cambridge Mass, MIT, Dept. Electrical Engineering, MS Thesis (1972), corrected June 1974.
     [44] Jeng, M.D. and F. DiCesare, “A Modular Synthesis Techniques for Petri Nets,” Japan-USA Sym. on Flexible Automation, 1992, pp. 1163-1170.
     [45] Jeng, M.D. and F. DiCesare, “A Review of Synthesis Techniques for Petri Nets with Application to Automated Manufacturing Systems,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 1, January/February 1993, pp. 301-312.
     [46] Jeng, M.D. and F. DiCesare, “Synthesis Using Resource Control Nets for Modeling Shared-Resource Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 3, June 1993, pp. 317-327.
     [47] Kemper, P. and F. Bause, “An Efficient Polynomial-Time Algorithm to Decide Liveness and Boundedness of Free-Choice Nets,” Advances in Petri Nets, Lecture Notes in Computer Science, 1992, G. Rozenberg ed., Springer Verlag, pp. 263-278.
     [48] Koh, I. and F. DiCesare, “Transformation Methods for Generalized Petri Nets and their Applications in Flexible Manufacturing Systems,” IEEE Trans System, Man, and Cybernetics, Vol. 21(6), 1991, pp. 963-973.
     [49] Krogh, B.H. and C.L. Beck, “Synthesis of Place/Transition Net for Simulation and Control of Manufacturing System,” Proc. IFIP Symp. Large Scale Systems, Zurich, Aug. 1986.
     [50] Landweber, L.H. and E.L. Robertson, “Properties of Conflict-Free and Persistent Petri Nets," Journal Of ACM, Vol. 25, No 3, 1978, pp. 352-364.
     [51] Lautenbach, K. and H. Ridder, “Liveness in Bounded Petri Nets which are Covered by T-Invariants,” Application and Theory of Petri Nets, Zaragoza, Spain, June 1994, LNCS, No. 815, R. Valette ed., Springer-Verlag, 1994, pp. 358-378.
     [52] Lee, Dong-Ik, Sadatoshi Kumagai, and Shinzo Kodama, “Complete Structural Characterization of State Machine Allocatable Nets,” IEICE Transactions, Vol. E74, No. 10, pp.3115-3123, October 1991.
     [53] Lee, Dong-Ik, Sadatoshi Kumagai, and Shinzo Kodama, “Handles and Reachability Analysis of Free choice Nets,” Application and Theory of Petri Nets, LNCS, No. 935, Springer-Verlag, 1995, pp. 298-316.
     [54] Lee, K. H. and J. Favrel, “Hierarchical Reduction Method for Analysis and Decomposition of Petri Nets,” IEEE Trans. Systems, Man, and Cybernetics, SMC-15, 2, 1985, pp. 272-280.
     [55] Lien, Y.L., “Termination Properties of Generalized Petri Nets,” SIAM Journal On Computing, Vol. 5, No. 2, 1976.
     [56] Lipton, R.J., “The Reachability Problem Requires Exponential Space,” New Haven, CT, Yale University, Dept. of Computer Science, Res. Rep. 62, 1976.
     [57] Murata, T., “Circuit Theoretic Analysis and Synthesis of Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-24, No. 7, 1977, pp. 400-405.
     [58] Murata, T., “Petri Nets: Properties, Analysis and Applications,” IEEE Proceedings, Vol. 77, No. 4, April 1989, pp. 541-580.
     [59] Murata, T., “Synthesis of Decision-Free Concurrent Systems for Prescribed Resources and Performance,” IEEE Trans. Software Engineering, SE-6, NO. 6, pp. 525-530.
     [60] Murata, T. and J. Y. Koh, “Reduction and Expansion of Live and Safe Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-27, 1980, pp. 68-70.
     [61] Murata, T. and Z. Wu, ”Fair Relation and Modified Synchronic Distances in a Petri Net,” Journal of the Franklin Institute, Vol. 320, No. 2, August 1985, pp. 83-82.
     [62] Narahari, Y. and N. Viswanadham, “A Petri Net Approach to the Modeling and Analysis Manufacturing System,” Annals of Operations Research, Vol. 3, 1985, pp. 449-472.
     [63] Peterson, J.L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1981.
     [64] Pouyan, Ali Akbar, “A Computer-Based Petri Net Approach to Modeling Automated Manufacturing Systems,” Swinburne University of Technology, Australia, PhD Thesis, November 1997.
     [65] Ramamoorthy, C.V., S.T. Dong, and Y. Usuda, “The Implementation of an Automated Protocol Synthesizer (APS) and its Application to the X.21 Protocol,” IEEE Trans. on Software Engineering, No. 9, September 1985, pp. 886-908.
     [66] Ramamoorthy, C.V., Y. Yaw, and W.T. Tsai, “A Petri Net Reduction Algorithm for Protocol Analysis,” Computer Communication Review (USA), Vol. 16, No. 3, Aug. 1986, pp. 157-166.
     [67] Ramamoorthy, C.V., Y. Yaw, and W.T. Tsai, “Synthesis Rules for Cyclic Interactions Among Processes in Concurrent Systems,” Proc. COMPSAC, 1988, pp. 497-504.
     [68] Ramamoorthy, C.V., Y. Yaw, W.T. Tsai, R. Aggarwal, and J. Song, “Synthesis and Performance Evaluation of Two-Party Error-Recoverable Protocols,” COMSAC Symp., Oct. 1986, pp.214-220.
     [69] Ramamoorthy, C.V., Y. Yaw, W.T. Tsai, R. Aggarwal, and J. Song, “Synthesis of Two-Party Error Recoverable Protocols,” Computer Communication Review (USA), Vol. 16, No. 3, Aug. 1986, pp. 227-235.
     [70] Reisig, W., Petri Nets, EATCS Monographs on Theoretical Computer Science, Vol. 4, New York, Springer Verlag, 1985.
     [71] Savi, V.M. and X. Xie, “Liveness and Boundedness Analysis for Petri Nets with Event Graph Modules,” Advances in Petri Nets, Lecture Notes in Computer Science, G. Rozenberg ed., 1992, Springer Verlag, pp. 328-347.
     [72] Sifakis, J., “Structural Properties of Petri Nets,” Math. Fund. of Comp. Sci., Lecture Notes in Comp. Sci., Vol. 64, Springer Verlag, NY 1978, pp. 474-483
     [73] Suzuki, I., and T. Murata, “A Method for Hierarchically Representing Large Scale Petri Nets,” Proceedings, IEEE International Conference on Circuits and Computers, ICCC80, pp. 620-623.
     [74] Suzuki, I., and T. Murata, “A Method of Stepwise Refinement and Abstraction of Petri Nets,” Journal of Computer and System Sciences, Vol. 27, 1983, pp.51-76.
     [75] Teruel, E., P. Chrzastowski-Watchel, J.M. Colom, M. Silva, “On Weighted T-systems,” Research Report GISI-RR-92-04. Dpto. Ing. Electrica e Informatia, Universidad de Zaragoza, January, 1992 and in Application and Theory of Petri Nets, Lecture Notes In Computer Science, Jensen, K. ed., Springer-Verlag, 1992, pp. 348-367.
     [76] Valette, R., “Analysis of Petri Nets by Stepwise Refinement,” Journal of Computer & System Sciences, Vol. 18, 1979, pp.35-46.
     [77] Valvanis, K. S., “On the Hierarchical Analysis and Simulation of Flexible Manufacturing Systems with Extended Petri Nets,” IEEE Trans. of System, Man, and Cybernetics, SMC-20, 1, 1990, pp. 94-100.
     [78] Varpaaniemi, K., “On Stubborn Sets in the Verification of Linear Time Temporal Properties,” Application and Theory of Petri Nets, 19th International Conference ICATPN `98, Lisbon, Portugal, June 22-26 1998: proceedings, J. Desel and M. Silva eds., pp. 124-143.
     [79] Wang, D.T. and D.Y. Chao, “Enhanced Knitting Technique to Petri Net Synthesis,” Proc. 1994 IEEE Int`l Conf SMC, San Antonio, Texas, October 2-5, 1994, pp. 658-663.
     [80] Wang, D.T. and D.Y. Chao, “Extension of Knitting Technique to Petri Net Synthesis and Application to Flexible Manufacturing System Cell Preserving Well-Behaved Properties,” Research Report CIS-94-38, New Jersey Institute of Technology, July 1994.
     [81] Wang, D.T. and D.Y. Chao, “New Knitting Technique for Large Petri Net Synthesis with Automatic Preservation of Liveness, Boundedness and Reversibility,” Research Report CIS-94-41, New Jersey Institute of Technology, July 1994. Also in 1995 Proc. IEEE Int’l Conf SMC, Vancouver, Canada, October 22-25, 1995.
     [82] Yaw, Y., “Analysis and Synthesis of Distributed Systems and Protocols,” Ph.D. Dissertation, Dept. of EECS, U.C. Berkeley, 1987.
     [83] Yaw, Y. and F.L. Foun, “The Algorithm of a Synthesis Technique for Concurrent Systems,” 1989 IEEE Int. Workshop on Petri Nets and Performance Models, Dec. 1989, pp. 266-276.
     [84] Yaw, Y., C.V. Ramamoorthy, and W.T. Tsai, “A Synthesis Technique for Designing Concurrent Systems,” Proc. Second Parallel Processing Symposium, April 1988, pp. 143-166.
     [85] Zhou, M.C. and F. DiCesare, “Adaptive Design of Petri Net Controllers for Error Recovery in Automated Manufacturing Systems,” IEEE Trans. SMC, SMC-19, 5, 1989, pp. 963-973.
     [86] Zhou, M.C. and F. DiCesare, “Parallel and Sequential Mutual Exclusions for Petri Net Modelling of Manufacturing Systems with Shared Resources,” IEEE Transactions on Robotics and Automation, Vol. 7. No. 4, August 1991, pp. 515-527.
     [87] Zhou, M.C., F. DiCesare, and A.A. Desrochers, “A Hybrid Methodology for Petri Net Synthesis of Manufacturing Systems,” IEEE Trans. on Robotics and Automation, Vol. 8 No. 3, 1992, pp. 350-361.
     [88] Zhou, M.C., F. DiCesare, and D. Rudolph, “Design and Implementation of a Petri Net Based Supervisor for a Flexible Manufacturing System,” Automatica, Vol. 28, No. 6, 1992, pp. 1199-1208.
     [89] Zhou, M.C., K. McDermott, and A. Patel, “Petri Net Synthesis and Analysis of a Flexible Manufacturing Systems Cell,” IEEE Trans. SMC, Vol. 23, No.1, March 1993, pp. 524-531.		zh_TW