トップページ⇒math
110コメント55KB

グラフ文法を語り尽くす

■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん2006/09/22(金) 16:14:17
誰かグラフ文法に詳しい人いない？
NLCとかNCEとか。
興味あるけど、ぐぐってもあまりいい資料が見つからないので、何でもいいから知っていることを語ってください。
0002１３２人目の素数さん2006/09/22(金) 16:19:18
しんどけ
0003１３２人目の素数さん2006/09/22(金) 16:55:18
>>1
まずきみが知っていることを解説してみてくれ
000412006/09/22(金) 16:55:45
よくわからないけど、例えば迷路を無向グラフで表したときに、スタートからゴールまで1つしか道筋のないもの、っていうのをグラフ文法で表現できたりするのかな？
どうもまだ生成規則の書き方からして、イマイチ想像できない。
000512006/09/22(金) 17:08:31
>>3
とりあえず、チョムスキーの言語理論とか、オートマトン理論とかから出てきた生成規則による文法の考え方を、グラフに拡張したもの、っていう認識です。
グラフ文法の立場からすると、文字列に適用される文法は、1方向にのみ伸びていくグラフって見るらしいです。
NLC文法の左辺は1つのノードに限定されてて、つまりチョムスキー階層でいうと、文脈自由文法に相当してて、PSPACE完全な言語を生成できるって聞いたことあるような、ないような。
000612006/09/22(金) 17:16:23
NLCはNode-label-controlled文法といって、ノードに「ラベル」をつけて、そのラベルに応じてグラフに置換する。
で、文法（生成規則）に基づいてどんどんでかくしていけて、ターゲットとするグラフが文法規則で表現できるかどうか、を分析するものだと思う。
NCEはNeighborhood-controlled-embedding文法といって、「ラベル」ではなく、ノード自体の一意性を元に文法規則を作るもの。
つまり、異なる二つのノードが同じラベルを持つことのできるNLCとは、その点で違う。
でもNLCの生成する言語は、NCEの生成する言語と等しいことがわかっている。
000712006/09/22(金) 17:20:40
と、まあ、言葉ばっかりで書いてても、結局根本的なことがわからないんです。
>>4に挙げたような命題でも、どう手がかりを見つけていいか見当もつかない。

あと他にも、「三角形だけから成るグラフを生成するには？」とか「平面グラフのみを受容する文法は？」とか単純そうなものを考えても、具体例がわからないんです。
0008１３２人目の素数さん2006/09/22(金) 17:28:59
どうしても理系カテの板でやりたいなら情報学板いけ
0009１３２人目の素数さん2006/09/22(金) 17:30:29
分からんかったら、分からん言えｗｗｗ
001012006/09/22(金) 17:50:08
>>8
情報学板とは？

>>9
すいません。わかりませんorz
0011１３２人目の素数さん2006/09/22(金) 18:19:51
情報学板
http://science4.2ch.net/informatics/
001232006/09/22(金) 18:25:38
解説ありがと。内容はよくわかんないけど、
ただの思いつきで建てたスレじゃないことは伝わった。
001312006/09/22(金) 18:39:33
>>11
そんな板あったのか。しかも最近できてたとは。
移動すべきか判断できてないので、ちょっと見てきます。

>>12
いえいえこちらこそ。
あんたいい人ね。
0014１３２人目の素数さん2006/09/22(金) 18:48:35
そういえば、その昔、ニフティのプログラマーズフォーラムに、
なにかっていうとグラフ文法がどうだとかタイプ理論がどうだとか
訳わかんないこと言い出すやつがいたっけ
そっちにあたってみたらどうだい
0015１３２人目の素数さん2006/09/22(金) 23:24:26
>>10
>>9は>>8に対して
001612006/09/23(土) 08:39:28
>>14
探してみたけど、どうやら閉鎖？みたいな感じでした。

>>15
そうですたか・・・

えーっと、情報学板に関しては、まだできたばっかって感じで混沌としてるので、ちょっと見合わせ。
たしかに計算機言語理論に関しては完全に計算機科学なので情報学板行きだと思うけど、グラフ文法は（ぱっと見だけど）もうちょい数学色が濃いような気がしてます。
0017１３２人目の素数さん2006/09/23(土) 13:40:59
おれはこういう話題は数学板で良いと思うんだけど、
数学板は純粋数学しか認めない人が多いんだよね。
0018１３２人目の素数さん2006/10/03(火) 03:09:29
age
001912006/10/03(火) 09:46:50
やっぱりちょっとマイナーな分野なのかな？
とりあえずいい定義のしかた見つけたので書いておきます。

まず文法を定義する前に、グラフ一般に関する諸定義。
グラフZを次のように定義する。
Z = (V, E, Σ, Γ, φ)
ただし、Vはノードの集合、Eはエッジの集合、Σはノードに付けるラベル（ノードラベル）の集合、Γはエッジに付けるラベル（エッジラベル）の集合、φ:V→Σはノードをラベル付けする関数とする。
またエッジの集合Eは、E ⊆ {(v, λ, w) : v, w∈V, v≠w, λ∈Γ}である。
ただし、v, wはノード、λはノードラベルである。

より一般的な問題を扱うために、以下のものを定義する。
V[Z]はグラフZに含まれるノードの集合を表し、E[Z]はグラフZに含まれるノードの集合を表すものとする。
φ[Z](v)は、Zに含まれるノードv(∈V[Z])のラベルを表す。

GR[Σ,Γ]はΣに含まれるノードラベルとΓに含まれるエッジラベルを任意に組み合わせて構成することのできるグラフの集合とする。
すなわち、上述のグラフは、Z∈GR[Σ,Γ]となる。
002012006/10/03(火) 09:50:26
eNCE文法Gを次のように定義する。
G = (Σ, Δ, Γ, Ω, P, S)
ただし、Σはノードラベルのアルファベット（集合）、Δは終端ノードラベルのアルファベット、Γはエッジラベルのアルファベット、Ωは終端エッジラベルのアルファベット、Pは生成規則の集合、S (∈Σ−Δ)は開始ノードラベルとする。
また、Σ−Δを非終端ノードラベルと言い、Γ−Ωを非終端エッジラベルと言う。
P = {π : π = (X → Y, ψ)}と表し、πは生成規則、X (∈Σ−Δ)は左辺のノードラベル、Y (∈GR[Σ, Γ])は右辺のグラフ、ψ(⊆V[X]×Γ×Γ×Σ)は規則適用の際の連結関係を表す。

eNLC文法が生成する言語クラスは、eNCE文法が生成する言語クラスの補集合で（注：実際にはeNLC=eNCEが証明されている）、eNCE文法との違いはψの定義の仕方に帰着する。
つまり、eNCEの定義の中で、ψ⊆Σ×Γ×Γ×Σに変更することで、生成規則中のノードの一意性を区別しないeNLCの定義を成す。

NCE文法は、eNCE文法のエッジの書き換え規則を一切省いたものと見なせばよい。
すなわち、
G = (Σ, Δ, P, S)
とし、ψ⊆V[X]×Σとすればよい。

NLC文法は、eNLC文法を定義するためにeNCE文法に加えた変更と同様の変更をNCE文法の定義に加えればよい（注：実際にはNCE=NLCが証明されている）。
つまり、ψ⊆Σ×Σとする。
002112006/10/03(火) 10:01:14
ごちゃごちゃしてますが、要は非終端ラベルをグラフに置き換え、そのグラフの中に含まれる非終端ラベルをまたグラフに置き換え、・・・と終端ラベルのみになるまで繰り返すことで、ある特定の性質をもったグラフを生成します。
で、グラフではなくただの文字列に適用される文法の場合は、非終端記号を何も考えずに置き換えればいいのですが、グラフの場合は非終端ラベルの部分にグラフを埋め込む際に、その非終端ラベルから出ているエッジをどうするかっていう問題があります。
その場合に考えなければならないのが、連結関係というやつらしいです。
つまり、置き換える非終端ラベルの近傍に何があるか、に応じて生成規則の適用を考えなければならないということです。
ただ、この「近傍のことまで考える」という点が、いわゆる文脈フリー文法の枠を超えて、文脈依存文法をシミュレートしているのと同じになってしまっていることが問題点になります。
つまり、そのせいで、NLC文法によって生成される一般的なグラフを、逆に解析する問題（つまりパース）は、PSPACE完全になってしまうため、実用性に乏しいことがわかっています。
そこで、NLC文法などにいくつかの制限を加えて、解析にも向いている文法が色々考案されています。
002212006/10/03(火) 10:04:57
と、色々書いてきたけど、たぶんグラフ文法を専門に扱ってる人が見たらつっこみどころ満載なんだろうなぁ。
でもまあ自分自身の勉強のためにも、いったいこのグラフ文法にどんな意義があるのかをもうちょい調べてみます。
とりあえずまだ御託を並べるしかできない、ツライ状態なので。
0023１３２人目の素数さん2006/10/06(金) 03:43:17
>>21
> ただ、この「近傍のことまで考える」という点が、いわゆる文脈フリー文法の枠を超えて、
> 文脈依存文法をシミュレートしているのと同じになってしまっていることが問題点になります。
ほんとに？
002412006/10/06(金) 14:45:08
>>23
レスがついてる！うれしっす。
ちょっとその部分は自信ないかも。
NCEだったら、全部一直線に伸ばせばCSGになるかなぁと思ってたけど、よく考えたらならないな。
でも複数方向にエッジを伸ばせるから、CSGに届く可能性はあると思う。
もうちょいリサーチが必要でした。
0025１３２人目の素数さん2006/10/06(金) 17:11:31
>>24
ＣＦＧになるケースとＣＳＧになるケースがあるような気がする。
002612006/10/07(土) 00:42:52
>>25
NLCもNCEも、任意のCFGをシミュレートすることは可能かと。
問題は、任意のCSGをシミュレートできるかどうか（つまりNCEとCSGはどっちが大きいクラスか、又は比較不可能なのか）ってことだとおもた。
002712006/10/07(土) 00:51:13
あ、ちょっと誤解のないように確認。
NLCとかCFGって言葉は「言語クラス（＝言語の集合）」を表す意味で使ってた。
（もしかして、それ自体間違った用法だったかな・・・？）
「言語」はもちろん形式的に（＝有限個数の規則で）定義された「オブジェクトの集合（＝文字列の集合＝グラフの集合）」。

本当はCFLとかCSLって言うほうが正しいのかな？でも「文法」は「言語」の表現手段に過ぎないわけで、結局同じものを指してるから、それじゃ「言語」を表すか「言語クラス」を表すかってのがうやむやな感じもする。

で、正則言語RL ⊂ 文脈自由言語CFL ⊂ 文脈依存言語CSL ⊂ 句構造言語PSLってことでいいかと。
あと、NLC ＝ NCE ⊂ eNLC = eNCE って感じ。
それで、CFL ⊂ NCEってのは間違いないと思われる。
0028１３２人目の素数さん2006/10/07(土) 00:54:07
>>26
「近傍のことまで考える」⇒ＣＳＧ、とは限らないのではないだろかということ。
逆に、ＣＦＧ⇒「近傍のことは考えてない」のかな？
002912006/10/07(土) 01:04:11
>>28
> 「近傍のことまで考える」⇒ＣＳＧ、とは限らないのではないだろかということ。

その指摘は理解したつもり。
で、もうちょっと調べてみないと断言できない。

> 逆に、ＣＦＧ⇒「近傍のことは考えてない」のかな？

それはそうだと思う。
そもそも文脈自由文法ってのは、「生成規則の左辺は必ず非終端記号１つ」っていう条件があるから、近傍（＝文脈）に依存しないという認識でいいと思う。
書き換える対象の非終端記号をAとすると、

A → （任意の文字列）

って感じで、Aの近傍にあるものを考慮する規則は作れない。
文脈依存文法の規則は、同じく書き換える対象の非終端記号をAとすると、

αAβ → α（任意の文字列）β

って感じで、文脈（ここではαとβ）に依存するけど、文脈自体は書き換えないって意味かと。
0030１３２人目の素数さん2006/10/07(土) 03:25:44
>>29
君の言うグラフ文法とは、
・グラフのノード→２次元言語の文字（もしくは終端記号）
・グラフのエッジ→２次元言語の文字から文字への前から後ろへの一方方向の後続関係
という対応を前提として
・グラフのノードの置き換え→２次元言語の生成規則
という理解でいいの？
0031１３２人目の素数さん2006/10/07(土) 03:30:01
>>30は２次元言語じゃなく１次元言語の間違い。不必要に混乱させたかもしれない。申し訳ない。
ここで、１次元言語で言わんとしているのは、いわゆる普通のプログラミング言語とかでいう言語
のことを、より高次であろうグラフと区別して呼びたいということで、便宜上そう呼ばせてもらった。
003212006/10/07(土) 07:45:55
>>30-31
そういわれてみれば、グラフではなく、いわゆる「普通の」文法って何ていうんだろう？
わからないので、とりあえず１次元文法って言い方させてもらいます。

グラフ文法は１次元ではなく色々な方向に、しかも１つのノードから複数のエッジを伸ばせるので、１次元文法より柔軟っていう風に認識してる。
グラフの１つのノードと１次元文法の１文字との関係は、完全に一致していると考えるのは難しいかも。
むしろ１次元文法の終端記号・非終端記号に対応するのは、ノードにつける終端ラベル・非終端ラベルと考えた方がいいと思う。
003312006/10/07(土) 07:50:12
１次元文法では暗黙のうちに一方向に文字が並んでいることを前提にするけど、そこにちょっとヒネリを入れて、グラフ構造を構成するためにノードとエッジという道具を使って、多次元に配置することができるようにしたのが、グラフ文法って感じ。
（多次元って言い方は数学的にはマズイのだろうか・・・）

で、グラフ文法でも、ノードとエッジを１方向にしか伸ばしていかなければ、１次元文法と同じものを表現できるって話になると思う。
（これに関しては厳密に議論するのはかなり大変だと思うので、飽くまで直感的なレベルだけど）
003412006/10/10(火) 23:04:17
>>23で指摘されたことについてGoogle Scholar等で調べてみたつもりなんだけど、そういうことに触れたものは見つからなかった。
もしかしたらNLCとCSLの包含関係なんて、誰も研究してないのかも・・・。
まあ、それがわかったところで、どうせ現実的な時間内にパースできないintractableなクラスなんで、あんま意義がないのかな？
003512006/10/10(火) 23:13:58
で、それだと結論が空しいので、とりあえず言えることだけ書いてみる。

NLCはPSPACE完全な言語を記述することができる。
CSLもPSPACE完全な言語を記述することができる。
（CFLはPの中）
なので、大まかに言ってNLCとCSLは同程度の言語を記述できると言えるんじゃないかと。

もちろんPSPACE自体が（その他PやNLなどとも同様に）、ある意味で近似的な一面を含んでいるのもあるから、どちらかがどちらかを含んでいる可能性はあるし、比較不可能っていう可能性もあるんだろうけど。
0036１３２人目の素数さん2006/10/11(水) 17:47:36
なにやら難しい話が進行中っぽいけど、トピックそのものは面白そうなんで
まずは>>4なんかを考えてみたけど、どうっすか。

その前に、ノードにラベルをつけるってのは、構文解析前に字句要素を抽出するみたいなノリでＯＫ？
そんな感じで、迷路のスタートとゴールのノードをsとg、袋小路(dead end)をd、袋小路でない交差点(cross)をcと
いうのがすでにラベル付けされているとして、エッジを-で表して、迷路のグラフ文法Mを
M := s-X-g
X := X-Y
X := X-X
Y := Y-d
Y := c-d
ってのはどうよ。
003712006/10/11(水) 18:29:45
>>36
おぉ！そういえば自分で>>4とか>>7みたいな問題提起しといて、そっち方面考えるの忘れてたorz
方針としてはそんな感じっぽい。
M := s-X-g で始めて、規則中にループが一つもなければいい、っていう考え方すれば、たしかに出来そう。
なるほど！
0038１３２人目の素数さん2006/10/11(水) 18:39:53
どうかんがえても>>36は1次元文法です。
003912006/10/11(水) 18:42:06
厳密に考える場合は、それぞれの規則中で、左辺の非終端ラベルのノードにつながっているエッジをどうするかっていう問題もあるかも。
長文書きすぎて情報が埋もれちゃったけどorz
いわゆる「連結関係」っていうやつで（実はこれ、connection relationを勝手に訳したので、本当は違う呼び方だったりして・・・orz）、左辺のノードについてるエッジを右辺のどこにつなげるか、っていう定義を文法の中に含める必要がある。
そうでないと、実際に文法を適用して、決定性的にグラフを派生することができない。
でも、>>36で提示してくれた基本的な方針がわかっていれば、何とかなりそうだね。
004012006/10/11(水) 18:48:29
>>38
直感的に見てみると、
　　　　　　　　　　.X　　　　　X
.　　　　　　　　　　 |　　　　　 |
X　⇒　X-X　⇒　X-X　⇒　X-X　⇒　・・・
　　　　　　　　　　　　　　　　 |
　　　　　　　　　　　　　　　　.X
っみたいな派生が可能かなぁと思ってみた。
0041１３２人目の素数さん2006/10/11(水) 19:22:34
>>39
連結関係などを考えずとも、>>36の場合だと右辺で書き換え規則に合致しなかったエッジは
そのまま左辺のノードへ付け替えるというので構わないのでは？
問題は決定性でしょう。
>>36のグラフ文法でエッジの付け替えの順序が変わると、その順序によって文法Ｍが
受理したり受理しなかったりという例は考えられるでしょうか。
004212006/10/11(水) 19:36:07
>>41
> そのまま左辺のノードへ付け替えるというので構わないのでは？

というわけにはいかないような希ガス。
つーか、左辺のノード「へ」付け替えるってことの意味がよくわからないかも。
一回の規則適用のときには、左辺のノード（およびそこにつながるエッジ全て）を消滅させて、そこに右辺のグラフを埋め込まなきゃならないので。（文字列の生成と同様に）

>>39で言った「決定性」は、エッジをどこにつなげるかが決定できないという意味なので、↑がはっきりしないと何とも言えないです・・・。
004312006/10/11(水) 19:56:44
ごめん、>>41を読み違えてた。
ボトムアップでパースする場合を考えてたのね。
俺はパースのことは考えず、逆にMから生成する方向で考えてた（この場合だとトップダウンでパースって言っても大差ないけど）。
ちょっと再考中・・・
004412006/10/11(水) 21:03:04
とりあえず>>36の文法だとXが無限再帰してるので、
X := c
も加えてみる。
エッジのつながり方を何でもかんでも許容してしまうと、問題が起こるっぽい。
例えばターゲットとしてこんなグラフを考えた場合、
.　　　　 c
　　　 ／ ＼
s---c----c---g

　　　　　　　　　　　　　　　X.
　　　　　　　　　　　　　　　 |
M　⇒　s--X--g　⇒　s--X--g

　　　　　　　　　 X　　　　　　　　　　　　　　　 c
　　　　　　　　／ ＼　　　　　　　　　　　　　／ ＼
　　⇒　s---X----X---g　⇒⇒⇒　s---c----c---g

という派生が可能なので、ループを含むグラフを受理してしまう。
X := c の代わりに、X := Y や X := Y-Y などにしても同様のループ構造が作れてしまう。

まあそういうわけで、たぶん一番の難点は１行目から２行目にうつるときにエッジが分裂してるところだと思う。
このエッジのつなげ方をもうちょい制限するのが連結関係だと考えてください。
004512006/10/11(水) 22:21:29
>>36のアイデアをもらって、NLCで書いてみた。
ちょっと連結関係の方は>>20と違う書き方になってしまうけど・・・
G = (Σ, Δ, P, C, M) ただしCは連結関係で、C⊆Σ×(2^Σ)で表す。
アルファベットは、Σ = {M, X, Y, Z, s, g, c, d}, Δ = {s, g, c, d}

規則の集合Pは以下の通り。
M := s-g
M := s-X-g
X := X-Y　　 # sとgの間を　s-X-Y-Y-Y-・・・-Y-g という形で伸ばす
X := X-Z　　 # sのすぐ隣のXから複数方向にZをにょきっと出す
X := c　　　　# sのすぐ隣のXは袋小路にならないのでcに変える
Y := Y-Z　　 # Yの部分を複数方向にZをにょきっと出す
Y := c　　　　# Yは袋小路にならないのでcに変える
Z := Y-Z　　 # 分岐したZを、Y-Y-Y-・・・-Y-Z という形で伸ばす
Z := d　　　　# Zは常に末端（袋小路）なので、dに変える

で、最後に連結関係
C = {
　(X, {s}), (Y, {X, Y, Z, g, c, d}), (Z, {}),
　(s, {}), (g, {}), (c, {X, Y, Z, s, g, c, d}), (d, {Y, c})
}
となります。
あ〜〜〜、ごちゃごちゃしすぎて説明不能ｗ

連結関係の部分だけ、注釈つけときます。
(X, {s})というのは、Xが右辺に現れた場合、規則を適用する際に、左辺の近傍に出現するsは、全て右辺中のXにつなげる、という意味です。
ややこしい・・・。
NCEで書いたらもっとすっきり書けたのかも。
0046休憩時間2006/10/11(水) 22:35:17
頭の体操ゲーム。
癒されるよ！！
http://www.hiyoko-team.com
0047１３２人目の素数さん2006/10/11(水) 22:40:16
↑無関係な宣伝
004812006/10/11(水) 22:43:23
しまった。
>>45は失敗。
X := X-Z
の規則を適用するときに、sじゃない側のエッジが切れてしまう。

完全に破綻しましたOTZ
0049１３２人目の素数さん2006/10/11(水) 23:21:02
なんか、>>1は自分で作ったルールに自分で首締められてる感じだね。
>>36は「迷路で、袋小路を埋めていくと、最後に残るのが答え」っていう
迷路のアルゴリズムの一番オーソドックスなやつでしょ。
それをそのまま素直に表現できないの？
0050１３２人目の素数さん2006/10/11(水) 23:34:50
連結関係で躓いているようだけど、SPOでなくDPOでやることは検討してみた？
005112006/10/12(木) 00:05:27
>>49
全くその通り。
何かしら意味のあるグラフ文法を自分で書くのが初めてだから、定義とにらめっこしながら頭悩ませてる感じ。
慣れてしまえばもっとスラスラ書けるのだろうか？

>>50
SPOとDPOという言葉は初耳で、今調べてみた。
Single-Pushout approach と Double-Pushout approach だよね？
有益な情報ありがとう！
自分でも調べてみてるけど、もし時間あったらちょっと解説してもらえるとうれしいです。
005212006/10/12(木) 00:31:31
NCEで書けた！！希ｶﾞｽ・・・
Σ = 大文字と小文字のやつ。Δ = 小文字のやつ。
P = {π : π ⊆ V[X] × (2^Σ)}で書いてみた。

M := s-G , (s, {}), (G, {})
C := C-D , (C, {s, g, c, d, G, C, D}), (D, {})
C := c　　 , (c, {s, g, c, d, G, C, D})
G := C-G , (C, {s, C}), (G, {})
G := g　　 , (g, {s, C})
D := C-D , (C, {c, C}), (D, {})
D := d　　 , (d, {c, C})

Cは後々cにする非終端ラベルで、任意個数のDをにょきっと出せる。
Gは後々gにする非終端ラベルで、G自身が末端になるように正解ルート上にCを伸ばしていく。
Dは後々dにする非終端ラベルで、D自身が末端になるように正解ルート以外の全域にCを伸ばしていく。
005312006/10/12(木) 00:41:22
どうでもいいけど一部訂正。
× P = {π : π ⊆ V[X] × (2^Σ)}
○ P = {π : π = (X := Y, ψ), ψ ⊆ V[Y] × (2^Σ)}
>>20も間違ってるな・・・orz
005412006/10/12(木) 00:45:50
http://en.wikipedia.org/wiki/Graph_rewriting
ここ読んでDPOを理解したい気持ちも去ることながら、そろそろ寝るかもです。
おやすみなさい。
レスしてくれた人たち本当ありがとう。
0055１３２人目の素数さん2006/10/12(木) 04:13:26
DPOとSPOの解説をここでするのははっきり言って無理。

簡単に言うと、生成規則に書き換えのための「糊」の役目をする部分があるのがDPO。
糊には代数的な制約である"gluing condition"があってそれがDPOの存在意義といっても良い。

一方、左辺と右辺の書き換えを直接行うように考えるのがSPO。

DPOかSPOかというのはあくまで代数的な理論構築のための方法論という
意味合いの方が強く、具体的なグラフの書き換えではあまり表にはでて来る話では
ないのではないかと思うが。なんで>>50はこんな話を持ち出したんだか。

どっちにしろ、この説明じゃあんまりよく分らないでしょ。
0056１３２人目の素数さん2006/10/12(木) 13:32:28
ところで、>>49に>>36は迷路のアルゴリズムをグラフ文法で表現したというような指摘があるが、
このアルゴリズムはもともとその迷路をグラフで表したら閉路がない単純接続グラフであることが
前提になっているんじゃないか？　袋小路を埋めて行き残った経路を迷路の解とするわけだから、
もし閉路や独立した通路がある場合には、解にその部分が含まれてしまう。逆に、閉路を
どっち回りに巡るかの組み合わせ分だけ迷路の解が存在することになる。

ならば、>>36がループを許容するグラフ文法になってしまっているのは当然ということなる。
これまでの流れからすると、>>1が>>7で考える迷路とは閉路が無いグラフになることを暗黙的に
前提しているのでいいのだよな？　＞１

少し視点を変えると、閉路が無い単純接続グラフとは、つまりどこかの頂点をルートにするツリーで
あるともいえる。つまり、迷路を表すグラフ文法とは、ツリーを表現するグラフ文法の一種であると
考えることも可能ということだ。

よって、方針として、迷路のグラフ文法を考える前に、まずはツリーを表すグラフ文法を考えた方がいいのではないか？
0057１３２人目の素数さん2006/10/12(木) 15:20:39
どう考えてもDPOはCSGです。
0058１３２人目の素数さん2006/10/12(木) 16:35:43
>>57
そりゃそうだ。
lhsとrhsに共通部分があるってことだし。
lhs-共通部分が接続関係ってことだし。
005912006/10/12(木) 20:49:39
>>55
うーむ、けっこう難しそう。
生成規則の中に、左辺と右辺の共通する「何か」を「糊」と呼んで、書き換えに利用していくような感じなのかな？
とりあえず何を何に書き換えるのかっていうのに混乱して、うまく理解できなかった。
でも解説ｻﾝｸｽ！
グラフ文法には直接的には役に立つものじゃなさそうっていうことなので、そういう概念もあるってことは頭の片隅に置いておこうと思います。
006012006/10/12(木) 20:59:18
>>56
たぶん、前半の話は「閉路（←今までループって呼んでました・・・orz）のないグラフをいつの間に前提にしてたんだ？」ってことかな？
実は>>4で書き込んだときに「１つしか道筋のないもの」って言っていたから、ずっとそれを前提にしてしまっていた。
誤解させてしまってたみたいなので、もう一回命題を明言しとけばよかったかも。ｽﾏｿ

で、後半のツリーのことなんだけど、たしかにツリーは閉路のないグラフって見れば色々な方面で単純化できると思うんだけど、「グラフ文法を使って構築する上で、ツリーは簡単に扱える対象なのか」ってことが、まだ自分の中ではっきりしていんだよなぁ。
でも、おもしろそうなので、

ツリーを受理するNLC文法（NCE文法）

をどうやって書けるかっていうのも考えてみたいかも。
それができたら、今回の「閉路のない迷路」にも応用がきく可能性もあるかもしれないし。
0061１３２人目の素数さん2006/10/12(木) 21:06:23
>>57-58
CSG⊂DPOみたいに見ちゃっていいってことなのかな？
もしかして実はCSG=DPO？？

あと、「接続関係」って言い方してるけど、そっちのほうが日本語としては普通の言い方？
もしそうなら、これからはそっちの言い回ししたいと思う。
006212006/10/12(木) 21:11:05
誰も気にしないかもしれないけど、>>52を書き換えの順序に依存しないようにするために、少し訂正。
× G := C-G , (C, {s, C}), (G, {})
× G := g　　 , (g, {s, C})
○ G := C-G , (C, {s, c, C}), (G, {})
○ G := g　　 , (g, {s, c, C})
006312006/10/12(木) 22:15:44
ツリーを生成するNCEは一瞬でした・・・
でも、すぐ思いついたのは迷路のやつをやってたおかげかも。

N := N-N , (左のNに全部つなげる), (右のNには何もつなげない)
N := n　　 , (nに全部つなげる)
006412006/10/12(木) 22:49:25
参考までに、NCEの場合は生成規則を従来の書き方ではなく、こんな書き方もできる。
下の図は>>63のNCE文法。
こっちのほうが直感的でわかりやすいかも。
2chでグラフ文法を表現するのは、ちょっとツライな。

　　┌────────┐
　　│N（←これが左辺)　│
N__.│___　　　　　　　　　　│
　　│　　＼　　　　　　　　│
　　│　　　　N─N 　 　　.│
　__│___／　　　　　　　　 .│
n　.│　　　　　　　　　　　 │
　　└────────┘

　　┌────────┐
　　│N　　　　　　　　　　 │
N__.│___　　　　　　　　　　│
　　│　　＼　　　　　　　　│
　　│　　　　n　　　　　　 .│
　__│___／　　　　　　　　 .│
n　.│　　　　　　　　　　　 │
　　└────────┘
0065１３２人目の素数さん2006/10/13(金) 01:18:27

　　　　 N. 　　　　 N
　　　　　| 　　　　／ ＼
N　⇒　N 　⇒　N----N
006612006/10/13(金) 01:33:10
>>65
それは>>63の文法でループができてしまう、と言いたいの？
>>63の一つ目の規則（N := N-N）では、「右側のNには何もつなげない」と書いたつもりなんだけど。
>>65の図で言うと、２つ目の派生で新たに生成されたNには、（規則の右辺で明示されているものを除いて）何もつなげないということ。
0067１３２人目の素数さん2006/10/13(金) 01:35:16
>>65
６３の
>(左のNに全部つなげる), (右のNには何もつなげない)
って部分がループを回避してるんじゃないの？
0068１３２人目の素数さん2006/10/13(金) 01:55:36
なにやらこんがらがってるみたいだけど生成規則ｐ_i: L_i→R_iで∃i L_i∩R_i≠φでないとツリーは表現できないよ。
0069１３２人目の素数さん2006/10/13(金) 02:40:31
まじで？
>>1がNCEとかいってるのは、Naglのでしょ。
ならば、depth-1 CFGのはずだから>>68のいうことと矛盾してない？
0070１３２人目の素数さん2006/10/13(金) 02:43:14
>>68
∀i L_i∩R_i＝φでも

S → A-B （Sの隣接は全てAのみにつなげる）
A → S　（Aの隣接は全てSにつなげる）
B → S　（Bの隣接は全てSにつなげる）
S → n　（Sの隣接は全てnにつなげる）

ってやったらツリーになるのでは？
0071１３２人目の素数さん2006/10/13(金) 02:53:44
connection instructionがあったらL_i∩R_i＝φにならないじゃん、ってことなんじゃね。
っていうか、68はNRとHRがごっちゃになっとるような希ガス。
1はあくまでNRで考えてるわけで、そうでない話を持ち出すとよけいにこんがらがる。
0072１３２人目の素数さん2006/10/13(金) 03:16:43
オレもツリーのグラフ文法を考えたぜ！

Ｎ　：＝　Ｎ　−　Ｎ　（Ｎがツリーになるようにつなげる）
0073１３２人目の素数さん2006/10/13(金) 09:28:50
>>72
逝ってよし
007412006/10/14(土) 04:38:37
ちょっと>>68-71の話についていけてないんですが・・・
>>7の「三角形だけから成るグラフを生成するには？」っていうのは、NLCやNCEじゃ表現できないかも。
例えば、１つのエッジを共有する無限個の三角形を考えた場合、共有しているエッジとは別のエッジを１つ選んで、そこに三角形を増やそうとすると、どうしても生成規則が書けない。
なぜかというと、有限個の規則では、無限個のノードの中から１つだけ接続するノードを選ぶように設定できないから。
007512006/10/14(土) 04:41:51
エッジの共有は一切許さないけど、ノードの共有は許すようなのならこんな感じかな？

　　　　　 N
　　　　／　＼
N := N───N　　３つの中の１つのNに全部つなげる

N := n　　　　　　　 nに全部つなげる
007612006/10/14(土) 04:44:29
あとは、エッジを共有するようなものに関しては、三角格子状にうまく並ぶような接続グラフっていうのを考えてみたけど、できそうでできない感覚と奮闘中orz
0077１３２人目の素数さん2006/10/14(土) 13:41:19
>>76
>>7の「三角形だけからなるグラフ」だけど、言い換えると「辺の長さが４以上の閉路がない」ってことなわけで、
>>4以来問題となっているツリー構造の問題と多かれ少なかれ関係しているのではないだろうか。
そういうわけで、閉路の有無についてもっといろいろな方向から光をあててみたらどうか。
0078１３２人目の素数さん2006/10/14(土) 16:20:24
どんなグラフ文法も一発で解き明かす大天才がまたやってきたぜ！
これが三角形だけを生成するナイスなグラフ文法だ！！

　　　　　 N
　　　　／　＼
N := N───N　　（辺の長さが３になるようにつなげる）
007912006/10/14(土) 23:57:09
>>77
なるほど！確かに。
あと、今までは途中途中の文形式の中に、常に三角形を形作らないとまずいような感じで考えていたけど、非終端記号だったらツリー等のときと同様に、にょきにょき伸ばしていってもいいわけだよね。
新たな方面で考えてみよう！

>>78
画期的ですね。
008012006/10/15(日) 00:07:50
三角形をごちゃごちゃ考えてたら、なぜか完全グラフを生成する文法が書けた。
（今回は開始ラベルはSです。今までも一番上の規則の左辺が開始ラベルってことで問題なかったと思います。）

　　　　　 N
　　　　／　＼
S := N───N

N := N───N　　両方のNに全部つなげる
N := n　　　　　　　 nに全部つなげる

よく考えてみたら完全グラフって、任意の３点が三角形になっているわけだから、ある意味で三角形だけから成るグラフの一種と言えるかも。
とりあえず自分で言っておいて、「三角形だけから成る」ってどういう状態だかずっと疑問だったけど、>>77で言われてはっきりした。
「一周が4以上の閉路を持たない」かつ「全てのノードは閉路の一部である」
って条件にすればいいかも。
（一応、２ノード間での相互ループはナシで）
008112006/10/15(日) 00:18:43
あれ、完全グラフってノードが１個か２個の場合でもいいんだっけ？
それだったら
N := N───N　　両方のNに全部つなげる
N := n　　　　　　　 nに全部つなげる
って書くだけで十分だった。
Nが開始ラベル。
0082１３２人目の素数さん2006/10/15(日) 15:32:54
先は永そうだが、がむばってくれたまへ。

閉路ぐらいじゃ実用性からは程遠いが、
bi-partiteグラフをどう表現するかというあたりへ
到達できれば一皮剥けるぞ。
0083１３２人目の素数さん2006/10/15(日) 16:44:09
どんなグラフ文法も一発で解き明かす大天才がまたまたやってきたぜ！
これがバイパティテグラフを生成するちょーナイスなグラフ文法だ！！

N := f(N)　　（おっぱい）
0084１３２人目の素数さん2006/10/15(日) 23:30:50
>>83
逝け
008512006/10/16(月) 00:26:23
いかん、三角形一般のグラフ文法はできそうにない・・・。
でも、ちょこちょこアドバイスとかもらえたり、知恵をもらったりできるのが、何気にかなりうれしいです。
ちょっと次の１週間忙しくなるので、あまり来れなくなるかも。
このスレどんどん落ちていきそうだなｗｗｗ
008612006/10/16(月) 00:29:36
個人的な感想としては、NLCはちょっと面倒臭いイメージ。
接続関係で同じラベルは否応なく全部つなげなきゃいけない圧迫感がツライ。
NCEのほうがずっと直感的にわかりやすい。
しかもNLCもNCEも結局は同じ言語を記述可能なことがわかっているから、NCEは最高です。

エッジにもラベルをつけたeNCEというのもあって、こちらのほうが多くの言語を表現できる上に、パースにかかるコストはPSPACE完全で一緒なので、さらにベターなのかもしれない。
でも、エッジラベル付だと言語設計の面倒臭さはさらに高まりそう。
（三角形の問題はeNCEなどの方面でも考えてみることを検討中）
008712006/10/16(月) 00:39:12
ここまで来ておいて今更だけど、NLCもNCEも現実的なリソースでパースできるアルゴリズムは未だ知られていない。

NLCに制限を加えたグラフ文法に以下のようなものがあるらしい（NCEバージョンもある）。
・NB-NLC (Nonterminal-bounded NLC)
　導出中の文形式における非終端ラベルの数を、定数個に制限。
・B-NLC (Boundary NLC)
　非終端ラベルが一切隣り合わない。
・A-NLC (Apex NLC)
　接続関係で非終端ラベルを隣り合わせない。
・Lin-NLC (Linear NLC)
　導出中の全ての文形式で、非終端ラベルが常に１つしかない。

これらの文法のパースはNP完全。
依然としてtractableではない。
0088１３２人目の素数さん2006/10/16(月) 00:49:09
パースをtractableにするには、接続グラフのみを受理することにしたり、ノードの次数の最大を定数個に制限する（パース中にある次数を超えたら拒否する）など。
接続グラフに限らなくても、接続部分の個数を定数個またはlog nに制限することでもおｋらしい。
（nはノードの数）

例えば、B-eNCEで接続部分の個数をlog nに制限、且つ次数を定数個に制限すると、パースはLOGCFL完全でできる（Lin-eNCEだとNL完全）。
NCに含まれているので、並列計算ではかなり高速でパースできる。
もちろんPに含まれているから、並列計算でなくてもtractable。
008912006/10/16(月) 01:01:36
すんません、88は俺です。

というわけで、１週間ほど休憩。
三角形は引き続き考える予定。
あと>>82のbi-partiteグラフも考えてみたい。
今後はパースが現実的にできるような言語設計の仕方も工夫できたらいいかも。
0090１３２人目の素数さん2006/10/16(月) 04:06:28
数学は数学だが、情報系だな。
0091１３２人目の素数さん2006/10/19(木) 02:47:22
age
0092１３２人目の素数さん2006/10/24(火) 11:25:50
age
009312006/10/25(水) 07:22:37
おひさしぶりです。
誰かageてくれてる人がいる！感謝感激です。

>>90
たしかに、理論の背景にあるのは情報系の由来だね。

えっと、知人との会話の中から思わぬことを指摘されてしまった。
迷路で１つしか正解ルートがないってのは、「閉路が一つもない」ということではなく、「正解ルート上に閉路が１つもない」だけであって、分岐先には閉路があっても問題ないのでは、とのこと。
たしかにそうだｗ
ちょっと考えてみることにします。
0094１３２人目の素数さん2006/10/31(火) 02:16:44
っていうか、>>1不在の間せっかくアゲてあげてたんだから、もうちょっとなんか書け。
0095１３２人目の素数さん2006/11/04(土) 18:53:49
>>93
わざと間違った方にいって、閉路をぐるっと回って
元に戻ったら？
0096１３２人目の素数さん2006/11/10(金) 10:13:14
age
009712006/11/10(金) 14:29:14
>>94 >>96
最近全然顔だしてなくて申し訳ない。
今週中には何かしら書けるようがんがります。
今はハイパーグラフ（エッジが相手にするノードが２つであるという条件をなくして、いくつのノードでも関連付けられるようなグラフ）を扱う文法（CFHGやHH）を少しずつ読み解いてます。
ただ、CFHGの元ネタにあたる論文が、思いっきり数式＆論理で埋め尽くされてて、ちょっとおいらの脳ミソがオーバーヒート気味ですorz

>>95
もともとの命題が曖昧だったので混乱を招いてｽﾏｿ。
とりあえず直感的には、迷路の「間違った道」の先に閉路があったとしても、正解ルートが１つしかないと言えると思う。
厳密さを求めるなら、迷路の正解ルートというのは「同じノードを2回通ってはいけない」ってことを条件として加えるべきだったかも。
0098１３２人目の素数さん2006/11/11(土) 12:16:41
>>4の設問に対する３６解は「袋小路を取り除いていくと最後に迷路の解が残る」というものだ。
ここで孤立した閉路が問題となるのなら、さらに「閉路も取り除く」というアルゴリズムを追加すれば良い。
これで迷路解に属さない分岐路上の袋小路と閉路はまとめて排除できるはず。
あとは、迷路解上に閉路が含まれる場合だが、「袋小路排除」＋「閉路排除」で生成された暫定的な
迷路解に、その後で「迷路解には任意個の閉路を追加可能」とすれば解決するのではないだろうか。
どうだろうか。
0099１３２人目の素数さん2006/11/14(火) 01:38:03
>>56以下
余計な情報かもしれないが，
木を定義する文法は「木文法」といって別に研究されている．
・参考リンク：Tree Automata Techniques and Applications:
http://www.grappa.univ-lille3.fr/tata/

こちらは木オートマトンとの関連で調べられていて，
最近XML分野（とくにXMLスキーマ）への基礎付けと応用
で割と盛んに研究されている．

それにしてもグラフ文法（書き換え系）
はカテゴリ論の話が出てくることが多いので
わけわからなくなるなあ.

自分は数学ができない情報系だけど．
Robin Milner：
http://www.cl.cam.ac.uk/~rm135/
とかもハイパーグラフ（カテゴリ）を並行プログラミングの基礎理論に
応用しているらしいが，論文読むのが苦痛で仕方がない．
0100１３２人目の素数さん2006/11/14(火) 07:26:44
これって無限なグラフ関係ありますか？
0101１３２人目の素数さん2006/11/14(火) 10:24:19
99の内容を見たわけじゃないが、グラフかどうか関わらず
文法の理論の一般論として、生成されたグラフが無限と
無関係なことは考えにくいと思うけど…。
0102１３２人目の素数さん2006/11/22(水) 07:21:27
age
0103１３２人目の素数さん2006/12/04(月) 09:57:17
あげ
0104１３２人目の素数さん2006/12/18(月) 15:57:38
あげ
0105１３２人目の素数さん2007/02/05(月) 17:01:50
567
0106１３２人目の素数さん2007/03/11(日) 20:34:24
266
0107１３２人目の素数さん2007/06/25(月) 07:43:40
572
0108１３２人目の素数さん2007/08/30(木) 10:38:41
http://www.asahibeer.co.jp/enjoy/hapiken/maian
0109１３２人目の素数さん2007/09/09(日) 04:35:13
.
0110１３２人目の素数さん2007/10/30(火) 12:42:55
126
■ このスレッドは過去ログ倉庫に格納されています