> < ^ Date: Mon, 03 Mar 1997 12:27:23 +0100
< ^ From: Paul R. Brown <pbrown@math.berkeley.edu >
> < ^ Subject: Re: GAP question

(Moderators remark: This mail was originally rejected by Miles as it came
from another address that the subscribed one.)

On Fri, 28 Feb 1997, william banks wrote:
#>I am trying to use GAP to study a certain finite (finitely presented)
#>group. To make the question simple, suppose I want to consider a
#>free group with 1 generator X and 1 relation: X*X = 1.
#>This group has two elements: IdWord & X .
#>Given an element, such as X*X*X*X*X*X*X, how can I make the GAP program
#>reveal to me which of two elements, IdWord or X, this is?

You're completely out of luck unless you know more about the group. In
most cases, the problem of deciding whether or not a word is trivial
is unsolvable. The most notable exceptions to this rule are automatic
groups, and in this case, Derek Holt's kbmag, integrated into GAP or
standalone, provides a time-efficient solution of the word problem.
(The time-efficiency only applies AFTER the automatic structure is
found; finding the automatic structure can be a "hard" problem.)

Another tack on the problem is to find normal subgroups of finite
index and then see if the two elements match in the finite quotient
group; this sounds easy, but searching for the normal subgroups and
then finding a permutation representation via coset enumeration are
both "hard" problems from the computer's viewpoint.

If you send your presentation to me, I'll try to give you some



Paul Brown	Grad student, UCB mathematics	       (510)-843-7817
pbrown@math.berkeley.edu            http://math.berkeley.edu/~pbrown/

> < [top]