Refine
Has Fulltext
- no (93)
Year of publication
Document Type
- Article (93) (remove)
Language
- English (93) (remove)
Is part of the Bibliography
- yes (93)
Keywords
- linear term (5)
- clone (4)
- linear hypersubstitution (4)
- partial clone (4)
- formula (2)
- linear formula (2)
- linear tree language (2)
- term (2)
- Menger algebra of rank n (1)
- Operation (1)
- algebra of rank n (1)
- coloration of terms (1)
- colored solid varieties (1)
- dht-symmetric category (1)
- formulas (1)
- linear hyperidentity (1)
- linear identity (1)
- multi-hypersubstitutions (1)
- n-ary operation (1)
- n-ary term (1)
- nondeterministic linear hypersubstitution (1)
- partial (1)
- partial Menger (1)
- r-hypersubstitution (1)
- r-term (1)
- superposition (1)
- superposition of n-ary operations and n-ary (1)
- superposition of operations (1)
- terms (1)
- terms and (1)
- theory (1)
Institute
Valuations of Terms
(2003)
Let tau be a type of algebras. There are several commonly used measurements of the complexity of terms of type tau, including the depth or height of a term and the number of variable symbols appearing in a term. In this paper we formalize these various measurements, by defining a complexity or valuation mapping on terms. A valuation of terms is thus a mapping from the absolutely free term algebra of type tau into another algebra of the same type on which an order relation is defined. We develop the interconnections between such term valuations and the equational theory of Universal Algebra. The collection of all varieties of a given type forms a complete lattice which is very complex and difficult to study; valuations of terms offer a new method to study complete sublattices of this lattice
A term, also called a tree, is said to be linear, if each variable occurs in the term only once. The linear terms and sets of linear terms, the so-called linear tree languages, play some role in automata theory and in the theory of formal languages in connection with recognizability. We define a partial superposition operation on sets of linear trees of a given type and study the properties of some many-sorted partial clones that have sets of linear trees as elements and partial superposition operations as fundamental operations. The endomorphisms of those algebras correspond to nondeterministic linear hypersubstitutions.