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

01/12/2019
by   Dömötör Pálvölgyi, et al.
0

Suppose that some polynomial f with rational coefficients takes only natural values at natural numbers, i.e., L={f(n)| n∈ N}⊂ N. We show that the base-k 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset