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.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.