Unpublished conference/Abstract (Scientific congresses and symposiums)
A conjecture on the 2-abelian complexity of the Thue-Morse word
Rigo, Michel; Parreau, Aline; Vandomme, Elise
2014Representing Streams II
 

Files


Full Text
Vandomme_RepStreams2014.pdf
Author preprint (304.55 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
complexity; infinite word; abelian equivalence
Abstract :
[en] The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k-abelian complexity is a generalization of the abelian complexity, corresponding to the case where k=1. Formally, two words u and v of the same length are k-abelian equivalent if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The aim of this talk is to study the 2-abelian complexity a(n) of the Thue-Morse word. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a work of Madill and Rampersad (2012) where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will present some arguments supporting our conjecture. They are based on functions counting some subword of length 2 occuring in prefixes of the Thue-Morse word.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Parreau, Aline ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Vandomme, Elise  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
A conjecture on the 2-abelian complexity of the Thue-Morse word
Publication date :
20 January 2014
Event name :
Representing Streams II
Event organizer :
J. Endrullis, H. Hvid Hansen, D. Hendriks, C. Kalle, E. Verbitskiy
Event place :
Leiden, Netherlands
Event date :
from 20-01-2014 to 31-01-2014
Audience :
International
Available on ORBi :
since 05 February 2014

Statistics


Number of views
124 (24 by ULiège)
Number of downloads
88 (9 by ULiège)

Bibliography


Similar publications



Sorry the service is unavailable at the moment. Please try again later.
Contact ORBi