TY - JOUR
TI - On the frequency of the most frequently occurring variable in dual monotone DNFs
DO - https://doi.org/doi:10.7282/t3-vzan-q840
AU - Gurvich, Vladimir
AU - Khachiyan, Leonid
PY - 1995-08
AB - Let f(x1,....., xn) = VIεF^iεIxi and g(x1,.....,xn) = VIεF^iεIxi be a pair of dual monotone irredundant disjunctive normal forms, where F and G are the sets of the prime implicants of f and g, respectively. For a variable xi, i = 1,......, n, let i= #{I ε F|i ε I}/|F| and i = #{I ε G|i ε I}/|G| be the frequencies with which xi occurs in f and g. It is easily seen that maxf{u1, v1,......un,vn}>= 1/ log(|F|+|G|): We give examples of arbitrarily large F and G for which the above bound is tight up to a factor of 2.
KW - Monotone Boolean function
KW - Disjunctive normal form
KW - Prime implicant
KW - Duality
KW - Short implicant
KW - Frequent variable
KW - Transversal hypergraph
KW - Clutter
KW - Blocker
KW - Quasi-polynomial time
LA - English
ER -