Learning Boolean read-once formulas over generalized bases

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

    Research output: Contribution to journalArticle

    Abstract

    A formula is read-once if each variable appears on at most a single input. Previously, Angluin, Hellerstein, and Karpinski gave a polynomial time algorithm hat uses membership and equivalence queries to identify exactly read once boolean formulas over the basis (AND, OR, NOT). In this paper we consider natural generalizations of this basis, and develop exact identification algorithms for more powerful classes of read-once formulas. We show that read-once formulas over the basis of arbitrary boolean functions of constant fan-in L (i.e., any ƒ: (0,1)1 ≤ c ≤ k → (0,1), where k is a constant) are exactly identifiable i polynomial time using membership and equivalence queries. We also show that read-once formulas over the basis of arbitrary symmetric boolean functions are exactly identifiable in polynomial time in this model. Given standard cryptographic assumptions, there is no polynomial time identification algorithm for read-twice formulas over either of these bases in the model. We further show that for any basis class B meeting certain technical conditions, any polynomial time identification algorithm for read-once formulas over B can be extended to a polynomial time identification algorithm for read-once formulas over the union of B and the arbitrary functions of constant fan-in. As a result, read-once formulas over the union of arbitrary symmetric and arbitrary constant fan-in gates are also exactly identifiable in polynomial time using membership and equivalence queries.

    Original languageEnglish (US)
    Pages (from-to)521-542
    Number of pages22
    JournalJournal of Computer and System Sciences
    Volume50
    Issue number3
    DOIs
    StatePublished - Jun 1995

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Networks and Communications
    • Computational Theory and Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Learning Boolean read-once formulas over generalized bases'. Together they form a unique fingerprint.

  • Cite this