l-abelian complexity; combinatorics on words; automatic sequences; regular sequences
Abstract :
[en] We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue--Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular.
Jean-Paul Allouche and Je_rey Shallit, The ring of k-regular sequences, Theoretical Computer Science 98 (1992), 163-197.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences II, Theoretical Computer Science 307 (2003), 3-29.
Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, Cambridge, 2003.
Jean Berstel and Christophe Reutenauer, Noncommutative rational series with applications, Encyclopedia of Mathematics and its Applications, 137, Cambridge University Press, Cambridge, 2011.
Francine Blanchet-Sadri, James D. Currie, Narad Rampersad and Nathan Fox, Abelian complexity of fixed point of morphism 0→012; 1→02; 2→1, INTE- GERS 14 (2014) #A11.
Carpi, Arturo and D'Alonzo, Valerio, On factors of synchronized sequences, Theo- retical Computer Science, 411 (2010), 3932-3937.
Émilie Charlier, Narad Rampersad and Jeffrey Shallit, Enumeration and decidable properties of automatic sequences, Internat. J. Found. Comput. Sci. 23 (2012), no. 5, 1035-1066.
Alan Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 186-192.
Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974.
Anna Frid, On uniform DOL words, STACS'98, Lecture Notes in Computer Science, 1373 (1998), 544-554.
Florian Greinecker, On the 2-abelian complexity of Thue-Morse subwords, arXiv:1404.3906.
Juhani Karhumäki, Generalized Parikh mappings and homomorphisms, Information and Control 47 (1980), 155-165.
Juhani Karhumaki, Aleksi Saarela and Luca Q. Zamboni, On a generalization of Abelian equivalence and complexity of infinite words, J. Combin. Theory Ser. A 120 (2013), no. 8, 2189-2206.
Juhani Karhumaki, Aleksi Saarela and Luca Q. Zamboni, Variations of the Morse{Hedlund theorem for k-abelian equivalence, DLT 2014, Lecture Notes in Computer Science 8633 (2014), 203-214.
Blake Madill and Narad Rampersad, The abelian complexity of the paperfolding word, Discrete Math. 313 (2013), no. 7, 831-838.
The OEIS Foundation, The On-Line Encyclopedia of Integer Sequences, http:// oeis.org.
Michel Rigo and Élise Vandomme, 2-abelian complexity of the Thue-Morse sequence, http://hdl.handle.net/2268/135841, 2012.
