Reference : A numeration point of view on the HD0L periodicity problem
Scientific conferences in universities or research centers : Scientific conference in universities or research centers
Physical, chemical, mathematical & earth Sciences : Mathematics
A numeration point of view on the HD0L periodicity problem
Charlier, Emilie mailto [University of Waterloo > School of Computer Science > > >]
Languages and Automata Theory Seminar of the University of Waterloo
21 janvier 2011
[en] HD0L periodicity problem ; Numeration systems ; Combinatorics on words
[en] 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.

There is no file associated with this reference.

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.