On translating Lambek grammars with one division into context-free grammars

Аннотация

We describe a method of translating a Lambek grammar with one division into an equivalent context-free grammar whose size is bounded by a polynomial in the size of the original grammar. Earlier constructions by Buszkowski and Pentus lead to exponential growth of the grammar size.