The range of non-linear natural polynomials cannot be context-free

Pálvölgyi, Dömötör. "The range of non-linear natural polynomials cannot be context-free." Kybernetika 56.4 (2020): 722-726. <http://eudml.org/doc/297310>.

@article{Pálvölgyi2020,
abstract = {Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\lbrace f(n)\mid n\in \{\mathbb \{N\}\}\rbrace \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.},
author = {Pálvölgyi, Dömötör},
journal = {Kybernetika},
keywords = {contex-free languages; pumping lemma},
language = {eng},
number = {4},
pages = {722-726},
publisher = {Institute of Information Theory and Automation AS CR},
title = {The range of non-linear natural polynomials cannot be context-free},
url = {http://eudml.org/doc/297310},
volume = {56},
year = {2020},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 56
IS - 4
SP - 722
EP - 726
AB - Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\lbrace f(n)\mid n\in {\mathbb {N}}\rbrace \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.
LA - eng
KW - contex-free languages; pumping lemma
UR - http://eudml.org/doc/297310
ER -