[GAP Forum] Factorization for Semigroups

[Andrew Solomon]

Dear Jose Morais

On Fri, Jan 23, 2004 at 11:51:19AM +0000, Jose Joao Morais wrote:
> Dear GAP-Forum,
> 
> 	I need a Factorization function for semigroups (like the one for
> groups) that given a semigroup and an element of this semigroup would
> return the element's factorization in the generators of the semigroup.
> 
> 	I have looked at the code for 'Factorization' for groups but I could
> not get any enlightenment, so my question is if anyone could give some
> hints on how to implement such a function (what I do now is, starting
> with the generators of the semigroup, perform all the multiplications
> while storing the factors, but this takes too long for semigroups with
> enough elements and becomes impracticable...).
> 


According to Kozen

  D. Kozen {\em Lower bounds for natural proof systems},
  Proc.  18th Annual Symposium on the Foundations of Computer Science,
  IEEE Computer Society, Long Beach, CA (1977) 254--266.

the problem is PSPACE complete even for semigroups of transformations,
so one probably can't do very much better than the naive algorithm.
Even so, this may be worth implementing if the semigroups under
investigation are small.

`Factorization' for groups implements the naive algorithm, basically
multiplying with generators until all elements are found.

The mechanism for homomorphisms for permutation groups uses a more
elaborate setup using stabilizer chains. These however crucially rely
on the possibility to cancel, and thus do not seem to give an obvious
generalization to semigroups.

best wishes,

Andrew Solomon