Reachability Analysis over Term Rewriting Systems

This paper surveys some techniques and tools for achieving reachability analysis over term rewriting systems. The core of those techniques is a generic tree automata completion algorithm used to compute in an exact or approximated way the set of descendants (or reachable terms). This algorithm has been implemented in the Timbuk tool. Furthermore, we show that classes with regular sets of descendants of the literature corresponds to specic instances of the tree automata completion algorithm and can thus be eOEciently computed by Timbuk. An extension of the completion algorithm to conditional term rewriting systems and some applications are also presented