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.
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– Sam Jones2014-05-20 12:12:15 +00:00Commented 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– Newb2014-05-20 13:59:18 +00:00Commented 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– Sam Jones2014-05-20 14:16:26 +00:00Commented 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– Newb2014-05-20 14:42:14 +00:00Commented May 20, 2014 at 14:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Hint: Come up with a normal form for words in this group.
-
$\begingroup$ Do you mean a CNF? $\endgroup$Newb– Newb2014-05-21 06:51:04 +00:00Commented 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– Sam Jones2014-05-21 12:28:42 +00:00Commented May 21, 2014 at 12:28