I need to give an algorithm to show that the word problem in the group $\langle x,y \mid \mid x^{1984} = y^{2014} = 1 \rangle$ is decidable. How do I show this? I'm not too sure where to start.

  • 1
    $\begingroup$ What sort of course is this question from? How much group theory do you know? Can you see how to show this group is virtually-free? $\endgroup$ – Sam Jones May 20 '14 at 12:12
  • $\begingroup$ @SamJones I know a fair amount of group theory, but I don't see how to show that this group is virtually-free. This is from a course in computability theory, specifically it is a question from when we were focusing on Kolmogorov complexity. $\endgroup$ – Newb May 20 '14 at 13:59
  • 2
    $\begingroup$ This group is a free product of two finite groups which makes it virtually-free (see here math.stackexchange.com/questions/95695/…). You can then invoke the Muller-Schupp theorem to show that it has context-free word problem. However, this might not be the intended approach for that course. Yuval Filmus' hint below is probably more like what was intended. $\endgroup$ – Sam Jones May 20 '14 at 14:16
  • $\begingroup$ Indeed --- I don't think I'm meant to take the group-theoretic approach. I will ponder Yuval's hint some more. $\endgroup$ – Newb May 20 '14 at 14:42

Hint: Come up with a normal form for words in this group.

  • $\begingroup$ Do you mean a CNF? $\endgroup$ – Newb May 21 '14 at 6:51
  • $\begingroup$ Imagine the presentation was $<x, y \; || >$ i.e. the free group of rank 2. How do you know when two words over the alphabet $\Sigma = \{x, y, x^{-1}, y^{-1} \}$ represent the same element of the free group? Then can you see how to apply this to the presentation that you have? $\endgroup$ – Sam Jones May 21 '14 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.