Geodesic
$(m,n)$-rigid categorial grammars
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 7-23 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the article $(m,n)$-rigid categorial grammars are defined. An algorithm is proposed that verifies for a given grammar $G$ and natural numbers $m$, $n$ whether $G$ is $(m,n)$-rigid. It is proved that an infinite hierarchy exists in the class of $(m,n)$-rigid languages, and that the class of $(m,n)$-rigid grammars is incomparable with the class of regular languages. The complexity of the membership problem for $(m,n)$-rigid grammars is studied.
Mots-clés : formal grammars, rigid grammars
Keywords: categorial grammars, algorithm for rigidity checking, hierarchy of rigid languages, membership problem. 
@article{VTPMK_2017_4_a0,
     author = {B. N. Karlov},
     title = {$(m,n)$-rigid categorial grammars},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {7--23},
     year = {2017},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a0/}
}
TY  - JOUR
AU  - B. N. Karlov
TI  - $(m,n)$-rigid categorial grammars
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2017
SP  - 7
EP  - 23
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a0/
LA  - ru
ID  - VTPMK_2017_4_a0
ER  - 
%0 Journal Article
%A B. N. Karlov
%T $(m,n)$-rigid categorial grammars
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2017
%P 7-23
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a0/
%G ru
%F VTPMK_2017_4_a0
B. N. Karlov. $(m,n)$-rigid categorial grammars. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2017), pp. 7-23. http://geodesic.mathdoc.fr/item/VTPMK_2017_4_a0/

[1] Aho A., Ulman D., The Theory of Syntactic Analysis, Translation and Compilation, v. 1, Mir Publ., Moscow, 1978 (in Russian) | MR

[2] Gladkii A. V., Formal Grammars and Languages, Nauka Publ., Moscow, 1973 (in Russian) | MR

[3] Syntactically marked corpus of the Russian language: information for users. 2003-2017, (in Russian) http://www.ruscorpora.ru/instruction-syntax.html

[4] Bar-Hillel Y., “A quasi-arithmetical notation for syntactic description”, Language, 29:1 (1953), 47-58 | DOI | Zbl

[5] Bar-Hillel Y., Gaifman H., Shamir E., “On categorial and phrase structure grammars”, Bulletin of the Research Council of Israel, 9F (1960), 1-16 | MR

[6] Dekhtyar M., Dikovsky A., “Generalized categorial dependency grammars”, Pillars of Computer Science, Lecture Notes in Computer Science, 4800, eds. A. Avron, N. Dershowitz, A. Rabinovich, Springer, Berlin, Heidelberg, 2008, 230-255 | DOI | MR | Zbl

[7] Dekhtyar M., Dikovsky A., Karlov B., “Categorial dependency grammars”, Theoretical Computer Science, 579 (2015), 33-63 | DOI | MR | Zbl

[8] Kallmeyer L., Parsing Beyond Context-Free Grammars, Cognitive Technologies, Springer-Verlag, Berlin, Heidelberg, 2010 | DOI | Zbl

[9] Kanazawa M., Learnable Classes of Categorial Grammars, Studies in Logic, Language, and Information, FoLLI CSLI, 1998 | MR

[10] Pentus M., Equivalent types in Lambek calculus and linear logic, Preprint No. 2 of the Department of Mathematical Logic of the Math. V.A. Steklov Institute of RAS. Series: Mathematical Logic and Theoretical Informatics, Moscow, 1992, 21 pp. (in Russian)

[11] Vijay-Shanker K., Weir D. J., “The equivalence of four extensions of context-free grammars”, Mathematical Study Theory, 27 (1994), 511-545 | DOI | MR