This thesis presents four different techniques for improving the average-case performance of deterministic sequential circuit Automatic Test Patterns Generators (ATPG). Three techniques make use of information gathered during test generation to help identify more unjustifiable states with higher percentage of "don't care" value. An approach for reducing the search space of the ATPG was introduced. The technique can significantly reduce the size of the search space but cannot ensure the completeness of the search. Results on ISCAS–85 benchmark circuits show that all of the proposed techniques allow for better fault detection in shorter amounts of time. These techniques, when used together, produced test vectors with high fault coverages. Also investigated in this thesis is the Decision Inversion Problem which threatens the completeness of ATPG tools such as HITEC or ATOMS. We propose a technique which can eliminate this problem by forcing the ATPG to consider search space with certain flip-flops untouched. Results show that our technique eliminated the decision inversion problem, ensuring the soundness of the search algorithm under the 9-valued logic model.