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

Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 Bqq{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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
    PublisherPubl by ACM
    Pages1-15
    Number of pages15
    ISBN (Print)089791497X, 9780897914970
    DOIs
    StatePublished - 1992
    EventProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory - Pittsburgh, PA, USA
    Duration: Jul 27 1992Jul 29 1992

    Publication series

    NameProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory

    Other

    OtherProceedings of the Fifth Annual ACM Workshop on Computational Learning Theory
    CityPittsburgh, PA, USA
    Period7/27/927/29/92

    ASJC Scopus subject areas

    • Engineering(all)

    Fingerprint Dive into the research topics of 'Learning boolean read-once formulas with arbitrary symmetric and constant fan-in gates'. Together they form a unique fingerprint.

    Cite this