Abelian Complexity and Synchronization

Abstract

We present a general method for computing the abelian complexity ${\rho }_{\mathbf{s}}^{\mathrm{ab}}(n)$ of an automatic sequence $\mathbf{s}$ in the case where (a) ${\rho }_{\mathbf{s}}^{\mathrm{ab}}(n)$ is bounded by a constant and (b) the Parikh vectors of the length-$n$ prefixes of $\mathbf{s}$ form a synchronized sequence. We illustrate the idea in detail, using the free software Walnut to compute the abelian complexity of the Tribonacci word $\mathbf{TR}=0102010\cdots$, the fixed point of the morphism $0\to 01$, $1\to 02$, $2\to 0$. 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.

References in corpus (2)

• Abelian complexity and Abelian co-decomposition
• Enumeration and Decidable Properties of Automatic Sequences

Cited by in corpus (1)

• Abelian Combinatorics on Words: a Survey