Another grammatical system, known as a categorial grammar [1] bears some resemblance to link grammars. Below we show how to express any categorial grammar concisely as a link grammar. It appears to be more difficult to express a link grammar as a categorial grammar.
Just as in a link grammar, each word of a categorial grammar is
associated with one or more symbolic expressions. An expression is
either an atomic symbol or a pair of expressions combined with one of
two types of binary operators: / and \.
A sentence is in the language defined by the categorial grammar if, after choosing one expression associated with each word, there is a derivation which transforms the chosen sequence of expressions into S, a single expression consisting of a special atomic symbol. The derivation proceeds by combining two neighboring expressions into one using one of the following rules:
Here 
and 
are arbitrary expressions, and 
and
are other expressions built using and . In both cases
the two expressions being combined (the ones shown above the line)
must be adjacent in the current sequence of expressions. Each
combinational operation produces one expression (the one below the
line), and reduces the number of expressions by one. After 
operations have been applied, a sentence of length 
has be reduced
to one expression.
For example, consider the following categorial grammar [9]:
Harry: NP, S/(S\NP) likes: (S\NP)/NP peanuts: NP passionately: (S\NP)\(S\NP)
Here is the derivation of Harry likes peanuts passionately.
Harry likes peanuts passionately
S/(S\NP) (S\NP)/NP NP (S\NP)\(S\NP)
---------------
S/NP
----------------------------
S\NP
--------------------------------
S
The set of languages that can be represented by categorial grammars
(as they are described here) is the set of context-free
languages [1]
This fact alone sheds no light on the way in which the
formalism represents a language. To get a better understanding of the
connection between categorial grammars and link grammars, the
following paragraphs explain a way to construct a link grammar for a
given categorial grammar. The reverse (constructing a categorial
grammar from a given link grammar) seems to be more difficult, and we
do not know of an elegant way to do this.
To simplify the construction, we'll use a modified definition of a link grammar called a special link grammar. This differs from an ordinary link grammar in two ways: the links are not allowed to form cycles, and there is a special word at the beginning of each sentence called the wall. The wall will not be viewed as being part of any sentence.
Let 
be a categorial grammar expression. We'll show how to build
an equivalent link grammar expression 
. If a word 
has the
set 
of categorial expressions, then we'll
give that word the following link grammar expression:
The function
is defined recursively as follows:
Here
stands for any atomic symbol from the categorial grammar, and
,
and
are connector names in the link grammar formulas.
The wall has the formula S+.
Here is the link grammar corresponding to the categorial grammar above:
WALL: S+;
peanuts: NP+ or NP-;
Harry:
(NP- or NP+)
or (S/<S\NP>-
or S/<S\NP>+
or (S\NP+ & (S+ or S-)));
likes:
<S\NP>/NP- or <S\NP>/NP+
or (NP+ & (S\NP- or S\NP+
or (S- & (NP- or NP+))));
passionately:
<S\NP>/<S\NP>- or <S\NP>/<S\NP>+
or (S\NP- & (S\NP- or S\NP+
or (S- & (NP- or NP+))));
(Here we have replaced parentheses in the categorial grammar expressions with brackets when using them inside of a link grammar expression.)
This link grammar gives the following analysis of the sentence shown above:
to 20bp
Notice that in this construction, both the size of the link grammar formula, and the number of disjuncts it represents are linear in the size of the original categorial grammar expressions. This suggests that a very efficient way to parse a categorial grammar would be to transform it to a link grammar, then apply the algorithms and heuristics described in this paper.