Geodesic
Lambek calculus and formal grammars
Fundamentalʹnaâ i prikladnaâ matematika, Tome 1 (1995) no. 3, pp. 729-751.

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

We prove that the class of languages recognized by Lambek categorial grammars coincides with the class of all context-free languages. 
@article{FPM_1995_1_3_a10,
     author = {M. R. Pentus},
     title = {Lambek calculus and formal grammars},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {729--751},
     publisher = {mathdoc},
     volume = {1},
     number = {3},
     year = {1995},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_1995_1_3_a10/}
}
TY  - JOUR
AU  - M. R. Pentus
TI  - Lambek calculus and formal grammars
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 1995
SP  - 729
EP  - 751
VL  - 1
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_1995_1_3_a10/
LA  - ru
ID  - FPM_1995_1_3_a10
ER  - 
%0 Journal Article
%A M. R. Pentus
%T Lambek calculus and formal grammars
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 1995
%P 729-751
%V 1
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_1995_1_3_a10/
%G ru
%F FPM_1995_1_3_a10
M. R. Pentus. Lambek calculus and formal grammars. Fundamentalʹnaâ i prikladnaâ matematika, Tome 1 (1995) no. 3, pp. 729-751. http://geodesic.mathdoc.fr/item/FPM_1995_1_3_a10/

[1] Zh. Lalleman, Polugruppy i kombinatornye prilozheniya, Mir, M., 1985 | MR

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

[3] J van Benthem., Language in Action. Categories, Lambdas and Dynamic Logic, North-Holland, Amsterdam, 1991 | MR

[4] W. Buszkowski, “The equivalence of unidirectional Lambek categorial grammars and context-free grammars”, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 31 (1985), 369–384 | DOI | MR | Zbl

[5] W. Buszkowski, “Generative power of categorial grammars”, Categorial Grammars and Natural Language Structures, ed. R. T. Oehrle, E. Bach, D. Wheeler, Reidel, Dordrecht, 1988, 69–94

[6] W. Buszkowski, “On generative capacity of the Lambek calculus”, Logics in AI, ed. J. van Eijck, Springer, Berlin, 1991, 139–152 | MR | Zbl

[7] W. Buszkowski, On the equivalence of Lambek categorial grammars and basic categorial grammars, ILLC Prepublication Series, LP–93–07, Institute for Logic, Language and Computation, University of Amsterdam, 1993

[8] J. Lambek, “The mathematics of sentence structure”, American Mathematical Monthly, 65:3 (1958), 154–170 | DOI | MR | Zbl

[9] M. Pentus, Equivalent Types in Lambek Calculus and Linear Logic., Preprint No 2, of the Department of Math. Logic, Steklov Math. Institute, Series Logic and Computer Science, Moscow, 1992

[10] M. Pentus, Lambek Grammars Are Context Free, Preprint No 8, of the Department of Math. Logic, Steklov Math. Institute, Series Logic and Computer Science, Moscow, 1993 | MR

[11] M. Pentus, “Lambek grammars are context free”, Proceedings of the annual conference on Logic in Computer Science (LICS'93), 1993 | MR

[12] D. Roorda, Resource Logics: Proof-theoretical Investigations, PhD thesis, Fac. Math. and Comp. Sc., University of Amsterdam, 1991

[13] D. Roorda, “Interpolation in fragments of classical linear logic”, The Journal of Symbolic Logic, 59:2 (1994), 419–444 | DOI | MR | Zbl

[14] K. Schütte, “Der interpolationssatz der intuitionistischen prädikatenlogik”, Mathematische Annalen, 148 (1962), 192–200 | DOI | MR | Zbl

[15] D. N. Yetter., “Quantales and noncommutative linear logic”, Journal of Symbolic Logic, 55 (1990), 41–64 | DOI | MR | Zbl