Regular Sets of Descendants by some Rewrite Strategies

Pierre Rety and Julie Vuotto

Abstract :

For a constructor-based rewrite system $R$, a regular set of ground terms
$E$, and assuming some additional restrictions,
we build a finite tree automaton that recognizes the descendants of
$E$, i.e.~the terms issued from $E$ by rewriting, according to
innermost, innermost-leftmost, and outermost strategies.