政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/53434
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113392/144379 (79%)
Visitors : 51212022      Online Users : 909
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


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


    Title: 擴大多項式Reachability 問題的網的種類
    Other Titles: Enlarging Classes of Nets of Polynomial Reachability Problem
    Authors: 趙玉
    Contributors: 政治大學資訊管理系
    行政院國家科學委員會
    Keywords: 派翠網;可達性;活的;分解
    Petri nets reachability live decomposition
    Date: 2006
    Issue Date: 2012-08-30 15:49:16 (UTC+8)
    Abstract: 我們在以分解技術及多項式時間複雜性解決實際例子如FMS 的可達性(Reachability) 問 題上，是該領域的先趨。為了鞏固我們在此領域的領先地位，本計劃透過把多項式結 果延伸到更錯綜複雜的種類。 可達性問題的NP-問題的基本原因以前未被研究過。 因 為第一個階層架構在任何SNC 裡是對稱的，我們提議這與非對稱的第一個階層架構有 關(AFOS)。 我們叫這樣類型的派翠(Petri)網為艱難的普通派翠網(OPN)。 我們提議研 究其可達性問題可以被多項式時間複雜性解決的艱難的OPN 的子類。 對於這樣的派 翠網，為了多項式的結果存在門檻標記，這是因為Petri 網(PN)的行為不僅倚賴派翠網 圖的表架構， 而且倚賴在最初網的標記上。 我們提議找到這樣的門檻標記， 顯示， 可達性問題的艱難起源於為一般的PN(GPN) 的艱難可達性問題，這是因為他們經常可 以變為GPN。 我們提議藉著把他們轉變成簡單GPN 以更進一步簡化那些簡單的艱難 OPN 可達性的問題。 因此我們提議為以前從未被研究的簡單的GPN 研究可達性問 題。 更進一步，我們提議把分解原則用於稍微地偏離SNC 的無界的Petri 網的可達性 分析。 這與被修改的Reachability 樹(MRT)相比較，有避開架構可達性圖方面的優勢。
    We pioneered the decomposition technique to solve Reachability problem with polynomial time complexity for real life classes of nets such as FMS. We propose to consolidate our leading position by extending the polynomial results to more complicated classes of nets. The basic cause of the NP-problem of the Reachability problem has not been studied before. We propose that it is related to asymmetric first order structures (AFOS) since the first order structures in any SNC are symmetric. We call such nets hard ordinary Petri nets (OPN). We propose to study subclasses of hard OPN whose Reachability problem can be solved with polynomial time complexity. We propose that for such nets, there exist threshold markings for polynomial results since the behavior of a Petri net (PN) depends not only on the graphical structure, but also on the initial marking of the net. We propose to find such threshold markings and show that hardness of Reachability problem originates from the hard problem for general PN (GPN) since they often can be converted into GPN. We propose to further simplify the Reachability problem for simple hard OPN by converting them into simple GPN. Hence we propose to study the Reachability problem for simple GPN which has never been studied before. Further, we propose to apply the decomposition principle to reachability analysis to unbounded Petri nets slightly perturbed from SNC. This has the advantage of avoiding building reachability graph compared with the modified Reachability Trees (MRT) approach.
    Relation: 基礎研究
    學術補助
    研究期間:9508 ~ 9607
    研究經費:271仟元
    Data Type: report
    Appears in Collections:[Department of MIS] NSC Projects

    Files in This Item:

    File SizeFormat
    952416H014.pdf213KbAdobe PDF2687View/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