  Equational unification of two terms consists of finding a substitution that,
when applied to both terms, makes them equal modulo some equational properties.
Equational unification is of special relevance to automated deduction, theorem
proving, protocol analysis, partial evaluation, model checking, etc. Several
algorithms have been developed in the literature for specific equational
theories, such as associative-commutative symbols, exclusive-or,
Diffie-Hellman, or Abelian Groups. Narrowing was proved to be complete for
unification and several cases have been studied where narrowing provides a
decidable unification algorithm. A new narrowing-based equational unification
algorithm relying on the concept of the variants of a term has been developed
and it is available in the most recent version of Maude, version 2.7.1, which
provides quite sophisticated unification features. A variant of a term t is a
pair consisting of a substitution sigma and the canonical form of tsigma.
Variant-based unification is decidable when the equational theory satisfies the
finite variant property. However, it may compute many more unifiers than the
necessary and, in this paper, we explore how to strengthen the variant-based
unification algorithm implemented in Maude to produce a minimal set of most
general variant unifiers. Our experiments suggest that this new adaptation of
the variant-based unification is more efficient both in execution time and in
the number of computed variant unifiers than the original algorithm available
in Maude.
