[en] We address the following decision problem. Given a numeration system U and a U-recognizable set of non-negative integers X, i.e. the set of its greedy U-representations is recognized by a finite automaton, decide whether or not X is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linearly recurrent sequences. Based on arithmetical considerations about the recurrence equation and on p-adic methods, the DFA given as input provides a bound on the admissible periods to test.
Disciplines :
Mathematics
Author, co-author :
Massuir, Adeline ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Ultimate periodicity problem for linear numeration systems
Alternative titles :
[en] Problème d'ultime périodicité pour des systèmes de numération linéaires