Substitutions with Cofinal Fixed Points
Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2551-2563.

Let $\varphi$ be a substitution over a 2-letter alphabet, say $\left\{a,b\right\}$. If $\varphi \left(a\right)$ and $\varphi \left(b\right)$ 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.

Soit $\varphi$ une substitution en un alphabet $\left\{a,b\right\}$ de deux lettres. Si $\varphi \left(a\right)$ et $\varphi \left(b\right)$ commencent par $a$ et $b$ respectivement, alors $\varphi$ possède deux points fixes débutants par $a$ et $b$ respectivement.

Nous caractériserons les substitutions avec deux points fixes co-finaux (c’est-à-dire, qui diffèrent que par leur préfixe). La démonstration est combinatoire, elle se base sur une étude de répétitions de mots dans les points fixes.

DOI: 10.5802/aif.2249
Classification: 68R15, 11B85
Keywords: Cofinal sequences, substitution
Mot clés : Suites co-finales, substitution
TAN, Bo 1; WEN, Zhi-Xiong 1; WU, Jun 1; WEN, Zhi-Ying 2

1 Huazhong University of Science and Technology Department of Mathematics Wuhan, 430074 (P.R. China)
2 Tsinghua University Department of Mathematics Beijing, 100084 (P.R. China)
@article{AIF_2006__56_7_2551_0,
author = {TAN, Bo and WEN, Zhi-Xiong and WU, Jun and WEN, Zhi-Ying},
title = {Substitutions with {Cofinal} {Fixed} {Points}},
journal = {Annales de l'Institut Fourier},
pages = {2551--2563},
publisher = {Association des Annales de l{\textquoteright}institut Fourier},
volume = {56},
number = {7},
year = {2006},
doi = {10.5802/aif.2249},
mrnumber = {2290790},
zbl = {1121.68092},
language = {en},
url = {http://www.numdam.org/articles/10.5802/aif.2249/}
}
TY  - JOUR
AU  - TAN, Bo
AU  - WEN, Zhi-Xiong
AU  - WU, Jun
AU  - WEN, Zhi-Ying
TI  - Substitutions with Cofinal Fixed Points
JO  - Annales de l'Institut Fourier
PY  - 2006
SP  - 2551
EP  - 2563
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - http://www.numdam.org/articles/10.5802/aif.2249/
DO  - 10.5802/aif.2249
LA  - en
ID  - AIF_2006__56_7_2551_0
ER  - 
%0 Journal Article
%A TAN, Bo
%A WEN, Zhi-Xiong
%A WU, Jun
%A WEN, Zhi-Ying
%T Substitutions with Cofinal Fixed Points
%J Annales de l'Institut Fourier
%D 2006
%P 2551-2563
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U http://www.numdam.org/articles/10.5802/aif.2249/
%R 10.5802/aif.2249
%G en
%F AIF_2006__56_7_2551_0
TAN, Bo; WEN, Zhi-Xiong; WU, Jun; WEN, Zhi-Ying. Substitutions with Cofinal Fixed Points. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2551-2563. doi : 10.5802/aif.2249. http://www.numdam.org/articles/10.5802/aif.2249/

[1] Allouche, J.P.; Shallit, J.O. Automatic sequences: Theory and Applications, Cambridge University Press, Cambrige, 2002 | Zbl

[2] Arnoux, P.; Rauzy, G. Représentation géométrique de suites de complexité $2n+1$, Bull. Soc. Math., Volume 119 (1991) no. 2, pp. 199-215 (France) | Numdam | MR | Zbl

[3] Arnoux, P.; Ito, S Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001) no. 2, pp. 181-207 | MR | Zbl

[4] Ei, H.; Ito, S. Decomposition theorem on invertible substitutions, Osaka J. Math., Volume 35 (1998) no. 4, pp. 821-834 | MR | Zbl

[5] Lothaire, M. Combinatorics on words, Cambridge University Press, Cambridge, 1997 | MR | Zbl

[6] Lothaire, M. Algebraic combinatorics on words, Cambridge University Press, Cambridge, 2002 | MR | Zbl

[7] Lothaire, M. Applied combinatorics on words, Cambridge University Press, Cambridge, 2005 | MR | Zbl

[8] Nielsen, J. Die Isomorphismengruppen der freien Gruppen, Math. Ann, Volume 91 (1924), pp. 169-209 (Available at http://mathlib.sub.uni-goettingen.de/JFM/digit.php?an=JFM+50.0078.04) | DOI | MR

[9] Pytheas Fogg, N. Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematics, 1794, Springer, Berlin, 2002 | MR | Zbl

[10] Séébold, P. An effective solution to the D0L periodicity problem in the binary case, EATCS Bull., Volume 36 (1988), pp. 137-151 | Zbl

[11] Tan, B.; Wen, Z.-X.; Zhang, Y. P. The structure of invertible substitutions on a three-letter alphabet, Adv. in Appl. Math., Volume 32 (2004) no. 4, pp. 736-753 | DOI | MR | Zbl

[12] Wen, Z.-X.; Wen, Z.-Y. Local isomorphism of the invertible substitutions, C. R. Acad. Sci. Paris Sér. I Math., Volume 318 (1994) no. 4, pp. 299-304 | MR | Zbl

[13] Wen, Z.-X.; Wen, Z.-Y.; Wu, J. On invertible substitutions with two fixed points, C. R. Math. Acad. Sci. Paris, Volume 334 (2002) no. 9, pp. 727-731 | MR | Zbl

[14] Wen, Z.-X.; Zhang, Y. P. Some remarks on invertible substitutions on three letter alphabet, Chinese Sci. Bull., Volume 44 (1999) no. 19, pp. 1755-1760 | DOI | MR | Zbl

Cited by Sources: