VARIABLE AND TERM REMOVAL FROM BOOLEAN-FORMULAS

Citation
Y. Crama et al., VARIABLE AND TERM REMOVAL FROM BOOLEAN-FORMULAS, Discrete applied mathematics, 75(3), 1997, pp. 217-230
Citations number
15
Categorie Soggetti
Mathematics,Mathematics
Volume
75
Issue
3
Year of publication
1997
Pages
217 - 230
Database
ISI
SICI code
Abstract
Given a Boolean formula in disjunctive normal form, the variable delet ion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfyi ng some prescribed property. Similar problems can be defined with resp ect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broa d class of DNF properties.