Regular Sets of Descendants by Leftmost Strategy

Pierre Rety and Julie Vuotto

Keywords : term rewriting, strategy, tree automaton.

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
leftmost strategy.