| dc.contributor | 政治大學資訊管理系 | en_US |
| dc.contributor | 行政院國家科學委員會 | en_US |
| dc.creator (作者) | 趙玉 | zh_TW |
| dc.date (日期) | 2006 | en_US |
| dc.date.accessioned | 30-Aug-2012 15:49:16 (UTC+8) | - |
| dc.date.available | 30-Aug-2012 15:49:16 (UTC+8) | - |
| dc.date.issued (上傳時間) | 30-Aug-2012 15:49:16 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/53434 | - |
| dc.description.abstract (摘要) | 我們在以分解技術及多項式時間複雜性解決實際例子如FMS 的可達性(Reachability) 問 題上，是該領域的先趨。為了鞏固我們在此領域的領先地位，本計劃透過把多項式結 果延伸到更錯綜複雜的種類。 可達性問題的NP-問題的基本原因以前未被研究過。 因 為第一個階層架構在任何SNC 裡是對稱的，我們提議這與非對稱的第一個階層架構有 關(AFOS)。 我們叫這樣類型的派翠(Petri)網為艱難的普通派翠網(OPN)。 我們提議研 究其可達性問題可以被多項式時間複雜性解決的艱難的OPN 的子類。 對於這樣的派 翠網，為了多項式的結果存在門檻標記，這是因為Petri 網(PN)的行為不僅倚賴派翠網 圖的表架構， 而且倚賴在最初網的標記上。 我們提議找到這樣的門檻標記， 顯示， 可達性問題的艱難起源於為一般的PN(GPN) 的艱難可達性問題，這是因為他們經常可 以變為GPN。 我們提議藉著把他們轉變成簡單GPN 以更進一步簡化那些簡單的艱難 OPN 可達性的問題。 因此我們提議為以前從未被研究的簡單的GPN 研究可達性問 題。 更進一步，我們提議把分解原則用於稍微地偏離SNC 的無界的Petri 網的可達性 分析。 這與被修改的Reachability 樹(MRT)相比較，有避開架構可達性圖方面的優勢。 | en_US |
| dc.description.abstract (摘要) | 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. | en_US |
| dc.language.iso | en_US | - |
| dc.relation (關聯) | 基礎研究 | en_US |
| dc.relation (關聯) | 學術補助 | en_US |
| dc.relation (關聯) | 研究期間:9508 ~ 9607 | en_US |
| dc.relation (關聯) | 研究經費:271仟元 | en_US |
| dc.subject (關鍵詞) | 派翠網;可達性;活的;分解 | en_US |
| dc.subject (關鍵詞) | Petri nets reachability live decomposition | en_US |
| dc.title (題名) | 擴大多項式Reachability 問題的網的種類 | zh_TW |
| dc.title.alternative (其他題名) | Enlarging Classes of Nets of Polynomial Reachability Problem | en_US |
| dc.type (資料類型) | report | en |
