Some properties of substitutive words (Q1781918): Difference between revisions

The authors are interested in substitutive words (i.e., words obtained by applying a morphism of the free monoid to the iterative fixed point of some morphism of the free monoid). Cobham proved in 1968 that such a word can be obtained by a more precise construction where the first morphism above is a letter-to-letter morphism. The authors give a simpler proof of Cobham's result. They also obtain refined results for purely substitutive words and for the block-complexity of substitutive words. Please note that Reference [1] appeared: [\textit{J.-P. Allouche} and \textit{J. Shallit}, Automatic sequences. Theory, applications, generalizations. Cambridge: University Press (2003; Zbl 1086.11015)].