### 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 language | English (US) |
---|---|

Pages (from-to) | 235-251 |

Number of pages | 17 |

Journal | Discrete Applied Mathematics |

Volume | 46 |

Issue number | 3 |

DOIs | |

State | Published - 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

Hellerstein, L. (1993). Functions that are read-once on a subset of their inputs.

*Discrete Applied Mathematics*,*46*(3), 235-251. https://doi.org/10.1016/0166-218X(93)90105-W