Paper Info
Title
The Range Of Non-Linear Natural Polynomials Cannot Be Context-Free
Abstract
Suppose that some polynomial f with rational coefficients takes only natural values at natural numbers, i. e., L = {f (n) vertical bar n is an element of N} subset of 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.
Year
DOI
Venue
2019
10.14736/kyb-2020-4-0722
KYBERNETIKA
Keywords
DocType
Volume
contex-free languages, pumping lemma
Journal
56
Issue
ISSN
Citations 
4
0023-5954
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Dömötör Pálvölgyi1153.79