Valuations of terms (Q2496162)

Let \(\tau \) be a given type of algebras (with no nullary operation symbols). There are several commonly used measurements of the complexity of terms of type \(\tau \), such as the depth or height of a term and the number of variable symbols appearing in it. In this paper, the authors formalize these various measurements by defining a complexity or valuation mapping on terms. A valuation on terms is a mapping from the absolutely free term algebra of type \(\tau \) into a certain algebra of the same type on which an order relation is defined. The interconnection between such term valuations and the equational theory of Universal Algebra is developed. The collection of all varieties of a given type form a complete lattice that is very complex and difficult to study; valuations of terms offer a new tool to study complete sublattices of this lattice.