Substitutions with cofinal fixed points. (English) Zbl 1121.68092

Summary: Let \(\varphi \) be a substitution over a 2-letter alphabet, say \(\{a,b\}\). If \(\varphi (a)\) and \(\varphi (b)\) begin with \(a\) and \(b\) respectively, \(\varphi \) has two fixed points beginning with \(a\) and \(b\) respectively. We characterize substitutions with two cofinal fixed points (i.e., which differ only by prefixes). The proof is a combinatorial one, based on the study of repetitions of words in the fixed points.


68R15 Combinatorics on words
11B85 Automata sequences
Full Text: DOI Numdam Numdam EuDML


[1] Allouche, J. P.; Shallit, J. O., Automatic sequences: Theory and Applications (2002) · Zbl 1086.11015
[2] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. Soc. Math., 119, 2, 199-215 (1991) · Zbl 0789.28011
[3] Arnoux, P.; Ito, S., Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin, 8, 2, 181-207 (2001) · Zbl 1007.37001
[4] Ei, H.; Ito, S., Decomposition theorem on invertible substitutions, Osaka J. Math., 35, 4, 821-834 (1998) · Zbl 0924.20040
[5] Lothaire, M., Combinatorics on words (1997) · Zbl 0874.20040
[6] Lothaire, M., Algebraic combinatorics on words (2002) · Zbl 1001.68093
[7] Lothaire, M., Applied combinatorics on words (2005) · Zbl 1133.68067
[8] Nielsen, J., Die Isomorphismengruppen der freien Gruppen, Math. Ann, 91, 169-209 (1924) · JFM 50.0078.04
[9] Pytheas Fogg, N., Substitutions in Dynamics, Arithmetics and Combinatorics, 1794 (2002) · Zbl 1014.11015
[10] Séébold, P., An effective solution to the D0L periodicity problem in the binary case, EATCS Bull., 36, 137-151 (1988) · Zbl 0678.68072
[11] Tan, B.; Wen, Z.-X.; Zhang, Y. P., The structure of invertible substitutions on a three-letter alphabet, Adv. in Appl. Math., 32, 4, 736-753 (2004) · Zbl 1082.68092
[12] Wen, Z.-X.; Wen, Z.-Y., Local isomorphism of the invertible substitutions, C. R. Acad. Sci. Paris Sér. I Math., 318, 4, 299-304 (1994) · Zbl 0812.11018
[13] Wen, Z.-X.; Wen, Z.-Y.; Wu, J., On invertible substitutions with two fixed points, C. R. Math. Acad. Sci. Paris, 334, 9, 727-731 (2002) · Zbl 0996.68149
[14] Wen, Z.-X.; Zhang, Y. P., Some remarks on invertible substitutions on three letter alphabet, Chinese Sci. Bull., 44, 19, 1755-1760 (1999) · Zbl 1040.20504
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.