Pálvölgyi, Dömötör (2020) The range of non-linear natural polynomials cannot be context-free. KYBERNETIKA, 56 (4). pp. 722-726. ISSN 0023-5954
|
Text
1901.03913.pdf Available under License Creative Commons Attribution. Download (95kB) | Preview |
Official URL: https://doi.org/10.14736/kyb-2020-4-0722
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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | contex-free languages; |
| Subjects: | Q Science / természettudomány > Q1 Science (General) / természettudomány általában |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 12 Jun 2023 05:16 |
| Last Modified: | 12 Jun 2023 05:16 |
| URI: | http://real.mtak.hu/id/eprint/167093 |
Actions (login required)
 |
Edit Item |
