Generalized perturbed symmetry (Q1266345): Difference between revisions

The aim of this paper is to introduce and to study a generalization of the notion of perturbed symmetry introduced by Mendès France. For any word \(w\) on a finite alphabet \(A\), consider its mirror image \(w^R\) and let \(w^E= w\). The generalized perturbed symmetry is a map of the form \[ S(w)= w \prod_{1\leq i\leq k-1} x_iw^{e_i}, \] where \(e_i\in \{E,R\}\) and the \(x_i\) are fixed strings in \(A^*\), each of the same length. This process is convergent, and the iteration of the map \(S\) produces an infinite word \(S^\infty(w)\). For instance, the continued fraction expansion of \(f(n)= \sum_{n\geq 0} n^{2^{-k}}\) is produced by the iteration of such a map. The infinite word \(S^\infty(w)\) is first proved to be \(k\)-automatic. Then an exact description of the ultimately periodic case is given. The proof is based on a characterization of periodic fixed points of primitive and one-to-one substitutions of constant length due to \textit{F. M. Dekking} [Z. Wahrsch. Verw. Gebiete 41, No. 3, 221-239 (1978; Zbl 0359.54037)]. The paper ends by solving a conjecture of \textit{S. Blanchard} and \textit{S. Fabre} [Theor. Comput. Sci. 123, No. 1, 55-60 (1994; Zbl 0801.68142)], also proved independently in [\textit{A. Černý}, Theor. Comput. Sci. 188, No. 1-2, 161-174 (1997)].