International Journal of Mathematics and Mathematical Sciences
Volume 2003 (2003), Issue 15, Pages 959-969

Complexity of terms, composition, and hypersubstitution

Klaus Denecke1 and Shelly L. Wismath2

1Institut für Mathematik, Universität Potsdam, Am Neuen Palais, Potsdam 14415, Germany
2Department of Mathematics and Computer Science, University of Lethbridge, Alberta, Lethbridge T1K 3M4, Canada

Received 25 February 2002

Copyright © 2003 Klaus Denecke and Shelly L. Wismath. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We consider four useful measures of the complexity of a term: the maximum depth (usually called the depth), the minimum depth, the variable count, and the operation count. For each of these, we produce a formula for the complexity of the composition Smn(s,t1,,tn) in terms of the complexity of the inputs s, t1,, tn. As a corollary, we also obtain formulas for the complexity of σˆ[t] in terms of the complexity of t when t is a compound term and σ is a hypersubstitution. We then apply these formulas to the theory of M-solid varieties, examining the k-normalization chains of a variety with respect to the four complexity measures.