Geodesic
Complexity of hypersubstitutions and lattices of varieties
Discussiones Mathematicae. General Algebra and Applications, Tome 23 (2003) no. 1, pp. 31-43 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 of a hypersubstitution can be measured by the complexity of the resulting terms. We prove that the set of all hypersubstitutions with a complexity greater than a given natural number forms a sub-left-seminearring of the left-seminearring of all hypersubstitutions of the considered type. Next we look to a special complexity measure, the operation symbol count op(t) of a term t and determine the greatest M-solid variety of semigroups where M = H₂^op is the left-seminearring of all hypersubstitutions for which the number of operation symbols occurring in the resulting term is greater than or equal to 2. For every n ≥ 1 and for M = Hₙ^op we determine the complete lattices of all M-solid varieties of semigroups.
Keywords: hypersubstitution, left-seminearring, complexity ofa hypersubstitution, M-solid variety 
@article{DMGAA_2003_23_1_a3,
     author = {Changphas, Thawhat and Denecke, Klaus},
     title = {Complexity of hypersubstitutions and lattices of varieties},
     journal = {Discussiones Mathematicae. General Algebra and Applications},
     pages = {31--43},
     year = {2003},
     volume = {23},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGAA_2003_23_1_a3/}
}
TY  - JOUR
AU  - Changphas, Thawhat
AU  - Denecke, Klaus
TI  - Complexity of hypersubstitutions and lattices of varieties
JO  - Discussiones Mathematicae. General Algebra and Applications
PY  - 2003
SP  - 31
EP  - 43
VL  - 23
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGAA_2003_23_1_a3/
LA  - en
ID  - DMGAA_2003_23_1_a3
ER  - 
%0 Journal Article
%A Changphas, Thawhat
%A Denecke, Klaus
%T Complexity of hypersubstitutions and lattices of varieties
%J Discussiones Mathematicae. General Algebra and Applications
%D 2003
%P 31-43
%V 23
%N 1
%U http://geodesic.mathdoc.fr/item/DMGAA_2003_23_1_a3/
%G en
%F DMGAA_2003_23_1_a3
Changphas, Thawhat; Denecke, Klaus. Complexity of hypersubstitutions and lattices of varieties. Discussiones Mathematicae. General Algebra and Applications, Tome 23 (2003) no. 1, pp. 31-43. http://geodesic.mathdoc.fr/item/DMGAA_2003_23_1_a3/

[1] Th. Changphas and K. Denecke, Green's relations on the seminearring of full hypersubstitutions of type (n), preprint 2002.

[2] K. Denecke and J. Koppitz, Pre-solid varieties of semigroups, Tatra Mt. Math. Publ. 5 (1995), 35-41.

[3] K. Denecke, J. Koppitz and N. Pabhapote, The greatest regular-solid variety of semigroups, preprint 2002.

[4] K. Denecke, J. Koppitz and S. L. Wismath, Solid varieties of arbitrary type, Algebra Universalis 48 (2002), 357-378.

[5] K. Denecke and S. L. Wismath, Hyperidentities and Clones, Gordon and Breach Science Publishers, Amsterdam 2000.

[6] K. Denecke and S. L. Wismath, Universal Algebra and Applications in Theoretical Computer Science, Chapman Hall/CRC Publishers, Boca Raton, FL, 2002.

[7] K. Denecke and S. L. Wismath, Valuations of terms, preprint 2002.