17
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 20 '16 at 3:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Narad Rampersad Sep 20 '16 at 13:37
  • 1
    $\begingroup$ @NaradRampersad: You can ask him and post his answer here, if he is not on MO himself. $\endgroup$ – Mark Sapir Sep 20 '16 at 18:47
  • 1
    $\begingroup$ 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$. $\endgroup$ – domotorp Sep 21 '16 at 7:43
  • 3
    $\begingroup$ @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) $\endgroup$ – David Sep 21 '16 at 17:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.