G-RIDDLE: a formal analysis of logic designs conducive to the acceleration of backtracing

A formal approach to the analysis of combinatorial gate-level designs is presented which 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 decision (assignments) less likely to cause conflicts and by minimizing the amount of work between backtracks. The G-RIDDLE approach is introduced for performing this analysis, as a refinement of the more general case which handles designs consisting of multi-input/multioutput combinatorial blocks. Experimental results are given for a popular benchmark of combinatorial gate-level designs