索引言語

インデックス言語はアルフレッド・エイホによって発見された形式言語の一種である。^{[1]インデックス言語は}インデックス文法によって記述され、ネストされたスタックオートマトンによって認識される。^[2]

インデックス言語は文脈依存言語の適切なサブセットです。^{[1]インデックス言語は}抽象言語族（さらには完全なAFL）として適格であり、したがって多くの閉包特性を満たしています。ただし、交差や補集合に対しては閉じていません。^[1]

インデックス言語のクラスは、自然言語で発生する多くの非局所的制約をインデックス文法で記述できるため、計算的に容易な^[^{引用が必要}^]な文脈自由言語の一般化として自然言語処理において実用的な重要性を持っています。

ジェラルド・ガズダール（1988）^[3] とビジェイ・シャンカー（1987）^[4]は、現在では線形索引文法（LIG）として知られている、軽度文脈依存の言語クラスを導入した。 ^{[5]線形索引文法には、IGに比べて追加の制限がある。LIGは}木隣接文法と弱等価（同じ言語クラスを生成する）である。^[6]

例

次の言語はインデックス化されていますが、コンテキストフリーではありません。

\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}

^[3]

\{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}

^[2]

これら 2 つの言語もインデックス化されていますが、Gazdar の特徴によれば、コンテキストにほとんど依存しません。

\{a^{2^{n}}|n\geq 0\}

^[2]

\{www|w\in \{a,b\}^{+}\}

^[3]

一方、以下の言語は索引付けされていない。^[7]

\{(ab^{n})^{n}|n\geq 0\}

プロパティ

ホップクロフトとウルマンは、インデックス言語は次のようないくつかの形式主義によって生成されるため、「自然な」クラスであると考える傾向がある。^[9]

アホの索引文法書^[1]
アホの一方向ネストスタックオートマトン^[10]
フィッシャーのマクロ文法^[11]
積み重ねられたスタックを持つグライバッハのオートマトン^[12]
マイバウムの代数的特徴付け^[13]

林^[14]はポンピング補題をインデックス文法に一般化した。逆に、ギルマン^[7]はインデックス言語に対して「縮小補題」を与えている。

参照

チョムスキー階層

参考文献

^ abcd Aho, Alfred (1968). 「索引文法—文脈自由文法の拡張」Journal of the ACM . 15 (4): 647–671. doi : 10.1145/321479.321488 . S2CID 9539666.
^ abc パーティー、バーバラ;ター・ミューレン、アリス; ウォール、ロバート・E. (1990).言語学における数学的手法. クルーワー・アカデミック・パブリッシャーズ. pp. 536–542. ISBN 978-90-277-2245-4。
^ abc Gazdar, Gerald (1988). 「インデックス文法の自然言語への適用可能性」 Reyle, U.; Rohrer, C. (編)自然言語解析と言語理論言語学と哲学の研究第35巻 Springer Netherlands. pp. 69–94. doi :10.1007/978-94-009-1337-0_3. ISBN 978-94-009-1337-0。
^ Vijayashanker, K. (1987).木結合文法の研究(論文). ProQuest 303610666.
^ カルマイヤー、ローラ（2010）。文脈自由文法を超えた構文解析。シュプリンガー。p. 31。ISBN 978-3-642-14846-0。
^ Kallmeyer, Laura (2010年8月16日). Parsing Beyond Context-Free Grammars. Springer. p. 32. ISBN 978-3-642-14846-0。
^ ab Gilman, Robert H. (1996). 「インデックス付き言語の縮小補題」.理論計算機科学. 163 (1–2): 277–281. arXiv : math/9509205 . doi :10.1016/0304-3975(96)00244-7. S2CID 14479068.
^ ホップクロフト、ジョン、ウルマン、ジェフリー(1979)。オートマトン理論、言語、計算入門。アディソン・ウェズリー。p. 390。ISBN 978-0-201-02988-8。
^ オートマトン理論、言語、計算入門、^[8]書誌注記、p.394-395
^ Aho, Alfred V. (1969 年 7 月). 「Nested Stack Automata」. Journal of the ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID 685569.
^ Fischer, Michael J. (1968 年 10 月). 「マクロのような生成を持つ文法」.第 9 回スイッチングおよびオートマトン理論に関する年次シンポジウム (Swat 1968) . 第 9 回スイッチングおよびオートマトン理論に関する年次シンポジウム(Swat 1968) . pp. 131–142. doi :10.1109/SWAT.1968.12.
^ Greibach, Sheila A. (1970年3月). 「完全なAFLとネストされた反復置換」.情報と制御. 16 (1): 7–35. doi :10.1016/s0019-9958(70)80039-0.
^ Maibaum, TSE (1974年6月). 「形式言語への一般化されたアプローチ」. Journal of Computer and System Sciences . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .
^ 林毅 (1973). 「インデックス文法の導出木について: {$uvwxy$}定理の拡張」.数理解析研究所刊行物. 9 (1): 61–92. doi : 10.2977/prims/1195192738 .

外部リンク

「Prolog における NLP」のインデックス付き文法と言語に関する章

[aho1968-1] Aho, Alfred (1968). 「索引文法—文脈自由文法の拡張」Journal of the ACM . 15 (4): 647–671. doi : 10.1145/321479.321488 . S2CID 9539666.

[partee_etal_1990-2] パーティー、バーバラ;ター・ミューレン、アリス; ウォール、ロバート・E. (1990).言語学における数学的手法. クルーワー・アカデミック・パブリッシャーズ. pp. 536–542. ISBN 978-90-277-2245-4。

[gazdar1998-3] Gazdar, Gerald (1988). 「インデックス文法の自然言語への適用可能性」 Reyle, U.; Rohrer, C. (編)自然言語解析と言語理論言語学と哲学の研究第35巻 Springer Netherlands. pp. 69–94. doi :10.1007/978-94-009-1337-0_3. ISBN 978-94-009-1337-0。

[4] Vijayashanker, K. (1987).木結合文法の研究(論文). ProQuest 303610666.

[Kallmeyer2010-5] カルマイヤー、ローラ（2010）。文脈自由文法を超えた構文解析。シュプリンガー。p. 31。ISBN 978-3-642-14846-0。

[Kallmeyer2010b-6] Kallmeyer, Laura (2010年8月16日). Parsing Beyond Context-Free Grammars. Springer. p. 32. ISBN 978-3-642-14846-0。

[Gilman.1996-7] Gilman, Robert H. (1996). 「インデックス付き言語の縮小補題」.理論計算機科学. 163 (1–2): 277–281. arXiv : math/9509205 . doi :10.1016/0304-3975(96)00244-7. S2CID 14479068.

[hopcroft_ullman_1979-8] ホップクロフト、ジョン、ウルマン、ジェフリー(1979)。オートマトン理論、言語、計算入門。アディソン・ウェズリー。p. 390。ISBN 978-0-201-02988-8。

[9] オートマトン理論、言語、計算入門、^[8]書誌注記、p.394-395

[10] Aho, Alfred V. (1969 年 7 月). 「Nested Stack Automata」. Journal of the ACM . 16 (3): 383–406. doi : 10.1145/321526.321529 . S2CID 685569.

[11] Fischer, Michael J. (1968 年 10 月). 「マクロのような生成を持つ文法」.第 9 回スイッチングおよびオートマトン理論に関する年次シンポジウム (Swat 1968) . 第 9 回スイッチングおよびオートマトン理論に関する年次シンポジウム(Swat 1968) . pp. 131–142. doi :10.1109/SWAT.1968.12.

[12] Greibach, Sheila A. (1970年3月). 「完全なAFLとネストされた反復置換」.情報と制御. 16 (1): 7–35. doi :10.1016/s0019-9958(70)80039-0.

[13] Maibaum, TSE (1974年6月). 「形式言語への一般化されたアプローチ」. Journal of Computer and System Sciences . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .

[14] 林毅 (1973). 「インデックス文法の導出木について: {$uvwxy$}定理の拡張」.数理解析研究所刊行物. 9 (1): 61–92. doi : 10.2977/prims/1195192738 .