数理解析研究所講究録1093 巻 1999 年 194-199

194

線形プッシュダウン木オートマトン
笠井琢美

藤芳明生

電気通信大学大学院情報工学専攻

E–mail:fujiyo–a@calvyn. .uec.ac.jp$\mathrm{c}\mathrm{s}$1

はじめに最近の自然言語の形式化に関する研究の関心は, 文脈自由言語より大きな言語のクラスに向いている. 文脈自由文法より大きな言語のクラスを生成する文法の中で, 最近, Thee Adjoinig Grammarる.

TAG により生成される文字列言語を$O(n^{6})$$(\mathrm{T}\mathrm{A}\mathrm{G})[8]$が注目されてい

時間 [13] や $O(M(n)2)$ 時間 [10] で認識するような, 高速な認識ア

ルゴリズムが知られている. また, 自然言語の形式化としてそれぞれ独立して研究されていた, Head Grammar,

Combinatory Categorical Grammar, Linear Indexed Grammar 等により生成される文字列言語のクラスが TAG の
それと–致していることが示されたことは, 注目すべきことである [14].
TAG は木を生成する文法であり, 文脈自由木文法 [11] に制限を加えたものと見なすことができる. 文脈自由木文
法は,

文脈自由文法の生成規則の右辺を文字列から木に置き換えることにより得られる文法である. しかしながら,

TAG は複雑な制限が加わった文脈自由木文法となっているため, そのままでは形式的性質を研究することは容易ではない. そこで, TAG をもう –度文脈自由木文法の立場から見直し, より自然な制限を文脈自由木言語に与えることにより, Spine Grammar という, TAG と同じ文字列言語のクラスを生成する文法が定義された [5].
文脈自由木言語を受理する木オ– トマトンとして, ブッシュダウン木オートマトンが L\‘ene Guessarian [6] によって考案された. このプッシュダウン木オートマトンは通常のプッシュダウンオートマトン [ン型・木オートマトン $[1][2][12]$ を組み合わせたものと見なすことができる.

$7|$とトップダウトップダウン型木オートマトンとは,入力を根から読み始め, 葉に向かいながら, 分岐においては自分自身を複製しながら読み進んでいくのようなタイ

ブの馬オ一マトンである. Guessarian はプッシュダウン木オートマトンにより受理される木言語のクラスと文脈

自由木言語のクラスが–致することを示した.
本研究は, このプッシュダウン・木オートマトンに線形という制限をつけた線形プッシュダウン木オートマトンを考える. 線形という条件は, オートマトンが自分自身を複製する際に, それらの中の 1 つにのみプッシュダウン
記憶の中身をつたえ, ほかのもののプッシュダウン記憶は初期化されていなくてはならないという条件である. そして, 線形プッシュダウン・木オートマトンにより受理される木言語のクラスは,Spine Graanmar により生成される木言語のクラスと–致することを示す. このことより, Spine Grammar により生成される木言語のクラスは, 認

識可能木言語のクラスと文脈自由木言語のクラスの間に位置する自然な木言語のクラスであることが分かる.

2

諸定義

定義 2. 1N やを正整数全体からなる集合とする. 木の台集合とは, 次を満たすい’)*の有限部分集合 D である.

.

$\bullet$d\in D かつ$d=d’\cdot d\prime J,$$i,j\in N_{+}$ に対し$d’,$ $d”\in(N_{+})^{*}$, i\leq j かつD の元を節点と呼ぶ. 特に,

$d$

ならば,

$d’\in D$.

.j\in D ならば, $d\cdot i\in D$ となる.

$d\cdot 1\not\in D$

を満たす節点 を葉と呼ぶ. モノイド $(N+)^{*}$ の単位元を\mbox{\boldmath $\lambda$}で表し, 節点\mbox{\boldmath $\lambda$} を根と呼ぶ. 葉でも根でもない節点を内部節点と呼ぶ.

$d$

195

定義 2. 2$D$

定義 2. 3$\Sigma$

合である.

を木の大集合とし, $d\in D$ とする. 根から$d$への道とは節点の集合 { $d’\in D|$ d’ は の前部分語} である.
$d$を有限アルファベットとする. \Sigma 上の木とは, 関数\alpha : $Darrow\Sigma$ のことである. ただし,で木\alpha に対する木の台集合, つまり, 関数\alpha の定義域を表すものとする.

$D$

は木の台集

$D_{\alpha}$

定義 2. 4\Sigma 上の木\alpha , 節点$d\in D_{\alpha}$に対し,$\alpha/d=\{(d’, a)\in(N_{+})^{*}\cross\Sigma|(d\cdot d’, a)\in\alpha\}$とする.

$\alpha/d$を\alpha の節点$d$における部分木と呼ぶ.

定義 2. 5
定義 2. 6$\epsilon$

を特別な記号とする.

$\Sigma$を有限アルファベットとする.

の木全体の集合から$\Sigma^{*}$$\Sigma$は特別な記号\epsilon を含んでいてもよいものとする. 木\alpha の yield を, \Sigma 上への関数として, 次のように定義する.

$\bullet$$D_{\alpha}=\{\lambda\}$かっ\alpha (\mbox{\boldmath $\lambda$})\neq \epsilon ならば, yield$(\alpha)=\alpha(\lambda)$$\bullet$$D_{\alpha}=\{\lambda\}$かつ\alpha (\mbox{\boldmath $\lambda$})=\epsilon ならば, yield$(\alpha)=\lambda$$\bullet$$D_{\alpha}\neq\{\lambda\}$ならば, yield. ここで, \mbox{\boldmath $\lambda$}はモノイド. ここで,$(\alpha)=\mathrm{y}\mathrm{i}\mathrm{e}\mathrm{l}\mathrm{d}(\alpha/1)\cdots \mathrm{y}\mathrm{i}\mathrm{e}\mathrm{l}\mathrm{d}(\alpha/n)$

定義 2. 7 階層化アルファベットとは, 対もよい.

.

$(\Sigma, r)$

の単位元.

{

$n=\mathrm{m}\mathrm{a}s\mathrm{c}$のことである. ここで,また, H は\Sigma から N(自然数全体) への関数で, もし,$\Sigma^{*}$$\epsilon\in\Sigma$$\Sigma$ならば,$i\in N_{+}$目$\in D_{\alpha}$}.

は有限アルファベットで\epsilon を含んでいて$r(\epsilon)=0$

である.

とする.

$\Sigma_{n}=r^{-1}(n)$$r(a)$ を記号 $a$ のランクと呼ぶ.

定嚢 2. 8$\Sigma$を階層化アルファベットとする. すべての d\in D。に対し,ような\Sigma 上の木\alpha 全体からなる集合を

定義 2. 9$\Sigma$$r( \alpha(d))=\max\{i\in N_{+}|d\cdot i\in D_{\alpha}\}$と書きあらわす.

$\tau_{\Sigma}$を階層化アルファベット, I を$\Sigma$と共通部分を待たない有限集合とする.

る\Sigma 上のインデックス付き木とは, 次を満たす関数\alpha :D\alpha \rightarrow \Sigma \cup I である. 任意のば,り,は階層化アルファベットである.

$I$

I ならば,$I$

をインデックスの集合とす$d\in D_{\alpha}$に対し,$\alpha(d)\in$

刀ならは葉となっている. ただし, D。は木の台集合であをインデックスの集合とする\Sigma 上のインデックス付き木全体からなる集合$r( \alpha(d))=\max\{i\in N_{+}|d\cdot i\in D_{\alpha}\},$$\Sigma$である$\alpha(d)\in$$d$を $T_{E}(I)$ とかく.

定義 2. 10.

$\bullet$$\bullet$

ここで,$\alpha(\lambda)=a\in\Sigma_{0}$に対する表現を, \Sigma および I の元と括弧を用い次のように定義する.

$\text{木}\alpha\in h\cup\tau_{\Sigma}^{\backslash }(I)$ならば, 木\alpha を$a\text{で表す}.\iota$\alpha (\mbox{\boldmath $\lambda$})=L\in I ならば, 木\alpha を t で表す.
$\alpha(\lambda)=b\in\Sigma_{n}(n\geq 1)$

定義 2. 11$\alpha,$$\beta\in T_{\Sigma}$,d\in D。とする.

$\}\cup\{(d\cdot d’’, b)|(d’’, b)\in\beta\}$

定義 2. 12

$X_{0}=\emptyset$$\alpha\in T_{\Sigma}(X_{n}),$

このとき,$\beta_{1},$を固定された変数の集合とする. $X_{n}=\{x_{1},x_{2},$である. また,$\cdots$,$X_{1}$$\beta_{n}\in\tau_{B}(x)$それぞれの節点に A を代入した結果を\alpha \beta 1. .

..
.

$[$

$\alpha=a\in\Sigma\Sigma_{0}$ならば,$\alpha=x_{i}\in X_{n}$$\alpha$.

ならば,$=b(\alpha_{1}\cdots\alpha_{k})$$\alpha(darrow\beta)=\{(d’, a)|(d’, a)\in\alpha$

and

$d$

$b(\alpha_{1}\cdots\alpha_{\mathit{7}\iota})$

で表す.

は d’ の前部分語でないと定める. つまり, 木\alpha (d\leftarrow \beta ) は, 部分木\alpha /d を\beta で置き換えた結果である.

$X=\{x_{1},x_{2}, \cdots\}$

なる部分集合を表す.
定義 2. 13かっ, それぞれの $1\leq i\leq n$ に対し\alpha /i の表現が\alpha ’ ならば, 木\alpha を$a[\beta_{1}\cdots\beta_{n}]=a$とする.

$\beta_{n}]$

ここで,

$x$

,x 訂で, $X$ の先頭の 個の元から$n$で表してもよいものとする.

代入の概念を導入する. 木\alpha の娩をラベルとするで表し, 次のように定義する.

.

$x_{i}[\beta_{1}\cdots\beta n]=\beta_{i}$かつ $k\geq 1$ ならば,の場合, その唯–の元 x’ を$\cdots$.

$\alpha[\beta_{1}\cdots\beta_{n}]=b(\alpha_{1}[\beta_{1}\cdots\beta_{n}.|\cdots\alpha_{k}[\beta 1\ldots\beta n])\cdot$

196

文脈自由木文法と Spine Grammar3

定義 3. 1 文脈自由木文法とは,$N$$\bullet$と$\Sigma$

ここで,は, それぞれ非終端記号と終端記号の有限集合である.

$N$と$\alpha\in T_{N\cup\Sigma}(Xn)$

Sは$\bullet$$N_{0}$. または,$A\in N_{0},$$Aarrow\alpha,$$\mathcal{G}$$d\in D_{\alpha}$$T_{N\cup\Sigma}(X),$$A\in N_{n},$$\alpha\in T_{N\cup\Sigma}$$A(X_{1}\cdots x_{n})arrow\alpha,$$n\geq 1,$$A\in N_{n}$ ,.

の特別な元で, 開始記号である.

定義 3. 2 与えられた文脈自由木文法 に対し,$\alpha_{1},$に対し,$\alpha/d=A,$$A\in N_{0}$ステップの導出とは, 木の有限列\alpha o,$\cdot$,$T_{N\cup\Sigma}(X)\cross T_{N\cup\Sigma}(X)$A\rightarrow \beta \in P ならば,$A(x_{1}\ldots xn)arrow\beta\in P\text{ならば},$$\alpha_{n}\in T_{N\cup\Sigma},$$\cdots,$である. 導出\alpha o,$\cdot$. . , \alpha n が存在するとき,.. ,$\alpha_{n}\in T_{N\cup\Sigma}(X)$$\alpha_{0}\Rightarrow\alpha_{n}g^{*}$$T_{N\cup\Sigma}\cross T_{NU\Sigma}$

上の関係, 導出を

$T_{N\cup\Sigma}$

導出\alpha o? .. . , \alpha n がアウトサイド・イン

上の関係ずを次のように定義する.

$\alpha\Rightarrow\alpha(\mathcal{G}darrow\beta)$

また,,$\alpha\Rightarrow\alpha(\mathcal{G}darrow\beta[\alpha_{1}\ldots\alpha_{n])}$のことである. ただし,$\alpha\in$$\alpha/d=A(\alpha_{1}\cdots\alpha_{n})$

,

とする.

$n\geq 0,$$\alpha_{0}\Rightarrow\alpha_{1}\mathcal{G}\Rightarrow \mathcal{G}^{\cdot}..\Rightarrow\alpha_{n}\mathcal{G}$と書く.

後の証明における便宜上, 導出を変数付きの木の有限列と定義した.
をは共通部分を持たないものとする.

$\Sigma$

P は生成規則の有限集合で, それぞれ次のいずれかの形をしている.

$\bullet$$n$のことである.

$\mathcal{G}=(N, \Sigma, P, S)$

しかし, 言語を定義するだけならば,$\Rightarrow \mathcal{G}$の元の有限列と定義するだけで十分である.

$(\mathrm{O}\mathrm{I})$であるとは, すべての $i\in\{0, \cdots, n-1\}$ に対し,

とき生成規則が節点 $d\in D\alpha$ : に適応されだとすると,$d$$\alpha_{i+1}$から\alpha i 得られるよりも根に近いすべての節点は既に終端記号に書き換えられていなければならないという条件を満たしていることである.

$\alpha\Rightarrow \mathcal{G}*$\alpha ’ であるならば,$\alpha$より$\alpha’\in T_{\Sigma}$

を得る OI-導出が必ず存在することが知られている $[3]$ .
定義 3. 3る.

また,定義 3. 4が$\mathcal{G}$$\mathcal{G}$$\mathcal{G}$を文脈自由木文法とする.

$\mathcal{G}$により生成される言語とは, 集合により生成される文字列言語とは,と G’ を文脈自由木文法とする.

$L_{S}(\mathcal{G})=L_{S}(\mathcal{G}’)$$\mathcal{G}$$L(\mathcal{G})=\{\alpha\in T_{\Sigma}|S*\Rightarrow\alpha\}\mathcal{G}$$Ls(\mathcal{G})=\{\mathrm{y}\mathrm{i}\mathrm{e}\mathrm{l}\mathrm{d}(\alpha)|\alpha\in L(\mathcal{G})\}$のことであのことである.

と G’ が $L(\mathcal{G})=L(\mathcal{G}’)$ であるとき, 等価であるという.

また,$\mathcal{G}$と$\mathcal{G}’$であるとき, 弱等価であるという.

Spine Grammar を定義するために, 背骨型という文脈自由木文法の制限を定義する. そのため, 各非終端記号にヘッドという自然数を新たに割り当てる.
これより,

定義 3. 5 ヘッド割り当て階層化アルファベットとは,$h$$(N,r, h)$ である.

は N から N(自然数全体) への関数で, 各 $A\in N$ に対し,なっている.

定義 3. 6..

$\mathcal{G}=(N, \Sigma, P, S)$$\bullet$には,

節点$r(A)\geq 1$ ならば,

$1\leq h(A)\leq r(A)$ ,また, $h(A)=0$ と$h(A)$ を記号 $A$ のヘッドと呼ぶ.

いるものとする.
$\alpha$ここで, $(N,r)$ は階層化アルファベット.

$n\geq 1$$x_{h(A)}$$d\in D_{\alpha}$について, 生成規則 $A$ ( $x_{1}\cdots$ xn)\rightarrow \alpha \in P が次を満たすとき, 背骨型であるという.

をラベルとする葉が正確に–つ存在する. 根からこの葉までの道を, \alpha の背骨と呼ぶ.

において,$X_{n}-\{x_{h(A)}\}$

を文脈自由木文法とする. ただし, N がヘッド割り当て階層化アルファベットとなって$d$が背骨上にあり\alpha (d)=B\in N であるならば, 節点 $d\cdot h(B)$ も背骨上にある.

をラベルとするすべての節点は, 背骨上にある節点の直接の子供となっている.

文脈自由木文法 $\mathcal{G}=(N, \Sigma, P, S)$ が背骨型であるとは, すべての $n\geq 1$ なる生成規則 $A(x_{1n}\ldots x)arrow\alpha\in P\text{が}$ , 背骨型であることである. 背骨型文脈自由木言語を Spine Gmmmar と呼ぶことにする.

定義 3. 7$\mathcal{G}=(N, \Sigma, P, S)$

を Spine Grammar とする. G が標準形であるとは,G が次を満たすことである.

197

すべての $A\in N$ に対し, $r(A)=0$ または, $r(A)=1$ である.

$\bullet$$\bullet$$A\in N_{0}$に対し, A\rightarrow \alpha \in P ならば,$\bullet$$A\in N_{1}$

に対し,

は,

$\alpha=a,$A(x)\rightarrow \alpha \in P ならば,
$n\geq 1,$$\alpha=b(c_{1}\cdots c_{n}),$$b\in\Sigma_{n},$$a\in\Sigma_{0}$または,$\alpha=B(C),$$\alpha=B_{1}(\cdots(B_{m}(X))\cdots)$$C_{1},$$\cdots,$$C_{n}$,$B\in N_{1}$$m\geq 0,$$B_{1},$, C\in No である.

$\cdots,$$B_{m}\in N_{1}$であるか,は正確に–つだけ $C_{i}=x$ となっているが他はすべて

また$N_{0}$の元である.

文献 [5] において, Spine Grammar の標準形と Tree Adjoining Grammar [14] との関係が示されている.
定理 1 任意の Spine Grammar に対し, それと等価な標準形の Spine Grammar が存在する.
定理 2$\mathrm{R}\mathrm{e}\mathrm{e}$Adjoining Grammar により生成される文字列言語のクラスは, Spine Grammar により生成される文

字列言語のクラスと–致する.

4

線形プッシュダウン木オートマトン

定義 4. 1 プッシュダウン木オートマトン (PDTA) とは,$Q$$M=(Q, \Sigma, \Gamma, q_{0}, Z_{\mathit{0}}, R)$のことである.

ここで,は状態の有限集合である.

$\Sigma$は有限階層化アルファベットで, 入力アルファベットである.

$\Gamma$は\Gamma =\Gamma 0\cup \Gamma 1 をみたす有限階層化アルファベットで, プッシュダウンアルファベットである.

$q\mathit{0}\in Q$

は初期状態である.

$Z_{0}\in\tau_{0}$は開始記号である.

R は次の形の規則の集合である.
読み込み規則 ;(i) $q(a, A)arrow a$
ここで,$a\in\Sigma_{0},$$q\in Q,$

$A\in\Gamma_{0}$.

(ii) $q(b(x_{1}\cdots X_{n}), B)arrow b(q1(X_{1},\pi_{1})\cdots q_{n}(xn’\pi n))$
ここで,$\epsilon$$n\geq 1,$$b\in\Sigma_{n},$$q,$ $q_{1},$ $\cdots,$ $q_{n}\in Q,$$B\in\Gamma_{1},$$\pi_{1},$$\cdots,$$\pi_{n}\in\tau_{\iota^{\Gamma}0}^{*}\cup\Gamma_{1}^{*}$

.

-規則 :

(iii) $q(x, A)arrow q’(X, \pi)$
ここで,

$q,$

$q’\in Q,$$A\in\tau_{0},$$\pi\in\Gamma_{1}^{*}\Gamma_{\mathit{0}}$.

(iv) $q(x, B)arrow q’(x, \pi)$
ここで,定義 4. 2$q,$$q’\in Q,$ $B\in\tau_{1},$ $\pi\in\Gamma_{1}^{*}\Gamma_{0}\cup\Gamma 1^{*}$$M=(.Q, \Sigma, \Gamma, q_{\mathit{0}}, Z_{0}, R)$.

を PDTA とする. M の即席表現とは, 三つ組み

$q(\alpha, \pi)\in Q\cross T_{\Sigma}\cross\Gamma_{1}^{*}F_{\mathit{0}^{\text{のこ}}}$とである. ID で M の即時表現全体からなる集合を表すことにする. M の様相を $\tau_{E(ID}$ ) の元と定義する.

..

を次のように定義する. 任意の様相$\bullet$$c,$ $c’\in T_{\Sigma}(ID)$に対し, 次の条件の内の–つが成り立つとき,

$c$

財

$c’$

関係化
となる.

タイプ (i) の規則 ( , A)\rightarrow a\in R が存在して, ある d\in D。に対し, $c/d=q(a, A)$ かつ $c’=C(darrow a)$ である.
$q$

$a$

タイプ (ii) の規則 $q(b(x_{1}\cdots X_{n}), B)arrow b(q_{1}(X1,\pi_{1})\cdots qn$ ($T_{B},$$\rho\in\tau_{1}^{*}\tau_{0}$に対し,$c/d=q(b(\alpha_{1n}\ldots\alpha),B\rho)$

し, それぞれの $1\leq i\leq n$ に対し, もし\mbox{\boldmath $\pi$}’$x_{n}$,\mbox{\boldmath $\pi$}n) \in R が存在して, ある $d\in D_{c},$$)$$\alpha_{1},$$\cdots,$ $\alpha_{n}\in$

かつ $c’=c(darrow b(q_{1}(\alpha 1, \pi’1)\cdots q_{n}(\alpha_{n},\pi_{n})’))$ である. ただ’=\mbox{\boldmath $\pi$}’ であり, もし\mbox{\boldmath $\pi$}’$\in\tau\tau_{0}\text{なら}\iota 1^{*}i\ovalbox{\tt\small REJECT}_{\pi}$$\in\Gamma_{1}^{*}$

ならば\mbox{\boldmath $\pi$}(=\mbox{\boldmath $\pi$}’p である.

198$\bullet$タイプ (i 五) の規則 $q(x, A)arrow q’(x,\pi)\in$ R が存在して, ある $d\in D_{c},$$c’=c(darrow q’(\alpha, \pi))$ である$\bullet$$\alpha\in T_{\Sigma}$に対し,$\mathrm{c}/d=q(\alpha, A)$

かつ.

タイプ (iv) の規則 $q(x,B)arrow q’(x$ ,\mbox{\boldmath $\pi$} \in R が存在して, ある $d\in D_{c},$$)$かっ $c’=C(darrow q’(\alpha, \pi’))$ である. ただし,$\text{もし}\pi\in\Gamma_{1}^{*}\Gamma 0\text{なら}t\mathrm{h}\pi$$\alpha\in T_{\Sigma},$$\rho\in\tau_{1^{*}}\tau_{0}$’=\mbox{\boldmath $\pi$}であり,に対し, $c/d=q(\alpha, B\rho)$

もし\mbox{\boldmath $\pi$}\in 尋ならば\mbox{\boldmath $\pi$}’=\mbox{\boldmath $\pi$}\rho である.

( ステップの) 計算とは, 様相の有限列が存在するとき, co
る. 計算
$n$

$c_{0},$$\vdash^{*}Mc_{n}$$c_{1},$

定義 4. 3$\cdots,$ $c_{n}$$M=(Q, \Sigma, \Gamma, q_{0,0}Z, R)$ を$T_{\Sigma}|q_{0}(\alpha, z_{\mathit{0}})\vdash^{*}M\alpha\}$$\cdots,$$c_{n}\in T_{\Sigma}(ID)(n\geq 0)$

で,$c_{0}\vdash_{M}c_{1}\vdash_{M}...\vdash_{M}c_{n}$を満たすものであと書く.

PDTA とする.

$M$によって受理される木言語とは, 集合 $T(M)=\{\alpha\in$のことである.

文献 [6] において, Guessarian は PDTA のバリエーションのいくつかを紹介し, それらにより受理される木言語のPDTA
クラスが–致することを示している. 本論文にある PDTA の定義は, 文献 [6] の言葉を用いると, “$\mathrm{r}\propto \mathrm{t}\mathrm{r}\mathrm{i}\mathrm{C}\mathrm{t}\mathrm{e}\mathrm{d}$accepting by empty store” と言い表すことができる.
これより, 線形という制限のされた PDTA を考える. そして, 線形な PDTA が受理する言語のクラスと Spine
Grammar により生成される言語のクラスが–致することを示す.
定義 4. 4$\bullet$$M=(Q, \Sigma, \Gamma, q_{0}, Z_{0}, R)$

を PDTA とする. M が線形であるとは, M が次を満たすことである.

すべてのタイプ (ii) の規則 $q(b(X_{1}\cdots xn), B)arrow b(q_{1}(X_{1}, \pi_{1})\cdots q_{n}(x_{n}, \pi n))\in$ R に対し, $|\{i|1\leq i\leq n$ ,である. つまり, タイプ (ii) の規則が適応されるときに–つをのぞくすべてのプッシュダウン$\pi_{i}\in\Gamma_{1}^{*}\}|=1$

記憶は初期化されなくてはならない.
$\bullet$

すべてのタイプ (iv) の規則 $q(x, B)arrow q’(x, \pi)\in R$ に対し,補題 4. 5 任意の Spine Grammar$\mathcal{G}$$\pi\in$

遅である.

に対し, 線形な PDTA M が存在して,$T(M)=L(\mathcal{G})$をみたす.

(証明) 省略
補題 4. 6 任意の線形な PDTA $M$ に対し, Spine Grammar G が存在して,口$L(\mathcal{G})=T(M)$をみたす.

(証明) 省略

口

補題 4. 5 と補題 4. 6 の結果より, 線形プッシュダウン木オートマトンについて次のような結果が得られる.
定理 8 線形プッシュダウン木オートマトン}こよりて受理される隔言語のクラスは, Spine Grammar によって生成される木言語のクラスと–致する.

199

参考文献
[1] W. S. Brainerd, kee generating regular systems, Information$\partial$

Control, vol.14, no.2, pp.217-231, 1969.

[2] J. Engelfriet, Bottom-up and top-down tree transformations–A comparison, Mathematicd System Theory,vo1.9, no 3, pp.198-231, 1975.
[3] J. Engelfriet and E. M. Schmidt, IO and$\mathrm{O}\mathrm{I}$, J. Computer 8 System Science, vol.15, no.3, pp.328-353, 1977

and vo116, no 1, pp.67-99, 1978.
[4] A. Fujiyoshi and T. Kasai, Multi-Phase ]}$\mathrm{e}\mathrm{e}i\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{O}}$, IEICE Trans. Fundamentals, vol.E80-A, no.4,

pp.761-768, 1997.
[5] 藤芳明生, 笠井琢美, Tree Adjoining Grammar の文脈自由木文法による特徴づけ, 1998 年夏の LA シンポジウ
ム, 情報基礎理論ワークショップ, pp.34-39,1998.
[6] I. Guessarian, Pushdown tree automata, Mathematical System Theory, vol.16, no.4, pp.237-263, 1983.

[7] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison

Wesley, Reading, MA, 1979
[8] A. K. Joshi,$\mathrm{L}.\mathrm{S}$. Levy and M.

$\mathrm{I}\mathrm{b}\ovalbox{\tt\small REJECT} \mathrm{k}\mathrm{a}\mathrm{h}\mathrm{a}\mathrm{s}\mathrm{h}\mathrm{i},$$\mathrm{R}\mathrm{e}\mathrm{e}$adjunct Grammars, J. Computer 6} System Science, vol.10,

no 1, pp.136-163, 1975.
[9] S. Rajasekaran, ]} -adjoining language parsing in $O(n^{6})$ time, SIAM J. Comput., vol.25, no.4, pp.862-873,$\mathrm{e}$1996.
[10] S. Rajasekaran and S. Yooseph, TAL Recognition in $O(M(n^{2}))$ time, J. Computer$\mathcal{E}f$

System Scimce, vol.56,

no 1, pp.83-89, 1998.
$\lfloor\lceil 11]$W. C. Rounds, Mapping1970.

$\mathrm{a}\mathrm{n}\mathrm{d}^{\backslash }$iammars on trees, Mathematical System Theow, vo1.4, no.3, pp.257-287,.12] J. W. Thatcher, ’bee automata: an brm-al survey, in Currents in the theory of computing, ed. A. V. Aho,
pp.143-172, Prentice-Hall, Englewood Cliffs, 1973.
$\dot{\mathrm{i}}\mathrm{n}$13] K. Vijay-Shanker and A. K. Joshi, Some computational properties of tree adjoining grammars, Proc.
Meeting of the Association for Computational Linguistics, pp.82-93, 1985.

$\mathit{2}\mathit{3}rd$

14] K. Vijay-Shanker and D. J. Weir, The equivalence of four extensions of context-free grammars, Mathematical

System Theory, vo1.27, no 6, pp.511-546, 1994.