Skip to main content
Journal cover image

Efficient algorithmic learning of the structure of permutation groups by examples

Publication ,  Journal Article
Azhar, S; Reif, JH
Published in: Computers and Mathematics with Applications
January 1, 1999

This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G≤Sn as input. We 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 O(n3 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≤Sn 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 two-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over GF(2). We present an O(log3 n) time learning algorithm using n$+ω/ processors for learning two groups from examples (where n×n matrix product takes logarithmic time using n$+ω/ processors).

Duke Scholars

Published In

Computers and Mathematics with Applications

DOI

ISSN

0898-1221

Publication Date

January 1, 1999

Volume

37

Issue

10

Start / End Page

105 / 132

Related Subject Headings

  • Numerical & Computational Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 35 Commerce, management, tourism and services
  • 15 Commerce, Management, Tourism and Services
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Azhar, S., & Reif, J. H. (1999). Efficient algorithmic learning of the structure of permutation groups by examples. Computers and Mathematics with Applications, 37(10), 105–132. https://doi.org/10.1016/S0898-1221(99)00129-7
Azhar, S., and J. H. Reif. “Efficient algorithmic learning of the structure of permutation groups by examples.” Computers and Mathematics with Applications 37, no. 10 (January 1, 1999): 105–32. https://doi.org/10.1016/S0898-1221(99)00129-7.
Azhar S, Reif JH. Efficient algorithmic learning of the structure of permutation groups by examples. Computers and Mathematics with Applications. 1999 Jan 1;37(10):105–32.
Azhar, S., and J. H. Reif. “Efficient algorithmic learning of the structure of permutation groups by examples.” Computers and Mathematics with Applications, vol. 37, no. 10, Jan. 1999, pp. 105–32. Scopus, doi:10.1016/S0898-1221(99)00129-7.
Azhar S, Reif JH. Efficient algorithmic learning of the structure of permutation groups by examples. Computers and Mathematics with Applications. 1999 Jan 1;37(10):105–132.
Journal cover image

Published In

Computers and Mathematics with Applications

DOI

ISSN

0898-1221

Publication Date

January 1, 1999

Volume

37

Issue

10

Start / End Page

105 / 132

Related Subject Headings

  • Numerical & Computational Mathematics
  • 49 Mathematical sciences
  • 46 Information and computing sciences
  • 35 Commerce, management, tourism and services
  • 15 Commerce, Management, Tourism and Services
  • 08 Information and Computing Sciences
  • 01 Mathematical Sciences