Paper published in a journal (Scientific congresses and symposiums)
Computing the k-binomial complextiy of the Thue-Morse word
Lejeune, Marie; Leroy, Julien; Rigo, Michel
2019In Lecture Notes in Computer Science, 11647, p. 278-291
Peer reviewed
 

Files


Full Text
binomialDLT.pdf
Author preprint (507.99 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Combinatorics on words; Thue-Morse words; Binomial complexity
Abstract :
[en] Two finite 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 abelian equivalence and the Simon congruence. The k-binomial complexity of an infinite word 𝐱 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 𝐱. This complexity measure has not been investigated 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 𝛹^ℓ(𝑤) for an arbitrary morphism 𝛹. We also thoroughly describe the factors of the Thue–Morse word by introducing a relevant new equivalence relation.
Disciplines :
Mathematics
Computer science
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 complextiy of the Thue-Morse word
Publication date :
2019
Event name :
Developments in Language Theory
Event place :
Warsaw, Poland
Event date :
August 5–9, 2019
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Germany
Special issue title :
Developments in Language Theory: 23rd International Conference, DLT 2019
Volume :
11647
Pages :
278-291
Peer reviewed :
Peer reviewed
Available on ORBi :
since 13 August 2019

Statistics


Number of views
65 (16 by ULiège)
Number of downloads
77 (12 by ULiège)

Scopus citations®
 
7
Scopus citations®
without self-citations
6
OpenCitations
 
5

Bibliography


Similar publications



Contact ORBi