ON THE PROPERTIES OF COMBINATION SET OPERATIONS

The problem of constructing a combination set to represent a collectio n of all solutions by solving constraint satisfaction problems is cons idered. Two kinds of combination set operations, restriction and exclu sion, are invented. Simplification theorems on these two operations pl ays an important role to avoid combinatorial explosions. In addition, a zero-suppressed BDD, a variation of ordered binary decision diagrams , is adopted to represent a combination set and efficient implementati ons of the two operations are presented. (C) 1998 Elsevier Science B.V . All rights reserved.