TITLE: the power of commuting
QUESTION [1 upvotes]: There is an interesting paper The power of commuting with finite sets of words. There I have a question about page 6 sentence:"...which is a contradiction because this word has no suffix belonging to $L^2$".
I cannot find the reason why this word has no suffix belonging to $L^2$ ?

REPLY [1 votes]: The proof is a bit technical due to the complicated expression of $L$. The alphabet is $A = \{a, b, c, e, \hat e, f, \hat f, g, \hat g\}$. By definition,
\begin{align}
  M &= efga^+ba^* \cup ga^*ba^*\hat g\hat f \cup a^*ba^*\hat g\hat f\hat e \cup fga^*ba^*\hat g \\
  L_0 &= (A\setminus \{c\})^* b(A\setminus \{c\})^* \setminus (\{ efg, fg, g, \varepsilon\}a^*ba^*\{\varepsilon, \hat g, \hat g\hat f, \hat g\hat f \hat e\})\\
  L &= \{c, ef, ga, e, fg, \hat f\hat e, a\hat g, \hat e, \hat g\hat f,fgba\hat g\} \cup A^*bA^*bA^* \cup L_0 \cup cM \cup Mc.
\end{align}
The word is $u = c^2fga^mba^n\hat g\hat f$. Since $L$ does not contain the empty word, the length of the words of $L^2$ is $\geqslant 2$. Suppose that a suffix $s$ of $u$ belong to $L^2$. Then $s = xy$ with $x,y \in L$. Since $|u|_b = 1$, neither $x$ nor $y$ belongs to $A^*bA^*bA^*$. Since $cc$ is a prefix of $u$ and $u$ does not contain any other occurrence of $c$, neither $x$ nor $y$ belong to $Mc$ or to $cM$. Furthermore, $y$ does not belong to $L_0$. It follows that $y \in  \{c, ef, ga, e, fg, \hat f\hat e, a\hat g, \hat e, \hat g\hat f,fgba\hat g\}$ and the unique possibility is $y = \hat g\hat f$. But then $x$ is a suffix of $c^2fga^mba^n$ and a simple verification shows that it cannot belong to $L$.
{"set_name": "stack_exchange", "score": 1, "question_id": 4424544}