政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/83318
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文笔数/总笔数 : 113393/144380 (79%)
造访人次 : 51240948      在线人数 : 910
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧：
  • 您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果
  • 若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据
    •  进阶搜寻
    政大機構典藏 > 商學院 > 資訊管理學系 > 學位論文 >  Item 140.119/83318


    请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/83318


    题名: 派翠網路的基本架構
    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
    上传时间: 2016-03-31 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
    显示于类别:[資訊管理學系] 學位論文

    文件中的档案:

    档案 大小格式浏览次数
    index.html0KbHTML2277检视/开启


    在政大典藏中所有的数据项都受到原著作权保护.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈