Page 337 - Encyclopedia of Philosophy of Language

NF\(S/NP), a -> NP/N, and man -> N. Then it can be shown that George saw a man is a sentence (S) by proving the theorem NP, NP\(S/NP), NP/N, N=>S.
NP,NF\(S/NP)=>S/NP S/NP,NP=> S NP,NP\(S/NP),NP=>S NP/N,N=>S
NP, Nf\(S/NP), NP/N, N=*S
Bar-Hillel, et al. (1960) proved that ABgrammars and context-free grammars recognize exactly the same set of languages.
Lambek (1958) proposed an important extension of AB. The (product-free part of this) calculus (L)consists of one axiom and five inference rules.
these categories, Montague uses a notation familiar from categorial grammar: besides basic categories, there are compound categories A/B and A//B. The syntactic category of an expression determines the semantic type of its interpretation (or rather: its IL translation), in that basic categories C are assigned some type TYPE(C), and A/B and A//B both get the type ((5,TYPE(5)),TYPE(^)). However, the categorial influence does not go further: there are fragment-spec- ific rules which give a recursive definition of the set of English expressions, and these rules do much more than merely concatenating expressions. They involve morphological retrieval, insertion of syn- categorematic expressions, substitution, etc. Thus one cannot simply say that expressions of category A/B are the ones which combine with an expression of category B on their right-hand side to yield an expression of category A (or, more formally, that B/A= {xeS\VyeA:yxeB}).
In Montague's work, the category-to-type assign- ment, TYPE, is a function. If an expression belongs to a category C, then its translation is rigidly and invariably of the unique type assigned to C, TYPE(C). This entails that one has to employ a strategy of gen- eralizing to the worst case: uniformly assign all expressions of a certain syntactic category the 'worst' (most complicated) type needed for some expression in that category. John, for instance, belongs to the same category as a man. But as the latter noun phrase needs an (extensional) interpretation of type ((e, i), t) (cf. above), the former will have to have such an interpretationaswell.(Luckily,AP•P(j) willdo.)This aspect has been criticized by Partee and Rooth (1983), among others. They argue that scope ambiguities in natural languages show that there is not always a worst case to generalize to, and propose a reverse, flexible strategy instead: an expression gets a lexical translation of the minimal type available for that expression, and general rules derive the necessary translations of more complicated types.
In the 1960s and 1970s, various proposals were made for strengthening the basic (AB) framework of categorial grammar. As a matter of historical irony, most of these proposals were already present in Lam- bek (1958). Around 1980, the rediscovery of this semi- nal paper led to a renaissance of categorial research, partly also inspired by Montague's work on the sem- antics of natural language. In view of its origins, cat- egorial grammar is a formalism which can accommodate both syntactic categories of expressions and semantic types of objects. In fact, van Benthem (1986) showed that both perspectives can be sys- tematically related. Product-free L, for instance, can be assigned a straightforward semantic interpretation in which all categories C are provided with a typed lambda term r (rendered as C:T below). The type o f t is determined by C: basic categories C are associated with some type TYPE(C), and compound categories
It is easily seen that L —{[/R], [\R]} is equivalent to ABU{[Ax]}. Notice, however, that the introduction of [/R] and [\R] essentially enlarges the set of theorems. For example, Lallows the derivation of theorems like A=>B/(A\B) ('raising'), A/B,B/C=>A/C ('com- position'), A\(C/B)o(A\Q/B ('associativity'), and A/B =>04/Q/CB/CX'division').
By showing that the set of theorems is not affected by leaving out [Cut], Lambek established the decid- ability of L. Moreover, Buszkowski, in Buszkowski, et al. (1988) has proved that L is complete (and AB, therefore, incomplete) with respect to the intuitive interpretation of categories as sets of expressions (S is the set of finite sequences of lexical items): that is, for A\B={xeS\VyeA:xyeB} and B/A = {xeS\VyeA:yxeB} it holds that T=>C iff T^C. Finally, Pentus (1993) has proved that the generative capacity of L is the same as that of context-free gram- mars.
3. TypesandCategories
As noted in the introduction, the first gathering of syntactic categories and semantic types can be dis- cerned in the linguistic papers of Montague. The most influential one (1974: ch. 8) presents a grammar for a fragment of English with a semantic component, where the expressions defined by the syntactic com- ponent are translated into expressions of the logical language IL. These IL expressions receive their model- theoretic interpretation in the usual way. Thus, the English expressions are indirectly assigned a semantic interpretation, viz., via the interpretation of the logical expressions into which they are translated.
In syntax, all expressions belong to categories. For
Categories and Types
315