4
$\begingroup$

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.

$\endgroup$
4
  • 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, 2014 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, 2014 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, 2014 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, 2014 at 14:42

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Do you mean a CNF? $\endgroup$
    – Newb
    May 21, 2014 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, 2014 at 12:28

Your Answer

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

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