Characterizing Conclusive Approximations by Logical Formulae

International audienceConsidering an initial set of terms E, a rewriting relation R and a goal set of terms Bad, reachability analysis in term rewriting tries to answer to the following question: does there exists at least one term of Bad that can be reached from E using the rewriting relation R? Some of the approaches try to show that there exists at least one term of Bad reachable from E using the rewriting relation R by computing the set of reachable terms. Some others tackle the unreachability problem i.e. no term of Bad is reachable by rewriting from E. For the latter, over-approximations are computed. A main obstacle is to be able to compute an over-approximation precise enough that does not intersect Bad i.e. a conclusive approximation. This notion of precision is often defined by a very technical parameter of techniques implementing this over-approximation approach. In this paper, we propose a new characterization of conclusive approximations by logical formulae generated from a new kind of automata called symbolic tree automata. Solving a such formula leads automatically to a conclusive approximation without extra technical parameters