Computing the minimum DNF representation of Boolean functions defined by intervals

被引:22
作者
Schieber, B
Geist, D
Zaks, A
机构
[1] IBM Corp, Thomas J Watson Res Ctr, Yorktown Hts, NY 10598 USA
[2] IBM Corp, Haifa Res Labs, IL-31905 Haifa, Israel
关键词
constraint satisfaction; automatic test generation; Boolean function; DNF; disjunctive normal form;
D O I
10.1016/j.dam.2004.08.009
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
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. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码:154 / 173
页数:20
相关论文
共 7 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]  
CHANDRA AK, 1992, P IEEE INT C COMP DE
[3]   CONSTRAINT-BASED AUTOMATIC TEST DATA GENERATION [J].
DEMILLO, RA ;
OFFUTT, AJ .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1991, 17 (09) :900-910
[4]  
Huang, 1999, P IEEE INT HIGH LEV
[5]  
LEWIN D, 1995, P 14 IEEE INT PHOEN, P45
[6]   The minimum equivalent DNF problem and shortest implicants [J].
Umans, C .
39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :556-563
[7]   Solving the generalized mask constraint for test generation of binary floating point add operation [J].
Ziv, A ;
Fournier, L .
THEORETICAL COMPUTER SCIENCE, 2003, 291 (02) :183-201