< ^ From:

> < ^ Subject:

(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

assistance.

Best,

Paul

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

> < [top]