Efficient algorithmic learning of the structure of permutation groups by examples

This paper discusses learning algorithms for ascertaining membership, inclu sion, and equality in permutation groups. The main results are randomized l eaning algorithms which take a random generator set of a fixed group G less than or equal to S-n as input. We discuss randomized algorithms for learni ng the concepts of group membership, inclusion, and equality by representin g the group in terms of its strong sequence of generators using random exam ples from G. We present O(n(3) log n) time sequential learning algorithms f or testing membership, inclusion and equality. The running time is expresse d as a function of the size of the object set. (G less than or equal to 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 ou r algorithms more practical. Finally, we show that learning two-groups is in class NC by reducing the me mbership, inclusion, and inequality problems to solving linear systems over GF(2). We present an O(log(3) n) time learning algorithm using n(omega) pr ocessors for learning two-groups from examples (where n x n matrix product takes logarithmic time using n(omega) processors). (C) 1999 Elsevier Scienc e Ltd. All rights reserved.