Complexity of terms, composition, and hypersubstitution

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.