数理解析研究所講究録
910 巻 1995 年 108-122

108

ペトリネッ トとその言語について
山崎

秀記(Hideki YAMASAKI)
橋大学
〒 186

1

数学共同研究室
国立市 中 2–1

前書き

ペトリネット (Petri net) は、非同期的かつ平行的なシステムにおける情報の流れや制御を記述し解析するための数学的モデルである. 1962 年に Petriによって提案されていらい [5], 広範囲に応用され, 深く研究されてきた.
本論文では, 特にペトリネットの言語理論的な側面に焦点をあてて, 論ずる. これはペトリネットでモデル化したシステムにおいて起こりうる動作
列全体を, そのペトリネットの生成する言語として捉えようとするものである. その結果, 従来のオートマトンによって定義される言語族とはかなり異なる性質を持つ言語族がえられる.
2 節で基本的定義を述べたあと, 3 節ではペトリネットで生成される有限の長さの語の集合 (ペトリネット言語) の族について, 4 節ではペトリネットで生成される無限の長さの語の集合 (ペトリネット \mbox{\boldmath $\omega$}言語) の族について
調べる.

2

基本的定義

整数の集合 $\{0,1,- 1,2,- 2, \ldots\}$ を Z で, 自然数 (非負整数) の集合 {0,1,2,}
で X から $Y$ への関数全体{f $|f$ : $Xarrow Y$ }を N で表す 集合 X と に対し,を表す. 特に $X$ が有限集合 $X=\{x_{1}, x_{2}, \ldots, x_{n}\}$ のとき, 関数
を$f(x_{2}),$$f(x_{n})$$-$上の次元ベクトル (f(xl),) と同 視する. また, 関数$\ldots$$\mathrm{Y}$$Y^{X}$$f\in \mathrm{Z}^{X}$$\mathrm{Z}$$n$$f,$ $g\in \mathrm{Z}^{X}$$\cdots,$と$z\in \mathrm{Z}$に対し, 和 $f+g$ ,常の成分毎の定義で与える.

$F\subseteq \mathrm{Z}^{X}$

スカラー倍 $zf$ , 部分順序 $f\leq g$ を通に対し, $F$ の元より大きなベク トの$\mathrm{K}\mathrm{s}$109

集合を\uparrow F で表す.
$\uparrow F=$$\Sigma$を$\text{ア}\mathrm{K}\mathrm{s}${ $m’|$ ある $m\in F$ が存在して $m’\geq m$ }.

ファベットとする. \Sigma 上の有限の長さの語の全体を \Sigma *で表し, 空
また, \Sigma 上の無限の長さの語の集合を \Sigma 0 で表す. すなわち,列を\mbox{\boldmath $\lambda$}で表す.

$\Sigma^{\omega}=\{a_{\iota^{a}}2\ldots|a_{1}, a_{2}, \cdots\in\Sigma\}$.

に対し, \alpha の $n$ 番目の文字をで表す. 任意のに対し, u\alpha で の後ろに を連接してえられるの語を表わす. \alpha =u\beta のとき,は\alpha の接頭語であるといい,と書く.
ペトリネット $N$ は $N=(P,$ $T,$ $A,$の 4 つ組で与えられる. ここで,$P$ はブレース(place) の有限集合, $T$ は遷移 (transition) の有限集合, $A$ :は-ノ\check -- $f$ 関数,
は初期マ一キング, である. 各遷
移 に対し, $A(t)=\{A(t),$ $A(t)\rangle$ で割り当てられる –対の関数 (ベクト )$\alpha=a_{1}a_{2}\cdots\in\Sigma\omega$$a_{n}$$u\in\Sigma^{*}$と$\alpha\in\Sigma^{*}(\Sigma\omega)$$u$$\alpha(n)$$\alpha$$\Sigma^{*}(\Sigma\omega)$$u$$u\subseteq\alpha$$m_{0)}$$Tarrow \mathrm{N}^{P}\mathrm{x}\mathrm{N}^{P}$$m_{0}\in \mathrm{N}^{P}$$t$$\mathrm{K}\mathrm{L}’$$A(i),$$A(t)$をそれぞれ$t$の入カベクトル, 出カベクトルという.

例 1 $N=(\{p_{1},p_{2},p_{3}\}, \{t_{1},t_{23}, t\}, A, \langle 1,1,0\rangle)$ とする.

ただし,

$A(t_{1})=\{\langle 1,0,1\rangle, \langle 1,1, \mathrm{o})), A(t_{2})=\mathrm{t}\langle 1,1,0\rangle, (0,0,1\}\},$ $A(t_{3})=(\langle \mathrm{o}, 1,0),$$\{0,0,2\rangle\rangle$

である.

を表し,

このときペトリネット $N$ は以下のように図示される.
$|$

アークが,

で遷移を表す. そして, ブレース
$t$

$P$

$\mathrm{O}\text{でプ_{レ}-}$ス

から遷移 $t\text{には}.A(\gamma)(p)$ 本のから $p$ には $A(t)(p)$ 本のアークが引かれる.

初期マーキングは各ブレースに置かれた. (トークンという) で表される. すなわち, 各プレ一
ス

$p$

には,

最初,

$m_{0}(p)$個のトークンが置かれる.

一般に
クンの配置
をペトリネット $N$ のマーキングという.
マーキングはペトリネッ トの状態を示すもので, マーキング $m$ において, 各
ブレース
は $m(p)$ 個のクンを持つ. 遷移 O くマーキング $m$ で発火可能$\mathrm{k}-$$p$$m\in \mathrm{N}^{P}$$\mathrm{t}\cdot-$

,

110

であるというのは $m\geq A(t)$ のときで,
果マーキングを

このときは $m$ で発火してその結$t$$m’=m-A(t)+A(t)$.

$m’$ と書く.
または
直観的に言うと遷移 の発に変える. このことを
火は A(t)(P) 個のトークンを各ブレースから取り去り, $A(t)(p)$ 個のトークンを各ブレース に分配する.
上の定義や記法は遷移の有限および無限列に拡張される. すなわち,$m[t\rangle$$m[t\rangle$

$t$

$P$

$P$

$m[t_{1}\rangle m\iota[t_{2}\rangle m_{2}\ldots mn-1[t\rangle nm’$のとき $m[t_{1}t_{2\cdots n}t$ },と書き,$m[t_{1}t_{2\cdots n}t\rangle$ $m’$$m[t_{1})m_{1}[t_{2}\rangle m_{2}\ldots$のとき$m[t_{\iota 2}t\ldots\rangle$と書く.

どの遷移も発火可能でないようなマーキングをデッドロックという.
例 2 例 1 のペトリネット $N$ において, 初期\tau 一キングで発火可能なとを発火するとマーキングは $(0,0,1)$ となり, これ以
遷移はt, である.
上どの遷移も発火可能でない (デッドロック).
初期マーキングで を発火すると, つづいて が発火可能になり,$\langle 1, 1, 0\rangle$$t_{2}$$t_{2}$$t_{3}$$t_{1}$$\langle 1, 1, \mathrm{o}\rangle[t3\rangle\langle 1, \mathrm{o}, 2\rangle[t_{1}\rangle \mathrm{t}1,1,1\rangle$

ここで (1, 1,となる.

$0\rangle$$<\langle 1,1,1\rangle$

であるから,$t_{3}t_{1}$は初期マーキングから繰り返し発火可能であることがわかる.
さて,いくつか具体的な問題に対するペトリネットの例をあげよう.

例 3 生産者消費者問題 : ある生産物の生産者と消費者の関係を表すペトリ
ネットである. 生産者は生産物をバッファに貯めていき, 消費者はバッファにある生産物を消費していく.
$N=(\{p_{1}, \cdots,p_{\epsilon}\}, \{t_{1}, \cdots,i_{4}\}, A, (0,1,1,0,0))$

ここで,$A(t_{1})=\{\langle 1,0,0,$$\mathrm{o},$$\mathrm{o}),$,$\langle 0,1,0, \mathrm{o}, 1)), A(t_{2})=(\langle 0,1,0,0,0\rangle, \langle 1,0,0,0,0\rangle\rangle$$A(t_{\epsilon})=\langle\langle 0,0,1,0,1\rangle, \{0,0,0,1,0\rangle\rangle,$$A(t_{4})=\langle\langle 0,0,0,1, \mathrm{o}\rangle, \langle 0,0,1, \mathrm{o}, 0\rangle\rangle$

であ

111

る.

ブレース

$p_{2}$を表し, 遷移中のトークンは生産者を,

ブレース

は生産の終了と開始を, 遷移$p_{3}$

中のトークンは消費者

は消費の開始と終了を表す. ブレース Ps がバッファで, その中のトークンが生産物に対応する. ’ このペトリネットでは生産者が生産した以上のものを消費することはできない
状況をモデル化していることに注意しよう.
$t_{1},$$t_{2}$$t_{3},$ $t_{4}$例 4 読み書き問題は, データを共有する読み出しや書き込みをどう制御するかという問題である. 読み出しプロセスはデータを変更しないので他の読み
出しプロセスと共存可能であるが, 書き込みプロセスは他のプロセスを (読み出しも書き込みも) すべて排除しなければならない. 以下のペトリネッ ト
では, 同時に可能な読み出しプロセスの最大数が個までという制限がつい
$n$

ている.
$N=(\{p_{1},p2,p_{3}\}, \{t_{1}, \cdots, t_{4}\})A,$ $\langle 0,0, n\rangle)$

ここで,$A(t_{1})=\langle\langle 0,0,1),$ $\langle 1,0,0\rangle)_{;}A(t_{2})=\langle\langle 1,0,0\rangle, \langle 0,0,1\rangle\rangle,$$\langle\langle 0,0, n\rangle, \langle 0,1,0\}\rangle_{l}A(t_{4})=(\langle 0,1,0\rangle, \langle 0,0, n\rangle\rangle$.

$A(t_{3})=$

この例では同時に可能な読み出しプロセスの上限が であるが, この上限がない場合, ペトリネットではモデル化できないことが知られている. これは, ペトリネットにおける発火条件が $m\geq A(t)$ という形をしていて, 「あるブレース中にトークンが存在しないときに発火可能になる」 といった条件を表わすことができないため
$n$

112

中のトークン (読み出しプロセス) がないこである (上の例ではブレースに $n$ 個のトークンがあることで間接的に判定している).
とを, ブレース
一般に, ペトリネットに, トークン数が であることを判定できる機能を付$p\iota$$p_{3}$$0$

け加えると,

3

チ $=-$ リング機械と同等の能力を持つことが知られている.

[9]

ペトリネット言語

ペトリネット言語を考えるさいには, その遷移にラベルをつけた, ラベルつきペトリネットを考え, 受理マーキングの集合を指定するのが–般的である.

上のラベル付きペトリネット $N$ は $N=(P, T, A, m_{0}, e, F)$ の 6 つ組で与, はペトリネットと同じで,えられる. ここで, $P,$ $T,$ $A,$:はラベル関数,はマーキングの有限集合, である. 以後, ラベル付
きペトリネットを単にペトリネットと呼ぶ.
われわれはペトリネット $N$ の振るまい, すなわち $N$ が生成する言語を,$\Sigma$$e$$m_{0}$$Tarrow\Sigma\cup\{\lambda\}$$F\subset \mathrm{N}^{P}$

受理マーキングに到達するような発火列全体のラベル関数による準同型写像の像{$e(v)|m_{0}[v\rangle m$

かっ $m$ は受理マーキング}で与える. そして, ラベル関数に対する制限と受理マーキングの与え方によって様々なペトリネット言語が定義される.
実際, ラベル関数として次の 3 タイプが研究されている.

, は異なる遷移はすべて異なる動作に対応するという考え方を反映したものである. これを自由な (free) ラベル付け

1. 1 対 1 写像,$e:Tarrow\Sigma$という

2. \mbox{\boldmath $\lambda$}なし写像,$e$:$Tarrow\Sigma$, は同– の動作が異なる環境のもとで起こりうることからそれらは異なる遷移でモデル化できるとの考え方を反映している.

3. 一般の写像,$e:Tarrow\Sigma\cup\{\lambda\}$, では, 空列によるラベル付けを許す.

こ

れはモデル化の過程でシステムの具体的動作には対応しないような遷移を導入ししてしまうこともあるとの立場から, そのような遷移には空列のラベルを付けることを許す考え方である.
また, 受理いる.

$\text{マ}$一キング (受理状態) の定め方では次の 4 タイプが研究されて

113

1.

$\mathrm{P}$型: 条件なし, マーキング全体,$P(N)=\{e(u)|u\in T^{*}, m_{0}[u\rangle\}$

これは,

2.

すべての発火可能な遷移列を受理する.

型 : デッドロック全体,$T(N)=$ { $e(u)|u\in T^{*},$ $m0[u\rangle m$ かつ $m$ はデッドロック}
これは, デッドロック (どの遷移も発火可能でない状態) に到達する$\mathrm{T}$遷移列を受理する.

3.

$\mathrm{L}$型: 有限集合 F で指定されたマーキング,$L(N)=\{e(u)|u\in T^{*}, m_{0[u\rangle m}\in F\}$

これは指定されたマーキングに正確に到達するような遷移列だけを受理
型のペトリネット言語のクラスは豊富でかつ強力であるが, このする.
ような受理条件を設けることは, ペトリネットの基本原理「m’ $\geq m[u\rangle$ な
らば型が」 に反するというおそれもある. このことから, 次の定義される.
$\mathrm{L}$$m’[u\rangle$$\mathrm{G}$4. G 型 :F で指定されたマーキングより大きなマーキング全体,$G(N)=\{e(u)|u\in T^{*}, m_{0[u\}m}\in\uparrow F\}$

例 5 $N=(\{p_{1}, \ldots,p_{5}\},$$A,$$\{t_{1}, \ldots, t\epsilon\},$( $1,0,$$\mathrm{o},$$\mathrm{o},$

$1\}$

,

$e,$

$\{(0,0,1,0,0\rangle\})$

とする.

ただし,
$A(t_{1})=\langle\langle 1,0,0,0, \mathrm{o}\rangle, (0,1, \mathrm{o}, 0, \mathrm{o}\rangle\rangle,$$A(t_{2})=\langle\langle 1,0,0,0,0\rangle,$ $\langle 1,0,0,1,0)\rangle$,$A(t_{3})=\langle(0,1,0,0,0), (0,0,1, \mathrm{o}, \mathrm{o}\rangle\rangle,$$A(t_{4})=(\mathrm{t}0,1,0,1,0),$,$A(t_{5})=\langle\langle 0,0,1, \mathrm{o}, 1), (0,0,1, \mathrm{o}, 0\rangle)$,$e(t_{1})=e(t_{2})=a,$ $e(t_{3})=e(\{_{4})=b,$ $e(t_{f})=C$ である.

$p_{\mathrm{I}}$このとき,$\langle 0,1, \mathrm{o}, \mathrm{o}, 1\rangle\rangle$

114$P(N)=\{u|u\subseteq a^{k}\iota m1\leq C^{n},n\leq m\leq k\}$$T(N)=G(N)=\{a\iota^{m}kc^{n}|1\leq n\leq m\leq k\}$
$L(N)=\{ab^{n_{C}}nn|1\leq n\}$となる.

ラベル関数の 3 タイプと受理マーキングの 4 タイプの組み合わせ

結局,で都合 12 タイプのペトリネット言語族についてその包含関係や言語演算のもとでの閉包性が調べられている. 包含関係については, 次のような結果が知られている. [9]1 対 1 ラベル関数$\mathrm{P}_{f}$$\subset$$\cap$\mbox{\boldmath $\lambda$}なしラベル関数$\mathrm{P}$$\subset$$\mathrm{P}_{\lambda}$$\mathrm{L}_{f}$$\cap$$\cap$$\mathrm{G}$$\subset$$\subset$$\mathrm{G}_{\lambda}$$\mathrm{L}$$\mathrm{T}_{f}$$\cap$$\subset$nl$\cap|$$\cap|$

一般のラベル関数$\mathrm{G}_{f}$$\subseteq$$\mathrm{L}_{\lambda}$$\mathrm{T}$$\mathrm{r}\iota$$=$$\mathrm{T}_{\lambda}$

方, 種々の言語演算のもとでの閉包性に付いては, 次のような結果が知られている.
$\cup$

ここで,は集合和, 寡は集合積,$\mathrm{C}$は補集合を表し,. は連接 : $A\cdot B=$ { $xy|x\in A$ かつ $y\in B$ },$\triangle$

はシャッフル演算 : $A\triangle B=\{x_{1}y1^{X}2y2\ldots Xynn|$$x_{\iota},$$\mathrm{R}$$\cdots,$ $x_{n},$$y1,$$\cdots,$$y_{n}\in\Sigma^{*},$$x1x_{2n}\ldots x\in A,$ $y1,$ $y2,$ $\cdots,$ $yn\in B\}$は逆転 : $A^{\mathrm{R}}=\{a_{n}\cdots a_{2}a_{1}|a_{1}, \cdots, a_{n}\in\Sigma, a1a2\ldots a_{n}\in A\}$ である.

$\cup \cap \mathrm{C} .
$\mathrm{L}_{\lambda}=\mathrm{T}_{\lambda}$$\mathrm{G}_{\lambda}, \mathrm{P}_{\lambda}$$\mathrm{L}$$\mathrm{G}, \mathrm{P}$$\mathrm{T}$$\mathrm{L}_{f}, \mathrm{G}_{f}, \mathrm{T}_{f}, \mathrm{P}_{j}$\triangle \mathrm{R}$$\mathrm{O}\mathrm{O} \cross \mathrm{O}\mathrm{O}\mathrm{O}$$\mathrm{O}\mathrm{O} \cross \mathrm{O}\mathrm{O} \cross$$\mathrm{O}\mathrm{O} \mathrm{O}\mathrm{O}\mathrm{O}$$\mathrm{O}\mathrm{O} \cross \mathrm{O}\mathrm{O} \cross$$\cross \mathrm{O} \cross \mathrm{O}\mathrm{O}\mathrm{O}$$\cross \mathrm{O} \cross \cross \cross \cross$

115

型ペトリネッ
上の結果を全部ここで証明することはできないが, 以下,を例に上げて, 閉包性やチョムスキー階層との比較を簡単
ト言語のクラスに議論しよう.
$\mathrm{L}$$\mathrm{L}$は正規言語の族を真に含み, 文脈依存言語族には真に含まれる.
定理 1
た, 文脈自由言語族とは比較不能である.
$\mathrm{L}$ま証明. ペトリネットが決定性有限オートマトンを模倣できることは明かである. 実際, ペトリネットのブレースを有限オートマトンの状態に対応させ,からの入力アークと有限オートマトンの遷移\mbox{\boldmath $\delta$}(p, ) $=q$ に対応して,
$a$

$q$ へ

$P$

の出力アークを 1 本ずつ持つペトリネットの遷移を構成する. オートマトンの現在の状態は, 対応するブレースが 1 個のトークンを持つマーキングで表は正規言語の族を含む.
わされる. したがって,$\mathrm{L}$方, 例 5 にあるように $\{a^{n}b^{n}cn|n\geq 1\}\in \mathrm{L}$ なので,は正規言語族を真に含み, 文脈自由言語族には含まれない.
に含まれないこここで, $|\Sigma|=k>1$ のとき, $I\mathrm{f}=\{ww^{R}|w\in\Sigma^{*}\}$ が$N$
が If を生成するためには, r 回の発火の後型ペトリネッ トとを示そう.
$\mathrm{L}$$\mathrm{L}$$\mathrm{L}$に到達可能なマーキングの個数がを個存在しなければならない. ところが,
到達可能マーキングは各遷移の発火回数によって–意に定まるので, r 回の発火の後の到達可能マーキングの総数は高々, r を $m$ 個 ( $m$ はペトリネット
N の遷移の個数) の自然数の和に分ける分け方の総数の多項式なので, 十分大きな r ではより小さい. よって,型ペトリネットで If を生成することは不可能である.
また上の議論から分かるように, 到達可能マーキングの集合は, 入力の長さの多項式で抑えられるので, 線形有界 $\neq>$ 一リング機械で模倣可能であ口る. よって,は文脈自由言語族に含まれる.
られる.

これは

$k^{r}$$r$$\mathrm{L}$$\mathrm{L}$が和および連接で閉じていることを示すために, ペトリネットの標準形を定義し, 任意のペトリネット $N$ に対し, $L(N)=L(N^{l})$ となる標
準形ペトリネット N’ を構成できることを示そう.
ペトリネット $N’=(P’, T’, A’, m’e0”, \{m_{f}^{i}\})$ が標準形であるというのは,次に,$\mathrm{L}$

1. 初期ブレース

P’ を持ち, 初期マーキング
レースに 1 個だけあるようなマーキングである$p_{\iota}\in$$m_{0}’$

はトークンが初期プ

116

2. 受理ブレース$PJ$\in P’ を持ち, 受理マーキングは受理ブレースにトーク

ンを 1 個だけ持つようなマーキング $m_{f}’1$ つだけである.

3.

$PJ$

にトークンがあるような任意のマーキングはデッドロックである.

$N=(P, T, A, m_{0}, e, F)$ を任意のペトリネットとする.

を標準形に変換す$P’=P\cup\{pS’
p_{r}, pJ\}$を付け加えに新しく 3 個のブレース$N$にトークンがあるときのみ,の各遷移が発火可能になるようにとする.
$N$ の各遷移 t\in T にへの出力アークを 1 本ずつ付けからの入力アークと
加える.
るために,

$N$

$N$

$p_{s},p_{r},pJ$$p_{r}$$p_{r}$$p_{r}$

次に,の初期マーキングで発火可能な遷移の集合を$N$ に新しく k 個の遷移畷, ... ,$mi$ とおく $(i=1, \ldots, k)$ .
$N$$\{t_{1,\text{。}}.

.

, tk\}$とし,を付け加える.
からの入力アークを 1 本と,の各ブレース への $m_{*}(p)$ 個の出
各 にはと同じラベルをつける.
カアークと p, への出力アーク 1 本を付け加え,
$N$
の働きは,
の初期マーキングで を発火させた後と同じ状態を $N’$ に作り出に移すことにある.
にあるトークンをし,$N$$m_{1}\in F$ に対し,
最後に, ペトリネットと同じラの各 $t\in T$ と $m,$
1
本と
, $N$
には
,
各
からの入力アークを追加する.
ベルを持つ遷移の各ブレース からの $m(p)$ 本の入力アークをを付け, Pf への出力アークを$m_{1}\in F$ となるとき,の働きは, $N$ においてに対応す
1 本付ける.
に対し,$m’f$ となるようにすることである.
る N’ のマーキング$m_{0}[t_{*}\rangle$$t_{:}’$$N$$p_{\iota}$$t_{k}’$$P$$t_{i}$$t’.\cdot$$t_{i}$$p_{r}$$p_{*}$$t$$m[t\rangle$$t_{m}$$t_{m}$$p_{r}$$P$$m[t\rangle$$t_{m}$$m_{1}’$

この結果,

定理 2
いる.

$\mathrm{L}$$m_{1}$$m’[t_{m}\rangle$

ペトリネット $N$ ほ標準形に変換される.

は集合和, 集合積, 連接,

シャッフル,

逆転の演算に関して閉じて117

を標準形ペトリネットとする. 連接 $L(N_{1})\cdot L(N_{2})$ を生成するの受理ブレースを同–視してえらの初期ブレースとペトリネットは,証明.

$N_{1},$ $N_{2}$$N_{1}$$N_{2}$

れる.
との初期ブレー
集合和 $L(N_{1})\cup L(N_{2})$ を受理するペトリネットは,との受理ブレースを同–視してえられる.
スを同–視し,を並べて,シャッフル $L(N_{1})\triangle L(N_{2})$ を受理するペトリネットは,$N_{1}$$N_{1}$$N_{2}$$N_{2}$$N_{1},$$N_{2}$

それぞれの初期ブレースに 1 個ずつトークンをおいたマーキングを初期マー
キングとすればよい. 受理マーキングはそれぞれの受理ブレースに 1 個ずつトークンがあるマーキングとする.
の各遷移の入力アークと出力を受理するペトリネットは,逆転
アークを交換し, さらに初期ブレースと受理ブレースを交換することによってえられる. 最後に, 集合論 $L(N_{1})\cap L(N_{2})$ を受理するペトリネットを構成とをとの直積ペトリネット $N$ を構成する. $N$ はするためには,同時平行的に模倣し, ともに, 受理マーキングに到達したとき, 入力を受理
口する. 詳しい構成は後の定理 5 の証明を参照して欲しい$L(N_{1})^{\mathrm{R}}$$N_{1}$$N_{1}$$N_{1}$$N_{2}$

表で抜けている箇所,

なお,$\mathrm{L}$$N_{2}$

が補集合演算で閉じているか否かは未解

決である.

4

ペトリネット$\omega$可語

ペトリネット 言語においては, \mbox{\boldmath $\lambda$}なしラベ 関数を考える. \mbox{\boldmath $\omega$}語の受理条件を考えるさいには, 有限の長さの語の場合めように, 最後に到達するマーキ
ングというものがないので, 最後の状態が受理マーキングか否かで判定する
わけにはいかない. そこで有限オートマトンのときと同様に, いくつかの受とする. ペトリネッ
理条件が考えられる. 受理マーキングの集合は 型のに対し
ト $N=(P, T, A, e, m_{0}, F)$ と$\omega$$\uparrow F$$\mathrm{G}$$\alpha\in T^{*}\cup T^{\omega}$$m_{0}[\alpha(1))m_{1}[\alpha(2)\}m_{2}\ldots$と定義する.
N で受理される次の 5 種類の\mbox{\boldmath $\omega$}言語を考える.

のとき,$N(\alpha)=m_{01}mm2\cdots$

特に受理条件を指定せず, すべての無限発火列を受理する場合,$L_{0}(N)=\{e(\alpha)|m_{0}[\alpha\rangle\}$

,

118

受理マーキングを通る発火列を受理する$L_{1}(N)=\mathrm{t}e(\alpha)|\underline{N(\alpha)}\cap\uparrow F\neq\emptyset\}$,

受理マーキングのみを通る発火列を受理する$L_{2}(N)=\{e.(\alpha)|\underline{N(\alpha)}\subseteq\uparrow F\}$,

受理マーキングを無限回通過する発火列を受理する$L_{3}(N)=\{e(\alpha)|\underline{N()}\cap-^{\alpha}\uparrow F\neq\emptyset\}$,

ある時点からさきはすべて受理マーキングである発火列を受理する$L_{4}(N)=\{e(\alpha)|\underline{N()}-^{\alpha}\subseteq\uparrow F\}$

さらに

{ $L:(N)|N$ は\Sigma 上のペトリネット} $(i=0, \ldots, 4)$$\mathrm{P}\dot{.}=$$[3, 4]$ では

.

を

$F$

$\uparrow F$の代わりに用いた$\mathrm{L}$と定義する.

型のペトリネッ ト \mbox{\boldmath $\omega$}言語が研究されている.

例 6 $N=(\{p\}, \{s, t\}, A, e, \langle 0\rangle, \langle 2\rangle\})$ とする.
$e(s)=a,$ $e(t)=^{\iota}$ である.
$A(t)=\langle\langle 1\rangle,$

ただし,$\langle 0)\rangle,$

このペトリネット $N$ に対し,
$L_{0}(N)=${$\alpha|$任意の$u\subset\alpha$$L_{1}(N)=L_{0}(N)-(ab)^{\omega}$$L_{2}(N)=\phi$に対して $\neq_{a}(u)\geq\#_{b}(u)$ },,,$L_{3}^{\cdot}(N)=L_{0}(N)-D(a\iota)\omega$,$L_{4}(N)=\{u|\# a(u)=\# b(u)+2\}L\mathrm{o}(N)\cap L_{0}(N)$,$A(s)=\langle\langle 0\rangle,$$\langle 1))$

,

119

ここで,

である

$\neq_{a}(u)$

は文字

$a$

の $u$ における出現回数を表し,$D$

は $\{a, b\}$上の Dyck 集合である.

は非決定性有限オートマトンで, 状態の有限集合 $Q$ ,入カアルファベット , 遷移関係\mbox{\boldmath $\delta$} $\subseteq Q\cross\Sigma\cross Q$ , 初期状態 , 受理状態
はの集合 $F$ からなるものとする. 任意の\alpha
$M$
$M$
のとき
,
のラ
に対して $p_{i}=q_{i+1}$のランと呼ばれる.
$q_{1}=s$ かつ任意のに対し, $M(\alpha)=q1q_{\mathit{2}}q_{s}..2$ とと定義する.
すると, ペトリネット同様, M で受理される次のような 5 種類の\mbox{\boldmath $\omega$}言語を定義できる$M=(Q, \Sigma, \delta, s, F)$$\Sigma$$s$$=\langle q_{1}, a_{1},p1\rangle\langle q_{\mathit{2}}, a_{\mathit{2}}, p2\rangle\ldots\in\delta^{\omega}$$i$$\Sigma(\alpha)=a_{1}a_{\mathit{2}}\ldots$$\text{ン}\alpha=\langle q_{\iota}, a1,p1\rangle\langle q\mathit{2}, a\mathit{2}, p\mathit{2}\rangle\ldots$$L_{0}(M)=${\Sigma (\alpha )|\alpha は $M$ のラン}, $L_{1}(M)=\{\Sigma(\alpha)|M(\alpha)\cap F\neq\phi\},$ $L_{2}(M)=$$\{\Sigma(\alpha)|\underline{M(\alpha)}\subseteq F\}$,

$L_{3}(M)=\{\Sigma(\alpha)|\underline{M(\alpha)}\cap F\neq\phi\},$さらに,$\mathrm{E}_{i}=$$L_{4}(M)=\{\Sigma(\alpha)|\underline{\underline{M(\alpha)}}\subseteq F\}$.

{ $L_{i}(M)|M$ は\Sigma 上の非決定性有限オートマトン} $(i=0, \ldots, 4)$と定義する
非決定性有限オートマトンで受理される\mbox{\boldmath $\omega$}言語の場合,

Eo$=\mathrm{E}_{2}\subset \mathrm{E}_{1}=$となることが知られている [6, 7, 11]. われわれは同様の結果をペトに対して示すリネッ ト \mbox{\boldmath $\omega$}言語のクラス
この節の証明のために, 発火列の\mbox{\boldmath $\omega$}言語で定義されるペトリネットの新しに対し,い受理条件を定義しよう. $N=(P, T, A, e, m0, \phi),$$\mathrm{E}_{4}\subset \mathrm{E}_{3}$$\mathrm{P}_{i}$$R\subseteq\tau^{\omega}$$L(N, R)=${$e(\alpha)|m_{0}[\alpha\rangle$

and$\alpha\in R$}と定義する.

定理 3 任意の $i=0,$
証明.
$N$

と

$M$

$4$
$\ldots,$

に対し$N=(P, T, A, e, m_{0}, \phi),$$\mathrm{P}_{i}=${ $L(N,$ $R)|N$ はペトリネット,$M=(Q, \Sigma, \delta, s, F)$の積オートマトン N’ を構成し,

$N$

と

$M$

$R\in \mathrm{E}_{i}$}.

とし, $L_{i}(M)=R$ とおく.

を同時平行的に模倣させれば,$L(N, R)=L(N, Li(M))=L\cdot(*)N’$ とできる.
$A,$$m_{0,)}F,$ $L=L_{i}(N)$ とする.
$N=(P,$
各 $t\in T$ と $m\in F$ に対し, 新$N$に付け加え,
をしい遷移と同じラベルを付ける. ここで,ある必要十分条件が $m_{1}\geq m$ かつ ml[tm m2 であるようにする. $m_{1}\geq m\in F$を意味するので,は と同じ働きをすると同時に, 現在のマーはキングがに属すか否かも検査できる.
$\tau,$$t_{m}$$e,$$t$$m_{1}[t_{m})m_{2}\text{で}$$\rangle$$m_{1}\in\uparrow F$$t_{m}$$t$$\uparrow F$$T_{F}=${ $t_{m}|t\in T$ かつ $m\in F$ } とすると, 明らかに

120

$L_{0}(N)=L(N’,\tau^{\omega}),$ $L_{1}(N)=L(N’,\tau*\tau F\tau^{\omega}),$ $L2(N)=L(N’, \tau_{F}^{\omega})$$L_{3}(N)=L(N’, (T^{*}TF)^{\omega}),$が成り立ち,
である.

定理 4$\tau^{\omega}\in \mathrm{E}_{0},$$L_{4}(N)=L(N’,$$\tau*\tau_{p}\tau\omega\in \mathrm{E}1,$,$T^{*\tau^{\omega})}F$$T^{\omega_{\in}}p2\mathrm{E},$$(T^{*}TF)^{\omega}\in \mathrm{E}_{3},$$T^{*}\tau^{\omega}\in \mathrm{E}_{4}F\square$$[6, 7]$$\mathrm{P}_{0}=\mathrm{p}_{2}\subset \mathrm{P}_{1}=\mathrm{P}_{4}\subset \mathrm{p}3$.

に対する結果よとなることは定理 3 と証明. PoP4$i=0,1,3$ を考える. これらのクラスの間の真のり明か. 以後, クラス
包含関係を導くために, 任意のペトリネット $N$ に対し, $L_{0}(N)$ は閉集合であとの位相的な性り, $L_{1}(N)$ は閉集合の加算和で表されるというクラス, (L\Sigma りをとった質を示す. ここで考えている位相は, 開集合として$=\mathrm{P}_{2}\subseteq \mathrm{P}_{1}=$$\subseteq \mathrm{P}_{3}$$\mathrm{E}_{*}$$\mathrm{P}_{:},$$\mathrm{p}_{0}$$\mathrm{P}_{1}$$L\Sigma\omega$. ものである.
$N=(P, T, A, e, m_{0}, F),$

{ $u|u$ ロ }$\alpha$が閉集合であることを示すために,$\subseteq\{u|u\subset\alpha\in L_{0}(N)\}$

を示そう.

とする.

$L_{0}(N)$の接頭語を生成する有限発火列の全体 $C=$ { $w|e(w)$ ロ かつ
} は無限集合になるの$\{u|u\subset\beta\}\subseteq
C$ が成り立つ.
が存在して,の補題により,で, K\"onig
かつ $e(\beta)=\alpha$ を意味するから,
である.
これはに対し, $N_{m}=(P, T, A, e, m, F)$ とする.
各$\alpha\in L_{0}(N)$$\alpha$$m_{0}[w\rangle$$\alpha$$\beta\in\tau^{\omega}$$m_{0}[\beta\rangle$$\alpha\in L$$m\in \mathrm{N}^{P}$$L_{1}(N)=\cup\{e(w)L_{0}(N_{m})|m_{0}[w\rangle m\in\uparrow F\}$であり,

これは閉集合の加算和である. この結果真の包含関係について,$\mathrm{p}_{0}\subset \mathrm{P}_{1}\subset \mathrm{P}_{3}$\mbox{\boldmath $\omega$}正則言語の位相的特徴付けから次のような例を見つけることができる $[6, 7]$ .
$a^{*}b^{\omega}\in^{\mathrm{p}}1^{-\mathrm{P}_{0}}$$(a^{*}\iota)^{\omega}\in \mathrm{p}_{\epsilon}-\mathrm{P}_{1}$口

最後\ell c ペトリネット\mbox{\boldmath $\omega$}言語の閉包性を証明する.

定理 5 ペトリネット\mbox{\boldmath $\omega$}言語のクラス $\mathrm{P}_{*}(i=0,1,3)$ 集合和, 共通部分に関して閉じていて, 補集合演算に関して閉じていない.

121

証明. $N’=(P’, T’, A’, e’, m’, \phi)$ と $N”=(P^{u}, \tau^{\iota l}, A/’,\prime\prime, me\emptyset/’))$ を同時に模倣するペトリネット $N$ を次のように定義する. $N=(P’\cup P’’, T, A, e, m^{l}\oplus m^{\prime/}, \emptyset)$ ,ここで,$T=\{\langle t’,t’’\rangle\in T’\cross T’|e’(t’)=e’’(t")\}$

であり,

各

$\langle t’, t’’\rangle\in T$

,

に対し,

$A((t’,t’/\rangle)=(A’(t’)\oplus A$ “ $(t”),$ $A’(t’)\oplus A’’(t’’)\rangle$,$e(\{t’, t;’))=e’(t’)$(と定義する.

ただし,れるのベク トルである.

$\mathrm{N}^{P’\cup P^{\ell\prime}}$

このとき,$R_{\mathrm{U}}=${$R_{\cap}=${$R’\subseteq T^{r\omega},$$\langle t_{1}’,$$A’(t’)\oplus A’;(t\prime\prime)\rangle \text{は}A’(t’)\text{と}$$R^{u}\subseteq T^{l/\omega}$$A”(t”)$を並べてえらに対して,$t\tau\rangle 0_{\mathit{2}}’,t^{\prime/}2\rangle\cdots\in\tau^{\omega}|t’t’\cdots\in 12R1$$\langle t_{1}’,t_{1}’J\rangle(t_{22}’,t’’\rangle\cdots\in T^{\omega}|t’t’\cdots\in 12R1$

または $t_{1}’’t’\cdots\in R_{2}$ },または $t\mathit{7}t’’\cdots\in 2R2$

}

とおくと,
$L(N’, R’)\cup L(N’’, R^{\prime/})=L(N, R_{\cup})$,$L(N’, R’)\cap L(N^{n}, R^{\prime/})=L(N, R_{\cap})$が成り立つ.
が補集合に対して閉じていないことは, 定理 4 の証明で与えた位相的な性質と, 正則\mbox{\boldmath $\omega$}言語に対する同様の結果から, 明かである.
が補集$L_{3}(N)=L_{0}(N)-D(ab)^{\omega}$
合に関して閉じているとしよう. 例 6 のを考える$\mathrm{P}_{0}$と$\mathrm{P}_{1}$$\mathrm{P}_{3}$と,$(\Sigma\omega-L_{3}(N))\cap L0(N)=D(a\iota)\omega$であるから,$L_{3}(N)=D(ab)\omega$となる
このとき, ある

ペトリネット $N=(P, T, A, m_{0}, e, F)$ が存在するはずである.
が存在して$m2$ かつ $m_{1}\leq m_{2}$ とできる.
なので, このことは $a^{j+k}b^{j}(ab)^{\omega}\in L_{3}(N)$ を意味し, 矛盾である.
も補集合に関して閉じていない.

$j,$

$k$

$m_{0}[a^{\mathrm{j}}\rangle$$m\iota[ak\rangle$$a^{j}\dot{\mathcal{U}}(ab)^{\omega}\in L_{3}(N)$よって,$\mathrm{P}_{3}$口References[1] J.R.B\"uchi, On a decision method in restricted second-order arithmetic, Logic,
Methodology and Philosophy of Science (Stanford Univ. Press, 1960) 1-11.

122[2] W. Fujikawa, Some Decision Problem for Vector Addition systems and PetriNets, 修士論文, 東工大 (1979).

[3] M.Parigot and E.Pelz, A logical formalism for the study of the finite behaviouI
nets, Advances on Petri nets 1985, LNCS 222, 346-361.
of$\mathrm{p}\mathrm{e}\mathrm{t}_{\mathrm{I}\mathrm{i}}$-languages of Petri nets and logical sentences, Proceedings of Application and Theory of Petri Nets 1986.

[4] E.Pelz,$\omega$[5] C.Petri, Kommunikation mit Automaten, Ph.D. dissertation, University ofBonn (1962).
[6] L.Staiger and K.Wagner, Automatentheoritische und Characterisierungentopologischer Klassen regularer Folgenmengen, $E.I$.K. 10 (1974) 379-302.

[7] M.Takahashi and H.Yamasaki, A note on -regular languages, T. C. S. 23 (1983)$\omega$

217-225.
[8] H.Yamasaki, M.Takahashi and K.Kobayashi, Characterization of -regular languages by monadic second-order formulas, T. C. S. 46 (1986) 91-99.
$\omega$[9]$\mathrm{J}.\mathrm{L}$.Peterson, ペトリネッ ト入門, 市川・小林訳, 共立出版 (1984).

[10] H.Yamasaki, ペトリネットの理論と応用, 情報処理

25 (1984) 188-198.

[11] K.Wagner, On -regular sets, Inf and Contr. 43 (1979) 123-177.
$\omega$