Email this article On translating Lambek grammars with one division into context-free grammars
- Authors: Kuznetsov S.L.1
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Issue: Vol 294, No 1 (2016)
- Pages: 129-138
- Section: Article
- URL: https://journals.rcsi.science/0081-5438/article/view/173925
- DOI: https://doi.org/10.1134/S0081543816060080
- ID: 173925
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
S. L. Kuznetsov
Steklov Mathematical Institute of Russian Academy of Sciences
Author for correspondence.
Email: sk@mi.ras.ru
Russian Federation, ul. Gubkina 8, Moscow, 119991
Supplementary files
