Computing the minimum DNF representation of Boolean functions defined by intervals

Baruch Schieber, Daniel Geist, Ayal Zaks

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

For any two n-bit numbers a≤b define the Boolean function f[a,b]:{0,1}n→{0,1} to be the function for which f[a,b](x)=1 if and only if x is the binary representation of a number in the interval [a,b]. We consider the disjunctive normal form representation of such functions, and show how to compute such a representation with a minimum number of disjuncts in linear time. We also show how to compute a minimum "disjoint" representation; i.e., a representation in which the domains of the disjuncts are mutually disjoint. The minimum disjunctive normal form can be applied to devise efficient constraint satisfaction systems for automatic generation of test patterns.

Original languageEnglish (US)
Pages (from-to)154-173
Number of pages20
JournalDiscrete Applied Mathematics
Volume149
Issue number1-3
DOIs
StatePublished - Aug 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Automatic test generation
  • Boolean function
  • Constraint satisfaction
  • DNF
  • Disjunctive normal form

Fingerprint Dive into the research topics of 'Computing the minimum DNF representation of Boolean functions defined by intervals'. Together they form a unique fingerprint.

Cite this