数理解析研究所講究録1093 巻 1999 年 224-229

224

あるクラスの文脈依存グラフ文法とその性質

1

東洋大学

安達由洋

東洋大学

小林卓

東洋大学

土田賢省

日本大学

夜呉竹夫

(Yoshihiro Adachi)(Suguru Kobayashi)(Kensei Tuchida)(Takeo Yaku)
存グラフ文法 [9] を–般化したものであり, またよくはじめに知られている NCE (context-free) graph grammar

グラフ文法は文字列を基にした形式言語理論のグラフへの–般化であり, 視覚的オブジェクトの生成変換を数学的に厳密にかつ分かりやすくモデル化する
ことのできるメカニズムを提供する. 1960 年代に始[1] の文脈依存形への拡張となっている.
次に, NCE 文脈依存グラフ文法のプロダクショ
ン・コピーの合成とその結合律について議論する.

まったグラフ文法の研究は着実に発展を続け, これま

プロダクションコピーの合成は, 制御システムにでに多くの異なったタイプのグラフ文法が定式化されフィ $-$ ドバック結合を埋め込む場合や,ている ([1]).

また, グラフ文法のビジュアルシステ

で部分図を再利用する場合のように, 特定の構造を持

ムへの実際的応用についても多くの研究が報告されてつ部分グラフをどのように埋め込むかをグラフ書き換え規則で定義するために理論的にも実用的にも重要でいる ([2, 3, 4, 5]).

’

プログラム図2 つ以上のノードからなる

ある. 本研究は, ユーザが望む構造を埋め込むためのグラフを左辺に持つ文脈依存プロダクションを用いる

方法をグラフ文法に基づいて表現する初めての試みでことができるので, 各々のプロダクションの左辺がたある.

だ 1 つのノードからなる文脈自由グラフ文法に比べてNCE 文脈依存グラフ文法の合流性とその条件について議論する. 一般に, NCE 文脈依存グラ

文脈依存グラフ文法は,さらに,より柔軟に視覚的オブジェクトの構文規則を記述することができる. Mariott ら [6] は, 視覚的言語の表現

フ文法に基づいて導出されるグラフは, プロダクショ

コピーの適用の順序に依存して変わる. 合流性と能力を研究する中で文脈依存記述は視覚的言語にとっン.

て重要であると結論づけている.

は, 導出の結果得られるグラフがプロダクションコ

ピーの適用の順番に依存しない性質である. この合流

安達ら $[7, 9]$ は, 導出過程においてプロダクションの結合命令に従い隣接ノードと埋め込むグラフのノー性は, 合成ドの間にのみ新しいエッジを張るような文脈依存グ保証し, また効率的な構文解析アルゴリズムの開発のラフ文法を定義した. そして, この文法に基づいて
ブロック線図 [7, 8, 9, 10] やシグナルフローグラフ

部分グラフの書き換えを用いた NCE 文脈依存グラ

ers ら [13] は, layered graph grammar と呼ぶ文脈

フ文法を定義する. この文法では, グラフ書き換えに依存グラフ文法を定義し, その構文解析法について議Zhang ら [14] は, この layered graphgrammar をもとに reserved graph grarmnar を開発した. この reserved graph grammar も文脈依存グラ
フ文法であり, 彼らはこの文法に対して多くの場合に多項式時間で構文解析できるアルゴリズムを報告している.

しかしながら, これらの研究を除いては文脈依

NCE 文脈依存グラフ文法

2

Rek-

論している.

ダクション. コピーの適用の妥当性をためにも重要な性質となる.

$-$$[11, 12]$ などに対する構文規則を定式化した.

$\text{プ}q$おける埋め込み過程で, 隣接ノードと埋め込んだノー.

ド間にのみ接続命令に従って新しいエッジを作る.

定義 1(グラフ)$\Sigma$をノードラベルのアルファベット,

ベルのアルファベットとする.

$\Sigma$と$\Gamma$$\Gamma$

をエッジラ
上のグラフ

3 つ組 $H=(V, E, \lambda)$ である. ただし,とは,はノードの空でない有限集合である.
(1)$E\subseteq\{(v,\gamma, w)|v, w\in V, v\neq w, \gamma\in\Gamma\}$ は(2)$V$

存グラフ文法についての理論的あるいは実用的な研究は少ない.
本研究では,

まず NCE 文脈依存グラフ文法

エッジの有限集合である.

(3):$Varrow\Sigma$

はノードラベリング関数である.

(context-sensitive graph grammar with neighborod controlled embedding, NCE-CSGG) を定義$\mathrm{h}\circ$

グラフ $H$ の構成要素を各々 $V_{H},$ $E_{H},$する. このグラフ文法は, 我々が以前定義した文脈依にする$\lambda$$\lambda_{H}$

と書くこと
口

225

グラフ

と

$H$

が存在して,$E_{H}\}$

に対して全単射

$K$

E-x

:

が成り立つとき,る (isomorphic) といい,

と

$K$

は

同形であ

を

$H$

から

$K$

への同形

$\theta$$V_{H}\cap V_{K}=\emptyset$は互いに素である (disjoint)$\dot{K}$ラフ $H$ に対して,を $[H]$ で表す.

(6) $P$ はプロダクションの空でない有限集合である.

$H$

ここで, プロダクションは組 $((A, X)::=$$(B, Y),$ $C)$ の形で表されるものとする.

$\lambda_{K}(\theta(v))=$$H$

写像 (isomorphism) という.と

$V_{H}arrow V_{K}$$=\{(\theta(v), \gamma, \theta(w))|(v, \gamma, w)\in$, かつ, すべての $v\in V_{H}$ に対して$\lambda_{H}(v)$$H$$\theta$(a)$A\in GR_{\Sigma,\Gamma}$のとき,という. グと上のすべての (コンクリート

誘導される $A$ の部分グラフ $K$ を文脈部分
グラフ (context subgraph) という.

(b) $Y\in GR\Sigma,\Gamma$ ,
ある.

.) グ

び $C$

$GR\Sigma,\mathrm{r}$(c)

ジラベルも付いているとき小文字’e’ を頭に添える.
以下に,文脈依存グラフ文法を定義する.
NCE 文脈依存グラフ文法,
文脈依存グラフ文
法,
文脈依存グラフ文法はこれの特別な場合$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$$\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$を$P$の左辺と呼び $lhs(p)$ と書く. また,$(B, Y)$ を$P$の右辺と呼び $rhs(p)$ と書く.

の各要素

(1)

$\Sigma_{n}$は非終端ノードラベルのアルファベットで
.

ある.

(2)

口

2 つのプロダクションと$\theta_{l}$$\beta,$から$B_{2}$$v_{y},$.

$=$$C_{2}$$\gamma,$$d$から$p_{2}$$((A_{1}, X_{1})$

$::=$

)

への (左辺の) 同形写像

$A_{2}$,への (右辺の) 同形写像.
$\{(X, \theta l(v_{x}),$ $\beta,$ $\gamma,$ $\theta r(v)y’ d)$$\in C_{1}\}$は同形である$p_{1}$$=$$p_{1}$$p_{2}=((A_{2},X_{2})::=(B_{2_{-}},’ Y_{2}),$ $C2)$

から$A_{1}$$B_{1}$$v_{x},$と$C_{1})$

が存在して

(X,
を

$\Sigma=\Sigma_{n}\cup\Sigma_{t}$はノードラベルのアルファベットが成り立つとき,という. また, 写像の対への同形写像という.

$G$$\theta$.

$p_{1}$$|$と$(\theta_{l}, \theta,)$$\Gamma_{n}$

ション集合

のプロダク

して含まないと仮定する. $P\in P$ に同形なプロダ
クションの集合を coPy $(p)$ で表す. coPy $(p)$ の要
素を $G$ の に対するプロダクション. コピーあるい$\bigcup_{p\in P^{Copy}}(p)$ある.
$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$る.

は終端エッジラベルのアルファベットであ,は空でない有限集合であり, 互い$\Gamma_{n}$$\Gamma_{t}$に素である.
$\Gamma=\Gamma_{n}\cup\Gamma_{t}$とする.’

文脈依存グラフ文法に基づくグラフの書き換えは次のように行われる. 与えられたホスト・グ
ラフ (host graPh) を $H$ とし, $A’$ を $H$ の誘導部分グラフとする. また, $p’$$((A’,X’)$$::=$$(B’, Y^{J}),$ $C’)$をある $P\in P$ のプロダクション. コ

ピーとする. ただし,はエッジのないノード 1 点からなるス

タートグラフcoPy $(P)=$$=$はエッジラベルのアルファベットである.
$S\in\Sigma_{n}$には, 同形なプロダクションを重複

は単にプロダクションコピーという.

は非終端エッジラベルのアルファベットで$(^{-}4)\Gamma_{t}$

$P$

$P$

である.

(5)

の結合命令 (connec-$\Sigma_{l}$$\Sigma_{n}$

(3)

$P$

$C$

tion instfuction) という.

$p_{2}$

は終端ノードラベルのアルファベットで ある.
, 易は空でない有限集合であり, 互いに素である.

を$(\sigma, v_{x}, \beta, \gamma, v_{y}, d)$に対して;である. ただし,{in, out} は$(A, X)$

定義 2($G=(\Sigma n’\Sigma t, \Gamma n’\Gamma t, S, P)$(依て,$(B_{1}, Y_{1}),$

文脈依存グラフ文法)
文脈依存グラフ文法とは 6 つ組

およプロダクション $P=((A, X)::=(B, Y),$ $C)$ においとしてみなすことができる.

$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$

,

$Y$

$X$

結合関係 (connection relation) である.

$\mathrm{e}\mathrm{N}\mathrm{C}\mathrm{E}$$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$,に依存して決まるグラフである.

$A$$C\subseteq\Sigma\cross Vx\cross\Gamma)(\Gamma)(V_{Y^{\cross}}$

NCE 文脈依存グラフ文法が有向グラフを生成する$\rangle$は,$B\in GR\Sigma,\mathrm{r}$に説明する. )分集合をグラフ言語という.

とき, これを明示するために小文字’d を頭に添える.
また, 生成されたグラフがノードラベルとともにエッかつ $1\leq|V_{X}|\leq|V_{Y}|$ で存の仕方については定義 3 のあとで具体的で表し, すべてのアブストラク
トグラフの集合を $[GR\Sigma,r]$ で表す. $[GR\Sigma,r]$ の部

ラフの集合を$A\neq X$ の合 $V_{A-X}=\{v|v\in V_{A}, v\not\in V_{X}\}$ によりに同形なすべてのグラフの集合

トグラフとアブストラクト・グラフを厳密には区別しない.

, そして $X$

$K=A-X$ , すなわち, ノード集とき,このとき $H$ をコンクリート・グラフ$\Gamma$$X\in GR_{\Sigma_{n},\mathrm{r}}$は $A$ の誘導部分グラフである.

(concrete graPh) といい, $[H]$ をアブストラクト.
グラフ (abstract graPh) という. 通常, コンクリー$\Sigma$,

ただし,$G_{s}$のノードのラベルである.

$Y’$

と

$H$

が互いに素である.

グラフ書き換えは以下の手順で行われる. (1) $H$ からマザーグラフ (mother graPh) $X’$ と $X’$ のノー

226への導出ステップ (derivation step) と呼ぶ. また,口
導出ステップの系列を導出 (derivation) と呼ぶ.

ドに接続している $H$ のエッジをすべて取り除き, 得
られたレスト・グラフ (rest graPh) を(2)
置$H^{-}$$\langle$$H^{-}$$H^{-}$とする.

$H^{-}$にドーター. グラフ (daughter graph) $Y’$ を

. (3)

$C’$

上記のように, プロダクション $P=((A, X)::=$の結合命令にしたがって $Y’$ のノードとの左適用による導出ステップは グラフ
$Y$
$A$ ,
$X$ ,
と, 結合関係 $C$ により完全に決定されを満たすグラフである. しる. グラフ $B$ は,$(B,\dot{Y}),$ $C)$のノード間のエッジを新しく作る. これを $Y’$ のへの埋め込み (embedding) という.

埋め込み過程において, 結合命令 ($\in C’$$\sigma,$$x,$ $\beta,$ $\gamma,$ $y$$A\Rightarrow B$

, in)

ア

は次の意味を持つ. ホスト・グラフ $H$ においてラベル$\sigma$$v$

からり自然であり, また文脈依存部分グラフに対応する部

マ$\gamma$分グラフを把握しやすくなる.

ザー・グラフのノードとの間にエッジを持つレストを隣接ノードという. 結
グラフのノード, 例えば

導出ステップを例を用いて説明する. Fig. 1 (a)$H$ ,Fig. 1 (b) はプロダクショ$v$, out) $\in C’$ の場合も, エッジの向きが異なるだけであとは同様である. 埋め込み過合命令 ($\sigma,$をであるが, プロダクションの右辺に $B$ を記す方がよ$y\in V_{\mathrm{Y}’}$へ向かうエッジ ( $v,$ , のを新しく作る. このとき,$B$用いなくてもプロダクションの記述は理論的には可能を持つノード $V\in V_{H}-V_{X’}$ から $x\in V_{X’}$へ向かうエッジ $(v, \beta, x)$ があれば,$K=B-Y=A-X$ が成り立つ.

たがって,はホスト・グラフ$x,$ $\beta,$ $\gamma,$ $y$

コピー $p’$ である. ホスト・グラフ $H$ にプロダク

ン.

程でドーター. グラフとレスト・グラフの間に新しくション. コピー作られるエッジはブリッジと呼ばれることがある.
NCE 文脈依存グラフ文法でのグラフ書き換えはグラを Fig. 2 に示す.

である. レスト・グラフ

フの局所的な変換である. また, 端点にノードの対応しない垂れ下がったエッジ (dangling edge) は生成置いたのが Fig. 2(b) である. そして, 埋め込みを行ない得られた結果のグラフ $H’$ が Fig. 2(c) である.

$p’$を左適用して行なう導出ステップ
レストグラフ$H^{-}$

が Fig. 2(a)$H^{-}$にドーターグラフをされない.

以上に説明した

文脈依存グラフ文法のグラ$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$フ書き換えを形式的に定義すると次のようになる.
を
定義 3(導出)
文脈依存グラフ文法とする. $H\in GR\Sigma,\mathrm{r}$ , $A’$ を$G–(\Sigma_{n},\dot{\Sigma}_{\mathrm{f}} , \Gamma_{n} , \Gamma_{t} , S, P)$$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$の誘導部分グラフとする. $P\in P$ を $G$ のプ
ロダクションとする. そして $p’=((A’, X’)$ $::=$$H$

ピーとする. ただし,(a) AHost graphに対するプロダクションコ$(B’, YJ),$ $c’)$ は $P\in P$

と

$H$

$Y’$

は互いに素である.
$\text{団_{}\mathrm{x}1}$

このとき, プロダクション. コピー $p’$ のグラフ $H$ へ$\Phi_{\mathrm{x}2}::=$.

の左適用とはグラフ $H’\in GR\Sigma,\mathrm{r}$ を以下のように構$\mathrm{C}=\{(\mathrm{a},\mathrm{X}1, \beta, \gamma,\mathrm{y}\mathrm{l},\mathrm{i}\mathrm{n}),(\mathrm{C},\mathrm{x}\mathrm{l}, \alpha, \sigma,\mathrm{y}\mathrm{l},\mathrm{i}\mathrm{n})$成することである.

$(\mathrm{c},\mathrm{x}2, \beta, \sigma,\mathrm{y}3,\mathrm{i}\mathrm{n}),(\mathrm{d},\mathrm{x}2, \beta, \mathrm{Y},\mathrm{y}3,\mathrm{o}\mathrm{u}\mathrm{t})\}$$V_{H’}$$=$$(V_{H}-V_{X’})\cup V_{\mathrm{Y}}’$$E_{H^{J}}$$=$$\{(v, \gamma, w)\in E_{H}$$V_{X’}\}$(b) Aproducfion copy,$\cup E_{Y’}\cup\{(v, \gamma, y)$$(\sigma, x, \beta,\gamma, y, \mathrm{i}\mathrm{n})$$\cup\{(y,\gamma, v)$$|\exists v\in$$V_{X’},$ $\exists\beta$$\sigma,$$(\{$$\lambda_{H’}(x)$$x,$ $\beta,$$\Gamma,$$\in$$\lambda_{H}(x)$$\lambda_{\mathrm{Y}’}(X)$$\exists v$$|$$(x, \beta, v)$

,
,

,

$=$

$V_{H}-$

$\in$

$\in$

$E_{H}$$y,$ $\circ \mathrm{u}\mathrm{t})\in C^{J},$ $\lambda H(v)=\sigma\}$$\gamma,$$=$$C’,$ $\lambda_{H}(v)$

$\in$

,

,

が得られるとき$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$$S,$ $P)$

文脈依存グラフ文法 $G=(\Sigma_{n},$に対して, 導出$\cdots\Rightarrow$H0_{\mathrm{P}_{1}}\Rightarrow,H_{1}\Rightarrow,$

は $rhs(p_{i}^{J})=(B_{i}^{J},Y_{i}’)$ について

$H_{0}$$\Sigma_{t},$p_{2}p_{n}’ H_{n},$と$Y_{i}’,$,$n\geq 0$ ,$\tau_{n},$$\Gamma t$$1\leq i\leq$, が互いに素であるとき生成的である (creative) という. 今後, 生成的な導出のみを扱うことにする. 上$n$$x\in V_{H}-V_{\mathrm{x}^{J}}$$x\in V_{\mathrm{Y}’}$記のような生成的導出が $H0=H$ と $H_{n}=H’$ にと書く. スタ一トグラフ
ついて存在するとき.

$H\Rightarrow^{*}H’$

グラフ $H$ にプロダクション. コピー $p’$ を左適下して $H’$’$\mathrm{p}$Fig. 1. A host graph and a production copy$|v,w\in V_{H}-$$V_{H}-V_{X}’,$ $\exists\beta\in\Gamma,$ $(v,\beta, X)\in E_{H}$$\sigma\}$$\mathrm{H}$$H’p$ と書き,

$H\Rightarrow,$

$H$

から

$H’$

$Gs$

に対して

$Gs\Rightarrow H*$

であるグラフ$H\in GR\Sigma,\mathrm{r}$を $G$ の文形式という. スタートグラフ$G_{S}$

から導出

227

(結合関係の付随した) グラフ書き換え規則 $p=$$((A_{1}, x_{1})::=(B, Y),$ $C)$ を以下のように構成する.
き,$B$$B_{1}$$\Rightarrow p_{2}$$( B, (A_{1}=X_{1})$$Y$$[eggd]$$=${$B-K_{1}$,

ここで,$(A_{1}\neq X_{1})$$($(a) lhe rest graph$K_{1}=A_{1}-X_{1}$$\mathrm{H}^{-}$

$C$

$=$

$\{(\sigma, v, \beta, \gamma, w, d)\in C_{1}|w\in V_{\mathrm{Y}_{1}}-Vx_{2}\}$$\cup\{(\sigma, x, \beta, \delta, y, d)|\exists w\in Vx_{2},$ $\exists\gamma\in\Gamma$,$(\sigma, x, \beta,\gamma, w, d)\in C_{1},$ $(\sigma, w,\gamma, \delta, y, d)$$\in C_{2}\}$

このとき,

$P$

を

コピーと呼び,$p_{1}$と$p_{1}\circ p2$

いに素であり,$p_{2}$と書く. また,$A_{2}\subseteq B_{1}$う条件が成り立つとき,(b) lne rest graph$\mathrm{H}^{-}$の合成プロダクション
かつ$A_{1}$$X_{2}\subseteq Y_{1}$$p_{1}\circ p2$と$Y_{2}$

が互であるといが定義可能であるという.

and the daughter grapn

口

合成プロダクションコピ一は,$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$

文脈依存

グラフ文法のプロダクションコピーとまったく同じ形式のグラフ書き換え規則として表現されている. したがって, 合成プロダクションコピーのグラフ $H$への左適用および導出ステップを定義 3 と同様に定義できる. また,(合成) プロダクションコピ一と (合成) プロダクションコピーの合成も定義 4 と同様に定義される.
( ’ rne resuitant grapn$\mathrm{C}$$\mathrm{n}$命題 1 $G=(\Sigma_{n}, \Sigma_{t}, \Gamma_{n}, \tau_{t}, S, P)$ を

Fig. 2. The process of the derivation step依存グラフ文法とする.
$(B_{1}, Y_{1}),$ $C_{1})$

される終端グラフの集合, すなわち $\mathcal{L}(G)=\{[H]\in$$GR\Sigma_{t},\Gamma|Gs\Rightarrow^{\tau}H$$G$

for some start graph-によって生成されるグラフ言語という.

$G_{S}$}$\xi_{\mathrm{i}}$

$G$

$=$

と $p_{2}=((A_{2}, X_{2})::=(B_{2}, Y_{2}),$$H\Rightarrow H_{1}\Rightarrow H_{2}p_{1}\mathrm{p}2$

かつ$H\Rightarrow H_{3}\text{ア}1^{\mathrm{O}}p_{2}$文脈$((A_{1}, X_{1})$の (合成) プロダクションコピーであり,が定義可能であるとする. 任意のて$\iota$$p_{1}$$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$$H\in G_{\Sigma},\mathrm{r}$$::=$$C_{2})$

が$p_{1}\mathrm{o}p2$に対しならば $H_{2}=H_{3}$ である

3

プロダクションコピーの合成$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$

口

ここで,

文脈依存グラフ文法のプロダクションコ

ブロック線図文法 [10] を用いてプロダク

ション・コピーの合成例を示す.

Fig.

3 にブロッピーの合成表現は, ホストグラフに望みの構造を持

ク線図文法のプロダクションの–部を示す. また,つ部分グラフを埋め込むためのグラフ書き換え規則をに, プログラム図へある特定の部分プログラムを埋めFig. 4 にプロダクションコピーの合成過程を示す.
で得られた合成プロダクション・コピー
Fig.
$((p_{B}2’\circ pB2;)\circ p_{B}10’)\circ_{PB}3$ ’ は,‘Elem’ とラベル込んだり, ブロック線図ヘフィードバック構造を埋め付けされた非終端ノードをフィードバック構造に書き込むための知識を表現するのに役立つ.

換えるグラフ書き換え規則である. この規則を左適用することにより, Fig. 5 に示すようにブロック線図に定式化する理論的かつ実用的な方法である. それゆえ

定義 4( $\text{プロダクション}\cdot$ コピーの合成)を
文脈依存グラ$G=(\Sigma_{n}, \Sigma_{t}, \Gamma_{n}, \Gamma t, S, P)$

フ文法とし,$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$を

ションコピーとする. このとき,$A_{1}$に素であり,

我々はブロック線図文法に基づいてブロック線図ののプロダク

編集, 構文解析, 構造認識などを支援するブロック線が互い

図処理システムを実現した. このシステムの実行画面.

$p_{2}=((A_{2}, X_{2})::=(B_{2}, Y_{2}),$ $C_{2})$$A_{2}\subseteq B_{1}$

かつ

$G$

フィ一ドバック構造を埋め込むことができる.

と$::=(B_{1}, Y_{1}),$ $C_{1})$$p_{1}=((A_{1}, X_{1})$$4(\mathrm{d})$と$X_{2}\subseteq Y_{1}$$Y_{2}$であるとを Fig. 6 に示す.

228$\mathrm{p}_{\mathrm{B}}1$$\mathrm{p}_{\mathrm{B}}2$.
.

$\Rightarrow$$\mathrm{K}?_{\mathrm{k}1}arrow[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]\mathrm{X}\mathrm{l}$.

$\mathrm{C}\circ\vdash \mathrm{r}\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}\mapsto$$::=\mathrm{K}?arrow[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{k}1\mathrm{m}51arrow[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]2\mathrm{y}$$\mathrm{K}?^{\epsilon}\{[egg0]$$\mathrm{C}=\mathrm{t}(\#,\mathrm{X}\mathrm{l},\mathrm{y}\mathrm{l},\mathrm{i}\mathrm{n}),(\#,\mathrm{x}\mathrm{l},\mathrm{y}2,\mathrm{o}\mathrm{u}\mathrm{t})\}$$\mathrm{p}_{\mathrm{B}}3$[BD]$\mathrm{C}=\emptyset$$:.=\mathrm{O}\circ>[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}arrow\overline{\mathrm{y}1}\mathrm{y}2\mathrm{y}3\geq$$[\mathrm{B}\mathrm{D}]_{\chi 1}$,$\mathrm{p}1$$\bullet$$\}$$(\#,\mathrm{X}\mathrm{l},\mathrm{y}\mathrm{l},\mathrm{o}\mathrm{u}\mathrm{t})\}$$[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]_{\mathrm{x}1}::=\ovalbox{\tt\small REJECT}_{\mathrm{v}1}1\mathrm{o}\mathrm{c}\mathrm{C}=\mathrm{t}(\#,\mathrm{x}\mathrm{l},\mathrm{y}\mathrm{l},\mathrm{i}\mathrm{n}),$Fig. 5. Derivation using a composite production
copy.

$\mathrm{p}_{\mathrm{B}}10$$\mathrm{C}=$$[\mathrm{E}\iota_{\mathrm{e}}\mathrm{m}]\mathrm{x}2$$[\mathrm{E}]\mathrm{e}\mathrm{m}|\mathrm{k}\mathrm{l}${$(\#,\mathrm{x}\mathrm{l},\mathrm{y}\iota,\mathrm{i}\mathrm{n})$$::=$, (#,xl,yl,out),$(\#,\mathrm{x}\angle,\mathrm{y}‘*,\ln_{J},$$\backslash \pi,\mathrm{x}z,\mathrm{y}\mathrm{o},\mathrm{o}\mathrm{u}\iota’$}

Fig. 3 Part of the productions of the block diagram grammar(a)$\mathrm{h}^{2}’$.

$\mathrm{K}?_{\mathrm{k}}7->[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]\mathrm{x}1$$:.=$$\mathrm{K}?_{\mathrm{k}1}arrow[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}1_{\mathrm{y}\mathrm{y}2}-\geq 1\text{旧}\mathrm{e}\mathrm{m}]$$\mathrm{C}=\{\langle\#,\mathrm{X}1,\mathrm{y}\iota,:\mathrm{n}),(\#,\mathrm{X}1,\mathrm{y}2_{0},\mathrm{u}\mathrm{t})\}$$\mathrm{K}?\epsilon\{[egg0],\bullet\}$(b)’$*^{2’ 0}\mathrm{h}^{2}$$\mathrm{K}?_{\mathrm{k}1}arrow[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]\mathrm{x}\mathrm{l}:.\cdot=\mathrm{K}?_{\mathrm{k}\overline{1}}\supset \mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}1-\geq[\mathrm{y}3\mathrm{y}4\mathrm{y}2\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]-\geq[\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{m}]$$\mathrm{K}?\epsilon\{[egg0],\bullet\}$Fig. 6. A screen of our block diagram processing
system$\mathrm{C}=\mathrm{t}(\#,\mathrm{x}\mathrm{l},\mathrm{y}3,\mathrm{i}\mathrm{n}),(\#,\mathrm{x}\mathrm{l},\mathrm{y}2,\mathrm{o}\mathrm{u}\mathrm{t})\}$$(p_{1}\mathrm{o}p2)\mathrm{o}r3=p_{1}\mathrm{o}(P2^{\mathrm{O}}p_{3})$$p_{1}\mathrm{o}p2$が定義可能であり, かつ

義可能であっても,\leftarrow l\\mbox{\boldmath $\pi$},\Lambda l,JV,m ノ,‘\mbox{\boldmath $\pi$},\Lambda l,Jw,vu\iota ノ’

(d)

となる.

$p_{2}\mathrm{o}p_{3}$$(p_{1}\mathrm{o}p_{2})\mathrm{o}p_{3}$$\square$が定が定義可能であるとは限らないので注意を要する.

’$((\mathrm{P}_{\mathrm{R}}^{2}’\circ \mathrm{p}_{\mathrm{n}}2’)\mathrm{O}\mathrm{p}_{\mathrm{n}^{10}’})\mathrm{o}\mathrm{p}_{\mathrm{n}}3$4

合流性$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$

文脈依存グラフ文法では, (生成的) 導出の結果得られるグラフは–般にはプロダクションコ

ピーを左適用する順序に依存して変わる.

$\mathrm{c}=\{(\#,\mathrm{x}1,\mathrm{y}6,\mathrm{i}\mathrm{n}),(\#,\mathrm{x}\iota_{\mathrm{y}8},,\mathrm{o}\mathrm{u}\mathrm{t})\}$

Fig. 4. An example of composite production copies
命題 2(結合律) $G=$ (および$\dot{p}_{3}=$

,

を ed-

の左適用の順序に依存しないという性質のことである. この合流性は, 合成プロダクションコピーを適$p_{1}=((A_{1}, X_{1})::=$

用して部分グラフを埋め込んだ結果得られるグラフの文法的正しさを保証するために重要である. また,$p_{2}=((A_{2},x_{2})::=(B_{2},Y_{2}),$ $C_{2})$NCE 文脈依存グラフ文法に基づく効率的な構文解析$\Sigma_{n}.’\Sigma_{t},$NCE 文脈依存グラフ文法とし,$(B_{1},Y_{1}),$ $C_{1})$, $S,$

合流性とは, 導出の結果がプロダクション・コピー$\Gamma_{n},$$\tau_{t}$$((A_{3},X\mathrm{s})::=(B_{3},Y_{3}),$ $c_{3})$(合成) プロダクションコピーとする.
義可能であり, かつ$p_{2}\circ p_{3}$$P\rangle$を$p_{1}\circ p2$

$G$

の

が定

が定義可能であるとき,アルゴリズムを開発するためにも重要な性質である.
まず, 結合関係から容易に成立するか否かを調べることができる静的合流性を定義する.

229

定義 5(静的合流性)$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$

文脈依存グラフ文法 $G=$

は, 任意の$S,$ $P)$と$H_{12}$いる.

$H\in GR\Sigma,\mathrm{r}$$H\Rightarrow,$$H_{2}\Rightarrow,H_{21}p_{2}p_{1}$$(\Sigma_{n},$について$\Sigma_{t},$$\Gamma_{n},$,$\tau_{t}$$H\Rightarrow P_{1}^{l}H_{1}\Rightarrow,p_{2}$となるとき静的に合流的である (conflu-

という.

口

命題 3
$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$$P)$

文脈依存グラフ文法 $G=(\Sigma_{n},$ $\Sigma_{tnt},$ $S$ ,$\Gamma,$ $\Gamma,$

が静的に合流的である必要十分条件は, 任意のプ

ロダクション $p_{1}=((A_{1}, x_{1})::=(B1, Y_{1}),$ $C_{1}),$ $p2=$, 任意のノード$x_{2}\in X_{2},$, 任意のエッジラベ
に対して以下が成立することである.

$((A_{2}, X_{2})::=(B_{2}, Y_{2}),$ $C_{2})\in P$$X_{1},$

ル$y_{1}\in Y_{1},$$\alpha,$$\delta\in\Gamma$$\text{グラフ文法に基づいた視覚的}$デザイン言語へ幅広く応用することができる.

.

が $G$ の (生成的) 導出ならば$H_{12}=H_{21}$$\underline{\mathrm{e}\mathrm{n}\mathrm{t})}$

また, 合成プロダクション. コピーに基づいた部分グラフの再利用は,$x_{1}\in$$y_{2}\in Y_{2}$

参考文献[1] Rozenberg, G. (Ed.), Handbook of Graph Grammars and Computing by Graph Transformation,
World Scientific Publishing (1997).
[2] Minas. M., Diagram Editing with Hypergraph
Parser Support, Proc. IEEE Symp. Visual Languages (1997), 230-237.
[3] Bardohl, R., GENGED A Generic Graphical Ed-

itor for Visual Languages based on Algebraic
Graph Grammars, Proc. IEEE Symp. Visual Languages (1998), 48-55.
[4] Zhang, D., and Zhang, K.,: A Visual Language Generation Toolset, Proc. IEEE Symp. Vi$\mathrm{V}\mathrm{i}\mathrm{s}\mathrm{p}_{\mathrm{r}}\mathrm{o}$$\exists\beta\in\Gamma$,$(\lambda_{X_{2}}(x2), X_{1}, \alpha,\beta, y_{1}, in)\in C_{1}$$\mathrm{B}>\cdot\supset$sual Languages (1998), 195-202.
[5] M\"unch, M., Sch\={u}rr, A., and Winter A., Integrity Constraints in the multi-paradigm language PROGRES, Proc. IEEE Symp. Visual Languages (1998), 84-85.

$(\lambda_{Y_{1}}(y_{1}), x_{2}, \beta,\Uparrow\delta, y_{2}, out)\in c_{2}$$\exists\gamma\in\Gamma,$$(\lambda x_{1}(x1), x2, \alpha, \gamma, y2, out)\in C_{2}l^{\mathrm{a}}\cdot\supset$$(\lambda_{Y_{2}}(y_{2}), X_{1,\gamma}, \delta, y1, in)\in C_{1}$口我々が定義したブロック線図文法とシグナルフロー
グラフ文法は, 生成されるグラフはエッジラベルを持
たず, また埋め込み過程が隣接ノードのラベルに依存しないので静的に合流的である.
次に, グラフ文法の分野で合流性の定義として普通用いられる動的合流性を定義する.

定義 6(動的合流性)
文脈依存グラフ文法 $G$$\mathrm{e}\mathrm{d}\mathrm{N}\mathrm{C}\mathrm{E}$$S,$ $P)$は,$G$の任意の文形式$=$$H$$(\Sigma_{n},$$\Sigma_{t},$$\tau_{n},$について$\Gamma t$,$H\Rightarrow p_{1}$’[6] Marriott, K., and Meyer, B., On the Classification of Visual Languages by Grammar Hierarchies,
Journal of Visual Languages and Computing, 8(1998), 375-402.
[7] Adachi, Y., Kobayashi, S., Anzai,. andTsuchida, K., Block Diagram Grammar and Structure Recognition Based on Graph Rewriting, Proc.
. $IFAC/IEEECACsD’g7$ (1997), 257-262.
$\mathrm{K}_{)}$[8] Anzai, K., Adachi, Y., Kobayashi, S., andTsuchida, K., Block Diagram Generation andParsing Based on Graph Grammar, Proc. IEEEISCAS’97 (1997), 1970-1973.

[9] Adachi, Y., Kobayashi, S., and Tsuchida, K.,-output Block Diagram Grammar, Proc. IEEE ISCAS’98 VI (1998), 183-186.
$\mathrm{M}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}- \mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}/\mathrm{m}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{i}$$H_{1}\Rightarrow,$$Hp_{2}12$と$H\Rightarrow,$$H_{2}\Rightarrow \mathrm{p}_{2}\mathrm{p}_{1}’ H21$

が $G$ の (生成的) 導出な

らば $H_{12}=H_{21}$ となるとき動的に合流的である (dy-namically confluent) という.

口

命題 4

NCE 文脈依存グラフ文法$G=(\Sigma_{n}, \Sigma_{t,n’ t}\Gamma\Gamma, S, P)$は静的に合流的であれば, 動的に合流的である

5

口

おわりに

非常に–般的な埋め込みメカニズムを持つ NCE 文脈依存グラフ文法を定義した. 次に, この文法に対してプロダクションコピーの合成と合流性について議論した. 本論文で議論した NCE 文脈依存グラフ文
法は, ブロック線図 $[9, 10]$ とシグナルフローグラフ$[11, 12]$ のグラフ構文規則を定式化するために実際に用いられ, その理論的および実用的有効性が示されて[10] Kobayashi, S., Adachi, Y., Tsuchida, K., andYaku, T., Attribute Block Diagram Grammar and
Its Application, IFAC World Congress’99 (1999),(to appear).
[11] 小林, 安達, 夜久, シグナルフロ一グラフのためのグラ
フ文法, 信学技法, COMP98-22, (1998), 9-16.
[12] 中島, 小林, 安達, 属性シグナルフローグラフ文法,
第 57 回情報処理学会全国大会講演論文集 (1) (1998),
27 本 275.

, A., Defining and Pars[13] Rekers, J., anding Visual Languages with Layered Garph Grammars, Journal of Visual Languages and Computing(1996), 27-55.
$\mathrm{S}\mathrm{c}\mathrm{h}\tilde{\mathrm{u}}\mathrm{I}\mathrm{r}$[14] Zhang, D., and Zhang, K., Reversed Graph
Grammar: A Specification Tool for Diagrammatic VPLs, Proc. IEEE Symp. Visual Languages(1997), 284-291.