Reference : A numeration point of view on the HD0L periodicity problem
 Document type : Scientific conferences in universities or research centers : Scientific conference in universities or research centers Discipline(s) : Physical, chemical, mathematical & earth Sciences : Mathematics To cite this reference: http://hdl.handle.net/2268/125706
 Title : A numeration point of view on the HD0L periodicity problem Language : English Author, co-author : Charlier, Emilie [University of Waterloo > School of Computer Science > > >] Publication date : Jan-2011 Audience : National Event name : Languages and Automata Theory Seminar of the University of Waterloo Event date : 21 janvier 2011 Event place (city) : Waterloo Event country : Canada Keywords : [en] HD0L periodicity problem ; Numeration systems ; Combinatorics on words Abstract : [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. Target : Researchers Permalink : http://hdl.handle.net/2268/125706

There is no file associated with this reference.

All documents in ORBi are protected by a user license.