  Dedukti is a type-checker for the $\lambda$$\Pi$-calculus modulo rewriting,
an extension of Edinburgh's logicalframework LF where functions and type
symbols can be defined by rewrite rules. It thereforecontains an engine for
rewriting LF terms and types according to the rewrite rules given by the user.A
key component of this engine is the matching algorithm to find which rules can
be fired. In thispaper, we describe the class of rewrite rules supported by
Dedukti and the new implementation ofthe matching algorithm. Dedukti supports
non-linear rewrite rules on terms with binders usinghigher-order
pattern-matching as in Combinatory Reduction Systems (CRS). The new
matchingalgorithm extends the technique of decision trees introduced by Luc
Maranget in the OCamlcompiler to this more general context.
