Complexity of terms, composition, and hypersubstitution (Q1864336): Difference between revisions

The authors present formulae for computing the complexity of the composition \(s(t_1,\dots,t_n)\) of an \(n\)-ary term \(s\) and \(n\) terms \(t_1,\dots,t_n\) of some arity \(m\) \((m,n\geq 1)\) for four measures of the complexity of a term: the maximal depth, the minimal depth, the total number of variable occurrences, and the total number of function symbol occurrences. Formulae for the complexities of terms resulting from hypersubstitutions are obtained as special cases; a hypersubstitution maps terms to terms by replacing each function symbol by a term of the same arity. A variety \(V\) of algebras is said to be \(M\)-solid, for a given set \(M\) of hypersubstitutions, if \(V\) satisfies every identity obtained by applying a hypersubstitution from \(M\) to both sides of an identity satisfied by \(V\). The above mentioned results yield some conditions for the preservation of such solidity properties when new varieties are derived in a certain way from an \(M\)-solid variety.