Asymptotic properties of free monoid morphisms (Q272351): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q355508 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Anton Černý / rank | |||
Normal rank |
Revision as of 21:13, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotic properties of free monoid morphisms |
scientific article |
Statements
Asymptotic properties of free monoid morphisms (English)
0 references
20 April 2016
0 references
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\).
0 references
iterated morphism
0 references
Cobham theorem
0 references
incidence matrix of a morphism
0 references
eigenvalue
0 references
free monoid
0 references
asymptotics
0 references
numeration system
0 references
algorithms
0 references