Abstract: We show how a procedure developed by Bledsoe for automatically finding substitution instances for set variables in higher-order logic can be adapted to provide increased automation in proof search in the Calculus of Constructions (CC). Bledsoe's procedure operates on an extension of first-order logic that allows existential quantification over set variables. The method finds maximal solutions for this special class of higher-order variables. This class of variables can also be identified in CC. The existence of a correspondence between higher-order logic and higher-order type theories such as CC is well-known. CC can be viewed as an extension of higher-order logic where the basic terms of the language, the simply-typed lambda-terms, are replaced with terms containing dependent types. We adapt Bledsoe's procedure to the corresponding class of variables in CC and extend it to handle terms with dependent types.