臺灣博碩士論文加值系統

派屈網路是現今對於並行系統的檢測和分析中,最受廣泛採用的模擬工具
之一.本篇論文提出一個改進過的派屈網路,稱做計時派屈網路.它可以藉
由操作系統中的計時器,在適當的時刻,對系統中的某些程序作執行順序上
的限制.它的表達能力可以涵蓋一般即時系統,不論是某一特定程序的執行
時間長短,或轉換發生時系統的時間組態,均可利用計時派屈網路的語法,
做簡潔而有效的描述.本篇論文的第二部份是對於計時派屈網路的可達性
問題,做複雜度的分析 .我們發現一般計時派屈網路的可達性問題仍是可
解的.對其一特殊階級,稱為無交談計時派屈網路,作詳細的路徑分析.

Petri nets are powerful modeling tools for concurrent systems.
However, the notion of time is absent in the original model of
Petri nets which makes it difficult to model real-time systems.
In this thesis, we propose an extended Petri net, called
clocked Petri nets, which incorporate the concept of time into
the syntax and semantics of Petri nets through the use of a
finite number of real-value clocks. Clocks, along with the
associated clock constraints, allow transitions in a Petri net
to fire in a more synchronous fashion. A computation of a
clocked Petri net is divided into two parts: the firing
sequence and the time sequence. What we are interested in this
research is the reachability problem, which is the problem of
deciding whether there exist a firing sequence and a time
sequence through which a certain token distribution can be met.
Our thesis contains two main parts. First, we present the model
of clocked Petri nets and demonstrate how they are used to
model real-time systems. Then, we thoroughly examine the
behavioral characteristics of clocked Petri nets to analyze the
reachability problem. We show that the reachability problem for
general clocked Petri nets is decidable. We also investigate a
restricted class of clocked Petri nets called alternating RQ
BPP-nets. As it turtns out, the reachability problem for such
Petri nets is NP-complete.