Optimal word chains for the Thue-Morse word (Q582129)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal word chains for the Thue-Morse word |
scientific article |
Statements
Optimal word chains for the Thue-Morse word (English)
0 references
1989
0 references
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.
0 references
Word chains
0 references
complexity measure for languages
0 references