DM-GAA

ISSN 1509-9415 (print version)

ISSN 2084-0373 (electronic version)

https://doi.org/10.7151/dmgaa

Discussiones Mathematicae - General Algebra and Applications

Cite Score (2023): 0.6

SJR (2023): 0.214

SNIP (2023): 0.604

Index Copernicus (2022): 121.02

H-Index: 5

Discussiones Mathematicae - General Algebra and Applications

PDF

Discussiones Mathematicae General Algebra and Applications 23(1) (2003) 31-43
DOI: https://doi.org/10.7151/dmgaa.1062

COMPLEXITY OF HYPERSUBSTITUTIONS AND LATTICES OF VARIETIES

Thawhat Changphas and Klaus Denecke

Universität Potsdam Institut für Mathematik
D-14415 Potsdam, PF 601553, Germany
e-mail: thacha@kku.ac.th
e-mail: kdenecke@rz.uni-potsdam.de

Abstract

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 = H2op 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 = Hnop we determine the complete lattices of all M-solid varieties of semigroups.

Keywords: hypersubstitution, left-seminearring, complexity ofa hypersubstitution, M-solid variety.

2000 Mathematics Subject Classification: 08B15, 20M07.

References

[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.

Received 12 November 2002
Revised 18 November 2002
Revised 11 February 2003

 

Close