Complexity of terms, composition, and hypersubstitution
Klaus Denecke, Shelly L. Wismath · International Journal of Mathematics and Mathematical Sciences · 2003
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 in terms of the complexity of the inputs s, t1, …, tn. As a corollary, we also obtain formulas for the complexity of 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.