Complexity of terms, composition, and hypersubstitution
Authors:
Open Access
- 1 January 2000
- journal article
- research article
- Published by Wiley in International Journal of Mathematics and Mathematical Sciences
- Vol. 2003 (15) , 959-969
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.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada