Derived sequences of complementary symmetric Rote sequences
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 3-4, pp. 125-151.

Complementary symmetric Rote sequences are binary sequences which have factor complexity C(n) = 2n for all integers n ≥ 1 and whose languages are closed under the exchange of letters. These sequences are intimately linked to Sturmian sequences. Using this connection we investigate the return words and the derived sequences to the prefixes of any complementary symmetric Rote sequence v which is associated with a standard Sturmian sequence u. We show that any non-empty prefix of v has three return words. We prove that any derived sequence of v is coding of three interval exchange transformation and we determine the parameters of this transformation. We also prove that v is primitive substitutive if and only if u is primitive substitutive. Moreover, if the sequence u is a fixed point of a primitive morphism, then all derived sequences of v are also fixed by primitive morphisms. In that case we provide an algorithm for finding these fixing morphisms.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2019004
Classification : 68R15
Mots-clés : Derived sequence, return word, Rote sequence, Sturmian sequence
Medková, Kateřina 1 ; Pelantová, Edita 1 ; Vuillon, Laurent 1

1 
@article{ITA_2019__53_3-4_125_0,
     author = {Medkov\'a, Kate\v{r}ina and Pelantov\'a, Edita and Vuillon, Laurent},
     title = {Derived sequences of complementary symmetric {Rote} sequences},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {125--151},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {3-4},
     year = {2019},
     doi = {10.1051/ita/2019004},
     mrnumber = {4052997},
     zbl = {1434.68387},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2019004/}
}
TY  - JOUR
AU  - Medková, Kateřina
AU  - Pelantová, Edita
AU  - Vuillon, Laurent
TI  - Derived sequences of complementary symmetric Rote sequences
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2019
SP  - 125
EP  - 151
VL  - 53
IS  - 3-4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2019004/
DO  - 10.1051/ita/2019004
LA  - en
ID  - ITA_2019__53_3-4_125_0
ER  - 
%0 Journal Article
%A Medková, Kateřina
%A Pelantová, Edita
%A Vuillon, Laurent
%T Derived sequences of complementary symmetric Rote sequences
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2019
%P 125-151
%V 53
%N 3-4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2019004/
%R 10.1051/ita/2019004
%G en
%F ITA_2019__53_3-4_125_0
Medková, Kateřina; Pelantová, Edita; Vuillon, Laurent. Derived sequences of complementary symmetric Rote sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 53 (2019) no. 3-4, pp. 125-151. doi : 10.1051/ita/2019004. http://archive.numdam.org/articles/10.1051/ita/2019004/

[1] I.M. Araújo and V. Bruyùre, Words derivated from Sturmian words. Theoret. Comput. Sci. 340 (2005) 204–219. | DOI | MR | Zbl

[2] L. Balková, M. Bucci, A. De Luca, J. Hladký and S. Puzynina, Aperiodic pseudorandom number generators based on infinite words. Theoret. Comput. Sci. 647 (2016) 85–100. | DOI | MR | Zbl

[3] L. Balková, E. Pelantová and Š. Starosta, Sturmian jungle (or garden?) on multiliteral alphabets. RAIRO: ITA 44 (2010) 443–470. | Numdam | MR | Zbl

[4] L. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words. Monatsh. Math. 155 (2008) 251–263. | DOI | MR | Zbl

[5] J. Berstel, Sturmian and Episturmian words, in Algebraic Informatics, edited by S. Bozapalidis and G. Rahonis. Springer, Berlin, Heidelberg (2007) 23–47. | DOI | MR | Zbl

[6] J. Berstel and P. Séébold, Sturmian words, in Algebraic Combinatorics on Words, edited by M. Lothaire. Cambridge University Press (2002) 45–110. | MR | Zbl

[7] V. Berthé, C. De Felice, F. Dolce, J. Leroy, D. Perrin, C. Reutenauer and G. Rindone, Acyclic, connected and tree sets. Monatsh. Math. 176 (2015) 521–550. | DOI | MR | Zbl

[8] V. Berthé, V. Delecroix, F. Dolce, D. Perrin, Ch. Reutenauer and G. Rindone, Return words of linear involutions and fundamental groups. Ergodic Theory Dyn. Syst. 37 (2017) 693–715. | DOI | MR | Zbl

[9] V. Berthé, F. Dolce, F. Durand, J. Leroy and D. Perrin, Rigidity and substitutive dendric words. IJFCS Int. J. Found. Comput. Sci. 29 (2018) 705–720. | DOI | MR | Zbl

[10] A. Blondin-Massé, S. Brlek, S. Labbé and L. Vuillon, Codings of rotations on two intervals are full. Electr. Notes Discrete Math. 34 (2009) 289–393. | DOI | Zbl

[11] A. Blondin-Massé, G. Paquin, H. Tremblay and L. Vuillon, On generalized pseudostandard words over binary alphabet. J. Int. Sequen. 16 (2013) 13.2.11. | MR | Zbl

[12] J. Cassaigne, Complexité et facteurs spéciaux. Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67–88. | DOI | MR | Zbl

[13] A. De Luca and A. De Luca, Pseudopalindromic closure operators in free monoids. Theoret. Comput. Sci. 362 (2006) 282–300. | DOI | MR | Zbl

[14] M. Dekking, Substitution invariant words and binary trees. Electr. J. Int. 18A (2018) #A7. | MR | Zbl

[15] F. Dolce and D. Perrin, Neutral and tree sets of arbitrary characteristic. Theoret. Comput. Sci. 658 (2017) 159–174. | DOI | MR | Zbl

[16] F. Durand, A characterization of substitutive sequences using return words. Discrete Math. 179 (1998) 89–101. | DOI | MR | Zbl

[17] F. Durand, A generalization of Cobham’s Theorem. Theory Comput. Syst. 31 (1998) 169–185. | DOI | MR | Zbl

[18] S. Ferenczi and T. Monteil, Infinite Words with Uniform frequencies and invariant measures, in Combinatorics, Automata and Number Theory, edited by V. Berthé and M. Rigo. Cambridge University Press (2010) 373–409. | DOI | MR | Zbl

[19] S. Ferenczi, C. Holton and L. Zamboni, The structure of three-interval exchange transformations II: a combinatorial description of the trajectories. J. Anal. Math. 89 (2003) 239–276. | DOI | MR | Zbl

[20] Y.K. Huang and Z.Y. Wen, Envelope words and the reflexivity of the return word sequences in the period-doubling sequence. Preprint (2017). | arXiv

[21] J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO: ITA 34 (2000) 343–356. | Numdam | MR | Zbl

[22] M.S. Keane, Interval exchange transformations. Math. Zeitsch. 141 (1975) 25–31. | DOI | MR | Zbl

[23] K. Klouda, K. Medková, E. Pelantová and S. Starosta, Fixed points of Sturmian morphisms and their derivated words. Theoret. Comput. Sci. 743 (2018) 23–37. | DOI | MR | Zbl

[24] M. Lothaire, Combinatorics on Words, Vol. 17 of Encyclopaedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass (1983). Reprinted in the Cambridge Mathematical Library, Cambridge University Press, Cambridge, UK (1997). | MR

[25] M. Morse and G.A. Hedlund, Symbolic dynamics II – Sturmian trajectories. Am. J. Math. 62 (1940) 1–42. | DOI | JFM | MR

[26] V.I. Oseledec, The spectrum of ergodic automorphisms. Doklady Akademii Nauk SSSR 168 (1966) 1009–1011. | MR | Zbl

[27] E. Pelantová and Š. Starosta, Constructions of words rich in palindromes and pseudopalindromes. Discr. Math. Theor. Comput. Sci. 18 (2016). | MR | Zbl

[28] M. Queffélec, Substitution dynamical systems – spectral analysis. Vol. 1294 of Lecture Notes in Math. Springer, Berlin (1987). | MR | Zbl

[29] G. Rauzy, Echanges d’intervalles et transformations induites. Acta Arith. 34 (1979) 315–328. | DOI | MR | Zbl

[30] G. Rote, Sequences with subword complexity 2n. J. Number Theory 46 (1994) 196–213. | DOI | MR | Zbl

[31] L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263–275. | DOI | MR | Zbl

[32] L. Vuillon, On the number of return words in infinite words with complexity 2n + 1. Pure Math. Appl. 18 (2007) 345–355. | MR | Zbl

Cité par Sources :