Refine
Has Fulltext
- no (106)
Year of publication
Document Type
- Article (94)
- Monograph/Edited Volume (11)
- Doctoral Thesis (1)
Is part of the Bibliography
- yes (106)
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)
Institute
- Institut für Mathematik (106) (remove)
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.
Generalizing a linear expression over a vector space, we call a term of an arbitrary type tau linear if its every variable occurs only once. Instead of the usual superposition of terms and of the total many-sorted clone of all terms in the case of linear terms, we define the partial many-sorted superposition operation and the partial many-sorted clone that satisfies the superassociative law as weak identity. The extensions of linear hypersubstitutions are weak endomorphisms of this partial clone. For a variety V of one-sorted total algebras of type tau, we define the partial many-sorted linear clone of V as the partial quotient algebra of the partial many-sorted clone of all linear terms by the set of all linear identities of V. We prove then that weak identities of this clone correspond to linear hyperidentities of V.
A term t is linear if no variable occurs more than once in t. An identity s ≈ t is said to be linear if s and t are linear terms. Identities are particular formulas. As for terms superposition operations can be defined for formulas too. We define the arbitrary linear formulas and seek for a condition for the set of all linear formulas to be closed under superposition. This will be used to define the partial superposition operations on the set of linear formulas and a partial many-sorted algebra Formclonelin(τ, τ′). This algebra has similar properties with the partial many-sorted clone of all linear terms. We extend the concept of a hypersubstitution of type τ to the linear hypersubstitutions of type (τ, τ′) for algebraic systems. The extensions of linear hypersubstitutions of type (τ, τ′) send linear formulas to linear formulas, presenting weak endomorphisms of Formclonelin(τ, τ′).
The dimension of a variety V of algebras of a given type was introduced by E. Graczynska and D. Schweigert in [7] as the cardinality of the set of all derived varieties of V which are properly contained in V. In this paper, we characterize all solid varieties of dimensions 0, 1, and 2; prove that the dimension of a variety of finite type is at most N-0; give an example of a variety which has infinite dimension; and show that for every n is an element of N there is a variety with dimension n. Finally, we show that the dimension of a variety is related to the concept of the semantical kernel of a hypersubstitution and apply this connection to calculate the dimension of the class of all algebras of type tau = (n).