範囲連結文法

範囲連結文法（RCG）は、1998年にピエール・ブーリエ^[1]によって開発された文法形式であり、軽度の文脈依存言語の範囲外にある中国語の数字やドイツ語の語順の混乱などの自然言語の多くの現象を特徴付ける試みである。^[2]

理論的な観点からは、多項式時間で解析できる言語はすべて、正範囲連結文法と呼ばれるRCGのサブセットに属し、逆もまた同様である。^[4]

RCG は Groenink のリテラル移動文法(LMG)の変形として意図されていますが、文法プロセスを生成としてではなく証明として扱います。LMG が開始述語から終端文字列を生成するのに対し、RCG は開始述語 (終端文字列を述語とする) を空文字列に縮約することを目指しており、これが言語における終端文字列のメンバーシップの証明を構成します。

正の範囲連結文法( PRCG) はタプルです。ここで、 ${\displaystyle G=(N,~T,~V,~S,~P)}$

• ${\displaystyle N}$、およびは、それぞれ述語名、終端記号、および変数名の互いに素な有限集合です。各述語名には、関数 によって指定された関連するアリティがあります。${\displaystyle T}$${\displaystyle V}$${\displaystyle \dim :N\rightarrow \mathbb {N} \setminus \{0\}}$
• ${\displaystyle S\in N}$開始述語名と検証です。${\displaystyle \dim(S)=1}$
• ${\displaystyle P}$は形式 の節の有限集合であり、 は形式 の述語であり、 と が含まれる。${\displaystyle \psi _{0}\rightarrow \psi _{1}\ldots \psi _{m}}$${\displaystyle \psi_{i}}$${\displaystyle A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}$${\displaystyle A_{i}\in N}$${\displaystyle \alpha _{i}\in (T\cup V)^{\star }}$

負の範囲連結文法( NRCG) は PRCG と同様に定義されますが、節の右側に出現する一部の述語が の形式を持つことができる点が加わります。このような述語は、否定述語と呼ばれます。 ${\displaystyle {\overline {A_{i}(\alpha _{1},\ldots ,\alpha _{\dim(A_{i})})}}}$

範囲連結文法は、肯定的なものか否定的なものかのどちらかです。PRCG は技術的には NRCG ですが、これらの用語は否定述語の不在 (PRCG) または存在 (NRCG) を強調するために使用されます。

単語内の範囲は、 のカップルで、 はの長さです。変数は範囲にバインドされますが、非終端記号の任意の文字列にはバインドされません。2 つの範囲 と は、 の場合にのみ連結でき、次のようになります。 節をインスタンス化する場合、引数は の複数の要素で構成され、それらの範囲は連結される必要があります。 ${\displaystyle w\in T^{\star }}$${\displaystyle \langle l,r\rangle _{w}}$${\displaystyle 0\leq l\leq r\leq n}$${\displaystyle n}$${\displaystyle w}$${\displaystyle \langle l_{1},r_{1}\rangle _{w}}$${\displaystyle \langle l_{2},r_{2}\rangle _{w}}$${\displaystyle r_{1}=l_{2}}$${\displaystyle \langle l_{1},r_{1}\rangle _{w}\cdot \langle l_{2},r_{2}\rangle _{w}=\langle l_{1},r_{2 }\rangle _{w}}$${\displaystyle T\cup V}$

単語 の場合、範囲のドット表記は次のようになります。 ${\displaystyle w=w_{1}w_{2}\ldots w_{n}}$${\displaystyle w_{i}\in T}$${\displaystyle \langle l,r\rangle _{w}=w_{1}\ldots w_{l-1}\bullet w_{l}\ldots w_{r-1}\bullet w_{r}\ldots w_{n}}$

書き換えられる述語の文字列は、テストされる文字列が満たさなければならない制約 (正の場合)、または否定述語の場合は満たさなければならない制約を表します。述語の順序は関係ありません。書き換え手順は、1 つの制約を 0 個以上のより単純な制約に置き換えることと同じです。

LMG と同様に、RCG 節には一般的なスキーマ があり、RCG では は空の文字列または述語の文字列のいずれかです。引数は終端記号や変数記号の文字列で構成され、LMG と同様に実際の引数値に対してパターン マッチングが行われます。隣接する変数はパーティションに対するマッチング ファミリを構成するため、2 つの変数を持つ引数 は、リテラル文字列と 3 つの異なる方法でマッチングします。これにより、その引数を含む節の 3 つの異なるインスタンス化が生成されます。 ${\displaystyle A(x_{1},...,x_{n})\to \alpha }$${\displaystyle \alpha}$${\displaystyle x_{i}}$${\displaystyle xy}$${\displaystyle ab}$${\displaystyle x=\epsilon ,\ y=ab;\ x=a,\ y=b;\ x=ab,\ y=\epsilon }$${\displaystyle xy}$

述語項には、正 (成功した場合は空の文字列を生成) と負 (失敗した場合/正の項が空の文字列を生成しない場合は空の文字列を生成) の 2 つの形式があります。負の項は、 のように、上線を使用して正の項と同じように示されます。 ${\displaystyle {\overline {A(x_{1},...,x_{n})}}}$

RCG の書き換えセマンティクスはかなり単純で、LMG の対応するセマンティクスと同一です。述語文字列 （記号は終端文字列）が与えられた場合、述語文字列が一致する文法規則があれば、述語文字列は に置き換えられ、各 内の一致した変数が に置き換えられます。 ${\displaystyle A(\alpha _{1},...,\alpha _{n})}$${\displaystyle \alpha_{i}}$${\displaystyle A(x_{1},...,x_{n})\to \beta }$${\displaystyle \beta}$${\displaystyle x_{i}}$

たとえば、 という規則があり、と が変数記号で、と が終端記号である場合、のときにが一致するため、述語文字列は と書き直すことができます。同様に、 という規則がある場合、は と書き直すことができます。 ${\displaystyle A(x,ayb)\to B(axb,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle a}$${\displaystyle b}$${\displaystyle A(a,abb)}$${\displaystyle B(aab,b)}$${\displaystyle A(a,abb)}$${\displaystyle A(x,ayb)}$${\displaystyle x=a,\ y=b}$${\displaystyle A(x,ayb)\to A(x,x)\ A(y,y)}$${\displaystyle A(a,abb)}$${\displaystyle A(a,a)\ A(b,b)}$

文字列の証明/認識は、 が空の文字列を生成することを示すことによって行われます。個々の書き換えステップでは、複数の代替変数の一致が可能な場合、証明全体を成功に導く可能性のある書き換えが考慮されます。したがって、最初の文字列から空の文字列を生成する方法が少なくとも 1 つある場合、失敗する他の方法がいくつ存在するかに関係なく、証明は成功と見なされます。 ${\displaystyle \alpha}$${\displaystyle S(\alpha )}$${\displaystyle S(\alpha )}$

RCG は、次のように非線形インデックス言語を認識できます。 ${\displaystyle \{www:w\in \{a,b\}^{*}\}}$

x、y、zを変数記号とすると、 abbabbbabb の証明は次のようになる 。$${\displaystyle {\begin{aligned}S(xyz)&\to A(x,y,z)\\A(ax,ay,az)&\to A(x,y,z)\\A(bx,by,bz)&\to A(x,y,z)\\A(\epsilon ,\epsilon ,\epsilon )&\to \epsilon \end{aligned}}}$$

${\displaystyle S(abbabbabb)\Rightarrow A(abb,abb,abb)\Rightarrow A(bb,bb,bb)\Rightarrow A(b,b,b)\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

または、範囲にもっと正確なドット表記法を使用します。

${\displaystyle S(\bullet {}abbabbabb\bullet {})\Rightarrow A(\bullet {}abb\bullet {}abbabb,abb\bullet {}abb\bullet {}abb,abbabb\bullet {}abb\bullet {})\Rightarrow A(a\bullet {}bb\bullet {}abbabb,abba\bullet {}bb\bullet {}abb,abbabba\bullet {}bb\bullet {})}$ ${\displaystyle \Rightarrow A(ab\bullet {}b\bullet {}abbabb,abbab\bullet {}b\bullet {}abb,abbabbab\bullet {}b\bullet {})\Rightarrow A(\epsilon ,\epsilon ,\epsilon )\Rightarrow \epsilon }$

文字列の場合、最初の節のさまざまなインスタンス化がありますが、すべての文字をそれぞれにするインスタンス化のみが、導出が に到達することを可能にします。 ${\displaystyle 3n}$${\displaystyle {\binom {3n+2}{2}}={\frac {(3n+2)(3n+1)}{2}}}$${\displaystyle x,y,z}$${\displaystyle n}$${\displaystyle \epsilon }$

すべての文脈自由文法(CFG) は範囲連結文法に変換できます。

• CFG のすべての非終端記号に対して、RCG にはアリティ述語があります。${\displaystyle A}$${\displaystyle 1}$${\displaystyle A(x)}$
• すべての CFG ルールに対して、RCG には があります。${\displaystyle A\to BC}$${\displaystyle A(xy)\to B(x)C(y)}$
• すべての CFG ルール(終端) に対して、RCG には があります。${\displaystyle A\to a}$${\displaystyle a}$${\displaystyle A(a)\to \epsilon }$

2 つの範囲連結言語の積集合と和集合は、明らかに範囲連結言語です。

• との共通部分については、 となります。${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S(x)\to A(x)B(x)}$
• と の和集合については、 およびとなります。${\displaystyle S}$${\displaystyle A}$${\displaystyle B}$${\displaystyle S(x)\to A(x)}$${\displaystyle S(x)\to B(x)}$

負の範囲連結言語も集合補集合の下で閉じている可能性があります。

上記の結果、 （正の）範囲連結言語が空でないかどうかは決定不可能である。これは、2 つの文脈自由言語の積集合が空でないかどうかは決定不可能であるためである。したがって、範囲連結文法は生成的ではない。