Free semigroup, yes. Sorry. But the questions also arise for free groups, assuming both the generators and their inverses are known. Colin Mallows (colinm at research.avayalabs.com)