Geodesic
The range of non-linear natural polynomials cannot be context-free
Kybernetika, Tome 56 (2020) no. 4, pp. 722-726

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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},
     publisher = {mathdoc},
     volume = {56},
     number = {4},
     year = {2020},
     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
PB  - mathdoc
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
%I mathdoc
%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

Cité par Sources :