FUNCTIONS THAT ARE READ-ONCE ON A SUBSET OF THEIR INPUTS

A monotone boolean function f:{0, 1}V --> {0, 1} is read-once if f 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 conditi on for f 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 to be read-once on a given subset of its inputs. For Z subset-or -equal-to V, we say that f is read-once on Z if f can be expressed as a formula in which every member of Z appears at most once.