| Title:
|
The range of non-linear natural polynomials cannot be context-free (English) |
| Author:
|
Pálvölgyi, Dömötör |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
56 |
| Issue:
|
4 |
| Year:
|
2020 |
| Pages:
|
722-726 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i. e., $L=\{f(n)\mid n\in {\mathbb N}\}\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. (English) |
| Keyword:
|
contex-free languages |
| Keyword:
|
pumping lemma |
| MSC:
|
68Q45 |
| idZBL:
|
Zbl 07286043 |
| idMR:
|
MR4168532 |
| DOI:
|
10.14736/kyb-2020-4-0722 |
| . |
| Date available:
|
2020-10-30T16:26:45Z |
| Last updated:
|
2021-02-23 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148380 |
| . |
| Reference:
|
[1] Bar-Hillel, Y., Perles, M. A., Shamir, E.: On formal properties of simple phrase-structure grammars..Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14 (1961), 2, 143-172. MR 0151376, 10.1524/stuf.1961.14.14.143 |
| Reference:
|
[2] Dömösi, P., Kudlek, M.: Strong iteration lemmata for regular, linear, context-free, and linear indexed languages..In: Fund. Comput. Theory 1999, pp. 226-233. MR 1850234, 10.1007/3-540-48321-7_18 |
| Reference:
|
[3] Ogden, W., Ross, R. J., Winklmann, K.: An “Interchange Lemma” for context-free languages..SIAM J. Comput. 14 (1982), 2, 410-415. MR 0784746, 10.1137/0214031 |
| Reference:
|
[4] Shallit, J.: A Second Course in Formal Languages and Automata Theory..Cambridge University Press, New York 2008. 10.1017/cbo9780511808876 |
| . |
