|
This article is cited in 4 scientific papers (total 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.
Received: April 13, 2016
Citation:
S. L. Kuznetsov, “On translating Lambek grammars with one division into context-free grammars”, Modern problems of mathematics, mechanics, and mathematical physics. II, Collected papers, Trudy Mat. Inst. Steklova, 294, MAIK Nauka/Interperiodica, Moscow, 2016, 141–151; Proc. Steklov Inst. Math., 294 (2016), 129–138
Linking options:
https://www.mathnet.ru/eng/tm3734https://doi.org/10.1134/S0371968516030080 https://www.mathnet.ru/eng/tm/v294/p141
|
|