TY - JOUR

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

AU - Hellerstein, Lisa

N1 - Funding Information:
Correspondence to: Dr. L. Hellerstein, EECS Department, Road, Evanston, IL 60208-3118, USA. * This paper was prepared while the author was at U. C. Berkeley and at the Massachusetts Technology. Support was provided by NSF Grant CCR-8411954, an AT&T Bell Labs GRPW a grant from the Siemens Corporation.

PY - 1993/10/26

Y1 - 1993/10/26

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=43949164291&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43949164291&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(93)90105-W

DO - 10.1016/0166-218X(93)90105-W

M3 - Article

AN - SCOPUS:43949164291

SN - 0166-218X

VL - 46

SP - 235

EP - 251

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -