Categorial grammar is a family of formalisms in natural language syntax that share the central assumption that syntactic constituents combine as functions and arguments. Categorial grammar posits a close relationship between the syntax and semantic composition, since it typically treats syntactic categories as corresponding to semantic types. Categorial grammars were developed in the 1930s by Kazimierz Ajdukiewicz and in the 1950s by Yehoshua Bar-Hillel and Joachim Lambek. It saw a surge of interest in the 1970s following the work of Richard Montague, whose Montague grammar assumed a similar view of syntax. It continues to be a major paradigm, particularly within formal semantics.
A categorial grammar consists of two parts: a lexicon, which assigns a set of types (also called categories) to each basic symbol, and some type inference rules, which determine how the type of a string of symbols follows from the types of the constituent symbols. It has the advantage that the type inference rules can be fixed once and for all, so that the specification of a particular language grammar is entirely determined by the lexicon.
A categorial grammar shares some features with the simply typed lambda calculus.Whereas the lambda calculus has only one function type
A → B
B/A
A\backslashB
B/A
B
A
A\backslashB
B
A
The notation is based upon algebra. A fraction when multiplied by (i.e. concatenated with) its denominator yields its numerator. As concatenation is not commutative, it makes a difference whether the denominator occurs to the left or right. The concatenation must be on the same side as the denominator for it to cancel out.
The first and simplest kind of categorial grammar is called a basic categorial grammar, or sometimes an AB-grammar (after Ajdukiewicz and Bar-Hillel).Given a set of primitive types
Prim
Tp(Prim)
Prim\subseteqTp(Prim)
X,Y\inTp(Prim)
(X/Y),(Y\backslashX)\inTp(Prim)
A basic categorial grammar is a tuple
(\Sigma,Prim,S,\triangleleft)
\Sigma
Prim
S\inTp(Prim)
The relation
\triangleleft
(\triangleleft)\subseteqTp(Prim) x \Sigma
TYPE\triangleleftsymbol
Such a grammar for English might have three basic types
(N,NP,andS)
N
NP
S
N/N
NP/N
NP\backslashS
(NP\backslashS)/NP
S
For example, take the string "the bad boy made that mess". Now "the" and "that" are determiners, "boy" and "mess" are nouns, "bad" is an adjective, and "made" is a transitive verb, so the lexicon is.
and the sequence of types in the string is
{the\atop{NP/N,}} {bad\atop{N/N,}} {boy\atop{N,}} {made\atop{(NP\backslashS)/NP,}} {that\atop{NP/N,}} {mess\atop{N}}
now find functions and appropriate arguments and reduce them according to the two inference rules
X\leftarrowX/Y, Y
X\leftarrowY, Y\backslashX
. NP/N, N/N, N, (NP\backslashS)/NP, \underbrace{NP/N, N}
. NP/N, N/N, N, \underbrace{(NP\backslashS)/NP, NP}
. NP/N, \underbrace{N/N, N}, (NP\backslashS)
. \underbrace{NP/N, N}, (NP\backslashS)
. \underbrace{NP, (NP\backslashS)}
. S
The fact that the result is
S
Categorial grammars of this form (having only function application rules) are equivalent in generative capacity to context-free grammars and are thus often considered inadequate for theories of natural language syntax. Unlike CFGs, categorial grammars are lexicalized, meaning that only a small number of (mostly language-independent) rules are employed, and all other syntactic phenomena derive from the lexical entries of specific words.
Another appealing aspect of categorial grammars is that it is often easy to assign them a compositional semantics, by first assigning interpretation types to all the basic categories, and then associating all the derived categories with appropriate function types. The interpretation of any constituent is then simply the value of a function at an argument. With some modifications to handle intensionality and quantification, this approach can be used to cover a wide variety of semantic phenomena.
A Lambek grammar is an elaboration of this idea that has aconcatenation operator for types, and several other inference rules.Mati Pentus has shown that these still have the generative capacity ofcontext-free grammars.
For the Lambek calculus, there is a type concatenationoperator
\star
Prim\subseteqTp(Prim)
X,Y\inTp(Prim)
(X/Y),(X\backslashY),(X\starY)\inTp(Prim)
The Lambek calculus consists of several deduction rules, which specifyhow type inclusion assertions can be derived. In the followingrules, upper case roman letters stand for types, upper case Greekletters stand for sequences of types. A sequent of the form
X\leftarrow\Gamma
The process is begun by the Axiom rule, which has no antecedents andjust says that any type includes itself.
(Axiom) {{}\overX\leftarrowX}
The Cut rule says that inclusions can be composed.
(Cut) {Z\leftarrow\DeltaX\Delta' X\leftarrow\Gamma \over Z\leftarrow\Delta\Gamma\Delta'}
The other rules come in pairs, one pair for each type constructionoperator, each pair consisting of one rule for the operator in thetarget, one in the source, of the arrow.The name of a rule consists of the operator and an arrow, with theoperator on the side of the arrow on which it occurs in the conclusion.
Target | Source | |
---|---|---|
(\backslash\leftarrow) {Y\leftarrowX\Gamma \over X\backslashY\leftarrow\Gamma} | (\leftarrow\backslash) {Z\leftarrow\DeltaY\Delta' X\leftarrow\Gamma \over Z\leftarrow\Delta\Gamma(X\backslashY)\Delta'} | |
(/\leftarrow) {Y\leftarrow\GammaX \over Y/X\leftarrow\Gamma} | (\leftarrow/) {Z\leftarrow\DeltaY\Delta' X\leftarrow\Gamma\over Z\leftarrow\Delta(Y/X)\Gamma\Delta'} | |
(\star\leftarrow) {X\leftarrow\Gamma Y\leftarrow\Gamma' \over X\starY\leftarrow\Gamma\Gamma'} | (\leftarrow\star) {Z\leftarrow\DeltaXY\Delta' \over Z\leftarrow\Delta(X\starY)\Delta'} |
For an example, here is a derivation of "type raising", which says that
(B/A)\backslashB\leftarrowA
\dfrac{\dfrac{}{B\leftarrowB} \dfrac{}{A\leftarrowA}} {\dfrac{B\leftarrow(B/A), A}{(B/A)\backslashB\leftarrowA}} \begin{matrix} (Axioms) {}\\ {(\leftarrow/)[Z=Y=B,X=A,\Gamma=(A),\Delta=\Delta'=]}\\ {(\backslash\leftarrow)[Y=B,X=(B/A),\Gamma=(A)]} {}\\ \end{matrix}
Recall that a context-free grammar is a 4-tuple
G=(V,\Sigma,::=,S)
V
\Sigma
::=
(::=)\subseteqV x (V\cup\Sigma)*
S
From the point of view of categorial grammars, a context-free grammar can be seen as a calculus with a set of special purpose axioms foreach language, but with no type construction operators and no inference rules except Cut.
Specifically, given a context-free grammar as above, define a categorial grammar
(Prim,\Sigma,\triangleleft,S)
Prim=V\cup\Sigma
Tp(Prim)=Prim
{x\leftarrowx}
x\inV\cup\Sigma
{X\leftarrow\Gamma}
X::=\Gamma
{s\trianglelefts}
s\in\Sigma
Of course, this is not a basic categorial grammar, since it has special axioms that depend upon the language; i.e. it is not lexicalized.Also, it makes no use at all of non-primitive types.
To show that any context-free language can be generated by a basic categorial grammar, recall that any context-free language can be generated by a context-free grammar in Greibach normal form.
The grammar is in Greibach normal form if every production rule is of the form
A::=sA0\ldotsAN-1
s\in\Sigma
N\ge0
Now given a CFG in Greibach normal form,define a basic categorial grammar with a primitive typefor each non-terminal variable
Prim=V
A/AN-1/\ldots/A0\trianglelefts
A::=sA0\ldotsAN-1
The same construction works for Lambek grammars, since they are an extension of basic categorial grammars. It is necessary to verify that the extra inference rules do not change the generated language. This can be done and shows that every context-free language is generated by some Lambek grammar.
To show the converse, that every language generated by a Lambek grammar is context-free, is much more difficult.It was an open problem for nearly thirty years, from the early 1960s until about 1991 when it was proven by Pentus.
The basic idea is, given a Lambek grammar,
(Prim,\Sigma,\triangleleft,S)
(V,\Sigma,::=,S)
V\subseteqTp(Prim)
T::=s
T\trianglelefts
T::=\Gamma
T\leftarrow\Gamma
Of course, there are infinitely many types and infinitely many derivable sequents, so inorder to make a finite grammar it is necessary put a bound on the size of the types and sequentsthat are needed. The heart of Pentus's proof is to show that there is such a finite bound.
The notation in this field is not standardized. The notations used informal language theory, logic, category theory, and linguistics, conflictwith each other. In logic, arrows point to the more general from the more particular,that is, to the conclusion from the hypotheses. In this article,this convention is followed, i.e. the target of the arrow is the more general (inclusive) type.
In logic, arrows usually point left to right. In this article this convention isreversed for consistency with the notation of context-free grammars, where thesingle non-terminal symbol is always on the left. We use the symbol
::=
Some authors on categorial grammars write
B\backslashA
A\backslashB
The basic ideas of categorial grammar date from work by Kazimierz Ajdukiewicz (in 1935) and other scholars from the Polish tradition of mathematical logic including Stanisław Leśniewski, Emil Post and Alfred Tarski. Ajdukiewicz's formal approach to syntax was influenced by Edmund Husserl's pure logical grammar, which was formalized by Rudolph Carnap. It represents a development in the historical idea of universal logical grammar as an underlying structure of all languages. A core concept of the approach is the substitutability of syntactic categories—hence the name categorial grammar. The membership of an element (e.g., word or phrase) in a syntactic category (word class, phrase type) is established by the commutation test, and the formal grammar is constructed through series of such tests.[1]
The term categorial grammar was coined by Yehoshua Bar-Hillel (in 1953). In 1958, Joachim Lambek introduced a syntactic calculus that formalized the function type constructors along with various rules for the combination of functions. This calculus is a forerunner of linear logic in that it is a substructural logic.
Montague grammar is based on the same principles as categorial grammar.[2] Montague's work helped to bolster interest in categorial grammar by associating it with his highly successful formal treatment of natural language semantics. Later work in categorial grammar has focused on the improvement of syntactic coverage. One formalism that has received considerable attention in recent years is Steedman and Szabolcsi's combinatory categorial grammar, which builds on combinatory logic invented by Moses Schönfinkel and Haskell Curry.
There are a number of related formalisms of this kind in linguistics, such as type logical grammar and abstract categorial grammar.[3]
A variety of changes to categorial grammar have been proposed to improve syntactic coverage. Some of the most common are listed below.
Most systems of categorial grammar subdivide categories. The most common way to do this is by tagging them with features, such as person, gender, number, and tense. Sometimes only atomic categories are tagged in this way. In Montague grammar, it is traditional to subdivide function categories using a multiple slash convention, so A/B and A//B would be two distinct categories of left-applying functions, that took the same arguments but could be distinguished between by other functions taking them as arguments.
Rules of function composition are included in many categorial grammars. An example of such a rule would be one that allowed the concatenation of a constituent of type A/B with one of type B/C to produce a new constituent of type A/C. The semantics of such a rule would simply involve the composition of the functions involved. Function composition is important in categorial accounts of conjunction and extraction, especially as they relate to phenomena like right node raising. The introduction of function composition into a categorial grammar leads to many kinds of derivational ambiguity that are vacuous in the sense that they do not correspond to semantic ambiguities.
Many categorial grammars include a typical conjunction rule, of the general form X CONJ X → X, where X is a category. Conjunction can generally be applied to nonstandard constituents resulting from type raising or function composition..
The grammar is extended to handle linguistic phenomena such as discontinuous idioms, gapping and extraction.[4]