リンク文法
リンク文法では、単語同士のリンクの結びつき方によって文法規則を表現する。例えば"The cat chased a snake."という文であれば
というようなリンクを張る事が出来るため、英文として合法である。尚、この時の文法規則は
である。ここで、&は左右両方が同時に使われる事を意味し、orは左右どちらか一方が使われる事を意味する。{A+}と書いた場合には(A+ or ())という意味になり、要するに省略可能な条件となる。又、@A+と書いた場合にはA+が1個以上何個でも伸ばせる事を意味する。又、+はリンクが右に伸びる事を意味し、-はリンクが左に伸びる事を意味する。他の記法に[A+]及び[[A+]]がLink Grammar Parserには存在するが、viterbi/READMEに書いてあるので詳細は省く。
リンクを張る際には、以下の3つの制約を守る必要がある。
平面性(Planarity):平面上に記述した時に、リンク同士は交わらない
結合性(Connectivity):文中の全てのリンクが成立(suffice)されなければならない
満足性(Satisfaction):文中の全ての語の条件が満足(satisfy)されなければならない
リンク文法の能力は文脈自由文法と等しい。又、動的計画法に基づくリンク算出の計算量は、単語数 n {\displaystyle n} に対し O ( n 3 ) {\displaystyle O(n^{3})} である。