Templates for the k-binomial complexity of the Tribonacci word

[en] Consider k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word 𝐱 maps the integer n to the number of pairwise non-equivalent factors of length n occurring in 𝐱. In this paper based on the notion of template introduced by Currie et al., we show that, for all 𝑘≥2, the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity 𝑝(𝑛)=2𝑛+1. A similar result was already known for Sturmian words, but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci.

Disciplines :

Mathematics

Author, co-author :

Lejeune, Marie ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Rosenfeld, Matthieu

Language :

English

Title :

Templates for the k-binomial complexity of the Tribonacci word

Publication date :

September 2019

Event name :

WORDS 2019 : Combinatorics on Words

Event date :

du 09 septembre 2019 au 13 septembre 2019

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer

Volume :

11682

Pages :

238-250

Peer reviewed :

Peer reviewed

Available on ORBi :

since 07 October 2019

Statistics

Number of views

61 (15 by ULiège)

Number of downloads

76 (8 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Aberkane, A., Currie, J.: A cyclic binary morphism avoiding abelian fourth powers. Theoret. Comput. Sci. 410, 44–52 (2009)
Aberkane, A., Currie, J., Rampersad, N.: The number of ternary words avoiding abelian cubes grows exponentially. J. Integer Seq. 7 (2004). Article 04.2.7
Allouche, J.-P., Shallit, J.: Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003)
Berthé, V., Rigo, M. (eds.): Combinatorics, Automata and Number Theory. Encyclopedia Mathematics Applications, vol. 135. Cambridge University Press, Cambridge (2010)
Cassaigne, J., Currie, J., Schaeffer, L., Shallit, J.: Avoiding three consecutive blocks of the same size and same sum. J. ACM 61(2) (2014). Art. 10
Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding Abelian powers in binary words with bounded Abelian complexity. Int. J. Found. Comput. Sci. 22, 905–920 (2011)
Currie, J., Rampersad, N.: Recurrent words with constant Abelian complexity. Adv. Appl. Math. 47, 116–124 (2011)
Currie, J., Rampersad, N.: Fixed points avoiding Abelian k-powers. J. Combin. Theory Ser. A 119, 942–948 (2012)
Karhumäki, J., Saarela, A., Zamboni, L.Q.: On a generalization of Abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A 120, 2189–2206 (2013)
Karhumäki, J., Saarela, A., Zamboni, L.Q.: Variations of the Morse-Hedlund theorem for k-Abelian equivalence. In: Shur, A.M., Volkov, M.V. (eds.) DLT 2014. LNCS, vol. 8633, pp. 203–214. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09698-8 18
Lejeune, M., Leroy, J., Rigo, M.: Computing the k-binomial complexity of the Thue-Morse word, 34 p. arXiv:1812.07330
Lejeune, M., Rigo, M., Rosenfeld, M.: Templates for the k-binomial complexity of the Tribonacci word (long version), 23 p. http://hdl.handle.net/2268/234215
Liétard, F.: Avoiding additive powers, talk at Mons TCS days, Bordeaux, 10–14 September 2018
Rao, M., Rigo, M., Salimov, P.: Avoiding 2-binomial squares and cubes. Theoret. Comput. Sci. 572, 83–91 (2015)
Rao, M., Rosenfeld, M.: Avoiding two consecutive blocks of same size and same sum over Z2. SIAM J. Disc. Math. 32(4), 2381–2397 (2018)
Richomme, G., Saari, K., Zamboni, L.Q.: Balance and Abelian complexity of the Tribonacci word. Adv. Appl. Math. 45, 212–231 (2010)
Rigo, M., Salimov, P.: Another generalization of abelian equivalence: binomial complexity of infinite words. Theoret. Comput. Sci. 601, 47–57 (2015)
Rigo, M.: Invited talk. Streams II, Lorentz Center, Leiden, January 2014
Rigo, M.: Relations on words. Indag. Math. (N.S.) 28, 183–204 (2017)