Boundedness of oriented walks generated by substitutions

Dekking, F. M.  ; Wen, Z.-Y. 

Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 377-386

Abstract (VO)

Let $x=x_0{x}_1\cdots$ be a fixed point of a substitution on the alphabet $\left\{a,b\right\},$ and let $U_a=\left(\begin{array}{cc}\hfill -1& \hfill -1\\ \hfill 0& \hfill 1\end{array}\right)$ and $U_b=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 0& \hfill 1\end{array}\right)$. We give a complete classification of the substitutions $\sigma :{\left\{a,b\right\}}^{☆}$ according to whether the sequence of matrices ${\left(U_{x_0}{U}_{x_1}\cdots U_{x_n}\right)}_{n=0}^{\infty }$ is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.

Résumé

Soit $x=x_0{x}_1\cdots$ un point fixe de la substitution sur l’alphabet $\left\{a,b\right\},$ et soit $U_a=\left(\begin{array}{cc}\hfill -1& \hfill -1\\ \hfill 0& \hfill 1\end{array}\right)$ et $U_b=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 0& \hfill 1\end{array}\right)$. On donne une classification complète des substitutions $\sigma :{\left\{a,b\right\}}^{☆}$ selon que la suite de matrices ${\left(U_{x_0}{U}_{x_1}\cdots U_{x_n}\right)}_{n=0}^{\infty }$ est bornée ou non. Cela correspond au fait que les chemins orientés engendrés par les substitutions sont bornés ou non.

Détail

Keywords: substitutions, self-similarity, walks