An efficient test generation algorithm based on search state dominance

J. Giraldi and M.L. Bushnell (1990) proposed a new test generation method, called the EST (equivalent state hashing) algorithm, which can reduce the search space for test generation by using binary decision diagram fragments to detect previously encountered search states. The authors extend the concept of search state equivalence to that of search state dominance, and propose a new extended method, the DST (dominant state hashing) algorithm, based on the search state dominance. The DST algorithm can prune the search space more effectively than the EST algorithm. The benefits of DST are illustrated through examples of decision trees.<>