Learning Boolean read-once formulas with arbitrary symmetric and constant fan-in gates

ABSTRACT

A formula is read-once if each variable appears on at most a single input. Angluin, Hellerstein, and Karpinski have shown that boolean formulas with AND, OR, and NOT gates are exactly identifiable in polynomial time using membership and equivalence queries [AHK89]. Hancock and Hellerstein have generalized this to allow a wider subclass of symmetric basis functions [HH91]. We show a polynomial time algorithm in this model for identifying read-once formulas whose gates compute arbitrary functions of fan-in k or less for some constant k (i.e. any f :{0,1}1≤c≤k → {0,1}). We further show that if there is a polynomial time membership and equivalence query algorithm to identify read-once formulas over some set of functions B that meets certain technical conditions, then there is also such an algorithm to identify read-once formulas over B&ugr;{f:{0,1}1≤c≤k → {0,1}}. Finally, we extend the previous results to show that there is a polynomial time identification algorithm for read-once formulas over the basis of all symmetric functions (and hence also over the union of arbitrary symmetric and arbitrary constant fan-in gates). Given standard cryptographic assumptions, none of these results are possible for read-twice formulas.

REFERENCES

• AHK89: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• AK91: Dana Angluin , Michael Kharitonov, When won't membership queries help?, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.444-454, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103420]
• BHH92: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129747]
• BHHK91: N. H. Bshouty, T. R. Hancock, L. Hellerstein, and M. Karpinski. Read-once threshold formulas, justifying assignments, and transformations. Technical report, International Computer Science Institute TR-92-020, 1991.
• Han90: Thomas R. Hancock, Identifying μ-formula decision trees with queries, Proceedings of the third annual workshop on Computational learning theory, p.23-37, August 06-08, 1990, Rochester, New York, United States
• HGM91: T. Hancock, M. Golea, and M. Marchand. Learning nonoverlapping perceptron networks from examples and membership queries. Technical report, Harvard University TR-26-91, 1991.
• HH91: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• RS90: Vijay Raghavan , Stephen R. Schach, Learning switch configurations, Proceedings of the third annual workshop on Computational learning theory, p.38-51, August 06-08, 1990, Rochester, New York, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

General Terms:
Algorithms, Theory, Verification