×

The structure of invertible substitutions on a three-letter alphabet. (English) Zbl 1082.68092

Summary: We study the structure of invertible substitutions on a three-letter alphabet. We show that there exists a finite set \(\mathbb{S}\) of invertible substitutions such that any invertible substitution can be written as \(I_w \circ\sigma_1\circ \sigma_2\circ\cdots\circ\sigma_k\), where \(I_w\) is the inner automorphism associated with \(w\), and \(\sigma_j\in\mathbb{S}\) for \(1 \leq j\leq k\). As a consequence, \(M\) is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pytheas Fogg, N., Substitutions in dynamics, arithmetics and combinatorics, (Berthé, V.; Ferenczi, S.; Mauduit, C.; Siegel, A., Lecture Notes in Math., vol. 1794 (2002), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1144.11020
[2] Arnoux, P.; Berthé, V.; Ei, H.; Ito, S., Tilings, quasicrystals, discrete planes, generalized substitutions, and multidimensional continued fractions, (Discrete Models: Combinatorics, Computation, and Geometry. Discrete Models: Combinatorics, Computation, and Geometry, Paris, 2001 (electronic). Discrete Models: Combinatorics, Computation, and Geometry. Discrete Models: Combinatorics, Computation, and Geometry, Paris, 2001 (electronic), Discrete Math. Theor. Comput. Sci. Proc., vol. AA (2001), Maison Inform. Math. Discrèt. (MIMD): Maison Inform. Math. Discrèt. (MIMD) Paris), 059-078 · Zbl 1017.68147
[3] Arnoux, P.; Ito, S., Pisot substitutions and Rauzy fractals, Journées Montoises d’Informatique Théorique. Journées Montoises d’Informatique Théorique, Marne-la-Vallée, 2000. Journées Montoises d’Informatique Théorique. Journées Montoises d’Informatique Théorique, Marne-la-Vallée, 2000, Bull. Belg. Math. Soc. Simon Stevin, 8, 2, 181-207 (2001) · Zbl 1007.37001
[4] Axel, F.; Gratias, D., Beyond Quasicrystals (1995), Springer-Verlag: Springer-Verlag Berlin-Heidelberg
[5] Berstel, J., Recent results in Sturmian words, (Developments in Language Theory, II (Magdeburg, 1995) (1996), World Scientific: World Scientific River Edge, NJ), 13-24 · Zbl 1096.68689
[6] Bombieri, E.; Taylor, J., Quasicrystals, tilings, and algebraic number theory: some preliminary connections, Contemp. Math., 64, 241-264 (1987) · Zbl 0617.43002
[7] Cobham, A., Uniform tag sequences, Math. System Theory, 6, 164-192 (1972) · Zbl 0253.02029
[8] Ei, H.; Ito, S., Decomposition theorem for invertible substitution, Osaka J. Math., 34, 821-834 (1998) · Zbl 0924.20040
[9] Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia Math. Appl., vol. 90 (2002), Cambridge Univ. Press: Cambridge Univ. Press Cambridge, UK · Zbl 1001.68093
[10] Luck, J. M.; Godrèche, C.; Janner, A.; Janssen, T., The nature of the atomic surfaces of quasiperiodic self-similar structures, J. Phys. A: Math. Gen., 26, 1951-1999 (1993) · Zbl 0785.11057
[11] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer-Verlag: Springer-Verlag Berlin-Heidelberg-New York · Zbl 0368.20023
[12] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations (1976), Dover · Zbl 0362.20023
[13] Mignosi, F.; Séébold, P., Morphisms sturmiens et règles de Rauzy, J. Théor. Nombres Bordeaux, 5, 221-233 (1993) · Zbl 0797.11029
[14] Nielsen, J., Die Isomorphismen der allgemeinen unendlichen Gruppe mit zwei Erzengenden, Math. Ann., 78, 385-397 (1918) · JFM 46.0175.01
[15] Nielsen, J., Die Isomorphismen der freien Gruppen, Math. Ann., 91, 169-209 (1924) · JFM 50.0078.04
[16] Peyrière, J.; Wen, Z.-X.; Wen, Z.-Y., Polynômes associées aux endomorphismes de groupes libres, Enseign. Math., 39, 153-175 (1993) · Zbl 0798.20017
[17] Queffélec, M., Substitution Dynamical System—Spectral Analysis, Lecture Notes in Math., vol. 1924 (1987), Springer-Verlag: Springer-Verlag New York · Zbl 0642.28013
[19] Séébold, P., Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci., 88, 365-384 (1991) · Zbl 0737.68068
[20] Süto, A., Singular continuous spectrum on a Cantor set of zero Lebesgue measure for the Fibonacci hamiltonian, J. Statist. Phys., 56, 527-543 (1989)
[21] Wen, Z.-X.; Wen, Z.-Y., Local isomorphism of the invertible substitutions, C. R. Acad. Sci. Paris Sér. I Math., 318, 299-304 (1994) · Zbl 0812.11018
[22] Wen, Z.-X.; Wen, Z.-Y., Some studies of factors of infinite words generated by invertible substitution, (Barlotti, A.; Delest, M.; Pinzani, R., Proc. 5th Conf. Formal Power Series and Algebraic Combinatorics (1993)), 455-466
[23] Wen, Z.-X.; Wen, Z.-Y., Some properties of the singular words of the Fibonacci word, European J. Combin., 15, 587-598 (1994) · Zbl 0823.68087
[24] Wen, Z.-X.; Wen, Z.-Y.; Wu, J., Invertible substitutions and local isomorphisms, C. R. Acad. Sci. Paris Sér. I Math., 334, 629-634 (2002) · Zbl 0996.68148
[25] Wen, Z.-X.; Zhang, Y., 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.