Article ID Journal Published Year Pages File Type
6875384 Theoretical Computer Science 2018 15 Pages PDF
Abstract
Any infinite uniformly recurrent word u can be written as concatenation of a finite number of return words to a chosen prefix w of u. Ordering of the return words to w in this concatenation is coded by derivated word du(w). In 1998, Durand proved that a fixed point u of a primitive morphism has only finitely many derivated words du(w) and each derivated word du(w) is fixed by a primitive morphism as well. In our article we focus on Sturmian words fixed by a primitive morphism. We provide an algorithm which to a given Sturmian morphism ψ lists the morphisms fixing the derivated words of the Sturmian word u=ψ(u). We provide a sharp upper bound on length of the list.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,