Abstract

Basic narrowing is a restricted form of narrowing which constrains narrowing steps to a set of unblocked positions. In this work, we study the modularity of termination of basic narrowing in hierarchical combinations of TRSs, which provides new algorithmic criteria to prove termination of basic narrowing. Basic narrowing has a number of important applications including equational unification in canonical theories. Another application is analyzing termination of narrowing by checking the termination of basic narrowing, as done in pioneering work by Hullot. As a particularly interesting application, we consider solving equations modulo a theory that is given by a TRS, and then distill a number of modularity results for the decidability of equational unification via the modularity of basic narrowing termination