数理解析研究所講究録1093 巻 1999 年 218-223

218

意並列解析可能ユニフィケーション文法
A Uniquely Parallel Parsable Unification Grammar
李佳, 森田憲–, 岩本宙造, 今井克暢
広島大学工学部{lijia, morita, iwamoto,1 はじめに$\mathrm{i}\mathrm{m}\mathrm{a}i$.

.
意解析可能文法 (Uniquely Parsable Grammar,
UPG) は、 書換規則にある種の明示的な条件をつける$-$

ことにより、構文解析をバックトラックなしに (–意に)進めるようにした文法として、 森田ら [1] によって提案された。 この制約条件にもかかわらず UPG は Turing 機
械と同等な生成能力を持ち、 従って万能である。
の考えを
本稿では、 ユニフィケーション文法
UPG に取り入れて拡張した–意解析可能ユニフィケー
ション文法に注目し、 その–意解析可能性に加え、構文解析を効率的に行える並列解析が実現できるように、各書換規則に文脈インデックスを導入し、 –意並列解析可能ユニフィケーション文法 (Uniquely Parallel Parsable
Unification Grammar, UPPUG) を定義する。 またその(直列的) –意解析可能性に加え、並列解析可能性も合わせて示す。
$(\mathrm{U}\mathrm{G})$2-意解析可能文法
意解析可能文法 UPG は、 構文解析をバックトラッ
クなしに行うことができる句構造文法である。 ここで構
文解析 (parsing) とは、 文法 $G$ に対して、 与えられた記号列が $G$ によって生成される言語に属するか否かの判定を行うと共に、 生成される場合には導出過程を求めることを言う。 しかし、 書換規則を逆適用し、 記号列を還元することによって解析を行う際、 一般に各ステップにおいて、 逆適用可能な規則が複数存在する。 そのため、 ある規則を選んで解析に失敗した時、別の選択肢があるところまで戻り、 別の規則を使う必要がある。 これをバッ
クトラックと呼ぶ。 構文解析をバックトラックなしに決定的 (–意) に進めることができれば効率的である。
UPG では、 書換規則に次のような制約条件 (UPG 条件) を設けている: まず、 ある規則の右辺の接頭辞と、別のある規則の右辺の接尾辞とが–致するならば、 それらの共通部分が、各規則の左辺において、 それぞれ同じ位
置になくてはならない。 さらに、任意の規則の右辺が別の規則の右辺に含まれることを禁ずる。 このような制約から、 逆適用可能な規則が複数あった場合、 それらがそれぞれの逆適用位置において重なる部分は、 いずれの規則を逆適用しても書き換えられることがない。 従って、
UPG の還元は–種の合流性を満たし、 バックトラックを行わずに–意に進むことができる。
さらに、 森田らは、 決定性 Turing 機械 (DTM) における言語受理のプロセスを、 UPG 条件を満たす書換規}$\emptyset \mathrm{k}\mathrm{e}.\mathrm{S}\mathrm{y}\mathrm{s}.\mathrm{h}i\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{m}\mathrm{a}-\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{j}\mathrm{p}$則による語の還元過程によって、完全に模倣できることを示した。 すなわち、 UPG の言語クラスと、 DTM によって受理される言語のクラスとが同等である。 また、
決定性 Chomsky 階層によって特徴づけられる UPG の三つのサブクラス [1] も定義した。

3 ユニフィケーション文法
は生成文法の各非終端
ユニフィケーション文法
記号に引数を持たした文法である。 これは引数間でユニフィケーションを行うことによって、 生成還元を実行する文法である。 また、 引数を利用して、情報の伝達や保持が簡潔に行える特徴を持つ。 これによって、 ユニフィ
ケーション文法は文法の記述力を高め、構文の曖昧性をうまく解消することができる。
特に、構文解析の効率の良さおよび文法構成の便利さから、 自然言語処理の分野 [5] において注目されてきた
文脈自由文法に対し、 自然言語における互いに割り込んだ構文要素間の依存関係 (例えば、 英語の respectively
構文) を適切に表現できないと指摘された。 また、 自然
言語の統語構造を文脈自由言語で記述しようとすると、類似の規則が非常に多数必要となる。 これらの問題の多くはユニフィケーション文法によって解決できる。 すな
わち、 文脈自由文法の非終端記号に素性構造 (引数) を持たせ、 比較的少数の規則型によって、 統語構造を簡潔に記述することができる。
$\mathrm{U}\mathrm{G}$

3.1 項およびユニフィケーション
において使われる
定義 31 ユニフィケーション文法
記号は、 関数記号と変数の 2 種類である。 関数記号 $f$ にはその引数の個数を示す非負整数 (アリティ)n が付随してとも表される。 アリティ の関数記号は定数と呼ばれる。 $F$ と $V$ をそれぞれ関数記号、 変数の集合とし、また $F$ 中の定数の集合を $C\sigma nst(F)$ と表す。 $F$ と $V$ 上の項は次のように再帰的に定義される$\mathrm{U}\mathrm{G}$$f^{(n)}$$0$(1) 変数は項である(2) 定数は項である(3) $f^{(n)}(\in F)$ が関数記号で、$f^{(n)}(t_{1}, \cdots, t_{n})$$t_{1},$$\cdots$, ちが項ならば、も項である

項全体の集合を艶 rm(F, $V$ ) と表し、 また変数以外の項を複合項と呼んでその集合を $CTe\prime m(F, V)$ と記す。 す口
なわち、 CTerm $(F, V)=Term(F, V)-V\mathrm{o}$定義 32 有限個の複合項を–列に並べたものを、複合項

219
列と呼び、 その集合を CTerm $(F, V)^{*}$ と表す。 さらに、

CTerm $(F, V)^{+}=CTerm(F, V)^{*}-\{\epsilon\}$$s_{n}\in CTer\dot{m}(F, V)^{+}$ にとする ( は空夕 D \eta$=s_{1},$ $\cdots,$$\epsilon$$\circ$

対して、

定義 36[導出] $\mathrm{U}\mathrm{G}G=(F,T, V, P, S^{(})n.\rangle$ において、 複
合項列 $\xi=r_{1},$ $\cdots,$ $r_{k}\in CTerm(F, V)^{*}$ に対して、規則,$R=s_{1},$ $\cdots$, $t_{n}(\in P)$ が$s_{m}arrow t_{1},$ $\cdots$

$\xi$

の位置

$j$

で適

用可能とは

head $(\eta)=s1$
tail $(\eta)=s_{n}$とする (但し、 head$(r_{j}, \cdots, r_{j1}+m-)\sigma=(\mathit{8}1, \cdots, s_{m})\sigma$となる代入) また、 $Var(t)$は、複合項夕 I $\in CTerm(F, V)^{*}$ に含まれる変数の集合を表す。
口.
定義 33[代入] $F,$ $V$ をそれぞれ関数記号および変数の集合とする時、写像 : $Varrow Term(F, V)$ を代入 (substitution) と呼ぶ。 また便宜上、代入を以下の集合によっ$(\epsilon)=tail(\epsilon)=\epsilon$。

が存在することを言う。 但し、 ここでと仮定する (そうでない時、 $R$
に対して変数の改名を行う)。 また、$\sigma$$Var(\xi)\cap Var(R)=\emptyset$$\cdot$$(r_{1}, \cdots ,r_{j-1}, t_{1}, \cdots , t_{n}, r_{j+m}, rk)\sigma$$\eta=$

であるならば、 $G$ において

$\xi$

から

$\eta$

が直接導出される$\sigma$て表す。 但し、 $X_{i}\in V,$ $t_{i}\in\tau_{e}rm(F, V)$

。

あるいは

$\xi\Rightarrow\eta c[R,j, \sigma]_{\text{、}}$と表記す$\xi^{[R}’\dot{\mathit{4}}^{\sigma]}\eta G$

る ( $G$ は省略可能)。 また、 $[R,j, \sigma]$ を書換えのラベルと呼ぶ。

$\{t_{i}/X_{i}|\sigma(x_{:})=t_{i}\wedge x_{i}\neq t_{i}\}$

なお、 導出の反射的推移的閉包をきで、 ステップの導出を尊で表す。 $X_{i}\in V(1\leq i\leq n_{\epsilon})$ を相異なる

そして、

$n$

$Dom(\sigma)=\{X_{i}|\sigma(X_{i})\neq xi\}$とする。 項 に対する代入 の適用を以下のように定義し、 その結果をかっと表す。 但し、$s$$f^{(n)}\in F_{\text{、}}$$r_{i}\in\tau_{e}rm(F, V)(1\leq i\leq n)$。

$\cdots,$ $s_{m}$への代入$\sigma$.

$s(X_{1}, \cdots, X_{n_{s}})\Rightarrow^{*}\eta c$

ならば、 複合項列 は $G$ から導出 (生成) 可能と言い、の文形式と呼ぶ。 文形式 が $G$ の文となるための必要かつ十分条件は $\eta\in\tau*$ である。 そして、 $G$ によって生成される言語 $L(G)$ はすべての文の集合である。

$G$$(r1\sigma,$$\cdots$,$r_{n}\sigma)$$s_{1},$

個の変数とする時、$\eta$(1) $s=X_{i}$ ならば、 $s\sigma=\sigma(Xi)$(2) $s=f^{(n})(r_{1}, \cdots, r_{n})$ ならば. $s\sigma=f^{(}n$)
複合項列
義する

$n_{\epsilon}$$\sigma$$s\sigma$$X_{i}\in V,$と言い、の適用を次のように定$\eta$$L(G)=\{w|s(X_{1}, \cdots, X_{n_{\epsilon}})\Rightarrow^{*}w\wedge Gw\in T^{*}\}$

口定義 37[還元] $\mathrm{U}\mathrm{G}G=(F, T, V, P_{S},(n_{s}))$ において、 複$(s_{1}, \cdots, S_{m})\sigma=\mathit{8}1\sigma,$

また、 二つの代入$\sigma$と$\cdots,$ $s_{m}\sigma$$\tau$の合成 (composition)

合項列 $\xi=r_{1},$ $\cdots,$ $r_{k}\in \mathit{0}\tau_{erm(}F,$$\sigma\circ\tau$は次のようなものである。

$R=s_{1},$,$\cdots$$V)^{*}$$s_{m}arrow t_{1},$ $\cdots,$ $t_{n}(\in P)$

がに対して、規則の位置 で逆$j$$\xi$

適用可能と言われるのは$s(\sigma 0\tau)=(s\sigma)\tau$

最後に、変数の改名 (renaming of variables) と呼ばれる特別な代入は単射 : $Varrow V$ である。
口

$r_{j},$$\cdots,$となる代入$r_{j1}+n-=(t1, \cdots, t_{n})\sigma$$\sigma$$\sigma$

定義 34[ユニフィケーション] 項 $t\in Term(F, V)$ がユニフィケ一ション可能 (unifiable) とは、となる代入 が存在することを言い、で表す。 同様に、$s,$$s\sigma=t\sigma$$s\sim t\backslash _{\mathrm{s}}$$\sigma$

複合項列により$\alpha,$$\beta\in(CTerm(F, V)^{*}$ に対して、 ある代入$\sigma$となるならば、 と が耳ニフィケー
ション可能と言い、と表す。 このような をユニ
フィケーション作用素 (unifier) と呼ぶ。
口$\alpha\sigma=\beta\sigma$$\alpha$$\beta$$\alpha\sim\beta$$\sigma$が存在することを言う。 また、.. ,$r_{j-1},$$r_{j+n}$ ,$(S_{1}, \cdots, s_{m})\sigma,$$\eta=r_{1},$ $\cdots,$

であるならば、 $G$ において言い、$\xi\Leftarrow\eta G[R,j, \sigma]_{\text{、}}$$\eta$

が

$\xi$

あるいは

$\cdot$$r_{k}$

から直接還元されると$\xi^{[R,,\sigma 1_{\eta}}\Leftarrow^{j}c$と表記する( は省略可能)。 導出と同様に $[R,j, \sigma]$ を書換えのラベルと呼ぶ。
なお、 還元の反射的推移的閉包を、 また ステップの還元をそれぞれ養, 茎と表す。 ある項
,
$G$

$n$

$u_{1},$ $\cdots$$u_{n_{s}}\in$$Term(F, V)$ に対し32 Unification Grammar の定義
定義 35[UG] ユニフィケーション文法$\xi\Leftarrow^{*}s(u_{1}G’\ldots, u_{n_{\epsilon}})$$\mathrm{U}\mathrm{G}$$G=(F, T, V,P_{S^{(n_{s}}},))$

によって定義される。 但し、 記号 $F,$ $T,$ $V,$ $P,$
次の通りである。

(1) $F$ は関数記号の集合で、 Const(2) $T(\subset ConSt(F))$ は終端記号の集合で、(3) $V$ は可算個の変数の集合

ならば、 が $G$ において開始記号まで還元できると言う。
口$\mathrm{U}\mathrm{G}G=(F,T,V,V,
P_{S^{(n_{\iota}}},))$
定義 3.8において、 直接$\xi$は$s^{(n_{\delta})}$は$(F)\neq\emptyset$

還元が直接最左還元と呼ばれるのは、 ある複合項列 $\eta’\in CTerm(F, V)^{*}$ により、$\xi\Leftarrow\eta[R, i, \sigma]$$\xi\Leftarrow\eta’[R’, i’, \sigma^{l}]$$T\neq\emptyset$となる任意の $[R’, i’, \sigma’]$ に対して、 $i\leq i’$ が成り立つことを言う。 ここで、 直接最左還元を$4^{4} \mathrm{t}_{\text{て}^{}\mathit{8}^{()}}n\not\leq\text{、}\mathrm{g}_{\Pi}\epsilon_{t\mathrm{Z}}F\ovalbox{\tt\small REJECT}\wedge\mathrm{h}_{\text{項}F\mathrm{J}^{\wedge}\text{書換}\sim}\text{開}i\mathrm{g}|\frac{=}{\text{を}\beta}\mathrm{B}\text{号}\check{\mathrm{X}}\text{る}arrow ba)\text{、}$規則の有限集合である。 各規則 $R(\in P)$ は次の形で与えられる。
$R=\alphaarrow\beta$

但し、 $\alpha\in \mathit{0}\tau_{erm}(F, V)+-T^{+},$ $\beta\in CTerm(F, V)^{*}$
かつ $Var(\alpha)\subseteq Var(\beta)_{\text{。}}$.

便宜上、 規則に現れる変数の集合を $Var(R)$ とする(従って、 $Var(R)=Var(\beta)$ ) 。同様に、 規則 $R$ への代
入 \mbox{\boldmath$\sigma$} の適用を
口と書く。
$R\sigma(=\alpha\sigmaarrow\beta\sigma)$$\xi\Leftarrow\eta[R, ilmr’\sigma]$と表記する。 また、 還元
元であるとは、$\eta\Leftarrow\xi_{1}\Leftarrow\cdots\Leftarrow\xi_{n}$が最左還$\eta\Leftarrow\xi_{1}\Leftarrow\cdots\Leftarrow\xi_{n}$$lmr$$\mathrm{t}mr$$lm$ ’となることを言う。 同様に、 最左還元の反射的推移的閉
包、および ステップの最左還元をそれぞれる, 番と
$n$

表す。

$lmrlmr$口

220
複合項列へ規則を適用する導出、 あるいは逆適用による還元のいずれも、 まずユニフィケーション操作を行っにおた後、書換えを実行するものであることから、ける導出と還元の関係は–般の句構造文法ほど自明でない。 しかしながら、任意の複合項列が文法 $G$ によって$\mathrm{U}\mathrm{G}$生成されることと、 その複合項列が $G$ において開始記号まで還元できることとが等価であることが示せる。
補題 31 $G=(F, T, V, P_{\mathit{8}},(n\mathrm{g}))$ を UG とする。 また、$\xi\in(CTerm(F, V)^{*}$ を任意の複合項列、$Term(F, V)$ を項とする。 もし、$t_{1},$$\cdots,$ $t_{n_{s}}\in$$\xi\Leftarrow s(*t_{1}, \cdots,t_{n_{\epsilon}})$ならば、 任意の代入$\sigma$に対して、(証明) 還元ステップ数 $n$ に関する帰納法を用いる。 まず$n=0$ ならば、 補題は自明である。 $n=k-1$ の時に、補題の成立を仮定し、 次の ステップの還元を考える。
$k$$\xi^{1^{R,\tau}]}\not\in.\eta k\Leftarrow^{1}-S(t_{1}, \cdots, t_{n_{\epsilon}})$とし、 $Var(\xi)\cap Var(R)=\emptyset$ と仮定すに対して、る (そうでない時、 任意の変数の改名$R=\alphaarrow\beta$$\xi\Leftarrow$$\sigma$が成り立つので、$Var(R\sigma)\cap Var(\xi)=\emptyset$の位置 で逆適用する。 但し、 変数の改名は単射で、 かつ $Var(R)=D_{om}(\sigma)$ と仮定しても $-$.
$\eta[R\sigma,j, \sigma^{-1}\circ\tau]$となる$R\sigma$

を

$j$

$\xi$

般性を失わない)。
還元の定義から、 ある$\gamma,$が存在$\lambda\in CTerm(F, V)^{*}$

し、$\xi\sigma\Leftarrow S(*\sigma t1, \cdots, t_{n_{*}}\sigma)$$\lambda[R\not\in.,\mathcal{T}]\gamma,$$\xi=\gamma.’\beta\tau,$が成り立つ。
(証明) 還元ステップ に関する帰納法を用いる。 まず$n=0$ の場合、 補題は自明である。 $n=k-1$ の時に補題の成立を仮定し、 次の ステップの還元を考える。
$n$$\alpha\tau,$$\lambda=\eta$なので、 $Var(\xi)\cap$と書ける。 -方、としても–般性を失わない。従って、となり、 それゆえ、 には $R$ が位置 で適用可能で、$Var(\xi)\cap Var(R)=\emptyset$$Dom(\mathcal{T})=\emptyset$$\eta\tau=\eta$$j$$\eta$$k$$\lambda\dot{g}^{\tau}[R,,]\beta\gamma,\tau,$ $\lambda$$\eta=\gamma,$$\alpha \mathcal{T},$$\xi^{[R,\tau 1-}\not\in.\eta^{k}\Leftarrow^{1}s(t_{1}, \cdots,t_{n_{*}})$

規則 $R=\alphaarrow\beta$ と仮定すると、 あると書ける。従って、$C.Term(F, V)^{*}$ に対して、 $\xi=\gamma,$$\gamma,$$\beta\tau,$$\lambda\eta$$\xi\sigma=\gamma\sigma,\beta(\tau\circ\sigma),$に対して、$\sigma$$\lambda\sigma^{[R,\circ}\epsilon\gamma\sigma j\tau\sigma],(\alpha \mathcal{T}\mathrm{O}\sigma),$となる。帰納法の仮定により、$\eta\sigma$

る$\lambda\sigma=\eta\sigma$$s(t_{1}\sigma, \cdots, t_{n_{\iota}}\sigma)$

で

あるので、
$\eta\sigma\Leftarrow^{*}s(t1\sigma, \cdots,t_{n_{\epsilon}}\sigma)$が成り立つ。
補題 32 $G=(F,T, V, P, s^{(n}*))$ を$\xi\in CTerm(F,V)^{*}$ を複合項列、異なる変数とする時、

口$\mathrm{U}\mathrm{G}$$X_{1},$とする。 ここで、$X_{n_{s}}\in V$ を相$\cdots,$$t_{1},$$\cdots,$$t_{n_{*}}\in Term(F, V)$が存在し.

$\xi\Leftarrow S(t_{1}*, \cdots,t_{n_{\ell}})$$k$$s(X_{1}, \cdots, X_{n_{\delta}})^{k-}\Rightarrow\eta\dot{g}^{T}11^{R},]\xi$$\lambda\in CTerm(F, V)^{*}$ に対して、 $\eta=\gamma,$
あるとする。 また、 $R=\alphaarrow\beta_{\text{、}}Var(\eta)\cap Var(R)=^{\mathrm{o}}$ と仮$\alpha’,$$\alpha’,$$\lambda$

定する (そうでない時、 $R$ に対する変数の改名を行う)。
とな
しかも導出の定義から、$R$によって還元可能であり、る。 従って、 は$\alpha’\tau=\alpha\tau_{\text{、}}$$\xi=\gamma\tau,$ $\beta\tau,$$\lambda_{\mathcal{T}}$$\xi$$\xi=\gamma\tau,\beta_{\mathcal{T},\lambda^{1}}R\not\in.,\tau$.

]$\gamma_{\mathcal{T}},$$\alpha\tau,$$\lambda_{T}=\eta\tau$が成り立つ (であるので)。従って、補題 31 およひ帰納法の仮定により、$\alpha’\tau=\alpha\tau$$\xi\Leftarrow^{*}s(t_{1}, \cdots,t_{n}.)$となる項$t_{1},$$\cdots,t_{n}$. が存在する。

.

口

補題 33 $G=(F,T,V, P_{S},(n\epsilon))$ を UG とする。 もし、に対して、 ある項
任意の複合項列 $\xi\in c\tau_{erm(}F,$$t_{1},$$\cdots,$.

$t_{n}$.

$V)^{*}$$\in Term(F,V)$ が存在し、$\xi\Leftarrow S(*t_{1}, \cdots,t_{n}.)$ならば、相異なる変数$X_{1},$ $\cdots X_{n_{\iota}}:’$$s(X_{1}, \cdots,X_{n}.)\Rightarrow^{*}\xi$が成り立つ。

$s(X_{1}, \cdots, X_{n_{S}})\Rightarrow^{*}\xi$口が成り立つ。
$G$から生成されうる複合項列
文法
以上の補題から、の集合と、 同じ $G$ において開始記号まで還元できるものの集合とが–致する。 従って、 書換規則を逆適用し、還元を行うことで、 $G$ の文を含む任意の複合項列の生成可能性を解析することができる。

3.3 文脈インデックスの導入
本研究では、 UPPUG における書換規則の制約を明示的に記述するため、 またその並列的な解析を定義するたする。
を
定義 39UG $G=(F,T,$ $V,$ $P_{S)},(n_{*})$ において、に対し、非負の整数とする。 規則と$CTerm(F, V)^{*}$ が存在し、の時、 head,
なり、 かっ$head(\beta 1),$ $tail.(\alpha 1)\neq tail(\beta_{1})$ ならば、をそれぞれ
規則の左文脈、 右文脈と呼ぶ。 さらに、 $|\gamma|=l,$ $|\delta|=r$とする時、 $(l, r)$ を文脈インデックス、$l,$ $r$が成り立つ。
(証明) 導出ステップ数釧こ関する帰納法を用いる。 まず$n=0$ ならば、 補題は自明である。 $n=k-1$ において補題の成立を仮定し、 次の ステップの導出を考える。

$\gamma,$であるので、

めに、文脈インデックス付き書換規則を次のように導入$s(X_{1}, \cdots,X_{n},)\Rightarrow^{*}\xi$

ならば、項$s(X_{1}, \cdots, X_{n_{\epsilon}})\Rightarrow^{*}\eta$$\lambda$$\xi=\gamma,\beta\tau.’\lambda^{[}R\dot{4},\tau]=\gamma,\alpha \mathcal{T},$となり、 そ流ゆえ、 任意の代入が成り立つ。帰納法の仮定により、$\lambda\in$\in V. に対して、$\alphaarrow\beta$$\alpha_{1},$$\alpha=\gamma\alpha_{1}\delta,$$\alpha_{1}$$\neq$$\epsilon$$\beta_{1}$$\neq$$\beta_{1},\gamma,\delta\in$$\beta=\gamma\beta_{1}\delta$$(\alpha_{1})$$\epsilon$$\neq$$\delta$$\gamma,$$[\alphaarrow\beta, (l,r)]$を文脈インデックス付き書換規則と呼ぶ。

$\square$

UPG と並んで、 森田らは $-$ 意解析可能アレイ文法
UPAG(Uniquely Parsable Array Grammar) [ を提案した。 UPAG では、書換規則にその規則の左辺および右$2|$

辺が同形であるという制約を加え、左辺と右辺で書き換
わらない部分を文脈部 (context portion) と呼ぶ。 さらに、 UPG と同様に、 ある二つの規則の右辺を重ねあわせた時に、一致する部分は各規則の左辺においても、 同じ場所になくてはならない、従って、規則の文脈の–部分である。 これらの制約により、 UPAG に対し、規則の逆適用を同時に行う並列還元を容易に定義できる。
しかし、 UPG では、ある規則の右辺の接頭辞が他 (または同 $-$ ) の規則の右辺の接尾辞と同じならば、 それらの部分は規則それぞれの左辺の接頭辞、接尾辞となるが、
X 脈 a)–部分にあたると限らない。 それは、 -次元生成

221
文法では、規則の左右の長さが–般に違うので、文脈の指定は必ずしも–意に決められない。例えば、 $Aarrow ABA$を考えると、 $A$ は左文脈、 あるいは右文脈のどちらとも呼べる。 $ABarrow ACAB$ についても同様である。従って、UPG では並列還元を行う操作が定義されていない。
そこで、 -意並列解析可能ユニフィケーション文法
UPPUG においては、各書換規則に文脈インデックスを付随させ、規則の文脈の部分を明確に指定する。 さらに、
UPG における制約と同様の制約をインデックス付き規則に対して課す。 これによって、 同時に逆適用可能な二つの規則が逆適用位置において重なった部分は、 常に両方の規則の文脈にあり、 UPAG と同様に、冬規則を並列に逆適用することができる。

4 UPPUG
定義 41[UPPUG] –意並列解析可能ユニフィケーショ
ン文法 UPPUG は $G=$ $(F,T, V, P, s(n_{S}),$ で定義される。 $F,T,$の定義は UG と同様で、 $は特別な境
界記号 ($\not\in F\cup V) を表す。 $P$ は文脈インデックス付き$V_{S},(n_{\epsilon})$

書換規則の有限集合で、 $\alpha\in CTerm(F, V)+-\tau+,$$\beta\in$$CTerm(F, V)^{+}$ に対し、各規則は次のいずれかの形で与えられる。

, $[alpha arrow beta, (l, r)]$, $[alpha arrowbeta\,.(\iota,r)]$$が成り立つ時、 $G$ において、は開始記号まで還元できると言う。 そして、 UPPUG の言語 $L(G)$ は UG と同様に、 すべての文の集合である。
$L(G)=\{w| s(X_{1}, \cdots, X_{n_{\epsilon}})Rightarrow^{*} wwedge w\in\tau^{*}\}$

なお、 UPPUG の生成能力が万能、すなわち、 Turing
機械により特徴付けられることは、次の定理より導くことができる。
定理 4.1 UPPUG の族は UPG と同様に、 万能な生成文法の族である。
(証明) 決定性 Tuing 機械 DTM における語の受理の動作
を、 UPG の制約を満たす書換規則 (文献 [1] 参照) の逆適用によって、 完全に模倣できる。 -方、 UPPUG は、
UPG の非終端記号や、 終端記号などを定数として扱う
ことにより、 それらの書換規則を模倣できる。 これにより、 UPPUG も Turing 機械を模倣することができ、従って万能である。

口

5UPPUG の–意解析性
補題 51[還元の合流性]$,$

はさらに以下の条件を満たす。
UPPUG 条件:に属する各書換規則の右辺$i_{1},$$\beta$は $s(X_{1}, \cdots,X_{n_{*}})$ ,$s(X_{1}, \cdots,X_{n_{\ell}} )$$P$$R_{1}=[\alpha_{1}arrow\beta_{1}, (l_{1}, r_{1})]$$R_{2}=[\alpha_{2}arrow\beta_{2}, (l_{2}, r_{2})]$

し、 もし

ならば、

[

$R_{1},$

il,

し

しかも

$i_{2}+|\alpha_{1}|-|\beta 1|)$ 。
$\eta^{[R_{1},i}\Leftarrow^{1}’\xi_{1}\sigma 1][R\mathrm{z},i’,\sigma 2\Leftarrow^{2}\xi]$(証明) (1)$\delta_{1}\sim\delta_{2}$ある$\gamma,$$i_{2}-i_{1}\geq|\beta_{1}|$$\theta,$の場合$\lambda\in(CTerm(F, V)\cup\{})^{*}$ に対し、に対して, もならば、 $R_{1}=R_{2}$$\square$$\theta,$$\beta_{2}\sigma_{2},$$\lambda$と書ける 但し、$|\gamma.|=i_{1}-1, |\gamma, \beta 1\sigma_{1}, \theta|=i_{2}-1)_{\text{。}}$
従って、
$($

UPPUG 条件 $2(a)$ は、 ある規則の右辺にある接頭辞$\xi_{1}=\gamma,$ $\alpha_{1}\sigma 1,$$\theta,$$\beta_{22}\sigma,$$\lambda$

が、 別 (または同 $-$ ) のある規則の右辺の接尾辞とユニ$\xi_{2}=\gamma,\beta.1\sigma_{1},$$\theta,\alpha 2\sigma_{2},$$\lambda$

フィケーション可能ならば、規則の左辺もそれらの部分
を、それぞれ接頭辞および接尾辞として持たな てはならないと述べている。 しかも、 それらの部分はいずれの規則においても、文脈インデックスが示す文脈部になくてはならない。そして、条件 $2(b)$ によって、 どの規則の右辺も、他の規則の右辺にある部分複合項列とユニフィ
ケーション可能でない。
次に、言語の生成および解析に関わる UPPUG の導出
や還元を同様に定義することができる。但し、 UPPUG において複合項列は、 常に両端が$によって囲まれ、 $\eta $ $(\eta\in \mathit{0}\tau_{erm(}F,V)*)$ の形で扱われる。 また、
複合項列 $\xi\in CTerm(p, V)^{+}$
に対して、 相異なる変数.
$\in V$ が存在し、$\cdots,X_{n}$$<$ととなる。 従って、には、 それぞれにおいて逆適用可能となる。 つまり、
置ち,$\xi_{1}$$R_{2},$$\xi_{2}$.

$s$(X_{1’ \mathfrak{n}}\ldots,X.)Rightarrow G*$

ならば、$\xi- \text{は}G$$\xi $$\alpha 1\sigma_{1}[R_{22}’,\sigma_{2}],\theta,\alpha_{2}\sigma_{2},$$\xi_{1}’\Leftarrow.\cdot\gamma,$から生成可能と言う。

.

ある項

が位

$\lambda$$\lambda[R_{1},i,\sigma_{1}]$$\xi_{2}\Leftarrow^{1}\gamma,$$\alpha 1\sigma 1,\theta,$となり、 補題が成り立つ(2)$i_{2}-i_{1}\leq|\beta_{1}|$$\alpha 2\sigma_{2},$$(\xi=\gamma,\alpha_{1}\sigma_{1},\theta,\alpha 2\sigma 2,\lambda)$。

の場合

UPPUG の条件により、ある$\delta_{2}\in(o\tau_{er}m(F, V)\cup\{})^{*}$$\gamma,$$\lambda,$$\alpha_{1}’,$$\beta’’1’\alpha 2’\beta’2’\delta’,\delta 1$が存在して、$\eta,$$R_{1},$ $R_{2}$,は次のように書ける。
$\eta=\gamma,$ $\beta_{1}’\sigma_{1},\delta’,\beta_{22}’\sigma,$$\lambda$$R_{1}=[\alpha_{11}’\deltaarrow\beta_{1}’\delta_{1}, (l_{1},r_{1})]$$R_{2}=[\delta_{2}\alpha’2\cdotarrow\delta 2\beta\prime 2\backslash ’(l_{2},r_{2}\rangle]$

但し、$\text{また_{、}}$$R_{1}$$i_{1}$$\mathrm{U}\mathrm{G}$$X_{1},$$\in$$r_{2}\geq|\delta_{2}|$$\delta\in(o\tau_{e}\Gamma m(F, V)\cup\{})^{*}$$\beta_{1}\sim\gamma\beta_{2}\delta$

]
$\xi$

$\eta=\gamma,$ $\beta_{1}\sigma_{1},$$\gamma,$$\sigma 1$$\eta^{[]}\Leftarrow\xi 2R_{2},i_{2},\sigma_{2}[R1,i\Leftarrow’\xi 1\sigma 1]$$\in(CTerm(F, V)\cup\{})^{+}$ に対$l_{1}\geq|\delta_{1}|,$$\eta\Leftarrow\xi_{1}$$i_{2}$

であるならば、 次の条件を満たす複合項列$(CTerm(p, V)\cup\{})^{+}$ が唯–存在する (但し、 $i_{2}’=$に対して ( $R_{1}=R_{2}$ の時$\beta_{1}=\delta_{1}\beta\prime 1’\beta_{2}=\beta_{2}’\delta 2\text{、}$を任意の複合$\eta\Leftarrow\xi_{2}[R_{2},i_{2}, \sigma_{2}]$も同様)、 以下が成立する。
$\delta_{1},\delta_{2},\beta_{1}’,\beta_{2}’,$$) を$G=(F, T, V, P, S^{(n_{\delta}}),$$r_{1})],$.

$s $(x_{1}, \cdots,X_{n}.)$ ,$, あるいは$s $(X_{1}, \cdots, X_{n}.)$ のいずれとも単–化可能でない。
(2) 中の任意の書換規則対,(b) ある$\xi$$(l_{1}$$P$(a) あるに対して、$t_{n_{\epsilon}}\in\tau_{erm}(F, V)$$xiLeftarrow^{*} s(t_{1}c’\ldots, t_{n_{\delta}} )$項列とする。 任意の二つの規則 $R_{1}=[\alpha_{1}arrow\beta_{1},$$R_{2}=[\alpha_{2}arrow\beta_{2}, (l_{2}, r_{2})]$ と、 $1\leq i_{1}<i_{2}\leq|\eta|$ を満たす任意の自然数に対し、 もし、$[\alpha arrow\beta\, (\iota,r)]$(1)$\cdots,$$\mathrm{U}\mathrm{P}\mathrm{P}\mathrm{U}\mathrm{G}\text{、}\eta\in(CTerm(F, V)\cup\{})^{+}$$[\alphaarrow\beta, (l, r)]$$P$$t_{1},$$1,$$\delta’=\delta_{1}\sigma 1=\delta_{2}\sigma 2,$$| \delta’|\leq\min\{r_{1},l_{2}\}$ 。

$|\gamma|=i_{1}-1,$$\delta_{1}\sigma_{1}=\delta_{2}\sigma_{2}$$|\gamma,\beta_{1}’\sigma_{1}|=i_{2}-$および $Var(R_{1})$ 寡

222
により (そうでない時、 $R_{1},R_{2}$ に対して変$Var(R_{2})=\emptyset$

数の改名を行う)、$\delta_{1}\sim\delta_{2}$が成り立つ。

$\eta$

従って、$\delta 1\sigma_{1,\beta’\sigma\lambda}2,\cdot$$\alpha_{12}’\sigma
1,$$\xi_{1}=\gamma,$$\xi_{2}=\gamma,\beta_{1}’\sigma 1,$

となる。
が位置

$\delta 2\sigma 2,$ $\alpha’\sigma 22’\lambda$$\delta_{1}\sigma_{1}=\delta_{2}\sigma_{2}$$R_{2},$$R_{1}$$i_{1}$$.i_{2}’,$にはそれぞれであるので、
で逆適用可能となる。 つまり、$\xi_{1},$$\alpha_{2}’1^{R_{2^{\dot{l}’\sigma}}}2’ 2]\sigma_{2},$$\xi_{1}’\Leftarrow\gamma,$ $\alpha_{1}’\sigma_{1},$ $\delta_{22}\sigma,$$\xi_{2}$$\lambda$$\lambda 1^{R_{1^{*}},,\sigma}]\prime\prime$$\xi_{2}\Leftarrow^{11}.\gamma,$$\delta 1\sigma 1,$$\alpha 1\sigma 1,$$\alpha 2\sigma 2,$

口となり、 補題が成り立つ
定理 51[–意解析可能性] $G=(F, T, V, P_{S^{(}},n_{\delta})$ , $) を$(\xi=\gamma, \alpha_{1}’\sigma 1, \delta’, \alpha_{2}\sigma_{2}, \lambda’)$$\mathrm{U}\mathrm{P}\mathrm{P}\mathrm{U}\mathrm{G}\text{、}\eta\in(CTem(F, V)\cup\{})^{+}$。

を $G$ から生成可能な任意の複合項列とする。 もし、 ある項有,$\cdot$.. ,$t_{n_{s}}\in$$CTerm(F, V)$ に対し、.

.

$\eta 4 s(t_{1}, \cdots, t_{n_{\epsilon}} )$によっても書換えられることがない。 さらに、還元の定義 43 より、 に対する 換は、 規則ごとの逆適用範囲に限定され、 それ以外の複合項に変数の置換や、 項の代入などの影響はまったくない。 従って、 両方の規則を同時に逆適用することが可能である。

61 並列解析の定義
UPPUG において逆適用可能な複数の規則が、並列的に逆適用可能になるのは、 各規則が UPPUG の制約を満たし、 ある規則と他の規則とが逆適用位置において重なっても、 それらの部分が規則それぞれの文脈インデックスが示す範囲内にあるからである。 従って、各規則の文脈以外の部分を同時に書換えることにより、 並列還元が実現できる。
定義 61[並列還元] $G=(F, T, V, P, s^{(})n_{\delta}$ , $) を UP-$

を任意の複合項列とする。 二つの規則 $R_{1}=[\alpha_{1}arrow\beta_{1}, (l_{1}, r_{1})]$ と $R_{2}=$において、 にがそれぞれ位置
対して並列逆適用可能であるとは、 次の (1) または (2)が成り立つことを言う。

$\mathrm{P}\mathrm{U}\mathrm{G}_{\text{、}}\xi\in(c\tau_{er}m(F, V)\cup\{})^{+}$

が成り立つならば、となるような任意の$[R,j, \sigma]$ に対して、 次の還元が成り立つ。
$\eta\Leftarrow\xi[R,j, \sigma]$$[\alpha_{2}arrow\beta_{2}, (l_{2},r_{2})]$$\eta^{[R,\mathrm{j}}\dot{4}^{\sigma}\xi^{n-}\Leftarrow^{1}$$s tl,$\langle$(証明) 還元回数$\cdots,$ $t_{n_{s}}$)$に関する帰納法を用いる。 まず $n=1$の場合、 定理の成立が自明である。 $n=k-1$ の時に $-$意解析可能性が成り立つと仮定し、 次の ステップの還元を考える。
$n$(1)$i_{2}-i_{1}\geq|\beta_{1}|$$k$$[R_{11}\dot{\iota},\sigma_{1}]k_{\Leftarrow^{1}}-$$\eta’\Leftarrow\xi_{1}$$[R_{1}, i_{1}, \sigma_{1}]\neq[R_{2},$$s(t l,$i_{2},$$\cdots,$$tn_{\mathrm{g}}$$\{})^{+}$

かつ、 ある$\sigma_{1},$$\xi=\gamma,$ $\beta_{1}\sigma_{1},$)$$\theta,$$\sigma_{2}$$\gamma,$$i_{2}$$\xi$$\lambda\in(CTerm(F, V)\cup$$\theta,$が存在し、$\beta_{2}\sigma_{2},$$\lambda$と書ける。

であるようなラベ$\sigma_{2}|(i_{1}\neq i_{2})$と代入$i_{1},$

ル $[R_{2}, i_{2}, \sigma_{2}]$ が存在して、(2)$i_{2}-i_{1}\leq|\beta_{1}|$かっ、 ある$\gamma,$$\lambda,$$\delta_{2}\in(o\tau_{erm}(F, V)\cup\{})^{*}$$\alpha_{1}’,$$\beta_{1’ 2}\prime\prime\beta_{2}^{i}\alpha,,$と代入$\sigma_{1}.’\sigma_{2}$$\delta’,$$\delta 1$

,

が存在

し、

$\eta^{[R_{2},i}\Leftarrow^{2}’\xi_{2}\sigma 21$となる。 補題 51 により、 ある,$\xi’$と$i_{1}’,$$i_{2}’$が存在し、$\xi=\gamma,\beta_{11}’\sigma,$$\delta’,\beta’2\sigma_{2},\lambda$$R_{1}=[\alpha_{1}’\delta 1arrow\beta_{1}’\delta_{1}, (l_{1},r_{1})]$$\eta\Leftarrow’\xi 1\Leftarrow^{2}\xi[R_{1},i_{11}\sigma][R_{2},i^{l},\sigma_{2}]$$R_{2}=[\delta_{2}\alpha_{2}’arrow\delta_{2}\beta_{2}’, (l_{2},r_{2})]$$\eta^{[R_{2},i_{2}}\Leftarrow’\xi 2\Leftarrow\sigma_{2}][R_{1},i_{1’ 1}’]\sigma\xi’$$\delta’=\delta_{1}\sigma_{1}=\delta_{2}\sigma 2$が成り立つ。 帰納法の仮定により、.

$\xi_{1}\Leftarrow^{2}\xi\prime k\Leftarrow^{2}-R_{2},i’,\sigma_{2}].s(t_{1}, \cdots, t_{n_{s}} )$$| \delta’|\leq\min\{r_{1}, \iota_{2}\}$

$

を満たす。

であるので、$\eta^{[R_{2},i_{2\sigma_{2}}}\Leftarrow’]\xi_{2}\Leftarrow- k1s(t_{1}, \cdots, t_{n_{\epsilon}} )$

ここで、

$

口
が得られる。
このように UPPUG において、 開始記号まで還元可能 (同時に生成可能) な複合項列に対し、 規則をどのように逆適用しても、 その逆適用順番に依存せずに、 同じ
還元ステップ数で決定的に解析を進めることができる。
そして、 定義 44 から、 次の系を容易に導くことができる。すなわち、最左還元によって、 -意に解析を行うことが可能である。
系 51 $G$ $=$ $(F,T, V, P, S^{(n_{s}\rangle},$ を$(\dot{C}\tau_{erm}(F, V)\cup\{})^{+}$ を任意の複合項列とする。 ある$t_{n_{*}}\in\tau_{e}rm(F, V)$ に対して、
項$\mathrm{U}\mathrm{P}\mathrm{P}\mathrm{U}\mathrm{G}\text{、}\eta$$t_{1},$$\in$$\cdots,$$\eta\not\in s(t_{1}, \cdots, t_{n_{*}} )$$となるならば、$\eta_{\iota_{m\prime}}\not\in$$s(tl,$\cdots$,$t_{n_{\iota}}$)$$\eta$を(1) の場合:(2) の場合:$\eta=\gamma,$$\alpha_{1}\sigma 1,$$\eta=\gamma,$$\alpha’1\sigma 1,$$\lambda$$\theta,$$\alpha_{2}\sigma_{2},$$\delta’,$とする時、 $G$ において がよって得られたと言い、$\eta${[ il,$GR1,$$\xi\Leftarrow\eta$$\sigma_{1}$],$\alpha_{2}’\sigma 2,$$\xi$$\lambda$

から並列的な直接還元に$[R_{2},i_{2,\sigma_{2}]\}}$

または$\xi^{\{[}R_{1},i\mathrm{r},\sigma_{1\llcorner\cdot,]\}},G1R_{2},\cdot 2\sigma_{2}\eta$と書く。
上記の定義を $m$ 個の規則に対する並列還元に拡張するのは容易である (但し、 (2) の場合のように、規則の逆適用範囲が重なる時の記述が繁雑になる)。 このような並列的直接還元を$\xi\Leftarrow\eta\{[GR_{1},i_{1}, \sigma_{1}1, \cdots, [R_{m},i_{m},\sigma_{m}]\}$

が成り立つ。

口または]”$\xi^{\{[}\Leftarrow$$\eta R_{1},i_{1},\sigma_{1}$$,\cdots,[RGmim\sigma m]\}$6UPPUG の–意並列解析性と書く。

複合項列 に対して、逆適用可能な二つの規則が存在するならば、 UPPUG 条件により、の逆適用位置が重なっても、 その部分はいずれの規則の逆適用$R_{1},$ $R_{2}$$\eta$$R_{1},$ $R_{2}$口

UPPUG では、複合項列 に対して、複数の $m$ 個の規則が並列逆適用可能で、 それらによる並列還元と、 各々の規則が に逆適用可能で、 それゆえ、各規則を順番に
$\xi$

$\xi$

223
逆適用することが可能となり、その直列還元とが、 同値になることは次の補題により導くことができる。
補題 61 $G=(F,T, V, P, S^{(}n_{*})$ , $) を$(c\tau_{erm}(F, V)\cup\{})^{+}$ を複合項列、, R、を $P$
を代入
を非負の整数、中の規則、とする。 この時、 次の (1) と (2) が同値である。
$\ldots,m’\sigma_{m}$ }$\eta R_{11\sigma}:11_{\Leftarrow^{1Ri_{m},]}}$(1)$\cdots,\gamma_{m-1}\in(c\tau_{er}m(F, V)\cup\{})^{\tau-}$ と、非(2) あるに対して、負整数菟, . . ,$\mathrm{U}\mathrm{P}\mathrm{P}\mathrm{U}\mathrm{G}\text{、}\xi,$$R_{1},$$i_{1},$$\cdots,$$i_{m}$$\sigma_{1},$$\eta\in$$\cdots$$\cdots,\sigma_{m}$”’$\xi^{\{[}$

しに、解析が可能という –意解析可能性に加え、新たに並列還元が定義され、 –意並列解析可能性も併せ持つ文法体系である。 なおかつ、 UPG と同じく万能な生成文法である。 また、 非終端記号に引数を持たせ、 ユニフィ
ケーシ白$\sqrt[\text{、]{}}$

計算によって、情報のやり取りを簡潔に行うことができるので、 自然言語、 計算機言語などに対する文法の記述力が高められ、 文法の設計も容易になる。

$\gamma_{1},$$i_{m}’$$\cdot$$\xi^{[\iota}\Leftarrow^{1}\gamma 1R_{1},i^{l},\sigma_{1}\Leftarrow\ldots\Leftarrow\gamma_{m-1}\iota R_{m},i’\sigma\not\in’ m]\eta$(証明概略){[Rl,$i_{1},$ $\sigma_{1}],$$\cdots,$$[R_{m},$ $i_{m},$ $\sigma_{m}]$

}が

$\xi$

に並列逆

$\xi$

$\eta$

実行に当たって、容易に把握できるものである。そして、各規則には予め文脈インデックスを付随させ、 簡単に共有することができる。 従って、 逆適用可能な規則の数に応じて配置される、 しかもそれぞれの規則を逆適用する
並列プロセッサ同士が、 以上の情報を用いて、 規則の文
脈範囲以外の部分を同時に (並列に) 書換えることができる。

62-意並列解析性
定理 6.1[–意並列解析性] $G=(F, T, V, P, s^{(}n_{\delta})$ , $) をる。 ある項$t_{1},$$\cdots,$ $t_{n_{\epsilon}}\in Term(F, V)$$\eta\not\in s(t_{1}, \cdots, t_{n_{\epsilon}} )$を複合項列とすに対して、$ .

が成り立つと仮定する。 この時にもし、$\{[R_{1}, i_{1}, \sigma_{1}], \cdots, [R_{m}, i_{m}, \sigma m]\}\backslash$が.

に対して並列逆適用可能ならば、 ある複合項列$(c\tau_{er}m(F, V)\cup\{})^{+}$ が存在して、$\xi\in$$\eta$$\mathrm{Y}.\backslash \backslash$$\eta^{\{[:_{1}}’\Leftarrow’\xi R_{1},,\sigma 11\cdots,[R_{mm’ m}i\sigma]\}n-\Leftarrow^{m_{t_{1}}}S,$..

$\cdot \mathrm{e}$$t_{n_{\delta}}$$,$)$が成り立つ。
(証明) 補題 61 により、$\eta\Leftarrow[R_{1},i_{1}’,\sigma 11\ldots[R_{m},i’,\sigma_{m}]\not\in\xi$および$\eta^{\{[]_{\Leftarrow\xi}}R_{1},i1,\sigma 1,\cdots,[Rm’ im’\sigma m]\}$が成り立つ。 さらに、 に対し、 UPPUG の–意解析性(定理 51) を $m$ 回適用することによって、$\eta$’$\eta^{[R_{1},i\sigma]}\Leftarrow^{1’ 1}$...

[1] K. Morita, N. Nishihara, Y. Yamamoto and Z.
of uniquely parsable grammar
Zhang: Aclasses and deterministic acceptors, Acta Informatica, 34, 389-410, 1997.
[2] Y. Yamamoto and K. Morita: Two-dimensional
uniquely parsable isometric array grammars, International Journal of Pattem Recognition and Artificial Intelligence, 6, 301-313, 1992.
. Hopcroft and. Ullman: Introduction to[3]
Automata Theory, Languages, and Computation,
Addison-Wesley, Reading, Massachusetts, 1979.
[4]. Aho and . Ullman: The Theory of Parsing,Translation, and Compiling: Volume 1: Parsing,
Prentice-Hall, 1972.
$\mathrm{h}^{\mathrm{l}\mathrm{x}_{\mathrm{l}\mathrm{e}\mathrm{r}\mathrm{a}}}r\mathrm{c}\mathrm{h}\mathrm{y}$適用可能であることと、各々の $[R_{k}, i_{k}, \sigma_{k}](1\leq k\leq m)$
が に逆適用可能であることが同値であることは、 並列逆適用可能性の定義から明らかである。 また、 (1) の並列還元と (2) の直列還元のいずれによっても が得られる
ことは、補題 51 と同様の方法によって証明できる。 口規則の左右の長さや、 逆適用位置などは、 直接還元の$\mathrm{U}\mathrm{P}\mathrm{P}\mathrm{U}\mathrm{G}\text{、}\eta\in(c\tau_{er}m(F, V)\cup\{})+$

参考文献

$

$[R_{m},i’,\sigma_{m}]\not\in\xi^{n}\Leftarrow\-m(\mathit{8}t_{1}, \cdots, t_{n_{\epsilon}} )$が得られる。 従って、$$\eta^{\mathrm{t}1R_{1}}’ i_{1},\sigma 1]_{\Leftarrow^{1Ri\sigma_{m}]}},\cdots,n’ m’\}\xi S(n_{\Leftarrow\}-mt_{1}, \cdots, t_{n_{\epsilon}} )$となり、 定理が成り立つ。

口

7 まとめ
本研究では、 ユニフィケーション文法の書換
規則に文脈インデックスを導入し、そして、 UPG における書換規則の制約と同様の制約を加えることにより、 $-$意並列解析可能ユニフィケーション文法 (UPPUG) の定式化を行った。 UPPUG は UPG のバックトラックな$(\mathrm{U}\mathrm{G})$$\mathrm{J}.\mathrm{D}$$\mathrm{J}.\mathrm{E}$$\mathrm{A}.\mathrm{V}$$\mathrm{J}.\mathrm{D}$[5] G. Gazdar and C. Mellish: Natural language processing in LISP : an introduction to computational
linguistics, Addison-Wesley Publishing Company,, 1989.
Menlo Park,$\mathrm{C}\mathrm{A}$