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 -