Construction of regular languages and recognizability of polynomials
| dc.creator | Rigo, Michel | |
| dc.date | 1999-08-27 | |
| dc.date.accessioned | 2026-07-07T03:24:19Z | |
| dc.date.available | 2026-07-07T03:24:19Z | |
| dc.description | A generalization of numeration system in which the set N of the natural numbers is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite regular language. Here we show that if P belonging to Q[x] is a polynomial such that P(N) is a subset of N then we can construct a numeration system in which the set of representations of P(N) is regular. The main issue in this construction is to setup a regular language with a density function equals to P(n+1)-P(n) for n large enough. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/cs/9908018 | |
| dc.identifier | http://arxiv.org/abs/cs/9908018 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33281 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.1; F.4.3 | |
| dc.title | Construction of regular languages and recognizability of polynomials | |
| dc.type | text |