  Rewriting is a formalism widely used in computer science and mathematical
logic. When using rewriting as a programming or modeling paradigm, the rewrite
rules describe the transformations one wants to operate and rewriting
strategies are used to con- trol their application. The operational semantics
of these strategies are generally accepted and approaches for analyzing the
termination of specific strategies have been studied. We propose in this paper
a generic encoding of classic control and traversal strategies used in rewrite
based languages such as Maude, Stratego and Tom into a plain term rewriting
system. The encoding is proven sound and complete and, as a direct consequence,
estab- lished termination methods used for term rewriting systems can be
applied to analyze the termination of strategy controlled term rewriting
systems. We show that the encoding of strategies into term rewriting systems
can be easily adapted to handle many-sorted signa- tures and we use a
meta-level representation of terms to reduce the size of the encodings. The
corresponding implementation in Tom generates term rewriting systems compatible
with the syntax of termination tools such as AProVE and TTT2, tools which
turned out to be very effective in (dis)proving the termination of the
generated term rewriting systems. The approach can also be seen as a generic
strategy compiler which can be integrated into languages providing pattern
matching primitives; experiments in Tom show that applying our encoding leads
to performances comparable to the native Tom strategies.
