Folding variant narrowing and optimal variant termination

If a set of equations EUAx is such that E is confluent, terminating, and coherent modulo Ax, narrowing with E modulo Ax provides a complete EUAx-unification algorithm. However, except for the hopelessly inefficient case of full narrowing, nothing seems to be known about effective narrowing strategies in the general modulo case beyond the quite depressing observation that basic narrowing is incomplete modulo AC. In this work we propose an effective strategy based on the idea of the EUAx-variants of a term that we call folding variant narrowing. This strategy is complete, both for computing EUAx-unifiers and for computing a minimal complete set of variants for any input term. And it is optimally variant terminating in the sense of terminating for an input term t iff t has a finite, complete set of variants. The applications of folding variant narrowing go beyond providing a complete EUAx-unification algorithm: computing the EUAx-variants of a term may be just as important as computing EUAx-unifiers in recent applications of folding variant narrowing such as termination methods modulo axioms, and checking confluence and coherence of rules modulo axioms.