Context-Free Tree Grammar - formallang.memo

"Mappings and Grammars on Trees" (1970)

Tree Transducer を提案すると同時に Context-Free Tree Grammar（と今では呼ばれているシステム）を提案した論文。

• William C. Rounds
• Mathematical Systems Theory, vol. 4, pp. 257-287
• http://dx.doi.org/10.1007/BF01695769

Context-Free Tree Grammar (CFTG) とは

G = <Σ,N,S,R>

• Σ : アルファベット（要は木のノードのラベル。ranked = ラベルによってこの数は固定）
• N : 非終端記号（ranked）
• S ∈ N : 開始記号。rank=0
• R : 導出規則
  • A(x1,...,xk) → RHS where RHS ::= σ(RHS,...,RHS) | A(RHS,...,RHS) の集まり

S から始めて非終端記号がなくなるまで書き換えを続けてってできたものが出力木、という形で木言語を定義する。

Context-Free Grammar(文字列) との関係

全ての非終端記号を rank=1 か rank=0 にすると文字列の文脈自由文法になる

S→aSa | bSb | a | b

は

S→S1($)
S1(x) → a(S1(a(y))) | b(S(b(y))) | a(y) | b(y)

こういう。

Macro Grammarとの関係

文字列 ⇔ 木 に関して

• Context-Free Grammar の導出木 ⇔ Regular Tree Grammar
• Macro Grammar の導出木 ⇔ Context-Free Tree Grammar

のような対応関係になっている。一段ずれたところに対応関係。

IO と OI

Macro Grammar 同様に、IO と OI の区別は本質的に重要。[Rounds70] では OI だけ考察されている。IO と OI をCFTGに最初に持ち込んで議論したのはどの論文だろう。。。

Pushdown?

文字列のContext-Free Languageはプッシュダウンオートマトンと対応することが知られている。木構造の場合は？いくつかの結果がある。

トップダウンのプッシュダウンツリーオートマトン。かなり自然なモデル。OI-CFTGと対応する。

• "Pushdown Tree Automata" (1983)
• Irène Guessarian
• Mathematical Systems Theory, vol. 16, pp. 237-263
• http://dx.doi.org/10.1007/BF01744582

ボトムアップ。これもOI-CFTGと対応する。左辺にnonlinearな変数をおいて木と木の同値性をチェックできるモデルになっているんだけどちょっと強力すぎやしないかなあ。

• "Tree Pushdown Automata" (1985)
• Karl M. Schimpf & Jean H. Gallier
• Journal of Computer and System Sciences, vol. 30, pp. 25-40
• http://dx.doi.org/10.1016/0022-0000(85)90002-9

IO-CFTGに対応するプッシュダウンツリーオートマトンは知られていない？

---