数理解析研究所講究録1020 巻 1997 年 160-164160

ペトリネットによる離散事象プロセスめ表現
大阪大学 工学部 電気工学科
熊谷貞俊

1

はじめに離散事象の並行・非同期的生起とそれによるシステム状態の (非時間的あるいは時制的) 発展を表す図的モデルであるペトリネットの理論と応用については例えば [1] や [2] に詳しい。 ここでは、 本来非決定的選択を含む離散事象モデルにおいて、 ある動作規範 (制御) のもとでの事象生起列の 1 つの実現 (これをプロセスと呼ぶ) を表現するオカレンスネットと並行動作を表す半順序から導かれる鎖 (li\vdash 反鎖 (co) の 2 つの相似関係 (similarity relation) について述べ、有界なオカレンスネット (プロセス) が鎖–反鎖について稠密であることを示す。

2オカレンスネット

図 1 に表わせるような離散事象システム (パイプライン処理を表す) に対し、から実現可能な–連の並列プロセスを表
その初期マーキング$\{\mathrm{p}_{1}, \mathrm{P}_{2’ 34}\mathrm{P}_{\mathrm{t}}, \mathrm{p}’\}$す図 2 のようなアサイクリックなネットをそのオカレンスネットと呼ぶ。 オカレンスネットでは並行発火可能なトランジション$\mathrm{t}1$,$\mathrm{t}3$や$\mathrm{t}‘ l$,$\mathrm{t}4$が明示的に表せる。 また、 各ブレースの入出力枝はそれぞれ 1 本以下である。 (ブレースでの枝分岐、枝合流が存在しない) さらに、 オカレンスネットでは各ブレースに存在できるトークンの数は高々 1 個である。 $-(\text{これをセーフなネットと呼ぶ})$

図1

図2

161

オカレンスネ-ットでのマーキング (トークンの存在するブレース集合を意味する) は、 常にもとのシステムで実現される状態 (これをケースと呼ぶ) に対応し、 任意のケースに対し、 それを入力状態としてもつ並行発火可能なトランジションの集合 (これをステップと呼ぶ) が対応する。 つまり

図 1 のようにペトリネットで表せる離散事象システムでのプロセスは、 対応するオカレンスネ$\dot{\text{、}}$

ットでのケースとステップの連鎖で表現されることになる。 当然 1 つのステッ

プ内のトランジションをどのような順序で発火させてもその結果得られるケースは唯– に定まる。 (これが並列発火可能の定義である。)$(\mathrm{t}1||\mathrm{t}2||\ldots||\mathrm{t}\mathrm{m})$図3
図 3 のケース$\mathrm{C}1$:で並行発火可能なトランジション$\mathrm{t}1$,$\mathrm{t}_{2}$で発火することに対応してケース Cl からケ $-$ ス C2 に至る. :.
$\mathrm{m}|$を任意の順序通りのパス (パス$\mathrm{t}_{\mathrm{m}}$個の各点は、 すべて並行発火の途中に現れるケースに対応する)が考えられるが、 いずれもケース C2 に至るという意味で途中に関心がなければ無視できるケースの集合である。
上の3$(2 \mathrm{r}\llcorner-2)$鎖–反鎖関係(ブレースまたはトランオカレンスネットの任意の 2 つの節点ジション) の間に有向枝または有向路 (a から への) が存在するときと定義するとアサイクリックなネットにおいて関係 $<$ は半順序 (反射的、推移的、反対称的) を定義する。 この半順序から導ける関係 li とをそれぞれ$\mathrm{b}(\mathrm{a}\neq \mathrm{b})$$\mathrm{a}\cdot,$$\mathrm{a}<\mathrm{b}$$\mathrm{b}$$\mathrm{C}\mathrm{O}$

alia$\Leftrightarrow$$\mathrm{b}$く》$\mathrm{c}\mathrm{o}\mathrm{b}$$\mathrm{a}=\mathrm{b}\vee \mathrm{a}<\mathrm{b}\vee \mathrm{b}<\mathrm{a}$$\mathrm{a}=\mathrm{b}\vee\neg(\mathrm{a} 1\mathrm{i}\mathrm{b})$は相似関係 (反射的、対称的) である。 の極大完全部分集
合 (任意の 2 元が li の関係にある極大部分集合) を鎖、 co の極大完全部分集合と定義する。

$1\mathrm{i},$$1\mathrm{i}$$\mathrm{c}\mathrm{o}$を反橋と呼ぶ。 2 節で述べたケースはプレースのみから成る反町に対応する。

並行プロセスはある時点におけるシステム状態のスナップショットに対応する
反鎖 (ケース) と時相的に順序づけられる鎖 (線形順序的な事象列) の 2 つの162異なった観点からの部分集合に分割できる。任意の鎖と反鎖は定義より 2 つ以上の元を共有することはないが、 任意の鎖と反響が常に唯 1 つの元を共有する
稠密 (k-dense) であると呼ばれる。現実の問題で妥当な仮定であるオカレンスネットの有界性 (ケーニッヒの定理の意味で、 すな
とき、 並行プロセスは$\mathrm{k}-$わち、 (1) ソースノードが有限 (2) 各ノードでの分岐が有限 (3) 有向路の長さが有限)
セスは$\mathrm{k}-$を仮定すれば、 任意のオカレンスネットで表現される並行プロ稠密であることが示せる。矛盾法による証明の概略は以下の通りである。今ある反鎖と鎖 1 について 1$\mathrm{c}$$\cap \mathrm{c}=\phi$とする。

図4

オカレンスネットの極小元集合、 極大元集合をそれぞれ X,$= \oint,$$1$

および a’$\mathrm{b},$$\mathrm{a}’\text{、}\mathrm{c}$$\mathrm{a},$上に元$\mathrm{b},$$\mathrm{b}$とすると、 1’ が存在して a$\cap \mathrm{X}$$<\mathrm{b}$’。

$>\mathrm{b}$このようならばしたがって] 上に元$\cap \mathrm{Y}=\phi$$\mathrm{Y}$$\mathrm{a}$. ’ のそれぞれ最大元、 最小元を$\mathrm{b}’\in \mathrm{c}$

したがって

’

$\mathrm{a}$が存在して$\mathrm{a}_{\max}<\mathrm{a}_{\min}’ 0$すなわち 1 上の元$\mathrm{a}_{\max}$,$\mathrm{b}’<$$\mathrm{a}_{\min}’<\mathrm{a}_{\mathrm{n}\iota \mathrm{a}\mathrm{x}}<\mathrm{b}$定義より’$\mathrm{a}_{\min}$$\mathrm{a}_{\mathrm{n}\iota \mathrm{a}\mathrm{x}},$$\mathrm{a}_{\min}$とする。

となり$\mathrm{c}$$\mathrm{a}_{\min}’<\mathrm{a}_{\max}$

なの反鎖性に矛盾。
’が存在してよりそれぞれ分岐枝、 合流枝が存在することになり、$\mathrm{b},$$\mathrm{b}’\in \mathrm{c}$$\mathrm{a}_{\max}<\mathrm{b},$$\mathrm{a}_{\min}’>\mathrm{b}$’はそれぞれトランジションでなければオカレンスネットの定義よりならない。 ペトリネットでは枝はブレースとトランジションとの間にしか存在となるブレースしないから、 したがってが存在し、$\mathrm{a}_{\max},$$\mathrm{a}_{\min}$$\mathrm{a}_{\max}<\mathrm{P}<$は$\mathrm{c}$の任意の元と$\mathrm{k}-$$\mathrm{c}\mathrm{o}$’$\mathrm{a}_{\min}$関係となるがこれは$\mathrm{c}$$\mathrm{P}\in 1$$\mathrm{P}$の極大性に矛盾する。

稠密性は、 並行プロセスにおける任意の時点でのスナップショット中に時制的な因果性をもつすべての事象列の各 1 個の代表が現れていることを意味する。 このことは、 プロセスを適当なケース (反鎖) で分離したり、. 結合したり出来ること、 すなわち、 要素プロセスへのあるケースでの分割や、 要素プロセスの極大、 極小ケースでの複合による合成が可能であることを意味する。
見自明のような性質であるが、 非有界なオカレンスネットや構造的にオカレ163

ンスネットの性質を満たさない –般のアサイクリックネットではい例が簡単に作れる。例えば図 5 のアサイクリックネットで反転$1= \oint$$\mathrm{c}$$\mathrm{k}-$稠密でなと鎖 1 は$\mathrm{c}\wedge$である。
$|\mathrm{P}_{1},$$\mathrm{c}=$

$1=$

(

$\mathrm{P}_{2},$$\mathrm{p}_{4}\}$$\mathrm{t}2$,$\mathrm{p}_{3}\}$

凶屋

4.

,

時間と同期

ペトリネットなどに代表される離散事象システムでは、 通常のダイナミカルシステムにおけるようなユニバーサルな時間の概念は存在しない。 逆に、 このような単– クロックを前提にしない並行事象の発展過程に離散事象システムの特徴があると言える。 -方、 生産システムや計算機システムなどでのスループット性能向上といった現実問題では経過時間に関する定量的評価が必要となる。
非同期システムでの時間概念の定式化は、 局所時間 (クロック) の導入により、様々な仕様に対して異なった方法で定義されている。例えば、 MAX-PLUS 代数
で定式化される同期の概念は列車の待ち合わせのような先発プロセスの後発プロセス待ちの仕様 (共通イベント の生起可能時間間隔 It の MAX で を発火)を満足する時間概念であり、 -方、 Interrupt 仕様では It の MIN で を発火させる定式化が必要となる。 (MAX-PLUS 代数では表現できない仕様である。)It$\mathfrak{c}$$\mathrm{t}$$\mathrm{t}$のいずれの時刻でも生起可能 (これを AND 仕様あるいは FUZZY 仕様と呼ぶ)とする定式化も考えられる。 [3] 最近、 デッドライン仕様 (各ブレースでの局所クロックの進め方として、 そのブレースの出力枝に定義されたデッドラインまで–様に進め、 それを越えると緊急状態 (Urgent) としてクロックを止めるように定める)をもつ時間的ペトリネットが提案 [4] されているが、現実問題の同期仕様の多様性を反映した様々な定式化が可能となる。

5.

おわりに

本稿では、 離散事象システムでの並行プロセス表現とペトリネットの関係について簡単な紹介を行い、 また同期仕様における時間の取り扱い方について述べた。 鎖–反鎖といった論理的な並行概念と同期時間概念を統–するより深化した考察が必要である。

164

参考文献
[1] 熊谷薦田 :「ペトリネットによる離散事象システム論」,

コロナ社, 1995$\not\in 1\ovalbox{\tt\small REJECT}$Nets: Properties, Analysis and Applications”, Proc. of theIEEE, Vol. 77, No. 4, pp.541-580, April 1989
[3] T. Murata: “Temporal Uncertainty and Fuzzy-Timing High-Level Petri Nets”,
Proc. of 17th International Conference on Application and Theory of PetriNets, Osaka, Lecture Notes in Computer Science 1091, Springer, pp. 11-28,

[2]T.

”

$\mathrm{M}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{a}:$$\mathrm{P}\mathrm{e}\mathrm{t}\mathrm{r}\mathrm{i}$1996[4] J. Sifakis: “On the Composition of Timed Systems”, Proc. of 18thInternational Conference on Application and Theory of Petri Nets, Toulouse,
Lecture Notes in Computer Science 1248, pp21-22, 1997