Logic in Computer Science (LICS 1993)

Paper: Lambek grammars are context free (at LICS 1993)

Authors: M. Pentus

Abstract

Basic categorial grammars are the context-free ones. Another kind of categorial grammars was introduced by J. Lambek (1958). These grammars are based on a syntactic calculus, known as the Lambek calculus. Chomsky (1963) conjectured that these grammars are also equivalent to context-free ones. Every basic categorial grammar (and thus every context-free grammar) is equivalent to a Lambek grammar. Conversely, some special kinds of Lambek grammars are context-free. These grammars use weakly unidirectional types, or types of order at most two. The main result of this paper says that Lambek grammars generate only context-free languages. Thus they are equivalent to context-free grammars and also to basic categorial grammars. The Chomsky conjecture, that all languages recognized by the Lambek calculus are context-free, is thus proved

BibTeX

  @InProceedings{Pentus-Lambekgrammarsareco,
    author = 	 {M. Pentus},
    title = 	 {Lambek grammars are context free},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1993},
    year =	 1993,
    editor =	 {Moshe Vardi},
    month =	 {June}, 
    pages =      {429--433},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }