A new approach to the 2-regularity of the -abelian complexity of 2-automatic sequences

zbMATH Open1317.68138arXiv1405.3532MaRDI QIDQ2256124FDOQ2256124

Authors: Aline Parreau, Michel Rigo, Élise Vandomme, Eric Rowland 

Publication date: 19 February 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that a sequence satisfying a certain symmetry property is $2$-regular in the sense of Allouche and Shallit, i.e., the $mathbbZ$-module generated by its $2$-kernel is finitely generated. We apply this theorem to develop a general approach for studying the $ell$-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.

Full work available at URL: https://arxiv.org/abs/1405.3532

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the 2-abelian complexity of the Thue-Morse word
• On the abelian complexity of generalized Thue-Morse sequences
• On the additive complexity of a Thue-Morse-like sequence
• Abelian complexity and synchronization
• On the abelian complexity of the Rudin-Shapiro sequence

zbMATH Keywords

automatic sequencesregular sequencesThue-Morse wordabelian complexityperiod-doubling word

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15) Automata sequences (11B85)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• The ring of \(k\)-regular sequences
• Title not available (Why is that?)
• Automatic Sequences
• Uniform tag sequences
• The ring of \(k\)-regular sequences. II.
• Noncommutative rational series with applications
• Variations of the Morse-Hedlund theorem for \(k\)-abelian equivalence
• Generalized Parikh mappings and homomorphisms
• On a generalization of abelian equivalence and complexity of infinite words
• On factors of synchronized sequences
• The abelian complexity of the paperfolding word
• Enumeration and decidable properties of automatic sequences
• On the 2-abelian complexity of the Thue-Morse word
• Abelian complexity of fixed point of morphism \(0 \mapsto 012, 1 \mapsto 02, 2 \mapsto 1\)
• Syntactic complexity of ultimately periodic sets of integers

Cited In (10)

• Computing abelian complexity of binary uniform morphic words
• On growth and fluctuation of \(k\)-abelian complexity
• Counting the number of non-zero coefficients in rows of generalized Pascal triangles
• On the 2-abelian complexity of the Thue-Morse word
• Relations on words
• On the \(k\)-abelian complexity of the Cantor sequence
• On the 2-abelian complexity of generalized Cantor sequences
• Automaticity and Parikh-Collinear Morphisms
• On growth and fluctuation of \(k\)-abelian complexity
• Abelian combinatorics on words: a survey

Uses Software

• OEIS

This page was built for publication: A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256124)