リンク文法

リンク文法（）は、Davy TemperleyとDaniel Sleatorにより発明された文法理論である。依存文法の一種であり、単語間の関係を元にして文が合成されるというアプローチをとる。例えば「冠詞(例：The)と名詞(例：apple)はこの順序で出現する」という文法規則は、Theに条件(linking requirements)codice_1を、appleには条件codice_2を持たせておき、Theとappleをリンクcodice_3によって満足させる(satisfied)事によって表現する。
概要.
リンク文法では、単語同士のリンクの結びつき方によって文法規則を表現する。例えば"The cat chased a snake."という文であれば
 +---O---+
 +-D-+--S--+ +-D-+
The cat chased a snake.
というようなリンクを張る事が出来るため、英文として合法である。尚、この時の文法規則は
a the: D+
snake cat: D- & (O- or S+)
chased: S- & O+
である。ここで、&は左右両方が同時に使われる事を意味し、orは左右どちらか一方が使われる事を意味する。codice_4と書いた場合にはcodice_5という意味になり、要するに省略可能な条件となる。又、codice_6と書いた場合にはcodice_7が1個以上何個でも伸ばせる事を意味する。又、+はリンクが右に伸びる事を意味し、-はリンクが左に伸びる事を意味する。他の記法にcodice_8及びcodice_7がLink Grammar Parserには存在するが、viterbi/READMEに書いてあるので詳細は省く。
リンクを張る際には、以下の3つの制約を守る必要がある。
リンク文法の能力は文脈自由文法と等しい。又、動的計画法に基づくリンク算出の計算量は、単語数formula_1に対しformula_2である。