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

Title:

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

Creator:

Pálvölgyi, Dömötör

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:1db936e3-b71f-47cb-87fc-72b6b8fe525a
uuid:1db936e3-b71f-47cb-87fc-72b6b8fe525a
doi:10.14736/kyb-2020-4-0722

Subject:

contex-free languages and pumping lemma

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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-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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

722-726

Source:

Kybernetika | 2020 Volume:56 | Number:4

Harvested from:

CDK

Metadata only:

false