"Generalized^2 Sequential Machine Maps" (1970)
文字列に対する有限状態変換器Generatized Sequential Machineを、一般のalgebraに拡張した変換モデルを提案。今で言う Top-Down
Tree Transducer。
"Mappings and Grammars on Trees" (1970)
同時期にTop-Down Tree Transducer（と今では呼ばれているシステム）を提案した論文。Algebraと言わないでTreeと言ってくれているので素人的にはどちらかというとこっちの方が読みやすい気がする。同時に
Context-Free Tree Grammarを提案していることでも重要。
Top-Down Tree Transducer とは
T = <Σ,Δ,Q,q0,R>
- Σ : 入力アルファベット（要は木のノードのラベル。ranked = ラベルによってこの数は固定）
- Δ : 出力アルファベット（要は木のノードのラベル。ranked）
- Q : 状態集合
- q0 ∈ Q : 初期状態
- R : 導出規則
- <q,σ(x1,...,xk)> → RHS where RHS ::= δ(RHS,...,RHS) | <q,xi> の集まり
<q0,入力木> から始めて状態ノードがなくなるまで書き換えを続けてってできたものが出力木、という形で木から木への変換を定義する。
R の中で使うルールに制限を加えることで
- Deterministic : 特定の q,σ に対する RHS はたかだか１つ
- Non-Deterministic : 2つ以上あるかも
- Total : 特定の q,σ に対する RHS は１つは出現
- Linear : 各 xi は右辺にたかだか1つずつ
- Non-deleting : 各 xi は右辺に1つは出現
などのサブクラスが色々ある。
- Homomorphism : Q = {q0} な１状態の(Deterministic Total) Transducerのこと
[Thatcher70]
- Theorem 3.8 正規木言語のyield(frontier) if and only if 文脈自由文字列言語
- page 350 の後半から "FST" (= DtT : Total Deterministic Top-Down Tree Transducer) の定義
- Lemma 6.9 : 合成で閉じてる DtT ; DtT ⊆ DtT
- page 359 "NFST" (= T : Top-Down Tree Transducer) の定義
- Lemma 8.7 : 合成で閉じてない T ; T ⊈ T
[Rounds70]
- Section 3 の最後 : 正規木言語のyield(frontier) if and only if 文脈自由文字列言語
- 木言語のことを "dendrolanguage" と呼んでる
- Part I : 決定性
- Section 4 : DT (parial/total双方とも)の定義
- Theorem 1 : dom(DT) ⊆ REGT
- Theorem 2 : DtT ; DtT ⊆ DtT
- Section 5 : regularなdomain Rとtransducer DTをペアにした"Transformation System"(R,DT)を提案
- DT;DTを単純にproduct compositionで作ろうとすると未定義な入力で死ぬので
- ※ これ、Regular Look-ahead で合成可能性を高める話の走りだなあ…
- Theorem 3 : DT(DT(R)) ⊆ DT(R)
- 出力言語に関しては合成で閉じてる
- Part II : 非決定性
- Theorem 1 : dom(T) ⊆ REGT
- Theorem 2 : REGT ⊆ dom(T)
- Theorem 3 : LT(T(R)) ⊆ T(R)
- 出力言語に関しては合成で閉じてる
- コメント。明らかに T ; LT ⊈ T であるという例が作れる
- Corollary T(R) は ∩REGT に関して閉じている。(LTでREGTのpartial identityが作れるので)
- Corollary T(R) の finiteness は決定可能
- Corollary T(R) は∩に関して閉じてない
- Corollary T(R) の∩にの空判定は決定不可能
- T(R) の emptiness は決定可能
- Part II-5 : Context-Free Tree Grammar の話
最終更新：2009年04月04日 01:09
