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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.