Complexity of terms, superpositions, and generalized hypersubstitutions

In this paper, we consider the four useful measurements of the complexity of a term, called the maximum depth, the minimum depth, the variable count, and the operation count. We construct a formula for the complexity of the superposition Sm(s,t1,…,tm)Sm(s,t1,…,tm) in terms of complexity of the inputs s,t1,…,tms,t1,…,tm for each of these measurements. We also obtain formulas for the complexity of σˆ[t] in terms of the complexity where tt is a compound term and σσ is a generalized hypersubstitution. We apply these formulas to the theory of MM-strongly solid varieties, examining the kk-normalization chains of a variety with respect to these complexity measurements.