Invertible substitutions and Sturmian sequences.
type: Item
instance of: scholarly article
title: Invertible substitutions and Sturmian sequences.
zbMATH Open document ID: 1040.11014
DOI: 10.1016/S0195-6698(03)00105-7
author: Bo Tan
author: Zhi-Ying Wen
published in: European Journal of Combinatorics
publication date: 2003-12-04T00:00:00Z
review text: A morphism of the free monoid on two letters \(a\) and \(b\) (also called binary substitution) is invertible if its natural extension to the free group generated by \(\{a,b\}\) is invertible. A morphism of the free monoid generated by \(\{a,b\}\) is called Sturmian if there exists a Sturmian sequence whose image is Sturmian (equivalently if all Sturmian sequences have Sturmian images). Actually the set of invertible morphisms and the set of Sturmian morphisms above are equal: both are equal to the monoid generated by three particular morphisms [see \textit{Zhixiong Wen} and \textit{Zhiying Wen}, C. R. Acad. Sci., Paris, Sér. I 318, 299--304 (1994; Zbl 0812.11018)] and \textit{F. Mignosi} and \textit{P. Séébold}, J. Théor. Nombres Bordx. 5, 221--233 (1993; Zbl 0797.11029)]. In the paper under review the authors give a new characterization of invertible binary morphisms: the morphism \(\tau\) is invertible if and only if there exist two words \(u\) and \(v\) on the alphabet \(\{a,b\}\) such that either \[ \begin{cases} \tau(ab)= uabv\\ \tau(ba)= ubav\end{cases}\qquad\text{or}\qquad \begin{cases} \tau(ab)= ubav\\ \tau(ba)= uabv.\end{cases} \] The paper ends with properties of fixed points of invertible morphisms. Note that References 6 and 30 have appeared [see \textit{W.-T. Cao} and \textit{Z.-Y. Wen}, Theor. Comput. Sci. 304, 365--385 (2003; Zbl 1045.68109) and \textit{Z. Wen}, \textit{Z. Wen} and \textit{J. Wu}, C. R., Math., Acad. Sci. Paris 334, 727--731 (2002; Zbl 0996.68149)]. Also note that the second book of Lothaire cited in the paper is not a new version of the first one but a continuation [see \textit{M. Lothaire}, Algebraic combinatorics on words, Cambridge University Press, Cambridge (2002; Zbl 1001.68093)].
Mathematics Subject Classification ID: 11B85
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 2012994
zbMATH Keywords: invertible substitutions
zbMATH Keywords: Sturmian sequences
zbMATH Keywords: morphisms of the free monoid
reviewed by: Jean-Paul Allouche
MaRDI profile type: Publication
cites work: Pisot substitutions and Rauzy fractals
cites work: Q5486010
cites work: Substitutions in dynamics, arithmetics and combinatorics
cites work: A Characterization of the Quadratic Irrationals
cites work: Some properties of the factors of Sturmian sequences.
cites work: Substitution invariant cutting sequences
cites work: Decomposition theorem on invertible substitutions
cites work: Determination of [nθ] by its Sequence of*Differences
cites work: Sturmian Minimal Sets
cites work: Q5752638
cites work: Q5727752
cites work: Q3125862
cites work: Substitution invariant inhomogeneous Beatty sequences
cites work: Q4529547
cites work: Sturmian morphisms and Rauzy's rules
cites work: Invariance properties of Sturmian words
cites work: Substitution invariant Sturmian bisequences
cites work: Polynomials associated with endomorphisms of free groups
cites work: Substitution dynamical systems - spectral analysis
cites work: Fibonacci morphisms and Sturmian words
cites work: Beatty Sequences, Continued Fractions, and Certain Shift Operators
cites work: Some properties of the singular words of the Fibonacci word
cites work: Q4296127
cites work: On invertible substitutions with two fixed points
cites work: On Sturmian sequences which are invariant under some substitutions
description: scientific article; zbMATH DE number 2012994