Geodesic
The range of non-linear natural polynomials cannot be context-free
Kybernetika, Tome 56 (2020) no. 4, pp. 722-726
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\{f(n)\mid n\in {\mathbb N}\}\subseteq {\mathbb N}$. We show that the base-$q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\{f(n)\mid n\in {\mathbb N}\}\subseteq {\mathbb N}$. We show that the base-$q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma.
DOI : 10.14736/kyb-2020-4-0722
Classification : 68Q45
Keywords: contex-free languages; pumping lemma 
@article{10_14736_kyb_2020_4_0722,
     author = {P\'alv\"olgyi, D\"om\"ot\"or},
     title = {The range of non-linear natural polynomials cannot be context-free},
     journal = {Kybernetika},
     pages = {722--726},
     year = {2020},
     volume = {56},
     number = {4},
     doi = {10.14736/kyb-2020-4-0722},
     mrnumber = {4168532},
     zbl = {07286043},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-4-0722/}
}
TY  - JOUR
AU  - Pálvölgyi, Dömötör
TI  - The range of non-linear natural polynomials cannot be context-free
JO  - Kybernetika
PY  - 2020
SP  - 722
EP  - 726
VL  - 56
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-4-0722/
DO  - 10.14736/kyb-2020-4-0722
LA  - en
ID  - 10_14736_kyb_2020_4_0722
ER  - 
%0 Journal Article
%A Pálvölgyi, Dömötör
%T The range of non-linear natural polynomials cannot be context-free
%J Kybernetika
%D 2020
%P 722-726
%V 56
%N 4
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2020-4-0722/
%R 10.14736/kyb-2020-4-0722
%G en
%F 10_14736_kyb_2020_4_0722
Pálvölgyi, Dömötör. The range of non-linear natural polynomials cannot be context-free. Kybernetika, Tome 56 (2020) no. 4, pp. 722-726. doi: 10.14736/kyb-2020-4-0722

[1] Bar-Hillel, Y., Perles, M. A., Shamir, E.: On formal properties of simple phrase-structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14 (1961), 2, 143-172. | DOI | MR

[2] Dömösi, P., Kudlek, M.: Strong iteration lemmata for regular, linear, context-free, and linear indexed languages. In: Fund. Comput. Theory 1999, pp. 226-233. | DOI | MR

[3] Ogden, W., Ross, R. J., Winklmann, K.: An “Interchange Lemma” for context-free languages. SIAM J. Comput. 14 (1982), 2, 410-415. | DOI | MR

[4] Shallit, J.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press, New York 2008. | DOI

Cité par Sources :