The subalgebra membership problem is one of the most well established and
most thoroughly
studied algorithmic problems in algebra. In this problem we are given a
(finite) set of elements, called generators, of
an algebraic structure (briefly: algebra), and we are
asked to check whether or not a given element belongs to the subalgebra
generated by the generators. This question has been studied
within the general algebraic theory
[1]}, [2]}, [3]}, [4]},
and
it is also an important problem in
computational group theory
[5]}, [6]}, [7]}
where it is referred to as the subgroup membership problem.
In addition to its
theoretical interest, the subalgebra membership problem
for general algebraic structures
has found applications in some learning
algorithms [8]}, [9]}, [10]}, and
the subgroup membership problem has found applications in areas
such as cryptography [11]}, [12]}.
