Let $A$ be a finite alphabet, $A^+$ be the set of finite nonempty words in $A$ and $\sigma\colon A\to A^+$ a map. For words $w = a_1\cdots a_{|w|} \in A^+$, we define $\sigma(w) = \sigma(a_1)\cdots\sigma(a_{|w|})$, where $|w|$ is the length of $w$. Then, $\sigma$ can be seen as a map from $A^+\to A^+$, and thus the compositions $\sigma^n = \sigma\circ\dots\circ\sigma$ are defined. In this context, we call $\sigma$ a ''substitution''.
We define the ''combinatorial rank'' of $\sigma$ as $r_c(\sigma) = \min\{\#X: X \subseteq A^+,\ \sigma(A) \subseteq X^+\}$. Here, $X^+$ is the set of words of the form $x_1\cdots x_n$, where $n \in \mathbb{N}$ and each $x_j$ belongs to $X$. For example, $r_c(0\mapsto 01, 1\mapsto 10) = 2$ and $r_c(0\mapsto 01, 1\mapsto 02, 2\mapsto 0) = 3$.
It is clear that $r_c(\sigma) \geq r_c(\sigma^2) \geq \dots$, so there exists $n_0$ such that $r_c(\sigma^n) = r_c(\sigma^{n_0})$ for all $n\geq n_0$. Let $n_\sigma$ the smallest number satisfying this condition for $\sigma$.
My question is: is $n_\sigma$ computable? Equivalently, does there exist a constant $C$, depending only on $\max_{a\in A}|\sigma(a)|$ and $\#A$, such that $n_\sigma \leq C$?
As a partial result, I can show the following: let $M_\sigma$ be the abelianization of $\sigma$ (this is, the $A\times A$-matrix whose $(a,b)$ entry is the number of times that the letter $b$ occurs in $\sigma(a)$) and suppose that $M_\sigma$ has nonzero determinant. Then, $r_c(\sigma^n) = r_c(\sigma) = \#A$ for all $n\geq1$, and therefore $n_\sigma = 1$. However, observe that if $A = \{0,1\}$, $\sigma(0) = 01$ and $\sigma(1) = 10$, then $r_c(\sigma) = 2$, $n_\sigma = 1$ and $M_\sigma$ has rank 1, so $n_\sigma$ depends also on ''non-abelian'' information of $\sigma$.
I think that $n_\sigma$ should be computable. Actually, I haven't been able to find a substitution with $n_\sigma > 1$.