On generalized constraints and certificates

Lisa Hellerstein

    Research output: Contribution to journalArticle

    Abstract

    We consider the problem of characterizing sets of Boolean functions. Extending results of Ekin et al. and Pippenger, we show that a set of Boolean (or finite) functions can be characterized by a set of objects called 'generalized constraints' iff the set is closed under the operations of permutation of variables and addition of dummy variables. We show a relationship between sets of Boolean functions that are characterizable by a finite set of generalized constraints and sets of Boolean functions that have constant-size certificates of non-membership. We then explore whether certain particular sets of Boolean functions have constant-size certificates of non-membership; most notably, we show that the well-known set of Boolean threshold functions does not have constant-size certificates of non-membership. Finally, we extend results of Pippenger to develop a Galois theory for sets of Boolean functions closed under the operations of permutation of variables and addition of dummy variables.

    Original languageEnglish (US)
    Pages (from-to)211-232
    Number of pages22
    JournalDiscrete Mathematics
    Volume226
    Issue number1-3
    DOIs
    StatePublished - 2001

    Keywords

    • Boolean functions
    • Certificates of non-membership
    • Constraints
    • Galois theory
    • Minors

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics

    Fingerprint Dive into the research topics of 'On generalized constraints and certificates'. Together they form a unique fingerprint.

  • Cite this