Circular critical exponents for Thue–Morse factors
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 37-49.

We prove various results about the largest exponent of a repetition in a factor of the Thue–Morse word, when that factor is considered as a circular word. Our results confirm and generalize previous results of Fitzpatrick and Aberkane & Currie.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2018008
Classification : 11B85, 68Q45, 68R15, 03D05, 03B35
Mots-clés : Thue–Morse sequence, critical exponent, finite automaton, circular word, critical exponents
Shallit, Jeffrey 1 ; Zarifi, Ramin 1

1 
@article{ITA_2019__53_1-2_37_0,
     author = {Shallit, Jeffrey and Zarifi, Ramin},
     title = {Circular critical exponents for {Thue{\textendash}Morse} factors},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {37--49},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1-2},
     year = {2019},
     doi = {10.1051/ita/2018008},
     mrnumber = {3920828},
     zbl = {1445.68185},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2018008/}
}
TY  - JOUR
AU  - Shallit, Jeffrey
AU  - Zarifi, Ramin
TI  - Circular critical exponents for Thue–Morse factors
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2019
SP  - 37
EP  - 49
VL  - 53
IS  - 1-2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2018008/
DO  - 10.1051/ita/2018008
LA  - en
ID  - ITA_2019__53_1-2_37_0
ER  - 
%0 Journal Article
%A Shallit, Jeffrey
%A Zarifi, Ramin
%T Circular critical exponents for Thue–Morse factors
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2019
%P 37-49
%V 53
%N 1-2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2018008/
%R 10.1051/ita/2018008
%G en
%F ITA_2019__53_1-2_37_0
Shallit, Jeffrey; Zarifi, Ramin. Circular critical exponents for Thue–Morse factors. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 1-2, pp. 37-49. doi : 10.1051/ita/2018008. http://www.numdam.org/articles/10.1051/ita/2018008/

[1] A. Aberkane and J.D. Currie, There exist binary circular 5∕2+ power free words of every length. Electron. J. Comb. 11 (2004) #R10 | DOI | MR | Zbl

[2] A. Aberkane and J.D. Currie, The Thue-Morse word contains circular 5∕2+ power free words of every length. Theor. Comput. Sci. 332 (2005) 573–581 | DOI | MR | Zbl

[3] J.-P. Allouche and J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications, Proceedings of SETA ’98, edited by C. Ding, T. Helleseth and H. Niederreiter. Springer-Verlag London (1999) 1–16 | MR | Zbl

[4] J. Berstel, Axel Thue’s work on repetitions in words, in Séries Formelles et Combinatoire Algébrique, edited by P. Leroux and C. Reutenauer. Vol. 11 of Publications du LaCim. Université du Québec à Montréal (1992) 65–80

[5] F.M. Dekking, M. Mendès France and A.J. van der Poorten, Folds! Math. Intell. 4 (1982) 130–138. (Erratum, 5 (1983) 5.) | MR | Zbl

[6] D.S. Fitzpatrick, There are binary circular cube-free words of length n contained within the Thue-Morse word for all positive integers n. Ars Combinatoria 74 (2005) 323–329 | MR | Zbl

[7] M. Mendès France and G. Tenenbaum, Dimension des courbes planes, papiers pliés et suites de Rudin-Shapiro. Bull. Soc. Math. France 109 (1981) 207–215 | DOI | Numdam | MR | Zbl

[8] H. Mousavi, Automatic theorem proving in Walnut. Preprint . Code available at https://github.com/hamousavi/Walnut, 2016 2018 | arXiv

[9] H. Mousavi and J. Shallit, Repetition avoidance in circular factors, in DLT 2013 – Developments in Language Theory, edited by M.-P. Béal and O. Carton. Vol. 7907 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, Heidelberg 2013 384–395 | DOI | MR | Zbl

[10] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67. (Reprinted in Selected Mathematical Papers of Axel Thue, edited by T. Nagell. Universitetsforlaget, Oslo (1977) 413–478.) | JFM | MR

Cité par Sources :