Asymptotic properties of free monoid morphisms (Q272351): Difference between revisions

A well-known result of Cobham states that any infinite word obtained by iterating a morphism and a final application of another morphism, that is, being of the form \(g\left( f^{\omega}\left( a\right) \right) \), can be expressed in a similar form \(\tau\left( \sigma^{\omega}\left( b\right) \right) \), where \(\sigma\) is a non-easing morphism and \(\tau\) a coding (alphabetical morphism) mapping each alphabetical symbol to a symbol -- possibly in a different alphabet. The paper provides an algorithm for construction of \(\sigma\) and \(\tau\) for a given pair \(f\), \(g,\) and studies the growth characteristic of the morphism \(\sigma\) occurring in this latter form. The investigations are based on studying the propeties of the incidence matrix \(\mathsf{Mat}_{f}\in\mathbb{N}^{A\times A}\) of a morphism \(f:A^{\ast }\rightarrow A^{\ast}\) where \(\left( \mathsf{Mat}_{f}\right) _{a,b}\) is the number of occurrences of \(a\) in \(f\left( b\right) \). The authors show that for such a morphism \(f\) and for each symbol \(a\in A\) there exists a unique pair \(\left( \lambda,d\right) \), where \(\lambda\) is an eigenvalue of \(\mathsf{Mat}_{f}\) and \(d\in\mathbb{N}\), such that \(\left| f^{n}\left( a\right) \right| =\Theta\left( n^{d}\lambda^{n}\right) \). If \(f\) is prolongable on \(a\in A\) and \(f^{\omega}\left( a\right) \) contains all symbols from \(A\) then the pair \(\left( \lambda,d\right) \) is called the growth type of \(f\) with respect to \(a.\) The main result states that if \(g\), \(f\), \(a\) are as in the Cobham theorem and \(f\) has growth type \(\left( \lambda,d\right) \) with respect to \(a\) then one can construct the corresponding \(\sigma\), \(\tau\), \(b\) such that \(\mathsf{Mat}_{\sigma}\) is a dilated matrix of \(\mathsf{Mat}_{f}\) and \(\sigma\) has growth type \(\left( \lambda,d\right) \) with respect to \(b\).