Refine
Has Fulltext
- no (94)
Year of publication
Document Type
- Article (94) (remove)
Is part of the Bibliography
- yes (94)
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
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.
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).
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
M-solidity testing systems
(2002)
Let v be a valuation of terms of type tau, assigning to each term t of type tau a value v(t) greater than or equal to 0. Let k greater than or equal to 1 be a natural number. An identity s approximate to t of type tau is called k- normal if either s = t or both s and t have value greater than or equal to k, and otherwise is called non-k-normal. A variety V of type tau is said to be k-normal if all its identities are k-normal, and non-k-normal otherwise. In the latter case, there is a unique smallest k-normal variety N-k(A) (V) to contain V , called the k-normalization of V. Inthe case k = 1, for the usual depth valuation of terms, these notions coincide with the well-known concepts of normal identity, normal variety, and normalization of a variety. I. Chajda has characterized the normalization of a variety by means of choice algebras. In this paper we generalize his results to a characterization of the k-normalization of a variety, using k-choice algebras. We also introduce the concept of a k-inflation algebra, and for the case that v is the usual depth valuation of terms, we prove that a variety V is k-normal iff it is closed under the formation of k- inflations, and that the k-normalization of V consists precisely of all homomorphic images of k-inflations of algebras in V
An n-ary cooperation is a mapping from a nonempty set A to the nth copower of A. A clone of cooperations is a set of cooperations which is closed under superposition and contains all injections. Coalgebras are pairs consisting of a set and a set of cooperations defined on this set. We define terms for coalgebras, coidentities and cohyperidentities. These concepts will be applied to give a new solution of the completeness problem for clones of cooperations defined on a two-element set and to separate clones of cooperations by coidentities.
A finite algebra A = (A; F-A) is said to be order-primal if its clone of all term operations is the set of all operations defined on A which preserve a given partial order <= on A. In this paper we study algebraic properties of order-primal algebras for connected ordered sets (A; <=). Such order-primal algebras are constantive, simple and have no non-identical automorphisms. We show that in this case F-A cannot have only unary fundamental operations or only one at least binary fundamental operation. We prove several properties of the varieties and the quasi-varieties generated by constantive and simple algebras and apply these properties to order-primal algebras. Further, we use the properties of order-primal algebras to formulate new primality criteria for finite algebras
Edge-solid varieties
(1995)
There is a close connection between a variety and its clone. The clone of a variety is a multibased algebra, where the different universes are the sets of n-ary terms over this variety for every natural number n and where the operations describe the superposition of terms of different arities. All projections are added as nullary operations. Subvarieties correspond to homomorphic images of clones. Subclones can be described by reducts of varieties, isomorphic clones by equivalent varieties. Clone identities correspond to hyperidentities and varieties of clones to hypervarieties. Pseudovarieties are classes of finite algebras which are closed under taking of subalgebras, homomorphic images and finite direct products. Pseudovarieties are important in the theories of finite state automata, rational languages, finite semigroups and their connections. In a very natural way, there arises the question for the clone of a pseudovariety. In the present paper, we will describe this algebraic structure