Learning Read-Once Formulas with Queries

Dana Angluin, Lisa Hellerstein, Marek Karpinski

    Research output: Contribution to journalArticlepeer-review

    Abstract

    A read-once formula is a Boolean formula in which each variable occurs, at most, once. Such formulas are also called μ-formulas or Boolean trees. This paper treats the problem of exactly identifying an unknown read-once formula using specific kinds of queries. The main results are a polynomial-time algorithm for exact identification of monotone read-once formulas using only membership queries, and a polynomial-time algorithm for exact identification of general read-once formulas using equivalence and membership queries 1993. The results of the authors improve on Valiant's previous results for read-once formulas [26]. It is also shown, that no polynomial-time algorithm using only membership queries or only equivalence queries can exactly identify all read-once formulas.

    Original languageEnglish (US)
    Pages (from-to)185-210
    Number of pages26
    JournalJournal of the ACM (JACM)
    Volume40
    Issue number1
    DOIs
    StatePublished - Feb 1 1993

    Keywords

    • equivalence queries
    • exact identification
    • interpolation
    • membership queries
    • polynomial-time learning
    • read-once formulas
    • μ-formulas

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Information Systems
    • Hardware and Architecture
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Learning Read-Once Formulas with Queries'. Together they form a unique fingerprint.

    Cite this