Link grammar

Connectors may also include head-dependent indicators h and d. In this case, a connector containing a head indicator is only allowed to connect to a connector containing the dependent indicator (or to a connector without any h-d indicators on it). When these indicators are used, the link is decorated with arrows to indicate the link direction.[10]

A recent extension simplifies the specification of connectors for languages that have little or no restrictions on word-order, such as Lithuanian. There are also extensions to make it easier to support languages with concatenative morphologies.

The parsing algorithm also requires that the final graph is a planar graph, i.e. that no links cross.[10] This constraint is based on empirical psycho-linguistic evidence that, indeed, for most languages, in nearly all situations, dependency links really do not cross.[12][13] There are rare exceptions, e.g. in Finnish, and even in English; they can be parsed by link-grammar only by introducing more complex and selective connector types to capture these situations.

Connectors can have an optional floating-point cost markup, so that some are "cheaper" to use than others, thus giving preference to certain parses over others.[10] That is, the total cost of parse is the sum of the individual costs of the connectors that were used; the cheapest parse indicates the most likely parse. This is used for parse-ranking multiple ambiguous parses. The fact that the costs are local to the connectors, and are not a global property of the algorithm makes them essentially Markovian in nature.[14][15][16][17][18][19]

The assignment of a log-likelihood to linkages allows link grammar to implement the semantic selection of predicate-argument relationships. That is, certain constructions, although syntactically valid, are extremely unlikely. In this way, link grammar embodies some of the ideas present in operator grammar.

Because the costs are additive, they behave like the logarithm of the probability (since log-likelihoods are additive), or equivalently, somewhat like the entropy (since entropies are additive). This makes Link Grammar compatible with machine learning techniques such as hidden Markov models and the Viterbi algorithm, because the link costs correspond to the link weights in Markov networks or Bayesian networks.

The Link Grammar link types can be understood to be the types in the sense of type theory.[10][20] In effect, the Link Grammar can be used to model the internal language of certain (non-symmetric) compact closed categories, such as pregroup grammars. In this sense, Link Grammar appears to be isomorphic or homomorphic to some categorial grammars. Thus, for example, in a categorial grammar the noun phrase "the bad boy" may be written as

${\displaystyle {{\text{the}} \atop {\text{NP/N,}}}{{\text{bad}} \atop {\text{N/N,}}}{{\text{boy}} \atop {\text{N}}}}$

whereas the corresponding disjuncts in Link Grammar would be

the: D+;
bad: A+;
boy: D- & A-;

The contraction rules (inference rules) of the Lambek calculus can be mapped to the connecting of connectors in Link Grammar. The + and - directional indicators correspond the forward and backward-slashes of the categorical grammar. Finally, the single-letter names A and D can be understood as labels or "easy-to-read" mnemonic names for the rather more verbose types NP/N, etc.

The primary distinction here is then that the categorical grammars have two type constructors, the forward and backward slashes, that can be used to create new types (such as NP/N) from base types (such as NP and N). Link-grammar omits the use of type constructors, opting instead to define a much larger set of base types having compact, easy-to-remember mnemonics.

A basic rule file for an SVO language might look like:

<determiner>     D+;
<noun-subject>  {D−} &  S+;
<noun-object>   {D−} &  O−;
<verb>           S−  & {O+};

Thus the English sentence, "The boy painted a picture" would appear as:

           +-----O-----+
 +-D-+--S--+     +--D--+
 |   |     |     |     |
The boy painted  a  picture

Similar parses apply for Chinese.[21]

Conversely, a rule file for a null subject SOV language might consist of the following links:

<noun-subject>   S+;
<noun-object>    O+;
<verb>          {O−} & {S−};

And a simple Persian sentence, man nAn xordam (من نان خوردم) 'I ate bread' would look like:[22][23][24]

 +-----S-----+
 |     +--O--+
 |     |     |
man   nAn xordam

VSO order can be likewise accommodated, such as for Arabic.[25]

In many languages with a concatenative morphology, the stem plays no grammatical role; the grammar is determined by the suffixes. Thus, in Russian, the sentence 'вверху плыли редкие облачка' might have the parse:[26][27]

    +------------Wd-----------+---------------SIp---------------+
    |         +-------EI------+              +--------Api-------+
    |         |      +--LLCZD-+       +-LLAQZ+         +--LLCAO-+
    |         |      |        |       |      |         |        |
LEFT-WALL вверху.e плы.= =ли.vnndpp ре.= =дкие.api облачк.= =а.ndnpi

The subscripts, such as '.vnndpp', are used to indicate the grammatical category. The primary links: Wd, EI, SIp and Api connect together the suffixes, as, in principle, other stems could appear here, without altering the structure of the sentence. The Api link indicates the adjective; SIp denotes subject-verb inversion; EI is a modifier. The Wd link is used to indicate the head noun; the head verb is not indicated in this sentence. The LLXXX links serve only to attach stems to suffixes.

The link-grammar can also indicate phonological agreement between neighboring words. For example:

                     +---------Ost--------+
    +------>WV------>+   +------Ds**x-----+
    +----Wd---+-Ss*b-+   +--PHv-+----A----+
    |         |      |   |      |         |
LEFT-WALL that.j-p is.v an abstract.a concept.n

Here, the connector 'PH' is used to constrain the determiners that can appear before the word 'abstract'. It effectively blocks (makes it costly) to use the determiner 'a' in this sentence, while the link to 'an' becomes cheap. The other links are roughly as in previous examples: S denoting subject, O denoting object, D denoting determiner. The 'WV' link indicates the head verb, and the 'W' link indicates the head noun. The lower-case letters following the upper-case link types serve to refine the type; so for example, Ds can only connect to a singular noun; Ss only to a singular subject, Os to a singular object. The lower-case v in PHv denotes 'vowel'; the lower-case d in Wd denotes a declarative sentence.

The Vietnamese language sentence "Bữa tiệc hôm qua là một thành công lớn" - "The party yesterday was a great success" may be parsed as follows:[28]

• Arabic Link Grammar extension (Source package)
• Persian Link Grammar extension
• Online Persian demonstration
• Russian Link Grammar demonstration
• Turkish Link Grammar extension developed as Master's degree thesis