Genclo and termequiv are exptime-complete

Abstract

In 1999, Bergman et al. showed that the following two problems are EXPTIME-complete: GENCLO, which decides whether an operation on a finite set A belongs to a clone generated by a finite set of operations on A; and TERMEQUIV, which decides whether two algebras on the same finite set and with finitely many fundamental operations are term-equivalent. However, the proof of one of the key statements was not correct. Using the techniques proposed by Bergman et al., in this paper we present the correct proof. © 2008 World Scientific Publishing Company.