Complexity of hypersubstitutions and lattices of varieties

Thawhat Changphas, and Klaus Denecke. "Complexity of hypersubstitutions and lattices of varieties." Discussiones Mathematicae - General Algebra and Applications 23.1 (2003): 31-43. <http://eudml.org/doc/287626>.

@article{ThawhatChangphas2003,
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 = 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.},
author = {Thawhat Changphas, Klaus Denecke},
journal = {Discussiones Mathematicae - General Algebra and Applications},
keywords = {hypersubstitution; left-seminearring; complexity ofa hypersubstitution; M-solid variety; term complexity; -solid variety; semigroup variety},
language = {eng},
number = {1},
pages = {31-43},
title = {Complexity of hypersubstitutions and lattices of varieties},
url = {http://eudml.org/doc/287626},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Thawhat Changphas
AU - Klaus Denecke
TI - Complexity of hypersubstitutions and lattices of varieties
JO - Discussiones Mathematicae - General Algebra and Applications
PY - 2003
VL - 23
IS - 1
SP - 31
EP - 43
AB - 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.
LA - eng
KW - hypersubstitution; left-seminearring; complexity ofa hypersubstitution; M-solid variety; term complexity; -solid variety; semigroup variety
UR - http://eudml.org/doc/287626
ER -