  This paper presents general syntactic conditions ensuring the strong
normalization and the logical consistency of the Calculus of Algebraic
Constructions, an extension of the Calculus of Constructions with functions and
predicates defined by higher-order rewrite rules. On the one hand, the Calculus
of Constructions is a powerful type system in which one can formalize the
propositions and natural deduction proofs of higher-order logic. On the other
hand, rewriting is a simple and powerful computation paradigm. The combination
of both allows, among other things, to develop formal proofs with a reduced
size and more automation compared with more traditional proof assistants. The
main novelty is to consider a general form of rewriting at the predicate-level
which generalizes the strong elimination of the Calculus of Inductive
Constructions.
