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

abelian complexityautomatic sequencesperiod-doubling wordregular sequencesThue-Morse word

Mathematics Subject Classification ID

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

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.

Review text

Summary: We prove that a sequence satisfying a certain symmetry property is \(2\)-regular in the sense of Allouche and Shallit, i.e., the \(\mathbb{Z}\)-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

• Abelian complexity of fixed point of morphism 0 012, 1 02, 2 1
• Automatic Sequences
• Enumeration and decidable properties of automatic sequences
• Generalized Parikh mappings and homomorphisms
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• 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 abelian complexity of the paperfolding word
• The On-Line Encyclopedia of Integer Sequences
• 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

(12)

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

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)