The subgroup membership problem was the first to be studied. The celebrated
algorithm by Sims [1]} decides, for any given
set of permutations \(a_1,\dots , a_k\)  on a finite set \(X\) ,
whether or not a given permutation \(b\) 
belongs to the subgroup of the
full symmetric group \(\mathbf {S}_X\) 
generated by \(a_1,\dots , a_k\) . This algorithm
has been widely used, and a number of improvements have been suggested
[2]}, [3]}, [4]}.
While Sims' algorithm is
quite efficient, Kozen [5]} proved that if the
group \(\mathbf {S}_X\)  is replaced
by the full transformation semigroup on \(X\) ,
the subalgebra membership
problem is \(\mathrm {PSPACE}\) -complete.
