Linguistic Analysis

A research journal devoted to the publication of high quality articles in formal phonology, morphology, syntax and semantics. In continuous publication since 1976. ISSN: 0098-9053


Lambek Calculus and Substructural Logics

To keep this paper in a reasonable size, I omit many interesting topics, e.g. Curry-Howard isomorphism, Abstract Categorial Grammars (an explicit application of the typed lambda-calculus as a grammar formalism, due to de Groote (2001)), proof nets (a graph-theoretic representation of proofs in multiplicative linear logics), modal categorial grammars, combinatory grammars, and learning theory. For some information on these topics see survey articles (Moortgat, 1997; Buszkowski, 1977, 2003b); also see the books cited above, the collection (Casadio et al, 2005), and two special issues of Studia Logica: 71.3 (2002) and 87.2-3 (2007).

Section 2 presents different Lambek systems and their algebraic models. It also provides some basic linguistic interpretations of type logics. Section 3 introduces sequent systems of type logics, discusses cut elimination and its consequences, and shows some applications of sequent systems in proofs of fine completeness theorems. Section 4 is concerned with categorial grammars, based on different type logics; we show how certain proof-theoretic tools (cut elimination, normalization, interpolation) are used to establish basic properties of Lambek systems and grammars (decidability, generative capacity, complexity). Section 5 briefly outlines some ways in the opposite direction: some results on Lambek systems and grammars help to solve problems in substructural logics.