The logic of categorial grammars. A deductive account of natural language syntax and semantics (Q433866)

This book is a clear and neat introduction to categorial grammars approached from a logical point of view. Categorial grammars are here introduced as deductive systems within the ``parsing-as-deduction'' frame and thorough proofs of their main properties are provided. Besides discussing the main results on the topic, the authors also give modern proofs of classic theorems for this type of grammars along with original results of their own, especially as regards proof nets. The book is divided into seven chapters, each one of which ends with several exercises to help the reader assimilate the new concepts she is learning. As the Lambek calculus makes it possible the complete logical treatment of categorial grammars, the book centers around it and its variants, and their corresponding grammars. In Chapter 1, classical categorical grammars are presented and compared to phrase structure grammars like context-free grammars. Appealing characteristics of categorical grammars, such as their connection to logical semantics and the fact that they are lexicalized grammars, are pointed out. It is remarked that, as a result of their lexicalization and their logical formulation, a learning algorithm for these grammars is obtained. Chapter 2 introduces the Lambek calculus (L) as a logic for categorial grammars and Lambek categorial grammars (LCG). The syntax of the Lambek calculus is displayed, with sequent calculus as well as with natural deduction, and the two syntax presentations are proved to be equivalent. The authors then focus on normalization and interpolation, as they are essential properties for showing the correspondence between Lambek grammars and context-free grammars. The weak equivalence between these two types of grammars is proved by following Pentus. A proof of the completeness for the Lambek calculus w.r.t. linguistically natural models is also provided in this chapter. Chapter 3 analyzes the connection between the Lambek calculus and Montague grammar by explaining how Lambek calculus proofs are related to derivations in Montague semantics. In Chapter 4, the authors of this book turn their attention to the non-associative Lambek calculus (NL), which is L without the rule of associativity. They note that an important difference between L and NL lies in the fact that the objects of study of the former are lists of formulas while in the latter the objects of study are trees of formulas, and given that in many linguistic frameworks the basic units of linguistic description are considered to be trees, this is a feature which makes NL worth studying it in order to find out if it may offer any advantages over L. Actually, they show that, although in some cases associativity is undesirable (e.g., there are ungrammatical sentences which are derivable in L but underivable in NL), there are cases where it seems necessary, and therefore conclude that NL offers both advantages and disadvantages when compared to L. They also give a Kripke-style model for NL w.r.t. which soundness and completeness of NL are proved, and show that, with the adequate frame constraints, Kripke models also provide soundness and completeness results for L. The chapter ends with a presentation of the polynomial time algorithms of Aarts \& Trautwein and of de Groote for NL. In Chapter 5, it is shown how NL and L can be combined into a single logic in order to obtain a multi-modal grammar. The multi-modal Lambek calculus is an extension of NL with unary connectives and restricted versions of the structural rules of associativity and commutativity. Multi-modal grammars not only allow us to stipulate lexically if associativity must be employed or not, but also allow us to give an account of facts that cannot adequately be dealt with in context-free grammars. In Chapter 6, the connection between LCG and linear logic is studied. The main goal of this chapter is to introduce proof nets, which are parse structures, for L. It is claimed that proof nets describe a deduction better than trees because they identify linguistically equivalent analyses of a given sentence. Since they only distinguish between proofs which correspond to different syntactic analyses, it is said that they implement the idea of parsing-as-deduction. It is also shown how they enable different parsing techniques and how they can be applied in the study of human processing. Finally, in Chapter 7, proof nets for the multi-modal Lambek calculus are provided. By adding non-associativity, mode information, unary connectives and structural rules to them, proof nets are extended to the multi-modal Lambek calculus. This is useful for parsing categorial grammars. In fact, it is explained that multi-modal proof nets form the basis of an implementation of a parser for multi-modal categorial grammars, and the Grail theorem prover is analyzed.