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

Improve this question
$\endgroup$
6
  • 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, 2016 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, 2016 at 13:37
  • 1
    $\begingroup$ @NaradRampersad: You can ask him and post his answer here, if he is not on MO himself. $\endgroup$
    – user6976
    Sep 20, 2016 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, 2016 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, 2016 at 17:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.