Substitutions with Cofinal Fixed Points
[Substitutions de Points fixes co-finaux]
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2551-2563.

Soit ϕ une substitution en un alphabet {a,b} de deux lettres. Si ϕ(a) et ϕ(b) commencent par a et b respectivement, alors ϕ 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.

Let ϕ be a substitution over a 2-letter alphabet, say {a,b}. If ϕ(a) and ϕ(b) begin with a and b respectively, ϕ 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.

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},
     zbl = {1121.68092},
     mrnumber = {2290790},
     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, Tome 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

Cité par Sources :