Abelian complexity and synchronization

MaRDI QIDQ4987418zbMATH OpenFDO

Authors Jeffrey Shallit

Publication date 3 May 2021

Full work available at URL https://arxiv.org/abs/2011.00453, http://math.colgate.edu/~integers/v36/v36.pdf

zbMATH Keywords

Abelian complexityautomatic sequencesynchronizationTribonacci sequence

Mathematics Subject Classification ID

Automata sequences (11B85) Combinatorics on words (68R15)

Abstract: We present a general method for computing the abelian complexity $$ of an automatic sequence $$ in the case where (a) $$ is bounded by a constant and (b) the Parikh vectors of the length-$n$ prefixes of $$ form a synchronized sequence. We illustrate the idea in detail, using the free software Walnut to compute the abelian complexity of the Tribonacci word $$, the fixed point of the morphism $0ightarrow01$, $1ightarrow02$, $2ightarrow0$. Previously, Richomme, Saari, and Zamboni showed that the abelian complexity of this word lies in $3,4,5,6,7$, and Turek gave a Tribonacci automaton computing it. We are able to "automatically" rederive these results, and more, using the method presented here.

Recommendations

• Abelian complexity function of the Tribonacci word
• Computing abelian complexity of binary uniform morphic words
• Abelian complexity and abelian co-decomposition
• Subword complexity and k-synchronization
• Abelian properties of Parry words

Cites work

• Abelian complexity and abelian co-decomposition
• Abelian complexity function of the Tribonacci word
• Abelian complexity of minimal subshifts
• Abelian complexity of Thue-Morse word over a ternary alphabet
• Automatic Sequences
• Balance and abelian complexity of the Tribonacci word
• Circular critical exponents for Thue-Morse factors
• Combinatorial, ergodic and arithmetic properties of the Tribonacci substitution
• Enumeration and decidable properties of automatic sequences
• scientific article; zbMATH DE number 3986648 (Why is no real title available?)
• scientific article; zbMATH DE number 4112682 (Why is no real title available?)
• scientific article; zbMATH DE number 2152304 (Why is no real title available?)
• Mechanical proofs of properties of the Tribonacci word
• On synchronized sequences and their separators
• Queens in exile: non-attacking queens on infinite chess boards
• Subword complexity and k-synchronization
• The Tribonacci substitution

Cited in

(14)

• On the k-abelian complexity of the Cantor sequence
• Synchronized sequences
• On the boundary sequence of an automatic sequence
• A new approach to the 2-regularity of the \(\ell\)-abelian complexity of 2-automatic sequences
• On factors of synchronized sequences
• Abelian properties of Parry words
• Abelian complexity function of the Tribonacci word
• Subword complexity and k-synchronization
• Properties of a ternary infinite word
• Abelian combinatorics on words: a survey
• Minimal Complexities for Infinite Words Written with d Letters
• Automaticity and Parikh-Collinear Morphisms
• Automatic abelian complexities of Parikh-collinear fixed points
• Additive word complexity and \texttt{Walnut}

Describes a project that uses

Uses Software

• Walnut
• GitHub

This page was built for publication: Abelian complexity and synchronization

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