  Congruence closure procedures are used extensively in automated reasoning and
are a core component of most satisfiability modulo theories solvers. However,
no known congruence closure algorithms can support any of the expressive logics
based on intensional type theory (ITT), which form the basis of many
interactive theorem provers. The main source of expressiveness in these logics
is dependent types, and yet existing congruence closure procedures found in
interactive theorem provers based on ITT do not handle dependent types at all
and only work on the simply-typed subsets of the logics. Here we present an
efficient and proof-producing congruence closure procedure that applies to
every function in ITT no matter how many dependencies exist among its
arguments, and that only relies on the commonly assumed uniqueness of identity
proofs axiom. We demonstrate its usefulness by solving interesting verification
problems involving functions with dependent types.
