政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/85394
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113160/144130 (79%)
Visitors : 50755419      Online Users : 732
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version
    政大典藏 > College of Commerce > Department of MIS > Theses >  Item 140.119/85394


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/85394


    Title: 應用同步選擇網路在派翠網路之分析
    Application of SNC (Synchronized choice net) to analysis Petri nets
    Authors: 巫亮宏
    Contributors: 趙玉
    巫亮宏
    Keywords: Petri Nets
    Lautenback`s Marking Condition (MC)
    Liveness
    Business Workflow Specifications
    Concurrent Systems
    Parallel Systems
    Flexible Manufacturing Systems
    Date: 2001
    Issue Date: 2016-04-18 16:27:45 (UTC+8)
    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.
    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.
    Description: 碩士
    國立政治大學
    資訊管理學系
    87356013
    Source URI: http://thesis.lib.nccu.edu.tw/record/#A2002001611
    Data Type: thesis
    Appears in Collections:[Department of MIS] Theses

    Files in This Item:

    File SizeFormat
    index.html0KbHTML2237View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 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 ©   - Feedback