Two-dimensional iterated morphisms and discrete planes. (English) Zbl 1068.37004

Summary: Iterated morphisms of the free monoid are very simple combinatorial objects which produce infinite sequences by replacing iteratively letters by words. The aim of this paper is to introduce a formalism for a notion of two-dimensional morphisms; we show that they can be iterated by using local rules, and that they generate two-dimensional patterns related to discrete approximations of irrational planes with algebraic parameters. We associate such a two-dimensional morphism with any usual Pisot unimodular one-dimensional iterated morphism over a three-letter alphabet.


37B10 Symbolic dynamics
05A05 Permutations, words, matrices
05B25 Combinatorial aspects of finite geometries
37B50 Multi-dimensional shifts of finite type, tiling dynamics (MSC2010)
68R15 Combinatorics on words
Full Text: DOI Link


[1] Allouche, J.-P.; Shallit, J.O., Automatic sequences: theory and applications, (2003), Cambridge University Press Cambridge
[2] Arnoux, P.; Berthé, V.; Ito, S., Discrete planes, \(Z\^{}\{2\}\)-actions, jacobi – perron algorithm and substitutions, Ann. inst. Fourier, 52, 2, 305-349, (2002) · Zbl 1017.11006
[3] Arnoux, P.; Ito, S., Pisot substitutions and Rauzy fractals, Bull. belg. math. soc. Simon stevin, 8, 2, 181-207, (2001), Journées Montoises d’Informatique Théorique, Marne-la-Vallée, 2000 · Zbl 1007.37001
[4] Arnoux, P.; Ito, S.; Sano, Y., Higher dimensional extensions of substitutions and their dual maps, J. anal. math., 83, 183-206, (2001) · Zbl 0987.11013
[5] M. Baake, R.V. Moody (Eds.), Directions in Mathematical Quasicrystals, CRM Monograph Series, Vol. 13, American Mathematical Society, Providence, RI, 2000. viii+379p.
[6] Berthé, V.; Vuillon, L., Suites doubles de basse complexité, J. théor. nombres Bordeaux, 12, 1, 179-208, (2000) · Zbl 1018.37010
[7] Berthé, V.; Vuillon, L., Tilings and rotations on the torusa two-dimensional generalization of Sturmian sequences, Discrete math., 223, 1-3, 27-53, (2000) · Zbl 0970.68124
[8] Canterini, V.; Siegel, A., Geometric representation of substitutions of Pisot type, Trans. amer. math. soc., 353, 12, 5121-5144, (2001) · Zbl 1142.37302
[9] Ferenczi, S., Rank and symbolic complexity, Ergodic theory dyn. systems, 16, 663-682, (1996) · Zbl 0858.68051
[10] Giammaressi, D.; Restivo, A., Two-dimensional languages, (1997), Springer Berlin
[11] C.W. Hansen, Dynamics of multi-dimensional substitutions, Ph.D. Thesis, George Washington University, 2000.
[12] Ito, S.; Ohtsuki, M., Modified jacobi – perron algorithm and generating Markov partitions for special hyperbolic toral automorphisms, Tokyo J. math., 16, 2, 441-472, (1993) · Zbl 0805.11056
[13] Ito, S.; Ohtsuki, M., Parallelogram tilings and jacobi – perron algorithm, Tokyo J. math., 17, 1, 33-58, (1994) · Zbl 0805.52011
[14] Lagarias, J.C.; Pleasants, P.A.B., Local complexity of Delone sets and crystallinity, Canad. math. bull., 45, 4, 634-652, (2002), (Dedicated to R.V. Moody) · Zbl 1016.52013
[15] Lothaire, M., Algebraic combinatorics on words, (2002), Cambridge University Press Cambridge · Zbl 1001.68093
[16] Pytheas Fogg, N., ()
[17] M. Queffélec, Substitution Dynamical Systems—Spectral Analysis, Lecture Notes in Mathematics, Vol. 1294, Springer, Berlin, 1987. xiv+240p. · Zbl 0642.28013
[18] Rauzy, G., Nombres algébriques et substitutions, Bull. soc. math. France, 110, 2, 147-178, (1982) · Zbl 0522.10032
[19] E.A. Robinson, Jr., The dynamical theory of tilings and quasicrystallography, in: Ergodic Theory of \( Z\^{}\{d\}\) Actions (Warwick, 1993-1994), London Mathematical Society, Lecture Note Series, Vol. 228, Cambridge Univ. Press, Cambridge, 1996, pp. 451-473.
[20] M. Senechal, Quasicrystals and Geometry, Cambridge University Press, Cambridge, 1995. xvi+286p.
[21] Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionnelle, Theoret. comput. sci., 209, 261-285, (1998) · Zbl 0913.68206
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.