International Journal of Mathematics and Mathematical Sciences
Volume 2003 (2003), Issue 15, Pages 959-969
doi:10.1155/S0161171203202118
Complexity of terms, composition, and hypersubstitution
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.
Abstract
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.