1999/08/27 by Michel Rigo, Rigo, Michel · 1 citation
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #F.4.3 #FOS: Computer and information sciences #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/9908018
11 pages
arxiv created 1999/08/27 · openalex publication_date 1999/08/27 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.