# Boundedness of oriented walks generated by substitutions

• Volume: 8, Issue: 2, page 377-386
• ISSN: 1246-7405

top

## Abstract

top
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.

## How to cite

top

Dekking, F. M., and Wen, Z.-Y.. "Boundedness of oriented walks generated by substitutions." Journal de théorie des nombres de Bordeaux 8.2 (1996): 377-386. <http://eudml.org/doc/247843>.

@article{Dekking1996,
abstract = {Let $x = x_0x_1 \dots$ be a fixed point of a substitution on the alphabet $\left\lbrace a,b \right\rbrace ,$ and let $U_a = \left( \begin\{array\}\{rr\}-1 & -1\\ 0 & 1 \end\{array\} \right)$ and $U_b = \left( \begin\{array\}\{rr\} 1 & 1\\ 0 & 1 \end\{array\} \right)$. We give a complete classification of the substitutions $\sigma : \left\lbrace a, b \right\rbrace ^\{\star \}$ according to whether the sequence of matrices $\left( U_\{x_0\} U_\{x_1\} \dots U_\{x_n\} \right)^\infty _\{n=0\}$ is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.},
author = {Dekking, F. M., Wen, Z.-Y.},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {substitutions; self-similarity; walks; automata sequences; boundedness; oriented one-dimensional walks; transition matrices},
language = {eng},
number = {2},
pages = {377-386},
publisher = {Université Bordeaux I},
title = {Boundedness of oriented walks generated by substitutions},
url = {http://eudml.org/doc/247843},
volume = {8},
year = {1996},
}

TY - JOUR
AU - Dekking, F. M.
AU - Wen, Z.-Y.
TI - Boundedness of oriented walks generated by substitutions
JO - Journal de théorie des nombres de Bordeaux
PY - 1996
PB - Université Bordeaux I
VL - 8
IS - 2
SP - 377
EP - 386
AB - Let $x = x_0x_1 \dots$ be a fixed point of a substitution on the alphabet $\left\lbrace a,b \right\rbrace ,$ and let $U_a = \left( \begin{array}{rr}-1 & -1\\ 0 & 1 \end{array} \right)$ and $U_b = \left( \begin{array}{rr} 1 & 1\\ 0 & 1 \end{array} \right)$. We give a complete classification of the substitutions $\sigma : \left\lbrace a, b \right\rbrace ^{\star }$ according to whether the sequence of matrices $\left( U_{x_0} U_{x_1} \dots U_{x_n} \right)^\infty _{n=0}$ is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.
LA - eng
KW - substitutions; self-similarity; walks; automata sequences; boundedness; oriented one-dimensional walks; transition matrices
UR - http://eudml.org/doc/247843
ER -

## References

top
1. [1] F.M. Dekking, Recurrent sets, Advances in Math.44 (1982), 78-104. Zbl0495.51017MR654549
2. [2] F.M. Dekking, On transience and recurrence of generalized random walks, Z. Wahrsch. verw. Geb.61 (1982), 459-465. Zbl0479.60070MR682573
3. [3] F.M. Dekking, Marches automatiques, J. Théor. Nombres Bordeaux5 (1993), 93-100. Zbl0795.11011MR1251229
4. [4] F.M. Dekking, Iteration of maps by an automaton, Discrete Math.126 (1994), 81-86. Zbl0795.68158MR1264477
5. [5] J.-M. Dumont et A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions, Theor. Comp. Science65 (1989), 153-169. Zbl0679.10010MR1020484
6. [6] J.-M. Dumont, Summation formulae for substitutions on a finite alphabet, Number Theory and Physics (Eds: J.-M. Luck, P. Moussa, M. Waldschmidt). Springer Lect. Notes Physics47 (1990), 185-194. Zbl0718.11009MR1058462
7. [7] M. Mendès France and J. Shallit, Wirebending and continued fractions, J. Combinatorial Theory Ser. A50 (1989), 1-23. Zbl0663.10056MR978063
8. [8] D. Levine and P.J. Steinhardt, Quasicrystals (I). Definition and structure. Physical ReviewB, vol. (2) 34, 1986, 596-615. MR831879
9. [9] P.A.B. Pleasants, Quasicrystallography: some interesting new patterns. Banach center publications, vol. 17, 1985, 439-461. Zbl0655.05023MR840489
10. [10] Z.-X. Wem and Z.-Y. Wen, Marches sur les arbres homogènes suivant une suite substitutive, J. Théor. Nombres Bordeaux, 4 (1992), 155-186. Zbl0755.11007MR1183924

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.