[en] We consider the following decidability problem: Given a linear numeration system U and a set X ⊆ N such that rep_U(X) is recognized by a (deterministic) finite automaton. Is it decidable whether or not X is ultimately periodic, i.e., whether or not X is a finite union of arithmetic progressions? In this work, we give a decision procedure for this problem whenever U is a linear numeration system such that N is U -recognizable and satisfying a relation of the form U_{i+k} = a_1 U_{i+k−1} + · · · + a_k U_i with a_k = ±1 (the main reason for this assumption is that 1 and −1 are the only two integers invertible modulo n for all n ≥ 2).
Disciplines :
Mathematics
Author, co-author :
Charlier, Emilie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
A decision problem for ultimately periodic sets in non-standard numeration systems