Scientific conference in universities or research centers (Scientific conferences in universities or research centers)
2-abelian complexity of the Thue-Morse sequence
Rigo, Michel; Vandomme, Elise
2012
 

Files


Full Text
Rigo.pdf
Author preprint (384.03 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
complexity; infinite word; abelian equivalence
Abstract :
[en] Let k be an integer. 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 Thue-Morse word is a well-known and extensively studied 2-automatic sequence. It is trivially abelian periodic and its (1)-abelian complexity takes only two values. The aim of this talk is to explain how to compute the 2-abelian complexity a(n) of the Thue-Morse word, showing in particular that it is unbounded. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a recent work of Madill and Rampersad where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will also explain why the usual logical framework introduced by Büchi and popularized by Bruyère (indeed, automatic sequences can be characterized in an extension of the Presburger arithmetic) and the recent work of Charlier et al. about "automatic theorem-proving" of properties of automatic sequences cannot be applied to these questions related to abelian complexity.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  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 :
2-abelian complexity of the Thue-Morse sequence
Publication date :
14 December 2012
Event name :
Representing Streams
Event organizer :
W. Bosma, R. Fokkink, J. W. Klop, C. Kraaikamp, J. Rutten, R. Tijdeman
Event place :
Leiden, Netherlands
Event date :
from 10-12-2012 to 14-12-2012
Audience :
International
Available on ORBi :
since 06 December 2012

Statistics


Number of views
240 (48 by ULiège)
Number of downloads
170 (29 by ULiège)

Bibliography


Similar publications



Contact ORBi