A numeration point of view on the HD0L periodicity problem

A HD0L system is a 5-tuple G = (∆, Γ, f, g, w) where
• ∆ and Γ are alphabet;
• f : ∆^∗ → ∆^∗ is a morphism;
• g : ∆^∗ → Γ^∗ is a morphism;
• w is a finite word over ∆.
If w is a prefix of f(w) and if g(f^ω(w)) is an infinite word over Γ, where f^ω(w) denotes the limit lim_{n→+∞}f^n(w), then we define the infinite word generated by G to be ω(G) = g(f^ω(w)). The question is to decide whether the infinite word ω(G) is ultimately periodic. This open problem is called the HD0L periodicity problem. It is not hard to see that we may assume that w is a letter. Furthermore, it is well known that we can assume that f is a non-erasing morphism and g is a coding. Therefore we will always consider that all these additional hypotheses hold. On the one hand, if f is uniform of length b, then ω(G) is b-automatic. In that particular case the problem is known to be decidable. Various proofs of this result have been given by several authors. On the other hand, in the general case, when f is not necessarily uniform, ω(G) is S-automatic for some abstract numeration system S. Therefore the HD0L periodicity problem is equivalent to the following problem involving numeration systems. Given an abstract numeration system S, is it decidable whether an S-recognizable set X ⊆ N is ultimately periodic? The numeration language L and the set X are given through DFAs accepting L and rep_S(X) respectively. Thanks to this numeration point of view, we can give decision procedures for large classes of numeration systems. In this talk, I will discuss some techniques used to provide such decision procedures.