Categorial grammar (also categorical grammar) is a term used for a family of formalisms in natural language syntax motivated by the principle of compositionality and organized according to the view that syntactic constituents should generally combine as functions or according to a functionargument relationship. Most versions of categorial grammar analyze sentence structure in terms of constituencies (as opposed to dependencies) and are therefore phrase structure grammars (as opposed to dependency grammars).
Basics
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\; \backslash rightarrow\; B$,
a categorial grammar typically has two function types, one type which is applied on the left,
and one on the right. For example, a simple categorial grammar might have two function types $B/A\backslash ,\backslash !$ and $A\backslash backslash\; B$.
The first, $B/A\backslash ,\backslash !$, is the type of a phrase that results in a phrase of type
$B\backslash ,\backslash !$ when followed (on the right) by a phrase of type $A\backslash ,\backslash !$.
The second, $A\backslash backslash\; B\backslash ,\backslash !$, is the type of a phrase that results
in a phrase of type $B\backslash ,\backslash !$ when preceded (on the left) by a phrase of type
$A\backslash ,\backslash !$.
As Joachim Lambek explains, the notation is based upon algebra.
A fraction when multiplied by (i.e. concatenated with) its denominator yields its numerator.
Since 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 ABgrammar (after Ajdukiewicz and BarHillel).
Given a set of primitive types $\backslash text\{Prim\}\backslash ,\backslash !$, let
$\backslash text\{Tp\}(\backslash text\{Prim\})\backslash ,\backslash !$ be the set of types constructed from primitive types. In the basic case, this is the least set such that $\backslash text\{Prim\}\backslash subseteq\; \backslash text\{Tp\}(\backslash text\{Prim\})$
and if $X,\; Y\backslash in\; \backslash text\{Tp\}(\backslash text\{Prim\})$
then $(X/Y),\; (Y\backslash backslash\; X)\; \backslash in\; \backslash text\{Tp\}(\backslash text\{Prim\})$.
Think of these as purely formal expressions freely generated from the primitive types; any semantics will be added later. Some authors assume a fixed infinite set of primitive types used by all grammars, but by making the primitive types part of the grammar, the whole construction is kept finite.
A basic categorial grammar is a tuple $(\backslash Sigma,\; \backslash text\{Prim\},\; S,\; \backslash triangleleft)$
where $\backslash Sigma\backslash ,\backslash !$ is a finite set of symbols,
$\backslash text\{Prim\}\backslash ,\backslash !$ is a finite set of primitive types, and $S\; \backslash in\; \backslash text\{Tp\}(\backslash text\{Prim\})$.
The relation $\backslash triangleleft$ is the lexicon, which relates types to symbols $(\backslash triangleleft)\; \backslash subseteq\; \backslash text\{Tp\}(\backslash text\{Prim\})\; \backslash times\; \backslash Sigma$.
Since the lexicon is finite, it can be specified by listing a set of pairs like $TYPE\backslash triangleleft\backslash text\{symbol\}$.
Such a grammar for English might have three basic types $(N,NP,\; \backslash text\{\; and\; \}\; S)\backslash ,\backslash !$, assigning count nouns the type $N\backslash ,\backslash !$, complete noun phrases the type
$NP\backslash ,\backslash !$, and sentences the type $S\backslash ,\backslash !$.
Then an adjective could have the type $N/N\backslash ,\backslash !$, because if it is followed by a noun then the whole phrase is a noun.
Similarly, a determiner has the type $NP/N\backslash ,\backslash !$,
because it forms a complete noun phrase when followed by a noun.
Intransitive verbs have the type $NP\backslash backslash\; S$, and transitive verbs the type $(NP\backslash backslash\; S)/NP$.
Then a string of words is a sentence if it has overall type $S\backslash ,\backslash !$.
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
{$NP/N\backslash triangleleft\backslash text\{the\}$,
$NP/N\backslash triangleleft\backslash text\{that\}$,
$N\backslash triangleleft\backslash text\{boy\}$,
$N\backslash triangleleft\backslash text\{mess\}$,
$N/N\backslash triangleleft\backslash text\{bad\}$,
$(NP\backslash backslash\; S)/NP\backslash triangleleft\backslash text\{made\}$}.
and the sequence of types in the string is
$\{\backslash text\{the\}\backslash atop\; \{NP/N,\}\}\; \{\backslash text\{bad\}\backslash atop\; \{N/N,\}\}\; \{\backslash text\{boy\}\backslash atop\; \{N,\}\}\; \{\backslash text\{made\}\backslash atop\; \{(NP\backslash backslash\; S)/NP,\}\}\; \{\backslash text\{that\}\backslash atop\; \{NP/N,\}\}\; \{\backslash text\{mess\}\backslash atop\; \{N\}\}$
now find functions and appropriate arguments and reduce them according to the two inference rules
$X\backslash leftarrow\; X/Y,\backslash ;\; Y$ and
$X\backslash leftarrow\; Y,\backslash ;\; Y\backslash backslash\; X$:
$.\backslash qquad\; NP/N,\backslash ;\; N/N,\backslash ;\; N,\backslash ;\; (NP\backslash backslash\; S)/NP,\backslash ;\; \backslash underbrace\{NP/N,\backslash ;\; N\}$
$.\backslash qquad\; NP/N,\backslash ;\; N/N,\backslash ;\; N,\backslash ;\; \backslash underbrace\{(NP\backslash backslash\; S)/NP,\; \backslash quad\; NP\}$
$.\backslash qquad\; NP/N,\backslash ;\; \backslash underbrace\{N/N,\backslash ;\; N\},\; \backslash qquad\; (NP\backslash backslash\; S)$
$.\backslash qquad\; \backslash underbrace\{NP/N,\backslash ;\; \backslash quad\; N\},\backslash ;\; \backslash qquad\; (NP\backslash backslash\; S)$
$.\backslash qquad\; \backslash qquad\backslash underbrace\{NP,\backslash ;\; \backslash qquad\; (NP\backslash backslash\; S)\}$
$.\backslash qquad\; \backslash qquad\backslash qquad\backslash quad\backslash ;\backslash ;\backslash ;\; S$
The fact that the result is $S\backslash ,\backslash !$ means that the string is a sentence, while the sequence of reductions shows that it must be parsed as ((the (bad boy)) (made (that mess))).
Categorial grammars of this form (having only function application rules) are equivalent in generative capacity to contextfree 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 languageindependent) 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.
Lambek Calculus
A Lambek grammar is an elaboration of this idea which has a
concatenation operator for types, and several other inference rules.
Pentus has shown that these still have the generative capacity of
contextfree grammars.
For the Lambek calculus, there is a type concatenation
operator $\backslash star\backslash ,\backslash !$, so
that $\backslash text\{Prim\}\backslash subseteq\; \backslash text\{Tp\}(\backslash text\{Prim\})$
and if $X,\; Y\backslash in\; \backslash text\{Tp\}(\backslash text\{Prim\})$
then $(X/Y),\; (X\backslash backslash\; Y),\; (X\backslash star\; Y)\backslash in\; \backslash text\{Tp\}(\backslash text\{Prim\})$.
The Lambek calculus consists of several deduction rules which specify
how type inclusion assertions can be derived. In the following
rules, upper case roman letters stand for types, upper case Greek
letters stand for sequences of types. A sequent of the form
$X\; \backslash leftarrow\; \backslash Gamma$
can be read: a string is of type $X\backslash ,\backslash !$ if it consists of the concatenation
of strings of each of the types in $\backslash Gamma\backslash ,\backslash !$. If a type is
interpreted as a set of strings, then the
$\backslash leftarrow$ may be interpreted as $\backslash supseteq\backslash ,\backslash !$,
that is, "includes as a subset".
A horizontal line means that the inclusion above the line
implies the one below the line.
The process is begun by the Axiom rule, which as no antecedents and
just says that any type includes itself.
$(Axiom)\backslash quad\; \backslash \backslash \; \{(\backslash backslash\backslash leftarrow)\backslash ,\backslash ,[Y=B,X=(B/A),\backslash Gamma=(A)]\}\backslash qquad\backslash qquad\backslash qquad\{\; \}\backslash \backslash $
\end{matrix}
Relation to Context Free Grammars
Recall that a contextfree grammar is a 4tuple:
$G\; =\; (V,\backslash ,\; \backslash Sigma,\backslash ,::=,\backslash ,\; S)$
where
1. $V\backslash ,$ is a finite set of nonterminals or variables.
2. $\backslash Sigma\backslash ,$ is a finite set of terminal symbols.
3. $::=\backslash ,$ is a finite set of production rules, that is, a finite relation
$(::=)\backslash subseteq\; V\; \backslash times\; (V\; \backslash cup\; \backslash Sigma)^*$.
4. $S\backslash ,$ is the start variable.
From the point of view of categorial grammars, a contextfree grammar
can be seen as a calculus with a set of special purpose axioms for
each language, but with no type construction operators and no
inference rules except Cut.
Specifically, given a contextfree grammar as above, define a categorial
grammar
$(\backslash text\{Prim\},\backslash ,\; \backslash Sigma,\backslash ,\; \backslash triangleleft,\backslash ,\; S)$
where $\backslash text\{Prim\}=V\backslash cup\backslash Sigma$,
and $\backslash text\{Tp\}(\backslash text\{Prim\})=\backslash text\{Prim\}\backslash ,\backslash !$.
Let there be an axiom
$\{x\; \backslash leftarrow\; x\}$ for every symbol
$x\; \backslash in\; V\backslash cup\backslash Sigma$,
an axiom $\{X\; \backslash leftarrow\; \backslash Gamma\}$
for every production rule $X::=\; \backslash Gamma\backslash ,\backslash !$,
a lexicon entry $\{s\; \backslash triangleleft\; s\}$ for every terminal symbol
$s\; \backslash in\; \backslash Sigma$,
and Cut for the only rule.
This categorial grammar generates the same language as the given CFG.
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 nonprimitive types.
To show that any contextfree language can be generated by
a basic categorial grammar, recall that
any contextfree language can be generated by a contextfree grammar
in Greibach normal form.
The grammar is in Greibach normal form if every production rule is
of the form
$A::=\; s\; A\_0\; \backslash ldots\; A\_\{N1\}$,
where capital letters are variables, $s\; \backslash in\; \backslash Sigma$,
and $N\backslash ge\; 0$,
that is, the right side of the production is a single terminal symbol
followed by zero or more (nonterminal) variables.
Now given a CFG in Greibach normal form,
define a basic categorial grammar with a primitive type
for each nonterminal variable
$\backslash text\{Prim\}=V\backslash ,\backslash !$,
and with an entry in the lexicon
$A/A\_\{N1\}/\; \backslash ldots\; /A\_0\; \backslash triangleleft\; s$,
for each production rule
$A::=\; s\; A\_0\; \backslash ldots\; A\_\{N1\}$.
It is fairly easy to see that this basic categorial grammar
generates the same language as the original CFG.
Note that the lexicon of this grammar will generally
assign multiple types to each symbol.
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 contextfree language is generated
by some Lambek grammar.
To show the converse, that every language generated by a
Lambek grammar is contextfree, 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,
$(\backslash text\{Prim\},\backslash ,\; \backslash Sigma,\backslash ,\; \backslash triangleleft,\backslash ,\; S)$
construct a contextfree grammar
$(V,\backslash ,\; \backslash Sigma,\backslash ,::=,\backslash ,\; S)$
with the same set of terminal symbols, the
same start symbol, with variables some (not all) types
$V\backslash subset\; \backslash text\{Tp\}(\backslash text\{Prim\})\backslash ,\backslash !$,
and with a production rule
$T::=\backslash text\{s\}\backslash ,\backslash !$
for each entry
$T\backslash triangleleft\backslash text\{s\}$
in the lexicon,
and production rules $T::=\backslash Gamma\backslash ,\backslash !$
for certain sequents $T\backslash leftarrow\backslash Gamma$
which are derivable in the Lambek calculus.
Of course, there are infinitely many types
and infinitely many derivable sequents, so in
order to make a finite grammar it is necessary
put a bound on the size of the types and sequents
that are needed. The heart of Pentus's proof
is to show that there is such a finite bound.
Notation
The notation in this field is not standardized. The notations used in
formal language theory, logic, category theory, and linguistics, conflict
with 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 is
reversed for consistency with the notation of contextfree grammars, where the
single nonterminal symbol is always on the left. We use the symbol $::=$
in a production rule as in BackusNaur form. Some authors use an arrow, which
unfortunately may point in either direction, depending on whether the grammar is
thought of as generating or recognizing the language.
Some authors on categorial grammars write $B\backslash backslash\; A$ instead of
$A\backslash backslash\; B$. The convention used here follows Lambek and algebra.
Historical notes
The basic ideas of categorial grammar date from work by Kazimierz Ajdukiewicz (in 1935) and Yehoshua BarHillel (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 uses an ad hoc syntactic system for English that is based on the principles of categorial grammar. Although Montague's work is sometimes regarded as syntactically uninteresting, it helped to bolster interest in categorial grammar by associating it with a highly successful formal treatment of natural language semantics. More recent work in categorial grammar has focused on the improvement of syntactic coverage. One formalism which 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.
Some definitions
 Derivation
 A derivation is a binary tree that encodes a proof.
 Parse tree
 A parse tree displays a derivation, showing the syntactic structure of a sentence.
 Functor and Argument
 In a right (left) function application, the node of the type A\B (B/A) is called the functor, and the node of the type A is called an argument.
 Functorargument structure
Refinements of categorial grammar
A variety of changes to categorial grammar have been proposed to improve syntactic coverage. Some of the most common ones are listed below.
Features and subcategories
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 leftapplying functions, that took the same arguments but could be distinguished between by other functions taking them as arguments.
Function composition
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.
Conjunction
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..
Discontinuity
The grammar is extended to handle linguistic phenomena such as discontinuous idioms, gapping and extraction.
See also
References
 Curry, Haskell B. and Richard Feys (1958), Combinatory Logic, Vol. 1. NorthHolland.
 Jacobson, Pauline (1999), “Towards a variablefree semantics.” Linguistics and Philosophy 22, 1999. pp. 117–184
 Lambek, J. (1958) "The mathematics of sentence structure", Amer. Math. Monthly 65, 3 pp 154–170
 Pentus, Mati (1997) "Lambek Calculus and Formal Grammars",Amer. Math. Soc. Transl.
 Steedman, Mark (1987),” Combinatory grammars and parasitic gaps”. Natural Language and Linguistic Theory 5, 403–439.
 Steedman, Mark (1996), Surface Structure and Interpretation. The MIT Press.
 Steedman, Mark (2000), The Syntactic Process. The MIT Press.
 Szabolcsi, Anna (1989), "Bound variables in syntax (are there any?)." Semantics and Contextual Expression, ed. by Bartsch, van Benthem, and van Emde Boas. Foris, 294–318.
 Szabolcsi, Anna (1992), "Combinatory grammar and projection from the lexicon." Lexical Matters. CSLI Lecture Notes 24, ed. by Sag and Szabolcsi. Stanford, CSLI Publications. 241–269.
 Szabolcsi, Anna (2003), “Binding on the fly: Crosssentential anaphora in variablefree semantics”. Resource Sensitivity in Binding and Anaphora, ed. by Kruijff and Oehrle. Kluwer, 215–229.
 Morril, Glynn (1995), "Discontinuity in categorial grammar" Linguistics and Philosophy. Springer, 175219.
Further reading
 Michael Moortgat, Categorial Type Logics, Chapter 2 in J. van Benthem and A. ter Meulen (eds.) Handbook of Logic and Language. Elsevier, 1997, ISBN 0262220539
 Wojciech Buszkowski, Mathematical linguistics and proof theory, Chapter 12 in J. van Benthem and A. ter Meulen (eds.) Handbook of Logic and Language. Elsevier, 1997, ISBN 0262220539



External links
 Grammar, categorial at Springer Encyclopaedia of Mathematics
 http://plato.stanford.edu/entries/typelogicalgrammar/
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.