Functions that are read-once on a subset of their inputs

Lisa Hellerstein

    Research output: Contribution to journalArticle

    Abstract

    A monotone boolean function f{hook}: {0,1}v → {0,1} is read-once if f{hook} can be expressed as a boolean formula over (AND, OR, NOT) in which every variable in V appears at most once. A necessary and sufficient condition for f{hook} to be read-once was shown by V.A. Gurvich (and independently by others). In this paper we show necessary and sufficient conditions for f{hook} to be read-once on a given subset of its inputs. For Z ⊆ V, we say that f{hook} is read-once on Z if f{hook} can be expressed as a formula in which every member of Z appears at most once.

    Original languageEnglish (US)
    Pages (from-to)235-251
    Number of pages17
    JournalDiscrete Applied Mathematics
    Volume46
    Issue number3
    DOIs
    StatePublished - Oct 26 1993

    ASJC Scopus subject areas

    • Discrete Mathematics and Combinatorics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Functions that are read-once on a subset of their inputs'. Together they form a unique fingerprint.

  • Cite this