On non-repetitive complexity of Arnoux–Rauzy words

Arnoux–Rauzy word; Directive sequence; Factor complexity; Non-repetitivity; Combinatorial mathematics; Infinite word; Return words; Mathematical techniques

Abstract :

[en] The non-repetitive complexity nrCu and the initial non-repetitive complexity inrCu are functions which reflect the structure of the infinite word u with respect to the repetitions of factors of a given length. We determine nrCu for the Arnoux–Rauzy words and inrCu for the standard Arnoux–Rauzy words. Our main tools are the S-adic representation of Arnoux–Rauzy words and a description of return words to their factors. The formulas we obtain are then used to evaluate nrCu and inrCu for the d-bonacci word. © 2020 Elsevier B.V.

Disciplines :

Mathematics

Author, co-author :

Medková, K.; Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2, 120 00, Czech Republic

Pelantová, E.; Department of Mathematics, FNSPE, Czech Technical University in Prague, Trojanova 13, Praha 2, 120 00, Czech Republic

Vandomme, Elise ; Université de Liège - ULiège

Language :

English

Title :

On non-repetitive complexity of Arnoux–Rauzy words

Publication date :

2020

Journal title :

Discrete Applied Mathematics

ISSN :

0166-218X

eISSN :

1872-6771

Publisher :

Elsevier, Amsterdam, Netherlands

Volume :

285

Pages :

423-433

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 27 August 2021

Statistics

Number of views

51 (5 by ULiège)

Number of downloads

1 (1 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Arnoux, P., Rauzy, G., Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119:2 (1991), 199–215.
Balková, L’., Pelantová, E., Starosta, Š., Sturmian jungle (or garden?) on multiliteral alphabets. RAIRO Theor. Inform. Appl. 44 (2010), 443–470.
Berthé, V., Cassaigne, J., Steiner, W., Balance properties of Arnoux–Rauzy words. Int. J. Algebra Comput. 23:04 (2013), 689–703.
Berthé, V., De Felice, C., Dolce, F., Leroy, J., Perrin, D., Reutenauer, Ch., Rindone, G., Acyclic, connected and tree sets. Monatsh. Math., 176(4), 2015.
Berthé, V., Dolce, F., Durand, F., Leroy, J., Perrin, D., Rigidity and substitutive dendric words. Int. J. Found. Comput. Sci. 29 (2018), 705–720.
Bugeaud, Y., Kim, D.H., A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers. Trans. Amer. Math. Soc. 371 (2019), 3281–3308.
Cassaigne, J., Limit values of the recurrence quotient of Sturmian sequences. Theoret. Comput. Sci. 218 (1999), 3–12.
Cassaigne, J., Chekhova, N., Fonctions de récurrence des suites d’ Arnoux–Rauzy et réponsé à une question de Morse et Hedlund. Ann. Inst. Fourier 56:7 (2006), 2249–2270.
Glen, A., Justin, J., Episturmian words: a survey. Theor. Inform. Appl. 43:3 (2009), 403–442.
Justin, J., Pirillo, G., Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276 (2002), 281–313.
Justin, J., Vuillon, L., Return words in Sturmian and episturmian words. RAIRO Theor. Inf. Appl. 34 (2000), 343–356.
Medková, K., Derived sequences of Arnoux–Rauzy sequences. Mercas, R., Reidenbach, D., (eds.) Proceedings WORDS 2019 Lecture Notes in Computer Science, vol. 11682, 2019, Springer, 251–263.
Moothathu, T.K.S., Eulerian entropy and non-repetitivity subword complexity. Theoret. Comput. Sci. 420 (2012), 80–88.
Morse, M., Hedlund, G.A., Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 61 (1940), 1–42.
Nicholson, J., Rampersad, N., Initial non-repetitivity complexity of infinite words. Discrete Appl. Math. 208:C (2016), 114–122.
Pytheas Fogg, N., Substitutions in Dynamics Arithmetics and Combinatorics Lecture Notes in Math., vol. 1794, 2002, Springer-Verlag.
Risley, R.N., Zamboni, L.Q., A generalization of Sturmian sequences: Combinatorial structure and transcendence. Acta Arith. 95 (2000), 167–184.