Back to Search
Start Over
Abelian Complexity and Synchronization
- Publication Year :
- 2020
-
Abstract
- We present a general method for computing the abelian complexity $\rho^{\rm ab}_{\bf s} (n)$ of an automatic sequence $\bf s$ in the case where (a) $\rho^{\rm ab}_{\bf s} (n)$ is bounded by a constant and (b) the Parikh vectors of the length-$n$ prefixes of $\bf 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 ${\bf TR} = 0102010\cdots$, the fixed point of the morphism $0 \rightarrow 01$, $1 \rightarrow 02$, $2 \rightarrow 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.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2011.00453
- Document Type :
- Working Paper