Tim Hsu writes in his e-mail article of 1994/04/13
Hi. I would like to be able to do the following thing: I have a
presentation of a finite group G, and I would like to be able to know,
say, the 100 "shortest" ways of expressing a word in the generators
which represents the identity in G as a product of conjugates of
relators. Is this easy to do in GAP? If not, do you know of another
program which does this?
This is similar to the word problem, so I very much doubt that a good
deterministic algorithm exists. What you could do is to systematically
enumerate the words in the relators and just check whether or not such a
word simplifies in the free group to the given word. Obviously this
will only work if the given word has a rather short representation as
word in the relators.
Another possibility might be to add the given word to the generators, and
then to use Tietze transformations to get rid of the word again. If one
keeps track of the transformations, this could be used to write the given
word in the original relators. This is, however, not very likely to
give the shortest such representation.
-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany