Valuations of terms
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.
- Valuations and hypersubstitutions
- Minimal characteristic algebras for rectangular k-normal identities
- Valuations of polynomials
- 2-Normalization of lattices
- Minimal characteristic algebras for leftmost \(k\)-normal identities
- Extensions of valuations
- Complexity of term representations of finitary functions
- The length of terms and their measurement
- Green's Relation ℛ on the Monoid of Clone Endomorphisms
This page was built for publication: Valuations of terms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496162)
