RIDDLE: a foundation for test generation on a high-level design description

A formal approach to the analysis of a combinational circuit described at the high level is presented. It produces information conducive to the acceleration of test generation algorithms. This analysis yields, as its main product, information which can be used to reduce the amount of effort expended during backtracing, by guiding this process towards decisions (assignments) less likely to cause conflicts and minimizing the amount of work between backtracks. RIDDLE, an algorithm which performs this analysis in time linear in the number of signals, is introduced. Experimental results for the special case of combinational gate-level designs are also given