Optimal word chains for the Thue-Morse word (Q582129)

Word chains are an extension of addition chains to words and can be used as a complexity measure for languages. Let \(\Sigma =\{a,b\}\) and \(\phi\) be the morphism \(\phi:\Sigma^*\to \Sigma^*\) given by \(\phi (a)=ab\) and \(\phi (b)=ba\). We study word chains for the iterates \(\phi^ n(a)\) of the Thue-Morse word. The Length of optimal word chains for \(\phi^ n(a)\) is proved to be 2n-1, and a conjecture on the enumeration of optimal word chains computing \(\phi^ n(a)\) is proposed.