Logo image
On the frequency of the most frequently occurring variable in dual monotone DNFs
Technical documentation   Open access

On the frequency of the most frequently occurring variable in dual monotone DNFs

Vladimir Gurvich and Leonid Khachiyan
Rutgers University
1995
DOI:
https://doi.org/10.7282/t3-vzan-q840

Abstract

Monotone Boolean function Disjunctive normal form Prime implicant Duality Short implicant Frequent variable Transversal hypergraph Clutter Blocker Quasi-polynomial time
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.
pdf
lcsr-tr-25275.29 kBDownloadView
Version of Record (VoR) Open Access
url
Report an accessibility issueView
Please complete a content remediation request to report an accessibility issue with a library electronic resource, website, or service.

Metrics

130 File downloads
67 Record Views

Details

Logo image