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 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 we determine the complete lattices of all M-solid varieties of semigroups.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1062,
author = {Thawhat Changphas and Klaus Denecke},
title = {Complexity of hypersubstitutions and lattices of varieties},
journal = {Discussiones Mathematicae - General Algebra and Applications},
volume = {23},
year = {2003},
pages = {31-43},
zbl = {1069.08005},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1062}
}
Thawhat Changphas; Klaus Denecke. Complexity of hypersubstitutions and lattices of varieties. Discussiones Mathematicae - General Algebra and Applications, Tome 23 (2003) pp. 31-43. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1062/
[000] [1] Th. Changphas and K. Denecke, Green's relations on the seminearring of full hypersubstitutions of type (n), preprint 2002.
[001] [2] K. Denecke and J. Koppitz, Pre-solid varieties of semigroups, Tatra Mt. Math. Publ. 5 (1995), 35-41. | Zbl 0852.20047
[002] [3] K. Denecke, J. Koppitz and N. Pabhapote, The greatest regular-solid variety of semigroups, preprint 2002. | Zbl 1158.20030
[003] [4] K. Denecke, J. Koppitz and S. L. Wismath, Solid varieties of arbitrary type, Algebra Universalis 48 (2002), 357-378. | Zbl 1064.08006
[004] [5] K. Denecke and S. L. Wismath, Hyperidentities and Clones, Gordon and Breach Science Publishers, Amsterdam 2000. | Zbl 0960.08001
[005] [6] K. Denecke and S. L. Wismath, Universal Algebra and Applications in Theoretical Computer Science, Chapman & Hall/CRC Publishers, Boca Raton, FL, 2002.
[006] [7] K. Denecke and S. L. Wismath, Valuations of terms, preprint 2002. | Zbl 1092.08003