2009/07/03 by Jason P. Bell, J. Bell, Bell, J. +9
Computer Science · Mathematics · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #History and Theory of Mathematics #Numerical Methods and Algorithms #Polynomial and algebraic computation #cs.DM #cs.FL
paper · pdf · doi:10.48550/arxiv.0907.0620
arxiv created 2009/07/03 · openalex publication_date 2009/07/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over \0,1\ without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.