Lambek calculus and formal grammars
Mati Reinovich Pentus · Translations - American Mathematical Society/Translations · 1999
Contents Introduction 1 1. Preliminaries 4 2. Free group interpretation 7 3. Thin sequents 9 4. Interpolation 10 5. Main theorem 14 6. Interpolation in fragments 18 7. Construction of a context-free grammar for a product-free Lambek grammar 23 8. Conjoinable types in the Lambek calculus 24 9. Multiplicative cyclic linear logic 26 Index 30 References 31 Introduction The question about the position of categorial grammars in the Chomsky hierarchy arose in late 1950s and early 1960s. In 1960 Bar-Hillel, Gaifman, and Shamir [1] proved that a formal language can be generated by some basic categorial grammar if and only if the language is context-free. They conjectured (see also [7]) that the same holds for Lambek grammars, i. e., for categorial grammars based on a syntactic calculus introduced in 1958 by J. Lambek [10] (this calculus operates with three connectives: multiplication or concatenation of languages, left di