Geodesic
On translating Lambek grammars with one division into context-free grammars
Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics. II, Tome 294 (2016), pp. 141-151.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{TRSPY_2016_294_a7,
     author = {S. L. Kuznetsov},
     title = {On translating {Lambek} grammars with one division into context-free grammars},
     journal = {Informatics and Automation},
     pages = {141--151},
     publisher = {mathdoc},
     volume = {294},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2016_294_a7/}
}
TY  - JOUR
AU  - S. L. Kuznetsov
TI  - On translating Lambek grammars with one division into context-free grammars
JO  - Informatics and Automation
PY  - 2016
SP  - 141
EP  - 151
VL  - 294
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2016_294_a7/
LA  - ru
ID  - TRSPY_2016_294_a7
ER  - 
%0 Journal Article
%A S. L. Kuznetsov
%T On translating Lambek grammars with one division into context-free grammars
%J Informatics and Automation
%D 2016
%P 141-151
%V 294
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2016_294_a7/
%G ru
%F TRSPY_2016_294_a7
S. L. Kuznetsov. On translating Lambek grammars with one division into context-free grammars. Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics. II, Tome 294 (2016), pp. 141-151. http://geodesic.mathdoc.fr/item/TRSPY_2016_294_a7/

[1] Akho A., Ulman Dzh., Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii, v. 1, Sintaksicheskii analiz, Mir, M., 1978

[2] Bar-Hillel Y., Gaifman C., Shamir E., “On categorial and phrase-structure grammars”, Bull. Res. Council Israel. Sect. F, 9F (1960), 1–16 | MR | Zbl

[3] Buszkowski W., “The equivalence of unidirectional Lambek categorial grammars and context-free grammars”, Z. math. Logik Grundlagen Math., 31 (1985), 369–384 | DOI | MR | Zbl

[4] Chomsky N., “Three models for the description of language”, IRE Trans. Inf. Theory, IT-2:3 (1956), 113–124 ; Хомский Н., “Три модели описания языка”, Кибернетический сборник: Сб. пер., 2, Изд-во иностр. лит., М., 1961, 237–266 | DOI | Zbl | Zbl

[5] Evey J., “Application of pushdown store machines”, Proc. 1963 Fall Joint Comput. Conf., Spartan Books, Baltimore, MD, 1963, 215–227

[6] Khopkroft Dzh., Motvani R., Ulman Dzh., Vvedenie v teoriyu avtomatov, yazykov i vychislenii, 2-e izd., Izd. dom “Vilyams”, M., 2002

[7] Jäger G., “On the generative capacity of multi-modal categorial grammars”, Res. Lang. Comput., 1:1–2 (2003), 105–125 | DOI | MR | Zbl

[8] Kanazawa M., “The Lambek calculus enriched with additional connectives”, J. Log. Lang. Inf., 1:2 (1992), 141–171 | DOI | MR | Zbl

[9] Kanazawa M., Salvati S., “The string-meaning relations definable by Lambek grammars and context-free grammars”, Formal Grammar, Proc. 17th and 18th Int. Confs. (FG 2012/2013), Lect. Notes Comput. Sci., 8036, eds. G. Morrill, M.-J. Nederhof, Springer, Berlin, 2013, 191–208 | DOI | MR | Zbl

[10] Kuznetsov S. L., “O preobrazovanii kontekstno-svobodnykh grammatik v grammatiki Lambeka”, Tr. MIAN, 290, 2015, 72–79 | DOI | MR | Zbl

[11] Kuznetsov S. L., Ryzhkova N. S., “Fragment ischisleniya Lambeka s iteratsiei”, Maltsevskie chteniya 2015, Tez. dokl. Mezhdunar. konf., Novosibirsk, 2015, 213

[12] Lambek J., “The mathematics of sentence structure”, Amer. Math. Mon., 65:3 (1958), 154–170 ; Ламбек И., “Математическое исследование структуры предложений”, Математическая лингвистика, Сб. пер., Мир, М., 1964, 47–68 | DOI | MR | Zbl

[13] Moortgat M., “Multimodal linguistic inference”, J. Log. Lang. Inf., 5:3–4 (1996), 349–385 | DOI | MR | Zbl

[14] Morrill G. V., Categorial grammar: Logical syntax, semantics, and processing, Oxford Univ. Press, Oxford, 2011

[15] Oettinger A. G., “Automatic syntactic analysis and the pushdown store”, Structure of language and its mathematical aspects, Proc. Symp. Appl. Math., 12, Amer. Math. Soc., Providence, RI, 1961, 104–129 | DOI

[16] Pentus A. E., Pentus M. R., Matematicheskaya teoriya formalnykh yazykov, Internet-univ. inf. tekhnol., Binom, M., 2006

[17] Pentus M. R., “Ischislenie Lambeka i formalnye grammatiki”, Fund. i prikl. matematika, 1:3 (1995), 729–751 | MR | Zbl

[18] Pentus M. R., “Polnota sintaksicheskogo ischisleniya Lambeka”, Fund. i prikl. matematika, 5:1 (1999), 193–219 | MR | Zbl

[19] Pentus M., “Lambek calculus is NP-complete”, Theor. Comput. Sci., 357 (2006), 186–201 | DOI | MR | Zbl

[20] Pentus M., “A polynomial-time algorithm for Lambek grammars of bounded order”, Linguist. Anal., 36 (2010), 441–471

[21] Podolskii V. V., “Circuit complexity meets ontology-based data access”, Computer science – theory and applications, Proc. 10th Int. Comput. Sci. Symp. (Russia, 2015), Lect. Notes Comput. Sci., 9139, Springer, Cham, 2015, 7–26 | DOI | MR | Zbl

[22] Savateev Yu., “Lambek grammars with one division are decidable in polynomial time”, Computer science – theory and applications, Proc. 3rd Int. Comput. Sci. Symp. (Russia, 2008), Lect. Notes Comput. Sci., 5010, Springer, Berlin, 2008, 273–282 | DOI | MR | Zbl

[23] Savateev Yu. V., “Raspoznavanie vyvodimosti dlya ischisleniya Lambeka s odnim deleniem”, Vestn. Mosk. un-ta. Matematika. Mekhanika, 2009, no. 2, 59–62 | MR | Zbl

[24] Savateev Yu. V., Algoritmicheskaya slozhnost fragmentov ischisleniya Lambeka, Dis. $\dots$ kand. fiz.-mat. nauk, MGU, M., 2009

[25] Savateev Yu., “Product-free Lambek calculus is NP-complete”, Ann. Pure Appl. Log., 163:7 (2012), 775–788 | DOI | MR | Zbl

[26] Shamkanov D. S., “Tsiklicheskie vyvody dlya logiki dokazuemosti Gëdelya–Lëba”, Mat. zametki, 96:4 (2014), 609–622 | DOI | MR | Zbl

[27] Shamkanov D., “Nested sequents for provability logic GLP”, Log. J. IGPL, 23:5 (2015), 789–815 | DOI | MR

[28] Schützenberger M. P., “On context-free languages and push-down automata”, Inf. Control., 6:3 (1963), 246–264 | DOI | MR | Zbl

[29] Valiant L. G., “General context-free recognition in less than cubic time”, J. Comput. Syst. Sci., 10 (1975), 308–315 | DOI | MR | Zbl