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

MaRDI QIDQ2256124zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1405.3532, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p27

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

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)

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.

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

Cites work

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

Cited in

(10)

• Abelian combinatorics on words: a survey
• 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

Describes a project that uses

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)