# Question about combinatorics on words

Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$.

Question: Is there an algorithm to check if for some $m,k$ some prefix of the word $\phi^m(a_1)$ coincides with some suffix of the word $\phi^k(a_2)$?

This is related to a question about the R. Thompson group $F$.

• Assuming the words are finite, there is the brute force method with no guarantee of termination. Are you looking for an algorithm with such a guarantee, or do you want even more? Also, is the n in the question the same as the alphabet size? (Probably not.) Gerhard "Just Checking On Some Details" Paseman, 2016.09.19. – Gerhard Paseman Sep 20 '16 at 3:19
• I don't have an actual solution to the problem, but I know the best person to ask about it: Juha Honkala of the University of Turku. If anyone knows the answer it would be him. – Narad Rampersad Sep 20 '16 at 13:37
• @NaradRampersad: You can ask him and post his answer here, if he is not on MO himself. – Mark Sapir Sep 20 '16 at 18:47
• With the below simple trick we can ensure that if a prefix equals a suffix, then the whole words are equal. I'm thinking that deciding equality might be already undecidable. Trick: $\phi(a_1)=a_{start} a_1' a_{end}$ and $\phi(a_2)=a_{start} a_2' a_{end}$, where $\phi(a_{start})=a_{start}$ and $\phi(a_{end})=a_{end}$, and none of $a_1, a_2, a_{start}, a_{end}$ are in the image of any other $a_i$. – domotorp Sep 21 '16 at 7:43
• @domotorp The equality version is decidable, by Theorem 4 of [1]. Unfortunately, this doesn't seem very helpful for the original question, because it goes via saying that if the substitution homomorphism is not injective, then it factors through a smaller alphabet and we are happy by induction. [1] A. Ehrenfeucht, G. Rozenberg, Simplifications of homomorphisms, Information and Control, Volume 38, Issue 3, 1978 (sciencedirect.com/science/article/pii/S0019995878900955) – David Sep 21 '16 at 17:41