Geodesic
On translating context-free grammars into Lambek grammars
Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics, Tome 290 (2015), pp. 72-79.

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

We consider context-free grammars and Lambek grammars enriched with semantic labeling. Such grammars do not just answer whether a given word belongs to the language described by the grammar, but, if the answer is positive, also assign the word a $\lambda $-term that corresponds to the semantic value (“meaning”) of the word. We present a modification of W. Buszkowski's direct translation of context-free grammars in the Chomsky normal form into Lambek grammars; this modification preserves semantic values of words. 
@article{TRSPY_2015_290_a5,
     author = {S. L. Kuznetsov},
     title = {On translating context-free grammars into {Lambek} grammars},
     journal = {Informatics and Automation},
     pages = {72--79},
     publisher = {mathdoc},
     volume = {290},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a5/}
}
TY  - JOUR
AU  - S. L. Kuznetsov
TI  - On translating context-free grammars into Lambek grammars
JO  - Informatics and Automation
PY  - 2015
SP  - 72
EP  - 79
VL  - 290
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a5/
LA  - ru
ID  - TRSPY_2015_290_a5
ER  - 
%0 Journal Article
%A S. L. Kuznetsov
%T On translating context-free grammars into Lambek grammars
%J Informatics and Automation
%D 2015
%P 72-79
%V 290
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a5/
%G ru
%F TRSPY_2015_290_a5
S. L. Kuznetsov. On translating context-free grammars into Lambek grammars. Informatics and Automation, Modern problems of mathematics, mechanics, and mathematical physics, Tome 290 (2015), pp. 72-79. http://geodesic.mathdoc.fr/item/TRSPY_2015_290_a5/

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

[2] van Benthem J., “The semantics of variety in categorial grammar”, Categorial grammar, J. Benjamins, Amsterdam, 1988, 37–55 | MR

[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] Buszkowski W., On the equivalence of Lambek categorial grammars and basic categorial grammars, ILLC Prepubl. Ser. Preprint LP-93-07, Univ. Amsterdam, Inst. Logic, Lang. and Comput., Amsterdam, 1993

[5] Carpenter B., Type-logical semantics, MIT Press, Cambridge, MA, 1997 | MR

[6] Chomsky N., “Three models for the description of language”, IRE Trans. Inf. Theory, IT-2:3 (1956), 113–124 | DOI

[7] Dowty D.R., Wall R.E., Peters S., Introduction to Montague semantics, D. Reidel, Dordrecht, 1981

[8] Greibach S.A., “A new normal-form theorem for context-free phrase structure grammars”, J. Assoc. Comput. Mach., 12:1 (1965), 42–52 | DOI | MR | Zbl

[9] Hendriks H., Studied flexibility: Categories and types in syntax and semantics, PhD Dissert, Univ. Amsterdam, Amsterdam, 1993

[10] Howard W.A., “The formulae-as-types notion of construction”, To H.B. Curry: Essays on combinatory logic, lambda calculus and formalism, Ed. by J.P. Seldin, H.J. Roger, Acad. Press, London, 1980, 479–490 | MR

[11] 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, Ed. by G. Morrill, M.-J. Nederhof, Springer, Berlin, 2013, 191–208 | DOI | MR | Zbl

[12] Kuznetsov S., “Lambek grammars with one division and one primitive type”, Log. J. IGPL., 20:1 (2012), 207–221 | DOI | MR | Zbl

[13] Lambek J., “The mathematics of sentence structure”, Amer. Math. Mon., 65:3 (1958), 154–170 | DOI | MR | Zbl

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

[15] Savateev Yu., “Product-free Lambek calculus is NP-complete”, Logical foundations of computer science, Proc. Int. Symp. LFCS 2009, Lect. Notes Comput. Sci., 5407, Ed. by S. Artemov, A. Nerode, Springer, Berlin, 2009, 380–394 | DOI | MR | Zbl