ペトリネット入門

太田淳

1995 年 4 月 18 日

1 離散事象システムとペトリネット

あるシステムの性質を解析したり、制御したりするには、対象とするシステムの性質に合ったモデルを用いることが有効である。例えば、線形時不変システムには、伝達関数や状態空間モデルなどが用いられている。

ペトリネット (Petri net) は「離散事象システム (discrete event system)」と呼ばれるシステムのためのモデルの一つである。

離散事象システムの一例として、電話を考えてみる。 A は受話器を上げてダイヤルする。そして B が出れば話をして電話を切る。出なければそのまま電話を切る。この様子を図 1(a) で表す。 A から電話がかかってくると、 B のベルが鳴る。 B が受話器をとれば、 A と話をして、電話を切る。その前に、 A が電話を切るかもしれない。この様子を図 1(b) で表す。

A:待機中 A が電話をかける呼出中 A が電話を切る通話中 A が電話を切る A:待機中 B が出る (a)  ^{B:待機中 A が電話をかける呼出ベル A が電話を切る通話中 B が電話を切る B:待機中 B が出る (b)}

図 1: 電話をかける

図中、は A または B の動作、は電話の状態を表す。

この「システム」の特徴をいくつか挙げてみる。まず、電話の状態は不連続である。例えば、ベルは鳴っているかいないかのいずれかであって、「15.4%鳴っている」ということはない。ベルが鳴っているとき、 A が電話を切らない限りは、 B はいつ電話に出てもよい。通話が終わった後 (とは限らない?)、 A と B はどちらが先に受話器を置いてもよい。次に述べるように、これらは離散事象システムを特徴づける性質である。

形式的には、離散事象システムとは、計量の入らない変数で表されるシステムである。離散事象システムにおける状態の遷移を「事象 (event) の生起」という。二つの状態 A と B の「中間の」状態は存在しないので、事象の生起は瞬時に起きる。離散事象システムには、通常の意味での「時計」は存在しない。事象の間に半順序関係 (順序が定義されていない組があってもよい点を除いて通常の「全順序」と同じものと考えてよい) が存在するのみである。この順序に反していなければ生起可能な事象はいつ生起してもよい (非同期性, asynchronousness) し、順序の定義されていない二つの事象は、どちらが先に生起してもよい (同時進行性, concurrency: Petri は相対性理論までもちだして説明している!)。

問題 1 離散事象システムの例を挙げよ。

2 ペトリネット

2.1 ペトリネットの定義

ペトリネットは、プレース (place)、トランジション (transition) という二種類のノード (node) をもつ二部有向グラフ (bipartite digraph) である。プレースは円で表されるノードであり、条件を表す。トランジションは棒または箱で表されるノードであり、事象を表す。これらを結ぶアーク (arc) は条件、事象の間の関係を表す。プレース、トランジション、アークがシステムの構造を表現する。アークには正整数の重みがつけられる場合がある。重みはアークの本数で表すか、アークに重みを併記して表す。重みがつけられないアークは重みが 1 であるとみなす。プレースの上には、非負整数個のトークン (token) が置かれる。トークンは点で表され、条件の成立を表す。プレース上のトークンの配置をマーキング (marking) といい、システムの状態を表す。

形式的には、ペトリネットは N = (P, T, F, W, m_{0}) で表される。

\{ \begin{matrix}P = \{p_{1}, p_{2}, ..., p_{|P|}\} & プレースの有限集合 (|P|; プレースの数) \\ T = \{t_{1}, t_{2}, ..., t_{|T |}\} & トランジションの有限集合 (|T |; トランジションの数) \\ F ⊆ (P × T) ∪ (T × P) & アークの集合 \\ W : F ↦ \{1, 2, ...\} & アークの重み \\ m_{0} : P ↦ \{0, 1, 2, ...\} & 初期マーキング \end{matrix}

マーキングはベクトルの形で、 m_{0} = [m_{0}(p_{1})m_{0}(p_{2}) ···m_{0}(p_{|P|})]^{T} のように表すこともできる。

トランジション t に向かうアークを t の入力アーク、 t の入力アークが出て行くもとのプレースを t の入力プレースという。 t から出て行くアークを出力アーク、 t の出力アークが入って行く先のプレースを t の出力プレースという。プレース p の入出力アーク、入出力トランジションもまた同様に定義する。

例 2.1 図 2 のペトリネットは、 P = {p_{1}, p_{2}, p_{3}, p_{4}} T = {t_{1}, t_{2}, t_{3}} F = {(p_{1},t_{1}), (p_{2},t_{1}), (p_{3},t_{2}), (p_{4},t_{2}), (p_{4},t_{3}), (t_{1},p_{3}), (t_{1},p_{4}), (t_{2},p_{2}), (t_{3},p_{1}), (t_{3},p_{4})} W ((p_{1},t_{1})) = 3, W ((p_{3},t_{2})) = 2, W ((p_{2},t_{1})) = ···= W ((t_{3},p_{4})) = 1 m_{0}(p_{1}) = 3, m_{0}(p_{2}) = 2, m_{0}(p_{3}) = 1, m_{0}(p_{4}) = 1 と表される。マーキングをベクトルの形で表すと、 m_{0} = [3211]^{T} となる。 t_{1} の入

p_{1}  p_{2} p_{3} p^{4} t_{1} t_{3}  t_{2} 3 図 2: ペトリネット

力プレースは {p_{1}p_{2}}、出力プレースは {p_{3}, p_{4}} である。 p_{1} の入力トランジションは {t_{3}}、出力トランジションは {t_{1}} である。

2.2 トランジションの発火

ペトリネットのマーキングはトランジションの発火 (firing) によって遷移する。トランジション t がマーキング m で発火可能 (fireable, enabled) であるとは、 t のすべての入力プレースが入力アークの重み以上の個数のトークンを持つことであり、 m[t⟩ で表す。発火可能なトランジションは発火してもしなくてもよい。発火可能なトランジション t が発火すると、各入力プレースから入力アークの重みの数だけのトークンを取り去り、各出力プレースに出力アークの重みの数だけのトークンを与える。この結果のマーキングを m′とすれば、 m[t⟩m′と表される。

例 2.2 図 2 のペトリネットで、 t_{1} と t_{3} は発火可能である。 t_{2} は p_{3} に入力アークの重み 2 以上のトークンがないので、発火可能ではない。 t_{1} が発火した結果のマーキングを m_{1} とすれば、 m_{1} = [0122]^{T} である。

2.3 同時進行と競合

マーキング m で 2 つのトランジション t、 t′が発火可能であるものとする。これらのトランジションが m から t、 t′の順にも、 t′、 t の順にも順次発火できるとき、 t と t′は同時発火可能 (simultaneously enabled) であるという。そうでないとき、 t と t′は競合 (conflict) の状態にあるという。

例 2.3 図 3 のペトリネットで、 t_{1}、 t_{2}、 t_{3} はともに発火可能である。 t_{1} と t_{3} は同時発火可能であるが、 t_{1} と t_{2}、 t_{2} と t_{3} は競合の関係にある。

t_{1}  t_{2}  t_{3} p_{1}  p_{2} 図 3: 同時進行と競合

問題 2 図 4 のペトリネットで、

1. 図のマーキング m_{0} から発火可能なトランジションはどれか。

2. m_{0} から発火可能なトランジションをそれぞれ発火させた結果のマーキングを示せ。

3. m_{0} で競合関係にあるトランジションはどれとどれか。

3 p_{1}  p_{2} p_{3}  p_{4} t_{1}  t_{2} t_{3}  t_{4} 図 4: ペトリネット

2.4 ペトリネットとモデル化

以下に、 3 つのモデル化の例を挙げる。ペトリネットのモデルとしての特徴にもふれる。

例 2.4 図 5 に簡単なジュースの自動販売機のモデルを示す。客は 110 円または 200 円を投入し、ボタンを押す。その結果、ジュースと釣り銭が出てくる。

‘= Y10’、 ‘= Y100’、 ‘button’ とラベルづけされたトランジションがそれぞれ、 10 円硬貨を投入する、 100 円硬貨を投入する、ボタンを押す動作を表す。 p_{1}、 p_{2} はそ

92 11  =Y10 =Y100  button =Y110 =Y200 juice  =Y10 p_{1}  p_{2}  p_{3} p_{4} t_{1}  t_{2}  t_{3} t_{4}  t_{5}

図 5: 自動販売機のモデル

れぞれ、投入された 10 円硬貨、 100 円硬貨をトークンとしてもつ。 t_{1}、 t_{2}、 t_{3} はそれぞれ、 10 円が 11 枚、 10 円が 1 枚と 100 円が 1 枚、 100 円が 2 枚投入されると発火可能となる。 p_{3} は十分な金額が投入されていて、ボタンを押せばジュースが出てくることを表している。このときボタンが押されると、 p_{4} にトークンが投入され、投入金額が 110 円か 200 円かによって、 t_{4} または t_{5} が発火する。 t_{4} が発火すればジュースのみが、 t_{5} が発火すればジュースと釣り銭 90 円が、 ‘juice’、 ‘= Y10’ のプレースに投入される。

例 2.5 図 6(a) は生産システムのモデルである。 2 種類の製品 1、 2 がそれぞれ機械 A、 B に加工されて完成する。 p_{a}、 p_{b} はそれぞれ、機械 A、 B が加工中でなく、使用可能であることを表す。 p_{is} (i = 1,2) は製品 i の加工準備ができていることを示す。 p_{ia}、 p_{ib} (i = 1,2) はそれぞれ、製品 i が機械 A、 B で加工中がであることを示す。 p_{it} (i = 1,2) は製品 i が機械 A のある場所から機械 B のある場所へ運ばれていることを示す。 p_{if} (i = 1,2) は製品 i の加工が終了したことを示す。 t_{ias}、 t_{ibs} (i = 1,2) はそれぞれ、製品 i の機械 A、 B による加工を開始することを表し、 t_{iaf} 、 t_{ibf} (i = 1,2) は加工の終了を表す。

ここで、機械 A と機械 B が離れた場所にあって、搬送車で運ばなければならないものとする。搬送車のモデルを (b) に示す。 t_{its}、 t_{itf} (i = 1,2) はそれぞれ、製品 i の搬送開始、終了を表す。 p_{va}、 p_{vb}はそれぞれ、搬送車が機械 A、 B の場所にあることを表す。 t_{mv}は搬送車が機械 B の場所から A の場所へ移動することを表す。

2 つのプレース p_{1t}、 p_{2t} を搬送車のモデル (b) で置き換えることによって、機械間の搬送を考慮したモデル (c) を得る。このように、あるペトリネットモデルの 1 つあるいは複数のプレースやトランジションを別のネットで置き換えることによって、より詳細なモデルを作ることができる。逆に、あるペトリネットの一部をより簡単なネットで置き換えることで、より抽象化されたモデルを得ることができる。

p_{a}  p_{b} p_{1s}  p_{1a}  p_{1t}  p_{1b}  p_{1f} t_{1as}  t_{1af}  t_{1bs}  t_{1bf} p_{2s}  p_{2a}  p_{2t}  p_{2b}  p_{2f} t_{2as}  t_{2af}  t_{2bs}  t_{2bf}  ^{p_{va}  p_{vb} t_{mv} p_{1t} p_{2t} t_{1ts}  t_{1tf} t_{2ts}  t_{2tf}}^{p_{a}  p_{b} p_{1s}  p_{1a}  p_{1t}  p_{1b}  p_{1f} t_{1as}  t_{1af}  t_{1ts}  t_{1tf}  t_{1bs}  t_{1bf} p_{2s}  p_{2a}  p_{2t}  p_{2b}  p_{2f} t_{2as}  t_{2af}  t_{2ts}  t_{2tf}  t_{2bs}  t_{2bf} p_{va}  p_{vb} t_{mv}} (a)  (b) (c) 図 6: 生産システムのモデル

例 2.6 図 7 にプリンタへの文字列の出力のモデルを示す。 (a) はコンピュータのプリンタ制御プログラム、 (b) はプリンタを表す。コンピュータはプリンタの BUSY 信号が偽 (0) になるのを待って、データを送信する。そして、データが有効であることを示すために、 STROBE 信号を送る。 STROBE 信号は負論理なので、まず、信号を立ち下げ (1 → 0)、所定の時間が経過した後、信号を立ち上げる (0 → 1)。

プリンタは STROBE 信号の立ち下がりでデータを取り込み、 BUSY 信号を真 (1) にする。そして、印字処理を行い、その終了後、 BUSY 信号を偽にする。

(a) と (b) のネットに共通のプレース\overline{BUSY}、 DATA とトランジション STROBE↓ をそれぞれ重ね合わせることによって、コンピュータで制御されたプリンタのモデルを得る。このように、複数のペトリネットのプレースやトランジションを重ね合わせて、結合システムのモデルを作ることができる。

問題 3 図 5 のモデルを、 50 円硬貨も受け付けるように修正せよ。

STROBE \overline{BUSY} DATA \overline{STROBE} READY    STRING         STROBE↓ SEND STROBE↑  ^{STROBE↓ \overline{BUSY}   PRINTING DATA         FINISH START}^{STROBE↓ STROBE\overline{BUSY}   PRINTING DATA \overline{STROBE} READY    STRING      SEND STROBE↑  FINISH START} (a)  (b) (c)

図 7: プリンタのモデル

3 ペトリネットの解析

3.1 挙動的解析

3.1.1 発火系列

ペトリネットのあるマーキング m とトランジションの列 w = t_{i_{1}}t_{i_{2}}··· t_{i_{r}} に対して、 m から w の各トランジションが順次発火可能であるとき、すなわち、 m[t_{i_{1}}⟩m_{1}, m_{1}[t_{i_{2}}⟩m_{2}, ..., m_{r−1} [t_{i_{r}}⟩ が成り立つとき、 w は m から可能な発火系列 (legal firing sequence) であるという。これを、 m[w⟩ と表す。その結果のマーキングが m′であるとき、 m[w⟩m′と書く。空列 ε (トランジションを 1 つも含まない「列」 ) に対して、 m[ε⟩m であるものとする。

3.1.2 可達集合

ペトリネット N の初期マーキング m_{0} から遷移可能なマーキング全体の集合を可達集合 (reachability set) といい、 R(N, m_{0}) と書く。形式的には、 R(N, m_{0}) = {m | ∃w ∈ T^{∗}; m_{0}[w⟩m}. ただし、 T^{∗} を空列も含むトランジションの列全体の集合とする。

例 3.1 図2のペトリネットの可達集合は、 R(N, m_{0}) = {[k+3211]^{T}, [k122]^{T}, [k033]^{T}, [k201]^{T}, [k112]^{T}, [k023]^{T}, [k102]^{T}, [k013]^{T} | k = 0,1,2,...} である (確かめてみよ)。

3.1.3 可達問題

ペトリネット N と目的マーキング m_{f} を与えたとき、 m_{0}[w⟩m_{f} となる発火系列 w が存在するかどうかを可達問題 (reachability problem) という。ペトリネットの制御としては、「発火可能なトランジションの発火を許可または禁止する」方法が一般的である。可達問題はこの制御方法による可制御性と解釈することができる。

3.1.4 活性

マーキング m から可達な任意のマーキング m′に対して、トランジション t が発火可能なマーキング m′′が m′から可達であるとき、 t は m で活性 (live) であるという。すべてのトランジションが初期マーキング m_{0} で活性であるとき、ペトリネット N は活性であるという。活性は定常動作の可能性に関係が深い。 3.1.5 有界性

自然数 k に対して、初期マーキングから可達な任意のマーキング m で m(p) ≤ k が成り立つとき、プレース p は k-有界 (k-bounded) であるという。 1-有界であることを特に安全 (safe) であるという。任意の自然数 G に対して m(p) > G なるマーキング m が可達であるとき、プレース p は非有界であるという。

すべてのプレースが k-有界であるとき、ペトリネット N が k-有界であるという。実システムのモデルは有界でなければならないし、とくに (2 値) 論理のモデル

は安全でなければならない。

問題 4 図 2 のペトリネットについて、以下の問いに答えよ。

1. 初期マーキング m_{0} から、 m_{f} = [0033]^{T} は可達であるか。もし、可達であれば、 m_{0}[w⟩m_{f} となる発火系列 w の 1 つを求めよ。

2. 各トランジションの活性を判定せよ。

3. 各プレースの有界性を判定せよ。

3.2 構造的解析

3.2.1 接続行列

ペトリネット N の入出力接続行列 (input/output incidence matrix) A^{−} = {a_{ij}^{−}}、 A^{+} = {a_{ij}^{+}} は以下に定義される |P| × |T | 行列である。

a_{ij}^{−} = \{ \begin{matrix}W ((p_{i},t_{j})) & if (p_{i},t_{j}) ∈ F \\ 0 & otherwise \end{matrix} a_{ij}^{+} = \{ \begin{matrix}W ((t_{j},p_{i})) & if (t_{j},p_{i}) ∈ F \\ 0 & otherwise \end{matrix}

また、 A = A^{+} − A^{−} を接続行列という。

例 3.2 図 2 のペトリネットの接続行列は以下のとおりである。

A^{−} = ( \begin{matrix}& t_{1} & t_{2} & t_{3} \\ p_{1} & 3 & 0 & 0 \\ p_{2} & 1 & 0 & 0 \\ p_{3} & 0 & 2 & 0 \\ p_{4} & 0 & 1 & 1 \end{matrix}) A^{+} = ( \begin{matrix}& t_{1} & t_{2} & t_{3} \\ p_{1} & 0 & 0 & 1 \\ p_{2} & 0 & 1 & 0 \\ p_{3} & 1 & 0 & 0 \\ p_{4} & 1 & 0 & 1 \end{matrix}) A = ( \begin{matrix}& t_{1} & t_{2} & t_{3} \\ p_{1} & −3 & 0 & 1 \\ p_{2} & −1 & 1 & 0 \\ p_{3} & 1 & −2 & 0 \\ p_{4} & 1 & −1 & 0 \end{matrix})

A には p_{4} と t_{3} の間の往復アーク (セルフループ, self-loop) が表現されていないことに注意する。

u_{j} = [0 ···0 1^{(j)} 0 ···0]^{T} を t_{j} に対する発火ベクトルという。マーキング m で t_{j} が発火可能であることは、 A^{−} u_{j} ≤ m と表される。 m[t_{j}⟩m′であるとき、 m′= m + Au_{j} である。マーキング m から発火可能な発火系列 w = t_{i_{1}}t_{i_{2}}··· t_{i_{r}} に対して、 x = ∑_{j=1}^{r} u_{i_{j}} とする。 w の発火の結果のマーキングを m′とすれば、 m′= m+Ax である。 x を w の発火回数ベクトル (firing count vector) という。

問題 5 方程式 m_{f} = m_{0}+Ax を用いれば、可達問題は容易に解くことができそうであるが、実際にはそうではない。その理由として、どんなことが考えられるか。

問題 6 図 8 のペトリネットの入出力接続行列 A^{−}, A^{+} 、および、接続行列 A を求めよ。また、 (入出力) 接続行列を用いてマーキング m_{0} = [0011]^{T} から、トランジション t_{1} が発火可能であることを示し、 w = t_{1}t_{4} の発火の結果のマーキングを求めよ。

p_{2}  p_{3} p_{4} p_{1} t_{2} t_{3}  t_{4} t_{1} 図 8: ペトリネット

3.2.2 T インバリアント

あるマーキング m から発火可能な空列でない発火系列 w の発火の結果のマーキングがふたたび m であるとする。 w の発火回数ベクトルを x とすれば、 m = m+Ax より、 Ax = 0 が成り立つ。方程式 Ax = 0 の非負整数解 x を T インバリアント (T-invariant) という。

3.2.3 S インバリアント

各プレース p_{j} に非負整数の重み y_{j} を考える。 y^{T}m はトークンの重み付き和である。もし、 y^{T}A = 0 が成り立つならば、 m_{0} から可達な任意のマーキング m に対して、 y^{T}m = y^{T}(m_{0}+ Ax) = y^{T}m_{0}+ (y^{T}A)x = y^{T}m_{0} より、重み付き和は不変である。方程式 A^{T}y = 0 の非負整数解 y を S インバリアント (S-invariant) あるいは、 P インバリアントという。

問題 7 図 8 のペトリネットの T インバリアント、 S インバリアントを求めよ。

4 ペトリネットのサブクラス

ペトリネットの構造に制約を加えたサブクラスが各種提案されている。ペトリネットの挙動的解析問題は一般的に解くことが難しいが、サブクラスによっては、ある種の問題が効率よく解ける場合がある。

4.1 マークグラフ

各プレースの入出力トランジションがちょうど 1 つずつであるペトリネットをマークグラフ (marked graph) という。マークグラフは競合を表すことができない。

4.2 状態機械

各トランジションのの入出力プレースがちょうど 1 つずつであるペトリネットを状態機械 (state machine) という。状態機械は同期を表すことができない。

4.3 自由選択ネット

プレース p からトランジション t へ向かうアークは、 p の唯一の出力アークである (図 9(a)) か、 t の唯一の入力アークである (図 9(b)) かのいずれかであるペトリネットを自由選択ネット (free choice net) という。自由選択ネットでは、共通の入力プレースをもつトランジションはすべてが発火可能であるか、すべてが発火可能でないかのいずれかである。

(a) (b) 図 9: 自由選択ネット

問題 8 図 10(a)(b)(c)(d) のネットは、マークグラフ、状態機械、自由選択ネット、その他のいずれであるか。

5 参考文献

1. J. L. Peterson 著、市川・小林訳、ペトリネット入門、共立出版 (1984) “Petri Net Theory and the Modeling of Systems (Prentice-Hall 1981)” の邦訳。

(a)  (b) (c)  (d) 図 10: サブクラス

2. W. Reisig 著、長谷川・高橋訳、ペトリネット理論入門、シュプリンガー・フェアラーク東京 (1988) “Petri Nets (Springer-Verlag 1985)” の邦訳。

3. 計測自動制御学会離散事象システム研究専門委員会編、ペトリネットとその応用、計測自動制御学会 (1992)

4. 村田忠夫、ペトリネットの解析と応用、近代科学社 (1992)

5. 椎塚久雄、実例ペトリネット、コロナ社 (1992)

A 問題略解

問題 1 例えば、コンピュータ、脳、通信プロトコル、列車の運行、訴訟、化学反応 (分子一つ一つに着目した場合) など。

問題 2 1. t_{1} と t_{3} と t_{4}

2. t_{1} の発火の結果は [1210]^{T}、 t_{3} の発火の結果は [2402]^{T}、 t_{4} の発火の結果は [3010]^{T}。

3. t_{1} と t_{4}

問題 3 例えば、図 11 のペトリネット。

問題 4

11 6  2 3  2 4  4 =Y110  =Y150  =Y200 juice  =Y10  =Y50 =Y10  =Y50  =Y100  button

図 11: 自動販売機のモデル 2

1. 可達である。 m_{0} から m_{f} に遷移する発火系列は、 t_{3}t_{3}t_{3}t_{1}t_{1}、 t_{3}t_{3}t_{1}t_{3}t_{1}、 t_{3}t_{1}t_{3}t_{3}t_{1}、 t_{1}t_{3}t_{3}t_{3}t_{1} のいずれか。

2. t_{1}、 t_{2} は活性でない。 m_{0} から可達なマーキング m_{d} = [0013]^{T} から可達なマーキングで t_{1}、 t_{2} が発火できるものは存在しない。 t_{3} は活性である。 p_{4} のマーキングはけっして 0 にならない。

3. p_{1} は非有界、 p_{2} は 2 有界、 p_{3}、 p_{4} は 3 有界である。

問題 5 発火可能のための条件が考慮されていないこと、発火回数ベクトルは発火の順序を考慮していないことによる。

問題 6 接続行列は以下のとおり。

A^{−} = [ \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{matrix} ] A^{+} = [ \begin{matrix}1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} ] A = [ \begin{matrix}1 & 0 & 0 & −1 \\ 1 & −1 & −1 & 0 \\ 0 & 1 & 1 & −1 \\ −1 & 0 & 0 & 1 \end{matrix} ]

t_{1} が発火可能であるための条件は、

A^{−} u_{1} = [ \begin{matrix}0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{matrix} ] [ \begin{matrix}1 \\ 0 \\ 0 \\ 0 \end{matrix} ] = [ \begin{matrix}0 \\ 0 \\ 0 \\ 1 \end{matrix} ] ≤ [ \begin{matrix}0 \\ 0 \\ 1 \\ 1 \end{matrix} ] (= m_{0})

より、満足されている。 w = t_{1}t_{4} の発火の結果のマーキングを m とすれば、

m = m_{0}+ A(u_{1}+ u_{4}) = [ \begin{matrix}0 \\ 0 \\ 1 \\ 1 \end{matrix} ] + [ \begin{matrix}1 & 0 & 0 & −1 \\ 1 & −1 & −1 & 0 \\ 0 & 1 & 1 & −1 \\ −1 & 0 & 0 & 1 \end{matrix} ] [ \begin{matrix}1 \\ 0 \\ 0 \\ 1 \end{matrix} ]

= [ \begin{matrix}0 \\ 0 \\ 1 \\ 1 \end{matrix} ] + [ \begin{matrix}0 \\ 1 \\ −1 \\ 0 \end{matrix} ]

= [ \begin{matrix}0 \\ 1 \\ 0 \\ 1 \end{matrix} ]

問題 7 x_{1} = [1101]^{T}、 x_{2} = [1011]^{T} として、 T インバリアントは、 x = a_{1}x_{1}+ a_{2}x_{2} (a_{1} ≥ 0, a_{2} ≥ 0) で表される任意のベクトル。 y_{1} = [1001]^{T}、 y_{2} = [0111]^{T} として、 S インバリアントは、 y = b_{1}y_{1}+ b_{2}y_{2} (b_{1} ≥ 0, b_{2} ≥ 0) で表される任意のベクトル。

問題 8 (a) マークグラフ (自由選択ネットでもある)、 (b) マークグラフ、状態機械、自由選択ネットのいずれでもない、 (c) 自由選択ネット、 (d) 状態機械 (自由選択ネットでもある)