\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{algorithmicx} \usepackage{algpseudocode} \usepackage{tikz} \usetikzlibrary{automata,positioning} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Abelian Complexity Function of the \\ \vskip .11in Tribonacci Word } \vskip 1cm \large Ond\v{r}ej~Turek \\ Nuclear Physics Institute \\ Academy of Sciences of the Czech Republic \\ 250 68 \v{R}e\v{z} \\ Czech Republic \\ and \\ Bogolyubov Laboratory of Theoretical Physics \\ Joint Institute for Nuclear Research \\ 141980 Dubna \\ Russia \\ \href{mailto:o.turek@ujf.cas.cz}{\tt o.turek@ujf.cas.cz} \\ \end{center} \vskip .2 in \def\N{\mathbb N} \def\A{\mathcal A} \def\Codec{\mathrm{Dec}} \def\Z{\mathcal Z} \def\D{\mathcal D} \def\P{\mathcal P} \def\u{\mathbf u} \def\t{\mathbf t} \def\q{\mathbf q} \def\Prel{\mathcal{P}^{\mathrm{rel}}} \def\AC{\rho^{\mathrm{ab}}} \def\Vect{\mathrm{Vect}} \begin{abstract} According to a result of Richomme, Saari and Zamboni, the abelian complexity of the Tribonacci word satisfies $\rho^{\mathrm{ab}}(n)\in\{3,4,5,6,7\}$ for each $n\in\mathbb{N}$. In this paper we derive an automaton that evaluates the function $\rho^{\mathrm{ab}}(n)$ explicitly. The automaton takes the Tribonacci representation of $n$ as its input; therefore, $(\rho^{\mathrm{ab}}(n))_{n\in\N}$ is an automatic sequence in a generalized sense. Since our evaluation of $\rho^{\mathrm{ab}}(n)$ uses $\mathcal{O}(\log n)$ operations, it is fast even for large values of $n$. Our result also leads to a solution of an open problem proposed by Richomme et al. concerning the characterization of those $n$ for which $\rho^{\mathrm{ab}}(n)=c$ with $c$ belonging to $\{4,5,6,7\}$. In addition, we apply the same approach on the $4$-bonacci word. In this way we find a description of the abelian complexity of the $4$-bonacci word, too. \end{abstract} \section{Introduction} The {\it abelian complexity\/} of a word $\u$ is a function $\N\to\N$ that counts the number of pairwise non-abelian-equivalent factors of $\u$ of length $n$. The term was introduced by Richomme, Saari and Zamboni \cite{RSZ} in 2009, and since then it has been extensively studied~\cite{ABJS,BBT,CRSZ,CR,MR,Tu2,Tu13}. In one of the first papers on the subject, Richomme, Saari and Zamboni~\cite{RSZ2} examined the Tribonacci word $\t$ \seqnum{A080843}, which is the fixed point of the substitution $0\mapsto01$, $1\mapsto02$, $2\mapsto0$, and they showed that $\AC_\t(n)\in\{3,4,5,6,7\}$ for all $n$. They also characterized those $n$ for which $\AC_\t(n)=3$, and proposed the following open problem: {\it for each $c\in\{4,5,6,7\}$, characterize those $n$ for which $\AC_\t(n)=c$}. Explicit characterization of $\AC_\u(n)$ of a given infinite word $\u$ is generally a difficult task, particularly in case of words defined over alphabets consisting of more than two letters. For example, despite the fact that a recurrent word over a ternary alphabet with constant abelian complexity equal to $3$ for all $n\in\N$ has been already constructed~\cite{RSZ}, there seems to be no other nontrivial example to date of a recurrent $m$-ary word with $m\geq3$ whose abelian complexity function has been precisely determined. In particular, the problem of precise characterization of the abelian complexity $\AC_\t(n)$ of the Tribonacci word $\t$, which is a ternary word, has remained open since 2009. Recently Mousavi and Shallit~\cite{MS} showed that many properties of the Tribonacci word, such as the aperiodicity, powers, palindromes etc., could be examined purely mechanically with the help of finite automata. Although in principle their method could also be used for the study of the characteristics of the abelian complexity function of the Tribonacci word, it turns out to be not computationally feasible. In this paper we propose a related method that is particularly designed for dealing with abelian properties (primarily with abelian complexity and the balance properties). Our approach is less general than the one of Mousavi and Shallit, but it is efficient enough to explicitly obtain a finite automaton that computes the function $\AC_\t(n)$. The automaton in question features a very small set of states, consisting of less than $70$ elements. Consequently, it can be easily implemented on any computer (a powerful machine is not needed), and the calculation can be even performed by hand. The automaton takes the Tribonacci representation of $n$ as its input, which means that the sequence $(\AC_t(n))_{n\in\N}$ \seqnum{A216190} is $T$-automatic (or ``Tribonacci-automatic'') in the sense of Shallit~\cite{AS,Sh88}. Our approach relies on the technique of abelian co-decomposition~\cite{Tu13}, which was originally developed as a tool for proving that the abelian complexity of a recurrent word attains a certain value infinitely often. As a result, our construction of the automaton can be generalized to certain other words as well. The paper is organized as follows. In Section~\ref{Sect.Preliminaries} we provide the necessary notation related to abelian complexity, the Tribonacci word and finite automata. Section~\ref{Sect.Codecomposition} summarizes basic facts about abelian co-decomposition. Section~\ref{Sect.Z} contains the core of the paper: we show that there exists a finite number of sets $\Z_1,\ldots,\Z_M$ such that each $n\in\N$ can be associated with a certain $\Z_q$ via the Tribonacci representation of $n$. Since each of those sets is related to a certain value of the abelian complexity, the indices $1,\ldots,M$ can be regarded as states of a finite automaton that evaluates $\AC_\t(n)$. Section~\ref{Sect.Range} is devoted to the first and easy application of the findings from Section~\ref{Sect.Z}: we demonstrate that the abelian complexity of the Tribonacci word takes values in $\{3,4,5,6,7\}$. Although this fact is already known~\cite{RSZ2}, it illustrates the applicability of our approach. The main result of the paper is presented in Section~\ref{Sect.Eval.AC}. We derive a formula for evaluating the abelian complexity of the Tribonacci word on the basis of results of Section~\ref{Sect.Z}. In particular, we show that the abelian complexity can be calculated by a finite automaton with $278$ states. This result is further improved in Section~\ref{Sect.Simplified}, where the size of the automaton is reduced from $278$ to $68$ states. It is easy to transform this automaton into an automaton that decides, for any $n\in\N$, whether $\AC_\t(n)$ attains a given value $c\in\{3,4,5,6,7\}$, which provides a solution of the problem of Richomme et al. In Section~\ref{Sect.mbon}, we demonstrate that the method allows one to examine the abelian complexity function of other $m$-bonacci words. In particular, we present results on the $4$-bonacci word; they show that the abelian complexity of $m$-bonacci words gains new properties when $m$ exceeds $3$. The paper is concluded by Section~\ref{Sect.Conclusions}, in which we discuss other applications and generalizations of the method. \section{Preliminaries}\label{Sect.Preliminaries} Let us consider a set $\A=\{0,1,2,\ldots,m-1\}$ (\emph{alphabet}) consisting of $m$ symbols (\emph{letters}) $0,1,\ldots,m-1$. Concatenations of letters from $\A$ are called \emph{words}. Let $\A^*$ denote the free monoid of all finite words over $\A$ including the empty word $\varepsilon$. The \emph{length} of a word $w=w_0w_1w_2\cdots w_{n-1}\in\A^*$ is the number of its letters, $|w|=n$. The symbol $|w|_\ell$ for $\ell\in\A$ and $w\in\A^*$ stands for the number of occurrences of the letter $\ell$ in the word $w$. The set of all infinite words over $\A$ is denoted by $\A^\N$. We say that an infinite word $\u$ is \emph{recurrent} if every factor of $\u$ occurs infinitely many times in $\u$. A finite word $w$ is a \emph{factor} of a (finite or infinite) word $\u$ if there exists a finite word $x$ and a (finite or infinite, respectively) word $y$ such that $\u=xwy$. If $x=\varepsilon$, the factor $w$ is called a \emph{prefix} of $\u$. For any word $w\in\A^*$ and $k\in\N$ we write $w^k=\overbrace{ww\cdots w}^{k \text{ times}}$. Similarly, we set $w^0=\varepsilon$. If a word $v\in\A^\N$ has the prefix $w^k$ for $k\in\N$, then the symbol $w^{-k}v$ stands for the word satisfying $w^kw^{-k}v=v$. The \emph{Parikh vector} of $w$ is the $m$-tuple $\Psi(w)=(|w|_0,|w|_1,\ldots,|w|_{m-1})$; note that $|w|_0+|w|_1+\cdots+|w|_{m-1}=|w|$. For any given infinite word $\u$, let $\mathcal{P}_\u(n)$ denote the set of all Parikh vectors corresponding to factors of $\u$ having the length $n$, i.e., $$ \mathcal{P}_\u(n)=\left\{\Psi(w)\,\left|\,\text{$w$ is a factor of $\u$}, |w|=n\right.\right\}. $$ The \emph{abelian complexity} of a word $\u$ is the function $\AC_\u:\N\to\N$ defined as \begin{equation}\label{AC} \AC_\u(n)=\#\P_\u(n), \end{equation} where $\#$ denotes the cardinality. It is useful to introduce the \emph{relative Parikh vector}~\cite{Tu13}, which is defined for any factor $w$ of $\u$ of length $n$ as $$ {\Psi}_\u^\mathrm{rel}(w)=\Psi(w)-\Psi(\u_{[n]})\,, $$ where $\u_{[n]}$ is the prefix of $\u$ of length $n$. Since the subtrahend $\Psi(\u_{[n]})$ depends only on the length of $w$ and not on $w$ itself, the set of relative Parikh vectors corresponding to the length $n$, $$ \Prel_\u(n):=\left\{\left.{\Psi}_\u^\mathrm{rel}(w)\;\right|\;\text{$w$ is a factor of $\u$}, |w|=n\right\}, $$ has the same cardinality as $\P_\u(n)$. Hence we obtain, with regard to~\eqref{AC}, \begin{equation}\label{ACrel} \AC_\u(n)=\#\Prel_\u(n)\,. \end{equation} An infinite word $\u$ is said to be \emph{$b$-balanced} for a certain $b\in\N$ if for every $\ell\in\A$ and for every pair of factors $v$, $w$ of $\u$ such that $|v|=|w|$, the inequality $\left||v|_\ell-|w|_\ell\right|\leq b$ holds. If $\u$ is a $b$-balanced word, the components of relative Parikh vectors are bounded by $b$~\cite{Tu13}. Therefore, the set of all relative Parikh vectors $\bigcup_{n\in\N}\Prel_\u(n)$ is finite for any $b$-balanced word $\u$. This paper is primarily concerned with the \emph{Tribonacci word} $\t$, which is defined over the alphabet $\A=\{0,1,2\}$ as the fixed point of the substitution \begin{equation}\label{Trib.subst} \begin{array}{lccl} \varphi_\t: & 0 & \mapsto & 01 \\ & 1 & \mapsto & 02 \\ & 2 & \mapsto & 0 \end{array} \end{equation} i.e., $$ \t=\lim_{k\to\infty}\varphi_\t^k(0)=01020100102010102010010201020100102010102010\cdots\,. $$ It is easy to check that $\varphi_\t^{j}(0)=\varphi_\t^{j-1}(0)\varphi_\t^{j-2}(0)\varphi_\t^{j-3}(0)$ for every $j\geq3$. Hence, the lengths of factors $\varphi_\t^{j}(0)$ satisfy the recurrence relation $|\varphi_\t^{j}(0)|=|\varphi_\t^{j-1}(0)|+|\varphi_\t^{j-2}(0)|+|\varphi_\t^{j-3}(0)|$. Comparing this relation with the Tribonacci recurrence relation $T_j=T_{j-1}+T_{j-2}+T_{j-3}$, we conclude that $|\varphi_\t^j(0)|=T_{j+3}$ for every $j\in\N\cup\{0\}$, where $\left(T_j\right)_{j\geq0}=(0,0,1,1,2,4,7,\ldots)$ is the sequence of Tribonacci numbers \seqnum{A000073}. Any $n\in\N$ can be written as a sum of Tribonacci numbers with binary coefficients, \begin{equation}\label{TribExp} n=\sum_{j=0}^{k} d_j T_{j+3} \qquad \text{for}\quad d_j\in\{0,1\},\; k\in\N\cup\{0\}\,. \end{equation} If coefficients $d_j\in\{0,1\}$ are obtained by the greedy algorithm, they form the \emph{normal $T$-representation} (also called the \emph{Tribonacci representation}) of $n$, which we denote by the symbol $\langle n \rangle_T$: \begin{equation}\label{Trep} \langle n \rangle_T=d_k d_{k-1}\cdots d_1d_0\,. \end{equation} For $n=0$, we have $\langle 0 \rangle_T=\varepsilon$. Table~\ref{T expansions} shows normal $T$-representations of several small integers. \begin{table} \begin{center} \begin{tabular}{|c|r||c|r||c|r||c|r||c|r|} \hline $n$ & $\langle n \rangle_T$ & $n$ & $\langle n \rangle_T$ & $n$ & $\langle n \rangle_T$ & $n$ & $\langle n \rangle_T$ & $n$ & $\langle n \rangle_T$ \\ \hline $1$ & $1$ & $4$ & $100$ & $7$ & $1000$ & $10$ & $1011$ & $13$ & $10000$ \\ $2$ & $10$ & $5$ & $101$ & $8$ & $1001$ & $11$ & $1100$ & $14$ & $10001$ \\ $3$ & $11$ & $6$ & $110$ & $9$ & $1010$ & $12$ & $1101$ & $15$ & $10010$ \\ \hline \end{tabular} \end{center} \caption{Normal $T$-representations of the numbers $1,\ldots,15$.} \label{T expansions} \end{table} The constant $k$ in expansion~\eqref{Trep} does not need to be chosen minimal, i.e., a normal $T$-representation can start with a block of zeros. For example, the representations $\langle n \rangle_T=011$ and $\langle n \rangle_T=00011$ are both equivalent to $\langle n \rangle_T=11$ and correspond to $n=3$. The substitution~\eqref{Trib.subst} is a special case of a \emph{simple Parry substitution}, defined over the alphabet $\A=\{0,1,\ldots,m-1\}$ in the way \begin{equation}\label{simpleParry} \begin{array}{lccl} \varphi: & 0 & \mapsto & 0^{\alpha_0}1 \\ & 1 & \mapsto & 0^{\alpha_1}2 \\ & & \vdots & \\ & m-2 & \mapsto & 0^{\alpha_{m-2}}(m-1) \\ & m-1 & \mapsto & 0^{\alpha_{m-1}} \end{array} \end{equation} with $\alpha_i\in\N\cup\{0\}$ satisfying the conditions $\alpha_0\geq1$ and $\alpha_\ell\leq \alpha_0$ for all $\ell\in\A$ \cite{Fa,Pa}. We call the fixed point of~\eqref{simpleParry} a \emph{simple Parry word}; in this sense the Tribonacci word is an example of a simple Parry word. Simple Parry words appear in nonstandard numeration systems. Without going into details, let us mention here that the order of letters in the fixed point of~\eqref{simpleParry} corresponds to the order of lengths of gaps between so-called $\beta$-integers for $\beta>1$ being a zero of the polynomial $\alpha_{m-1}x^{m-1}+\alpha_{m-2}x^{m-2}+\cdots+\alpha_1 x+\alpha_0$~\cite{Th89}. Since all simple Parry substitutions have common structure, the combinatorial properties of their fixed points can be often examined in a similar way. In particular, the approach we are going to apply in this paper is based on a method that can handle fixed points of all substitutions of type~\eqref{simpleParry}. Therefore, it is convenient here to formulate the representation~\eqref{Trep} more generally. Consider a simple Parry substitution $\varphi$, and set $U_j=|\varphi^j(0)|$ for every $j\in\N\cup\{0\}$. Any $n\in\N$ can be represented as a sum $$ n=\sum_{j=0}^{k} d_j U_j $$ with integer coefficients $d_j$. If coefficients $d_j$ are obtained by the greedy algorithm, the sequence $d_kd_{k-1}\cdots d_1d_0$ is called the \emph{normal $U$-representation} of $n$ \cite{Lo} and denoted \begin{equation}\label{Urep} \langle n \rangle_U=d_kd_{k-1}\cdots d_1d_0\,. \end{equation} It can be shown that the coefficients in~\eqref{Urep} satisfy $d_j\in\{0,1,\ldots,\alpha_0\}$ for all $j=0,1,\ldots,k$. A \emph{deterministic finite automaton with output} (DFAO)~\cite{AS} is an extension of the deterministic finite automaton (DFA) model. A DFAO is defined as a $6$-tuple $(Q,\Sigma,\delta,q_0,\Delta,\tau)$, where $Q$ is a finite set of states, $\Sigma$ is the finite input alphabet, $\delta:Q\times\Sigma\to Q$ is the transition function, $q_0$ is the initial state, $\Delta$ is the output alphabet, and $\tau:Q\to\Delta$ is the output function. If we extend the domain of $\delta$ to $Q\times\Sigma^*$ by defining $\delta(q,\epsilon)=q$ for all $q\in Q$, and $\delta(q,xa)=\delta(\delta(q,x),a)$ for all $q\in Q$, $x\in\Sigma^*$ and $a\in\Sigma$, a DFAO defines a function $f:\Sigma^*\to\Delta$, given as $$ f(w)=\tau(\delta(q_0,w)) \qquad \text{for $w\in\Sigma^*$}. $$ Let $[n]_k$ denote the representation of $n\in\N$ in base $k$ for a certain integer $k\geq2$. A sequence $(a_n)_{n\in\N}$ over a finite alphabet $\Delta$ is called \emph{$k$-automatic} if there exists a DFAO with $\Sigma=\{0,1,\ldots,k-1\}$ such that $a_n=\tau(\delta(q_0,[n]_k))$ for all $n\in\N$. Shallit~\cite{Sh88} introduced the concept of generalized automatic sequences, which are generated by automata using nonstandard representations instead of ordinary base-$k$ representations. In particular, we say that a sequence $(a_n)_{n\in\N}$ with values in a finite alphabet $\Delta$ is \emph{$U$-automatic} if there exists a DFAO $(Q,\Sigma,\delta,q_0,\Delta,\tau)$ such that $$ a_n=\tau(\delta(q_0,\langle n\rangle_U)) \qquad \text{for all $n\in\N$}, $$ where $\langle n\rangle_U$ is the normal $U$-representation defined above. \section{Abelian co-decomposition}\label{Sect.Codecomposition} Abelian co-decomposition, which we briefly summarize in this section, has been developed as a tool for calculating $\AC_\u(n)$ of recurrent words~\cite{Tu13}. The main idea is roughly the following: the method uses the normal $U$-representation $\langle n \rangle_U$ to associate any $n\in\N$ with a certain set $\Z_\u(n)$ of pairs of factors. At the same time the structure of the set $\Z_\u(n)$ is designed in a way that allows to find quickly the set of relative Parikh vectors $\Prel_\u(n)$, and, consequently, to obtain the value $\AC_\u(n)$ by formula~\eqref{ACrel}. Let $v,w$ be any factors of $\u$ such that $\Psi(v)=\Psi(w)$ (in particular, $|v|=|w|$). We factorize them as follows: \begin{equation}\label{rozklad} \begin{array}{ccc} v&=&z_0\:z_1\:z_2\:\cdots\:z_h \\ w&=&\tilde{z}_0\:\tilde{z}_1\:\tilde{z}_2\:\cdots\:\tilde{z}_h \end{array} \end{equation} where $z_0,z_1,\ldots,z_h$ and $\tilde{z}_0,\tilde{z}_1,\ldots,\tilde{z}_h$ are non-empty words satisfying $\Psi(\tilde{z}_j)=\Psi(z_j)$ for all $j\in\{0,1,\ldots,h\}$. The set of pairs \begin{equation}\label{codec} \left\{\begin{pmatrix}z_0\\ \tilde{z}_0\end{pmatrix},\begin{pmatrix}z_1\\ \tilde{z}_1\end{pmatrix},\begin{pmatrix}z_2\\ \tilde{z}_2\end{pmatrix},\cdots,\begin{pmatrix}z_h\\ \tilde{z}_h\end{pmatrix}\right\} \end{equation} is called the \emph{abelian co-decomposition} of the pair $\bigl(\begin{smallmatrix}v\\ w\end{smallmatrix}\bigr)$. An abelian co-decomposition~\eqref{codec} exists for any $v,w$ such that $\Psi(v)=\Psi(w)$, because one can take, e.g., $\left\{\bigl(\begin{smallmatrix}v\\ w\end{smallmatrix}\bigr)\right\}$. The decomposition~\eqref{rozklad} is in general not unique (see Example~\ref{Ex.Codec} below), but it can be made unique by an additional requirement. Here we will adopt, throughout the whole paper, the following convention: \emph{The number $h$ in equation~\eqref{rozklad} is chosen to be maximal.} The abelian co-decomposition satisfying this requirement will be denoted $\Codec\bigl(\begin{smallmatrix}v\\ w\end{smallmatrix}\bigr)$. \begin{example}\label{Ex.Codec} Let $v=0102$, $w=1020$. There exist two possible decompositions~\eqref{rozklad}: $$ \begin{array}{ccc} v &=& \overbrace{0102}^{z_0} \\ w &=& \underbrace{1020}_{\tilde{z}_0} \end{array} \qquad\text{or}\qquad \begin{array}{ccc} v &=& \overbrace{01}^{z_0}\,\overbrace{02}^{z_1} \\ w &=& \underbrace{10}_{\tilde{z}_0}\,\underbrace{20}_{\tilde{z}_1} \end{array} $$ Hence the abelian co-decomposition of the pair $\bigl(\begin{smallmatrix}0102\\1020\end{smallmatrix}\bigr)$, obeying our convention of maximality of number of elements, is $$ \Codec\begin{pmatrix}v\\ w\end{pmatrix}=\left\{\begin{pmatrix}01\\10\end{pmatrix},\begin{pmatrix}02\\20\end{pmatrix}\right\}. $$ \end{example} For any pair $\bigl(\begin{smallmatrix}v\\ w\end{smallmatrix}\bigr)$ of factors of $\u$ such that $|v|=|w|$, we introduce the following set of vectors: \begin{equation}\label{P} \Vect\begin{pmatrix}v\\w\end{pmatrix}:=\left\{\Psi(s)-\Psi(r)\;\left|\;\text{$r$ is a prefix of $v$, $s$ is a prefix of $w$, $|s|=|r|$}\right.\right\}\,. \end{equation} \begin{example}\label{Ex.P} \begin{align*} \Vect\begin{pmatrix}0102\\1020\end{pmatrix}=&\bigl\{\,\Psi(1)-\Psi(0),\Psi(10)-\Psi(01),\Psi(102)-\Psi(010),\Psi(1020)-\Psi(0102)\,\bigr\}\\ =&\{(-1,1,0),(0,0,0),(-1,0,1)\}. \end{align*} \end{example} Let $\u$ be the fixed point of~\eqref{simpleParry}. For every $n\in\N$, we define the set~\cite[Def.~3.7 and Prop.~4.8]{Tu13} \begin{equation}\label{Z(n)} \Z_\u(n):=\Codec\begin{pmatrix}\varphi^{K+R}(0)\\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}\end{pmatrix}\,, \end{equation} where $K$ is any integer such that $n\leq U_K$ and $R$ is a constant that we choose using the formula \begin{equation}\label{R} R=m-1+\min\{j\,|\,(\forall\ell\in\A)(\varphi^j(\ell) \text{ has the prefix } 0)\}\,. \end{equation} Note that the factors $\varphi^{K+R}(0)$ and $\u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}$ are obviously abelian equivalent, thus we are allowed to consider their abelian co-decomposition. In Proposition~\ref{Z(n)correct} we will see that the right-hand side of~\eqref{Z(n)} is independent of the choice of $K$, i.e., the symbol $\Z_\u(n)$ is well-defined. \begin{proposition}\label{Z(n)correct} Let $R$ be given by equation~\eqref{R}. For any $n\in\N$ and for any integer $K$ such that $n\leq U_K$ we have \begin{equation}\label{Codex_explicit} \Codec\begin{pmatrix}\varphi^{K+R}(0)\\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}\end{pmatrix}=\bigcup_{\ell\in\A}\Codec\begin{pmatrix}\varphi^{K_0+R-m+1}(\ell)\\ \u_{[n]}^{-1}\varphi^{K_0+R-m+1}(\ell)\u_{[n]}\end{pmatrix}\,, \end{equation} where $K_0=\min\{K'\in\N\cup\{0\}\;|\;n\leq U_{K'}\}$. In particular, the right-hand side of equation~\eqref{Z(n)} is independent of the choice of $K$. \end{proposition} \begin{proof} Let us take an arbitrary $K$ such that $n\leq U_K$. Since we have $R\geq m-1$ by~\eqref{R}, we can write $$ \varphi^{K+R}(0)=\varphi^{K_0}(\varphi^{R-m+1}(\varphi^{m-1+K-K_0}(0)))\,. $$ It is easy to see that for every $j\geq m-1$, the factor $\varphi^{j}(0)$ contains each letter from $\A$, which follows from~\eqref{simpleParry}. We have $K\geq K_0$, thus $m-1+K-K_0\geq m-1$. Therefore, the factor $\varphi^{m-1+K-K_0}(0)$ contains each letter $\ell\in\A$. Hence \begin{equation}\label{phiKR} \varphi^{K+R}(0)=\varphi^{K_0}(w_0w_1w_2\cdots w_h)\,, \end{equation} where $$ \{w_0,w_1,w_2,\ldots,w_h\}=\left\{\left.\varphi^{R-m+1}(\ell)\;\right|\;\ell\in\A\right\}\,. $$ The definition of $R$ requires that the factor $\varphi^{R-m+1}(\ell)$ has the prefix $0$ for any $\ell\in\A$. As a result, each factor of type $\varphi^{K_0}(\varphi^{R-m+1}(\ell))$ has the prefix $\varphi^{K_0}(0)$. At the same time we know, with regard to the assumption $n\leq U_{K_0}$, that $\u_{[n]}$ is a prefix of $\varphi^{K_0}(0)$. To sum up, the words $\varphi^{R-m+1}(\ell)$ for $\ell\in\A$ have $\u_{[n]}$ as their prefixes. Now we can rewrite equation~\eqref{phiKR} as follows: $$ \varphi^{K+R}(0)=\varphi^{K_0}(w_0)\varphi^{K_0}(w_1)\varphi^{K_0}(w_2)\cdots\varphi^{K_0}(w_h)=z_0z_1z_2\cdots z_h\,, $$ where the factors $z_0,z_1,z_2,\ldots,z_h$ satisfy \begin{equation}\label{zz} \{z_0,z_1,z_2,\ldots,z_h\}=\left\{\left.\varphi^{K_0+R-m+1}(\ell)\;\right|\;\ell\in\A\right\}, \end{equation} and, moreover, $\u_{[n]}$ is a prefix of $z_j$ for every $j\in\{0,1,\ldots,h\}$. This allows us to decompose $$ \begin{array}{ccccccc} \varphi^{K+R}(0)&=&z_0&z_1&z_2&\cdots&z_h \\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}&=&\u_{[n]}^{-1}z_0\u_{[n]}&\u_{[n]}^{-1}z_1\u_{[n]}&\u_{[n]}^{-1}z_2\u_{[n]}&\cdots&\u_{[n]}^{-1}z_h\u_{[n]} \end{array} $$ Factors $z_j$ and $\tilde{z}_j=\u_{[n]}^{-1}z_j\u_{[n]}$ are abelian equivalent for every $j=0,1,\ldots h$, thus $\bigcup_{j=0}^h\left\{\bigl(\begin{smallmatrix}z_j\\ \tilde{z}_j\end{smallmatrix}\bigr)\right\}$ is an abelian co-decomposition of $\bigl(\begin{smallmatrix}\varphi^{K_0+R}(0)\\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}\end{smallmatrix}\bigr)$. The ``maximal'' (i.e., having maximal number of elements) abelian co-decomposition of $\bigl(\begin{smallmatrix}\varphi^{K_0+R}(0)\\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}\end{smallmatrix}\bigr)$ is obviously obtained as the union of the ``maximal'' abelian co-decompositions of $\binom{z_j}{\tilde{z}_j}$ for $j=0,1,\ldots h$, i.e., \begin{equation}\label{corr1} \Codec\begin{pmatrix}\varphi^{K+R}(0)\\ \u_{[n]}^{-1}\varphi^{K+R}(0)\u_{[n]}\end{pmatrix}=\bigcup_{j=0}^h\Codec\begin{pmatrix}z_j\\ \u_{[n]}^{-1}z_j\u_{[n]}\end{pmatrix}\,. \end{equation} Finally, equation~\eqref{zz} gives the identity \begin{equation}\label{corr2} \bigcup_{j=0}^h\Codec\begin{pmatrix}z_j\\ \u_{[n]}^{-1}z_j\u_{[n]}\end{pmatrix}=\bigcup_{\ell\in\A}\Codec\begin{pmatrix}\varphi^{K_0+R-m+1}(\ell)\\ \u_{[n]}^{-1}\varphi^{K_0+R-m+1}(\ell)\u_{[n]}\end{pmatrix}\,. \end{equation} Combining equations~\eqref{corr1} and \eqref{corr2} one gets equation~\eqref{Codex_explicit}. \end{proof} The set $\Z_\u(n)$ together with the map $\Vect$ allow to determine the set of relative Parikh vectors corresponding to the number $n$. Indeed, one can prove that~\cite[Prop.~3.8]{Tu13} \begin{equation}\label{Pred(n)} \Prel_\u(n)=\bigcup_{\begin{pmatrix}z\\ \tilde{z}\end{pmatrix}\in\Z_\u(n)}\Vect\begin{pmatrix}z\\ \tilde{z}\end{pmatrix} \end{equation} for any $n\in\N$. Consequently, if $\Z_\u(n)$ is known, it is a trivial task to calculate $\AC_\u(n)$ using the formula \begin{equation}\label{ACP} \AC_\u(n)=\#\bigcup_{\begin{pmatrix}z\\ \tilde{z}\end{pmatrix}\in\Z_\u(n)}\Vect\begin{pmatrix}z\\ \tilde{z}\end{pmatrix}\,, \end{equation} which follows immediately from equations~\eqref{ACrel} and \eqref{Pred(n)}. \begin{example}\label{Z(1)} Let us calculate $\Z_\t(1)$. We have $\mathbf{t}_{[1]}=0$. Since $1\leq T_0=1$ and $R=3-1+\min\{1,2,3,\ldots\}=3$, we shall use formula~\eqref{Z(n)} with $K+R=0+3=3$. Therefore, from~\eqref{Z(n)}, $$ \Z_\t(1)=\Codec\begin{pmatrix}\varphi_\t^3(0)\\ 0^{-1}\varphi_\t^3(0)0\end{pmatrix}\,. $$ We have $$ \begin{array}{ccc} \varphi_\t^3(0)&=&01\:02\:01\:0 \\ 0^{-1}\varphi_\t^3(0)0&=&10\:20\:10\:0 \end{array} $$ whence we obtain $$ \Z_\t(1)=\left\{\begin{pmatrix}0\\0\end{pmatrix},\begin{pmatrix}01\\10\end{pmatrix},\begin{pmatrix}02\\20\end{pmatrix}\right\}\,. $$ Let us continue the example and demonstrate the application of equations~\eqref{Pred(n)} and \eqref{ACP}. We have $$ \Vect\binom{0}{0}=\{(0,0,0)\},\; \Vect\binom{01}{10}=\{(-1,1,0),(0,0,0)\},\; \Vect\binom{02}{20}=\{(-1,0,1),(0,0,0)\}. $$ Equation~\eqref{Pred(n)} then gives $\Prel_\t(1)=\{(0,0,0),(-1,1,0),(-1,0,1)\}$, and hence, from Eq.~\eqref{ACP} we get $\AC_\t(1)=3$. This calculation has an illustrative purpose only -- the result $\AC_\t(1)=3$ could be of course found much easier from equation~\eqref{AC}. \end{example} The essential point is that sets $\Z_\u(n)$ does not need to be calculated from definition~\eqref{Z(n)} for each $n\in\N$. We are going to present a recurrence relation that will allow us to express $\Z_\u(N)$ in terms of $\Z_\u(n)$ for a certain $n=1pt,node distance=2cm,on grid,auto] \node[state,initial] (q_0) {$q_0$}; \node[state,accepting] (q_1) [right=of q_0] {$q_1$}; \node[state] (q_3) [right=of q_1] {$q_3$}; \node[state,accepting] (q_2) [above right=of q_3] {$q_2$}; \node[state,accepting] (q_4) [below right=of q_3] {$q_4$}; \path[->] (q_0) edge node {1} (q_1) edge [loop above] node {0} () (q_1) edge [bend left=40] node {0} (q_2) edge node {1} (q_3) (q_2) edge [bend left] node {0} (q_4) edge node {1} (q_3) (q_3) edge [loop below] node {0,1} () (q_4) edge node [swap] {0} (q_3) edge [bend left=40] node {1} (q_1); \end{tikzpicture} \end{center} \caption{The minimal automaton accepting the set $\{\langle n\rangle_T\;|\;\AC(n)=3\}$.} \label{Autom.3} \end{figure} \begin{remark}\label{Rem.AC3} The minimal automaton corresponding to $A_3$, which accepts $\langle n\rangle_T$ if and only if $\AC(n)=3$, has the transition diagram shown in Figure~\ref{Autom.3}. Hence we obtain one more characterization of those $n$ for which $\AC(n)=3$ on top of those that were found in~\cite[Prop.~3.3]{RSZ2}, namely: \begin{equation}\label{AC3} \AC(n)=3 \qquad\Leftrightarrow\qquad \langle n\rangle_T \text{ is a prefix of } 100100100\cdots. \end{equation} \end{remark} \section{On the abelian complexity of $m$-bonacci words for $m \geq 4$}\label{Sect.mbon} The $m$-bonacci word is defined for any integer $m\geq2$ over the alphabet $\A=\{0,1,\ldots,m-1\}$ as the fixed point of the substitution $$ \varphi_m:\qquad 0\mapsto01,\;1\mapsto02,\;\ldots,\;m-2\mapsto0(m-1),\;m-1\mapsto0\,. $$ The Fibonacci word and the Tribonacci word are its special cases for $m=2$ and $m=3$, respectively. It is easy to see that the procedure, used in previous sections to examine the abelian complexity of the Tribonacci word, can be straightforwardly applied to any $m$-bonacci word, regardless of $m$. Indeed, to explore an $m$-bonacci word for a given $m\geq2$ by this method, it suffices to change just the constant $R$ in Example~\ref{Z(1)} from the value $3$ to $m$, and to use the $m$-bonacci representation of integers. The $m$-bonacci representation is a normal $U$-representation defined for $U_j=|\varphi_m^j(0)|$; note that the values $U_j$ satisfy $$ U_j=\begin{cases} 2^j, & \text{if } j\in\{0,1,\ldots,m-1\}; \\ U_{j-1}+U_{j-2}+\cdots U_{j-m}, & \text{if } j\geq m. \end{cases} $$ On the other hand, the cardinality of $\Z_\mathrm{super}$ seems to quickly grow with $m$; thus the method ceases to be efficient for high values of $m$. For instance, we have considered the $4$-bonacci word \seqnum{A254990} and successfully found an explicit DFAO that evaluates its abelian complexity \seqnum{A255014}; the automaton has $5665$ states ($66881$ before the reduction of states). We provide main results below. For the sake of brevity we will denote the $4$-bonacci word by the symbol $\q$. For any $n\in\N$, let $\langle n\rangle_Q$ be the $4$-bonacci representation of $n$, constructed for $U_{j}=Q_{j+4}$, where $\left(Q_j\right)_{j\geq0}=(0,0,0,1,1,2,4,8,15,\ldots)$ is the sequence of Tetranacci numbers \seqnum{A000078}. The minimal and maximal values of the output function of the automaton evaluating $\AC_\q$ are $4$ and $16$, respectively. Therefore, the abelian complexity function $\AC_\q$ takes values between $4$ and $16$. However, the output function of the automaton does not attain the value $5$, which implies that there exists no $n\in\N$ such that $\AC_\q(n)=5$. To sum up, $$ \left\{\AC_\q(n)\;|\; n\in\N\right\}=\{4\}\cup\{6,7,\ldots,16\}. $$ The existence of gaps in ranges of abelian complexity functions of $m$-bonacci words was already observed a few years ago by K.~B\v{r}inda~\cite{Brinda} on the basis of computer-assisted calculations performed for $m\in\{4,5,\ldots,12\}$. Our automaton confirms his observation in the case $m=4$. Furthermore, we are able to characterize those $n$ for which $\AC_\q(n)=4$. We apply Moore's minimization algorithm on the automaton accepting the set $\{\langle n\rangle_T\;|\;\AC_\q(n)=4\}$, which leads to an automaton having just $6$ states. The transition diagram of the automaton is depicted in Figure~\ref{Autom4.4}. \begin{figure} \begin{center} \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] \node[state,initial] (q_0) {$q_0$}; \node[state,accepting] (q_1) [right=of q_0] {$q_1$}; \node[state] (q_3) [right=of q_1] {$q_3$}; \node[state,accepting] (q_2) [above=of q_3] {$q_2$}; \node[state,accepting] (q_4) [right=of q_3] {$q_4$}; \node[state,accepting] (q_5) [below=of q_3] {$q_5$}; \path[->] (q_0) edge node {1} (q_1) edge [loop above] node {0} () (q_1) edge [bend left] node {0} (q_2) edge node {1} (q_3) (q_2) edge [bend left] node {0} (q_4) edge node {1} (q_3) (q_3) edge [out=240,in=210,loop] node {0,1} () (q_4) edge [bend left] node {0} (q_5) edge node [swap] {1} (q_3) (q_5) edge node [swap] {0} (q_3) edge [bend left] node {1} (q_1); \end{tikzpicture} \end{center} \caption{($4$-bonacci word) The minimal automaton accepting the set $\left\{\langle n\rangle_Q\;|\;\AC_\q(n)=4\right\}$.} \label{Autom4.4} \end{figure} One can see directly from its structure that \begin{equation}\label{AC4} \AC_\q(n)=4 \qquad\Leftrightarrow\qquad \langle n\rangle_Q \text{ is a prefix of } 100010001000\cdots. \end{equation} This result is the $4$-bonacci version of the Tribonacci equivalence~\eqref{AC3}. Let us proceed to characterization of those $n$ such that $\AC_\q(n)=6$. We again apply Moore's minimization, and again get an automaton having only $6$ states; see Figure~\ref{Autom4.6}. \begin{figure} \begin{center} \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto] \node[state,initial] (q_0) {$q_0$}; \node[state] (q_1) [right=of q_0] {$q_1$}; \node[state] (q_2) [above right=of q_1] {$q_2$}; \node[state,accepting] (q_3) [below right=of q_1] {$q_3$}; \node[state,accepting] (q_4) [right=of q_3] {$q_4$}; \node[state,accepting] (q_5) [right=of q_2] {$q_{5}$}; \path[->] (q_0) edge node {1} (q_1) edge [loop above] node {0} () (q_1) edge node {0} (q_2) edge node [swap] {1} (q_3) (q_2) edge [loop above] node {0,1} () (q_3) edge node {0} (q_4) edge node {1} (q_2) (q_4) edge node [swap] {0} (q_5) edge node [swap] {1} (q_2) (q_5) edge node [swap] {0,1} (q_2); \end{tikzpicture} \end{center} \caption{($4$-bonacci word) The minimal automaton accepting the set $\left\{\langle n\rangle_Q\;|\;\AC_\q(n)=6\right\}$.} \label{Autom4.6} \end{figure} It is obvious from the graph that $$ \AC_\q(n)=6 \qquad\Leftrightarrow\qquad \langle n\rangle_Q\in\{11,110,1100\}, $$ i.e., the value $6$ is attained only for $n\in\{3,6,12\}$. The fact that the function $\AC_\q$ takes a certain value only finitely many times is remarkable, because it implies a significant qualitative difference between abelian complexity functions of the Tribonacci and the $4$-bonacci word. Recall that each value in the range of $\AC_\t$ is attained infinitely often~\cite{RSZ2,Tu13}. Now we will comment on the remaining values of $\AC_\q$, i.e., $c\in\{7,\ldots,16\}$. Although one can again construct minimal automata accepting $\{\langle n\rangle_Q\;|\;\AC_\q(n)=c\}$, they are not useful for obtaining a nice characterization of the numbers $n$ such that $\AC_\q(n)=c$. This follows from Table~\ref{Tab.Ac4}: \begin{table} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline $c$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ & $13$ & $14$ & $15$ & $16$ \\ \hline states & $6$ & -- & $6$ & $66$ & $4649$ & $4683$ & $4735$ & $5004$ & $5256$ & $5299$ & $5322$ & $5324$ & $5032$ \\ \hline \end{tabular} \end{center} \caption{($4$-bonacci word) Sizes of minimal automata accepting the sets $\{\langle n\rangle_Q\;|\;\AC_\q(n)=c\}$.} \label{Tab.Ac4} \end{table} the automata are too large, especially for $c\geq8$. Nevertheless, we are still able to demonstrate that each value in the set $\{7,\ldots,16\}$ is attained infinitely many times. For every $c\in\{7,\ldots,16\}$, we give in Table~\ref{Tab.inf} an infinite family of normal $Q$-representations $\langle n\rangle_Q$ such that $\AC_\q(n)=c$. \begin{table} \begin{center} \begin{tabular}{|c|cc||c|cc|} \hline $c$ & $\langle n\rangle_Q$ & & $c$ & $\langle n\rangle_Q$ & \\ \hline $7$ & $(1000)^j0$ & ($\forall j\geq1$) & $12$ & $10^j1$ & ($\forall j\geq19$) \\ $8$ & $(100)^j$ & ($\forall j\geq3$) & $13$ & $10^j$ & ($\forall j\geq19$) \\ $9$ & $(10)^j$ & ($\forall j\geq11$) & $14$ & $(10000)^j$ & ($\forall j\geq6$) \\ $10$ & $10^j11$ & ($\forall j\geq19$) & $15$ & $(10000)^j0$ & ($\forall j\geq6$) \\ $11$ & $(10)^j0$ & ($\forall j\geq11$) & $16$ & $(10000)^j00$ & ($\forall j\geq6$) \\ \hline \end{tabular} \end{center} \caption{($4$-bonacci word) Examples of infinite families of normal $Q$-representations $\langle n\rangle_Q$ such that $\AC_\q(n)=c$ for $c\in\{7,\ldots,16\}$. The data in the table were obtained by trial and error: we used the automaton evaluating $\AC_\q(n)$ to explore several periodic expansions, some with an aperiodic part at the end, and noted down those expansions that were useful. Many other such examples can be found.} \label{Tab.inf} \end{table} Let us summarize the results obtained on the $4$-bonacci word. \begin{theorem} The abelian complexity function of the $4$-bonacci word has the following properties. \begin{itemize} \item $\left\{\AC_\q(n)\;|\; n\in\N\right\}=\{4\}\cup\{6,7,\ldots,16\}$. \item $\AC_\q(n)=4$ if and only if $\langle n\rangle_Q$ is a prefix of $100010001000\cdots$. \item $\AC_\q(n)=6$ if and only if $n\in\{3,6,12\}$. \item For every value $c\in\{7,\ldots,16\}$ there exist infinitely many integers $n\in\N$ such that $\AC_\q(n)=c$. \end{itemize} \end{theorem} We are convinced that the existence of gaps in the range of the abelian complexity function, as well as the existence of values that are attained only finitely many times, are common properties of all $m$-bonacci words with $m\geq4$. We finish the section by a remark on the minimal value of the abelian complexity function of the $m$-bonacci word for a general $m$. Let $\u$ be an $m$-bonacci word. One can easily show that for every $n\in\N$ and $\ell\in\{0,1,\ldots,m-1\}$, the factor $\ell\u_{[n-1]}$ is a factor of $\u$, thus $\AC_\u(n)\geq m$. At the same time we have $\AC_\u(1)=m$. To sum up, $\min_{n\in\N}\AC_\u(n)=m$ for any $m$-bonacci word. Results of K.~B\v{r}inda's calculations~\cite{Brinda} together with proven formulas~\eqref{AC3} and \eqref{AC4} suggest a conjecture on a precise characterization of the numbers for which the abelian complexity function of an $m$-bonacci word $\u$ attains its minimum: \begin{equation}\label{ACm} \AC_\u(n)=m \qquad\Leftrightarrow\qquad \langle n\rangle_U \text{ is a prefix of } 10^{m-1}10^{m-1}10^{m-1}\cdots; \end{equation} the symbol $\langle n\rangle_U$ stands here for the $m$-bonacci representation of $n$. We are able to prove the implication $\Leftarrow$ in~\eqref{ACm} for a general $m$ by the abelian co-decomposition method, introduced earlier~\cite{Tu13}. The implication $\Rightarrow$ remains so far open, although we expect that it is probably not difficult to be proven either. \section{Conclusions and generalizations}\label{Sect.Conclusions} In this paper we focused on the abelian complexity of the Tribonacci word (or, more generally, $m$-bonacci words), but the method can be easily adapted for application on any simple Parry word. Let us consider the fixed point $\u$ of a substitution~\eqref{simpleParry}. The calculation naturally takes advantage of the numeration system associated with $\varphi$, i.e., of the normal $U$-representation for $U_j=|\varphi^j(0)|$. Let us briefly sketch the procedure. First of all, for the sake of generality, we slightly reformulate the definition of $\Codec\bigl(\begin{smallmatrix}v\\ w\end{smallmatrix}\bigr)$ by imposing an additional technical assumption on the decomposition~\eqref{rozklad}. Namely, we assume that for every $j\in\{1,\ldots,h\}$, the factor $\tilde{z}$ has the prefix $0$, and require that $h$ is maximal subject to this condition. We also need to introduce maps $\D_0,\D_1,\ldots,\D_{\alpha_0}$, defined in a way analogous to equations~\eqref{D0D1}, i.e., $$ \D_j(\zeta):=\Codec\begin{pmatrix}\varphi(z)\\ 0^{-j}\varphi(\tilde{z})0^j\end{pmatrix} \qquad\text{for }\zeta=\binom{z}{\tilde{z}}\,,\; j\in\{0,1,\ldots,\alpha_0\}\,. $$ The search for sets $\Z_1,\ldots,\Z_M$ starts with calculating $\Z_\u(n)$ by formula~\eqref{Z(n)} for every $n\in\{1,\ldots,\alpha_0\}$. Then we take the bunch of sets $\Z_\u(1),\ldots,\Z_\u(\alpha_0)$, which we denote by $\Z_1,\ldots,\Z_{\alpha_0}$, and apply the maps $\D_0,\D_1,\ldots,\D_{\alpha_0}$ on each of the sets, similarly as in the proof of Theorem~\ref{Subsets}. In this way we obtain a new bunch of sets, we apply $\D_0,\D_1,\ldots,\D_{\alpha_0}$ on them again, and so forth. However, unlike in the case of $m$-bonacci words, one needs to keep track of the admissibility of the normal $U$-representations $\langle n\rangle_U$ during the calculation. Briefly speaking, if a normal $U$-representation, examined at a given moment, cannot be validly extended by a certain specific digit $d$, then the map $\D_d$ is not applied at that stage. The procedure ends when the application of $\D_0,\D_1,\ldots,\D_{\alpha_0}$ generates no new data. The abelian co-decomposition method also allows us to deal with the other type of Parry words, called non-simple Parry words, which are fixed points of substitutions $$ \begin{array}{lccl} \varphi: & 0 & \mapsto & 0^{\alpha_0}1 \\ & 1 & \mapsto & 0^{\alpha_1}2 \\ & & \vdots & \\ & m & \mapsto & 0^{\alpha_{m}}(m+1) \\ & & \vdots & \\ & m+p-2 & \mapsto & 0^{\alpha_{m+p-2}}(m+p-1) \\ & m+p-1 & \mapsto & 0^{\alpha_{m+p-1}}m \end{array} $$ where $\alpha_j$ satisfy $\alpha_0\geq1$, $\alpha_\ell\leq\alpha_0$ for all $\ell\in\A$, and $(\exists\ell\in\{m,m+1,\ldots,m+p-1\})(\alpha_\ell\geq1)$. Although we have not explicitly discussed non-simple Parry words in previous sections, the implementation of the procedure would be the same; we just need to replace the value $m$ in the definition of $R$~\eqref{R} by $m+p$. To sum up, the approach is applicable on any Parry word; but one shall keep in mind that in practice it will more likely work well in cases when the image of the abelian complexity function is a set of low cardinality. Nevertheless, it can still give new results for various words for which other methods fail. Those Parry words, for which this approach turns out to be inefficient, can be perhaps treated by a newer technique, which replaces pairs $\binom{z}{\tilde{z}}$ by certain conveniently chosen triples~\cite{Tu15}. That technique is more involved, but it is expected to have smaller memory requirements in most cases and to work faster. A potentially interesting question is whether this approach (possibly after a certain improvement) can be used for dealing with a word that depends on a parameter, i.e., whether one can explore a parametric family of words as a whole. Consider for instance the $m$-bonacci word for a general $m\geq2$. We are convinced that the procedure could be implemented with a parameter as well, although the calculation would be of course intricate and lengthy. The procedure also gives, as a by-product, the optimal balance bound of the examined word. The optimal bound is equal to the maximal entries of vectors $\psi$ having the form $\psi=v_i-v_j$ for $v_i,v_j$ belonging to the same set $\bigcup_{\zeta\in\Z_q}\Vect(\zeta)$. For example, one can check in this way that the $4$-bonacci word is $3$-balanced. Consequently, we can regard the method not only as a tool for evaluating abelian complexity, but also as a tool for exploring balance properties of words. In particular, it is possible that this approach can lead to the optimal balance bound for the $m$-bonacci word for any $m$. Recall that the optimal bound for the $m$-bonacci word is not known yet, despite the fact that an upper bound has been already determined~\cite{BPT13}. \section{Acknowledgements} The author thanks J.-P. Allouche for useful comments and suggestions, and the referees for valuable hints and corrections that helped to improve the manuscript. \begin{thebibliography}{88} \addcontentsline{toc}{section}{Bibliography} \bibitem{AS} J.-P.\ Allouche and J.\ Shallit, {\it Automatic Sequences: Theory, Applications, Generalizations}, Cambridge University Press, 2003. \bibitem{ABJS} H.\ Ardal, T.\ Brown, V.\ Jungi\'c, and J.\ Sahasrabudhe, On abelian and additive complexity in infinite words, {\it Integers} {\bf 12} (2012), \#A21. \bibitem{BBT} L$\!$'.\ Balkov\'a, K.\ B\v rinda, and O.\ Turek, Abelian complexity of infinite words associated with quadratic Parry numbers, {\it Theor.\ Comput.\ Sci.} {\bf 412} (2011), 6252--6260. \bibitem{Brinda} K.\ B\v rinda, {\it Abelian complexity of infinite words and Abelian return words}, Research project, Czech Technical University in Prague, 2012. \bibitem{BPT13} K.\ B\v rinda, E.\ Pelantov\'a, and O.\ Turek, Balances of $m$-bonacci words, {\it Fundam.\ Inform.} {\bf 132} (2014), 33--61. \bibitem{CRSZ} J.\ Cassaigne, G.\ Richomme, K.\ Saari, and L.\ Q.\ Zamboni, Avoiding Abelian powers in binary words with bounded Abelian complexity, {\it Int.\ J.\ Found.\ Comp.\ Sci.} {\bf 22} (2011), 905--920. \bibitem{CoHe} E.\ M.\ Coven and G.\ A.\ Hedlund, Sequences with minimal block growth, \emph{Math.\ Syst.\ Theory} {\bf 7} (1973), 138--153. \bibitem{CR} J.\ Currie and N.\ Rampersad, Recurrent words with constant Abelian complexity, \emph{Adv.\ Appl.\ Math.} {\bf 47} (2011), 116--124. \bibitem{Fa} S.\ Fabre, Substitutions et $\beta$-syst\`emes de num\'eration, {\it Theor.\ Comput.\ Sci.} {\bf 137} (1995), 219--236. \bibitem{Lo} M.\ Lothaire, {\it Algebraic Combinatorics on Words}, Vol.~90 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2002. \bibitem{MR} B.\ Madill and N.\ Rampersad, The abelian complexity of the paperfolding word, \emph{Discrete Math.} {\bf 313} (2013), 831--838. \bibitem{MS} H.\ Mousavi and J.\ Shallit, Mechanical proofs of properties of the Tribonacci word, preprint, 2014. Available at \url{http://arxiv.org/abs/1407.5841}. \bibitem{Pa} W.\ Parry, On the $\beta$-expansions of real numbers, {\it Acta Math.\ Hungar.} {\bf 11} (1960), 401--416. \bibitem{RSZ} G.\ Richomme, K.\ Saari, and L.\ Q.\ Zamboni, Abelian complexity in minimal subshifts, {\it J.\ London Math.\ Soc.} {\bf 83} (2011), 79--95. \bibitem{RSZ2} G.\ Richomme, K.\ Saari, and L.\ Q.\ Zamboni, Balance and Abelian complexity of the Tribonacci word, {\it Adv.\ Appl.\ Math.} {\bf 45} (2010), 212--231. \bibitem{Sh88} J.\ Shallit, A generalization of automatic sequences, {\it Theor.\ Comput.\ Sci.} {\bf 61} (1988), 1--16. \bibitem{Th89} W.\ Thurston, Groups, tilings and finite state automata, {\it AMS Colloquium Lecture Notes}, 1989. Available at \url{http://timo.jolivet.free.fr/docs/ThurstonLectNotes.pdf}. \bibitem{Tu2} O.\ Turek, Balances and Abelian complexity of a certain class of infinite ternary words, {\it RAIRO Theoret.\ Informatics Appl.} {\bf 44} (2010), 313--337. \bibitem{Tu13} O.\ Turek, Abelian complexity and abelian co-decomposition, {\it Theor.\ Comput.\ Sci.} {\bf 469} (2013), 77--91. \bibitem{Tu15} O.\ Turek, Abelian properties of Parry words, {\it Theor.\ Comput.\ Sci.} {\bf 566} (2015), 26--38. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B85; Secondary 68R15. \noindent \emph{Keywords: } abelian complexity, Tribonacci word, finite automaton, $4$-bonacci word. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000073}, \seqnum{A000078}, \seqnum{A080843}, \seqnum{A216190}, \seqnum{A254990}, and \seqnum{A255014}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 7 2014; revised version received February 12 2015. Published in {\it Journal of Integer Sequences}, February 14 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}