學術產出-Theses
Article View/Open
Publication Export
-
題名 應用同步選擇網路在派翠網路之分析
Application of SNC (Synchronized choice net) to analysis Petri nets作者 巫亮宏 貢獻者 趙玉
巫亮宏關鍵詞 Petri Nets
Lautenback`s Marking Condition (MC)
Liveness
Business Workflow Specifications
Concurrent Systems
Parallel Systems
Flexible Manufacturing Systems日期 2001 上傳時間 18-Apr-2016 16:27:45 (UTC+8) 摘要 Well-behaved SNC covers well-behaved and various classes of FC (free-choice) and is not included in AC (asymmetric choice). An SNC allows internal choices and concurrency and hence is powerful for irodeling. Any SNC is bounded and its liveness conditions are simple. An integrated algorithm, has been presented for verification of a net being SNC and its liveness with polynomial time complexity. Scholars often need to verify properties on nets appearing in literatures. Verification by CAD tool is less desirable than that by hand due to the extra efforts to input the model aid learn to use the tool. We propose to manually search the maximum SNC component followed by locating bad siphons in an incremental manner. We then apply Lautenback`s Maridng Condition (MC) for liveness to berify the property of liveness. But there are two drawbacks associated with the above MC. First, it guarantees only deadlock-freeness, and not necessary liveness. We have identified the structure cause for this and developed its livess conditions correspondingly. Second a net may be live even if the MC is not satisfied. We have identified the structure cause for this. The MC has been readjusted based on our proposed new theorey. 參考文獻 [1] Chao, D.Y., “A CAD Tool for Constructing Large Petri Nets,” revised for IEEE Trans. SMC. [2] 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. [3] 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. [4] 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. [5] D.Y. Chao and Jose A. Nicdao,”Liveness for Synchronized Choice Petri Nets,” Computer Journal (British Computer Society), Vol. 44, No. 1, 2001, pp. 124-136. [6] D.Y. Chao and Jose A. Nicdao, “Extended Synchronized Choice Nets,” Workshop on Algorithms and Theory of Computation, ICS2000, December 6-8, pp. 123-130. [7] 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. [8] 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. [9] 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. [10] Desel, J. and J. Esparza, Free Choice Petri Nets, Cambridge University Press, 1995. [11] Dong-Ik Lee, Sadatoshi Kumagai and Shinzo Kodama, “Complete Structural Characterization of State Machine Allocatable Nets,” IEICE Transactions, Vol. E74, No. 10, pp.3115-3123, October 1991. [12] Dong-Ik Lee, Sadatoshi Kumagai and Shinzo Kodama, “Handles and Reachability Analysis of Free choice Nets,” In Application and Theory of Petri Nets, LNCS, No. 935, Springer-Verlag, pp.298-316, 1995. [13] 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. [14] 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. [15] Jeng, M.D. and F. DiCesare, “A Modular Synthesis Techniques for Petri Nets,” Japan-USA Sym. on Flexible Automation, 1992, pp. 1163-1170. [16] 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. [17] M. D. Jeng, F. Dicesare, “Synthesis Using Resource Control Nets for Modeling Shared-Resource Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 2 April 1995, pp. 317-327. [18] Murata, T., “Circuit Theoretic Analysis and Synthesis of Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-24, No. 7, 1977, pp. 400-405. [19] Murata, T., “Petri Nets: Properties, Analysis and Applications,” IEEE Proceedings, Vol. 77, No. 4, April 1989, pp. 541-580. [20] 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. [21] Peterson, J.L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1981. [22] R. J. Lipton, “The reachability problem requires exponential space,” New Haven, CT, Yale University, Dept. of Computer Science, Res. Rep. 62, 1976. [23] Chu, F.; Xie, X.-L., “Deadlock analysis of Petri nets using siphons and mathematical programming,” IEEE Trans. on Robotics and Automation, Vol. 13, No. 6, 1997, pp. 793-804. 描述 碩士
國立政治大學
資訊管理學系
87356013資料來源 http://thesis.lib.nccu.edu.tw/record/#A2002001611 資料類型 thesis dc.contributor.advisor 趙玉 zh_TW dc.contributor.author (Authors) 巫亮宏 zh_TW dc.creator (作者) 巫亮宏 zh_TW dc.date (日期) 2001 en_US dc.date.accessioned 18-Apr-2016 16:27:45 (UTC+8) - dc.date.available 18-Apr-2016 16:27:45 (UTC+8) - dc.date.issued (上傳時間) 18-Apr-2016 16:27:45 (UTC+8) - dc.identifier (Other Identifiers) A2002001611 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/85394 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊管理學系 zh_TW dc.description (描述) 87356013 zh_TW dc.description.abstract (摘要) Well-behaved SNC covers well-behaved and various classes of FC (free-choice) and is not included in AC (asymmetric choice). An SNC allows internal choices and concurrency and hence is powerful for irodeling. Any SNC is bounded and its liveness conditions are simple. An integrated algorithm, has been presented for verification of a net being SNC and its liveness with polynomial time complexity. Scholars often need to verify properties on nets appearing in literatures. Verification by CAD tool is less desirable than that by hand due to the extra efforts to input the model aid learn to use the tool. We propose to manually search the maximum SNC component followed by locating bad siphons in an incremental manner. We then apply Lautenback`s Maridng Condition (MC) for liveness to berify the property of liveness. But there are two drawbacks associated with the above MC. First, it guarantees only deadlock-freeness, and not necessary liveness. We have identified the structure cause for this and developed its livess conditions correspondingly. Second a net may be live even if the MC is not satisfied. We have identified the structure cause for this. The MC has been readjusted based on our proposed new theorey. en_US dc.description.tableofcontents 封面頁 證明書 論文摘要 目錄 表目錄 圖目錄 Chapter 1 INTRODUCTION 1.1 Background 1.2 Motive 1.3 Scope 1.4 Model Chapter2 FUNDAMENTALS OF PETRI NETS 2.1 Overview 2.2 Properity 2.3 Subclasses of Petri nets 2.4 Token-free siphon and commoner`s property Chapter3 SNC 3.1 Overview 3.2 Handles, Bridges, First and second order structures 3.3 Inconsistent pair and liveness conditions 3.4 P-components and two types of minimal siphons 3.5 Formal Theorem of liveness condition Chpater4 MARKING CONDITIONS FOR LIVES AND THE ASSOCIATED NEW CLASSES OF PETRI NETS 4.1 Manual searching for minimal siphons 4.2 Marking condition for liveness 4.3 Improved marking condition for liveness Chapter5 CONCLUSION BIBLIOGRAPHY zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2002001611 en_US dc.subject (關鍵詞) Petri Nets en_US dc.subject (關鍵詞) Lautenback`s Marking Condition (MC) en_US dc.subject (關鍵詞) Liveness en_US dc.subject (關鍵詞) Business Workflow Specifications en_US dc.subject (關鍵詞) Concurrent Systems en_US dc.subject (關鍵詞) Parallel Systems en_US dc.subject (關鍵詞) Flexible Manufacturing Systems en_US dc.title (題名) 應用同步選擇網路在派翠網路之分析 zh_TW dc.title (題名) Application of SNC (Synchronized choice net) to analysis Petri nets en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Chao, D.Y., “A CAD Tool for Constructing Large Petri Nets,” revised for IEEE Trans. SMC. [2] 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. [3] 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. [4] 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. [5] D.Y. Chao and Jose A. Nicdao,”Liveness for Synchronized Choice Petri Nets,” Computer Journal (British Computer Society), Vol. 44, No. 1, 2001, pp. 124-136. [6] D.Y. Chao and Jose A. Nicdao, “Extended Synchronized Choice Nets,” Workshop on Algorithms and Theory of Computation, ICS2000, December 6-8, pp. 123-130. [7] 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. [8] 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. [9] 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. [10] Desel, J. and J. Esparza, Free Choice Petri Nets, Cambridge University Press, 1995. [11] Dong-Ik Lee, Sadatoshi Kumagai and Shinzo Kodama, “Complete Structural Characterization of State Machine Allocatable Nets,” IEICE Transactions, Vol. E74, No. 10, pp.3115-3123, October 1991. [12] Dong-Ik Lee, Sadatoshi Kumagai and Shinzo Kodama, “Handles and Reachability Analysis of Free choice Nets,” In Application and Theory of Petri Nets, LNCS, No. 935, Springer-Verlag, pp.298-316, 1995. [13] 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. [14] 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. [15] Jeng, M.D. and F. DiCesare, “A Modular Synthesis Techniques for Petri Nets,” Japan-USA Sym. on Flexible Automation, 1992, pp. 1163-1170. [16] 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. [17] M. D. Jeng, F. Dicesare, “Synthesis Using Resource Control Nets for Modeling Shared-Resource Systems,” IEEE Transactions on Robotics and Automation, Vol. 11, No. 2 April 1995, pp. 317-327. [18] Murata, T., “Circuit Theoretic Analysis and Synthesis of Marked Graphs,” IEEE Trans. Circ. and Sys., CAS-24, No. 7, 1977, pp. 400-405. [19] Murata, T., “Petri Nets: Properties, Analysis and Applications,” IEEE Proceedings, Vol. 77, No. 4, April 1989, pp. 541-580. [20] 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. [21] Peterson, J.L., Petri Net Theory and the Modeling of Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1981. [22] R. J. Lipton, “The reachability problem requires exponential space,” New Haven, CT, Yale University, Dept. of Computer Science, Res. Rep. 62, 1976. [23] Chu, F.; Xie, X.-L., “Deadlock analysis of Petri nets using siphons and mathematical programming,” IEEE Trans. on Robotics and Automation, Vol. 13, No. 6, 1997, pp. 793-804. zh_TW
