RUS  ENG
Full version
JOURNALS // Trudy Matematicheskogo Instituta imeni V.A. Steklova // Archive

Trudy Mat. Inst. Steklova, 2016 Volume 294, Pages 141–151 (Mi tm3734)

This article is cited in 4 papers

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

S. L. Kuznetsov

Steklov Mathematical Institute of Russian Academy of Sciences, ul. Gubkina 8, Moscow, 119991 Russia

Abstract: 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.

UDC: 519.766.23

Received: April 13, 2016

DOI: 10.1134/S0371968516030080


 English version:
Proceedings of the Steklov Institute of Mathematics, 2016, 294, 129–138

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025