Complexity of terms, composition, and hypersubstitution.
Functional completeness in pseudocomplemented de Morgan algebras
A characterization of Sheffer functions by hyperidentities.
Nd-solid varieties
A non-deterministic hypersubstitution maps any operation symbol of a tree language of type τ to a set of trees of the same type, i.e. to a tree language. Non-deterministic hypersubstitutions can be extended to mappings which map tree languages to tree languages preserving the arities. We define the application of a non-deterministic hypersubstitution to an algebra of type τ and obtain a class of derived algebras. Non-deterministic hypersubstitutions can also be applied to equations of type τ. Formally,...
On sets related to maximal clones
For an arbitrary h-ary relation ρ we are interested to express n-clone Polⁿρ in terms of some subsets of the set of all n-ary operations Oⁿ(A) on a finite set A, which are in general not clones but we can obtain Polⁿρ from these sets by using intersection and union. Therefore we specify the concept a function preserves a relation and moreover, we study the properties of this new concept and the connection between these sets and Polⁿρ. Particularly we study for arbitrary partial order relations,...
Hypersatisfaction of formulas in agebraic systems
In [2] the theory of hyperidentities and solid varieties was extended to algebraic systems and solid model classes of algebraic systems. The disadvantage of this approach is that it needs the concept of a formula system. In this paper we present a different approach which is based on the concept of a relational clone. The main result is a characterization of solid model classes of algebraic systems. The results will be applied to study the properties of the monoid of all hypersubstitutions of an...
Regular elements and Green's relations in Menger algebras of terms
Defining an (n+1)-ary superposition operation on the set of all n-ary terms of type τ, one obtains an algebra of type (n+1,0,...,0). The algebra n-clone τ is free in the variety of all Menger algebras ([9]). Using the operation there are different possibilities to define binary associative operations on the set and on the cartesian power . In this paper we study idempotent and regular elements as well as Green’s relations in semigroups of terms with these binary associative operations...
Binary relations on the monoid of V-proper hypersubstitutions
In this paper we consider different relations on the set P(V) of all proper hypersubstitutions with respect to a given variety V and their properties. Using these relations we introduce the cardinalities of the corresponding quotient sets as degrees and determine the properties of solid varieties having given degrees. Finally, for all varieties of bands we determine their degrees.
Hyperidentities in many-sorted algebras
The theory of hyperidentities generalizes the equational theory of universal algebras and is applicable in several fields of science, especially in computers sciences (see e.g. [2,1]). The main tool to study hyperidentities is the concept of a hypersubstitution. Hypersubstitutions of many-sorted algebras were studied in [3]. On the basis of hypersubstitutions one defines a pair of closure operators which turns out to be a conjugate pair. The theory of conjugate pairs of additive closure operators...
T-Varieties and Clones of T-terms
The aim of this paper is to describe how varieties of algebras of type τ can be classified by using the form of the terms which build the (defining) identities of the variety. There are several possibilities to do so. In [3], [19], [15] normal identities were considered, i.e. identities which have the form x ≈ x or s ≈ t, where s and t contain at least one operation symbol. This was generalized in [14] to k-normal identities and in [4] to P-compatible identities. More generally, we select a subset...
The order of normalform hypersubstitutions of type (2)
In [2] it was proved that all hypersubstitutions of type τ = (2) which are not idempotent and are different from the hypersubstitution whichmaps the binary operation symbol f to the binary term f(y,x) haveinfinite order. In this paper we consider the order of hypersubstitutionswithin given varieties of semigroups. For the theory of hypersubstitution see [3].
Complexity of hypersubstitutions and lattices of varieties
Hypersubstitutions are mappings which map operation symbols to terms. The set of all hypersubstitutions of a given type forms a monoid with respect to the composition of operations. Together with a second binary operation, to be written as addition, the set of all hypersubstitutions of a given type forms a left-seminearring. Monoids and left-seminearrings of hypersubstitutions can be used to describe complete sublattices of the lattice of all varieties of algebras of a given type. The complexity...
Tree transformations defined by hypersubstitutions
Tree transducers are systems which transform trees into trees just as automata transform strings into strings. They produce transformations, i.e. sets consisting of pairs of trees where the first components are trees belonging to a first language and the second components belong to a second language. In this paper we consider hypersubstitutions, i.e. mappings which map operation symbols of the first language into terms of the second one and tree transformations defined by such hypersubstitutions....
Locally finite M-solid varieties of semigroups
An algebra of type τ is said to be locally finite if all its finitely generated subalgebras are finite. A class K of algebras of type τ is called locally finite if all its elements are locally finite. It is well-known (see [2]) that a variety of algebras of the same type τ is locally finite iff all its finitely generated free algebras are finite. A variety V is finitely based if it admits a finite basis of identities, i.e. if there is a finite set σ of identities such that V = ModΣ, the class of...
[unknown]
A regular hypersubstitution is a mapping which takes every -ary operation symbol to an -ary term. A variety is called regular-solid if it contains all algebras derived by regular hypersubstitutions. We determine the greatest regular-solid variety of semigroups. This result will be used to give a new proof for the equational description of the greatest solid variety of semigroups. We show that every variety of semigroups which is finitely based by hyperidentities is also finitely based by identities....
Four-part semigroups - semigroups of Boolean operations
Four-part semigroups form a new class of semigroups which became important when sets of Boolean operations which are closed under the binary superposition operation f + g := f(g,...,g), were studied. In this paper we describe the lattice of all subsemigroups of an arbitrary four-part semigroup, determine regular and idempotent elements, regular and idempotent subsemigroups, homomorphic images, Green's relations, and prove a representation theorem for four-part semigroups.
The semantical hyperunification problem
A hypersubstitution of a fixed type τ maps n-ary operation symbols of the type to n-ary terms of the type. Such a mapping induces a unique mapping defined on the set of all terms of type t. The kernel of this induced mapping is called the kernel of the hypersubstitution, and it is a fully invariant congruence relation on the (absolutely free) term algebra of the considered type ([2]). If V is a variety of type τ, we consider the composition of the natural homomorphism with the mapping induced...
-solid varieties and -free clones
The Galois correspondence between subvariety lattices and monoids of hpersubstitutions
Denecke and Reichel have described a method of studying the lattice of all varieties of a given type by using monoids of hypersubstitutions. In this paper we develop a Galois correspondence between monoids of hypersubstitutions of a given type and lattices of subvarieties of a given variety of that type. We then apply the results obtained to the lattice of varieties of bands (idempotent semigroups), and study the complete sublattices of this lattice obtained through the Galois correspondence.
Page 1