Reference : 2-abelian complexity of the Thue-Morse sequence
Scientific conferences in universities or research centers : Scientific conference in universities or research centers
Physical, chemical, mathematical & earth Sciences : Mathematics
2-abelian complexity of the Thue-Morse sequence
Rigo, Michel mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Vandomme, Elise mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Representing Streams
from 10-12-2012 to 14-12-2012
W. Bosma, R. Fokkink, J. W. Klop, C. Kraaikamp, J. Rutten, R. Tijdeman
The Netherlands
[en] complexity ; infinite word ; abelian equivalence
[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.

File(s) associated to this reference

Fulltext file(s):

Open access
Rigo.pdfAuthor preprint375.03 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.