Article (Scientific journals)
Computing the k-binomial complexity of the Thue–Morse word
Lejeune, Marie; Leroy, Julien; Rigo, Michel
2020In Journal of Combinatorial Theory. Series A, 176
Peer Reviewed verified by ORBi
 

Files


Full Text
binomial-TM-lastVersion.pdf
Author preprint (439.73 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[en] Two words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both the abelian equivalence and the Simon congruence. The k-binomial complexity of an infinite word x maps the integer n to the number of classes in the quotient, by this k-binomial equivalence relation, of the set of factors of length n occurring in x. This complexity measure has not been investigation very much. In this paper, we characterize the k-binomial complexity of the Thue–Morse word. The result is striking, compared to more familiar complexity functions. Although the Thue–Morse word is aperiodic, its k-binomial complexity eventually takes only two values. In this paper, we first express the number of occurrences of subwords appearing in iterates of the form Ψ^l(w) for an arbitrary morphism Ψ. We also thoroughly describe the factors of the Thue–Morse word by introducing a relevant new equivalence relation.
Disciplines :
Mathematics
Author, co-author :
Lejeune, Marie ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Leroy, Julien ;  Université de Liège - ULiège > Département de mathématique > Département de mathématique
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Computing the k-binomial complexity of the Thue–Morse word
Publication date :
2020
Journal title :
Journal of Combinatorial Theory. Series A
ISSN :
0097-3165
Publisher :
Elsevier, Atlanta, Georgia
Volume :
176
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 27 March 2019

Statistics


Number of views
114 (19 by ULiège)
Number of downloads
71 (3 by ULiège)

Scopus citations®
 
8
Scopus citations®
without self-citations
5
OpenCitations
 
4

Bibliography


Similar publications



Contact ORBi