Complexity of terms, superpositions, and generalized hypersubstitutions

Abstract

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) in terms of complexity of the inputs s, t1, ..., tmfor each of these measurements. We also obtain formulas for the complexity of over(σ, ̂) [t] in terms of the complexity where t is a compound term and σ is a generalized hypersubstitution. We apply these formulas to the theory of M-strongly solid varieties, examining the k-normalization chains of a variety with respect to these complexity measurements. Crown Copyright © 2009.