Generating set-cum-membership test-based black-box group algorithm for normality testing

Summary

Item	Value
Problem being solved	normality testing problem: test whether a given subgroup of a given group is normal
Input format	A group $G$ with an encoding and specified by means of a finite generating set $A$, a subgroup $H$ specified by means of a finite generating set $B$ Membership test for $H$ in terms of the encoding Note that $G,H$ need not be finite groups NOTE: In fact, we do not require $A$ to generate $G$. We only require that $A\cup B$ generate $G$, or equivalently, that $A\cup H$ generate $G$.
Output format	Yes/No depending on whether $H$ is normal in $G$ Optionally, if $H$ is not normal, can output $a\in A$ and $b\in B$ such that one or both of $aba^{-1}$ and $a^{-1}ba$ is not in $H$
Running time	Assuming the groups are finite: $O(|A||B|\max\{x,y\})$ where $x$ is the time taken for group multiplication and inversion and $y$ is the time taken to do a membership test. With the log-size assumption $x$ is usually negligible, so this is in practice $O(|A||B|y)$. Note that the algorithm always takes about this much time if the subgroup is normal, but can terminate much more quickly if the subgroup is not normal, as soon as a counterexample is found.
Memory requirement	Basically, same as the memory requirement for the membership testing algorithm, plus memory requirement for generating sets (though the generating sets can be processed online).
Mode of input processing	Can be made online on $B$ (clarify this)
Parallelizable version	The algorithm can be completely parallelized by carrying it out separately for each $a\in A,b\in B$. With this, the time taken reduces to $O(\max\{x,y\})$ where $x$ is the time for doing multiplication and $y$ is the time for doing membership test. The parallelization works best if it is possible to kill all processes as soon as a counterexample is found.
Pre-processing improvements	The following are some candidates: Reduce the size of $A$, i.e., replace $A$ by a smaller generating set. Reduce the size of $B$, i.e., replace $B$ by a smaller generating set. Whether these improvements are worth it depends on the situation.

Idea and outline

For each $a\in A$ and $b\in B$, check that $aba^{-1}\in H$ and $a^{-1}ba\in H$.

Note that when $G$ is finite, it suffices to check that for each $a\in A$ and $b\in B$, $aba^{-1}\in H$.