Efficent Algorithmic Learning of the Structure of Permutation Groups by Examples

This paper discusses learning algorithms for ascertaining membership, inclusion and equality in permutation groups. The main results are randomized {\em learning algorithms} which take a random generator set of a fixed group $G \leq S_n$ as input. We will discuss randomized algorithms for learning the concepts of group membership, inclusion, and equality by representing the group in terms of its strong sequence of generators using random examples from $G$. We present $0(n^3 log~n)$ time sequential learning algorithms for testing membership, inclusion and equality. The running time is expressed as a function of the size of the object set. $(G \leq S_n$ can have as many as $n!$ elements.) Our bounds hold for all input groups. We also introduce limited parallelism, and our lower processor bounds make our algorithms more practical. Finally, we show that learning 2-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over $GF$(2). We present an $0(log^3n)$ time learning algorithm using $n ^{log_2 7}$ processors for learning 2-groups from examples.