Complexity of hypersubstitutions and lattices of varieties

• Autorzy: Thawhat Changphas , Klaus Denecke
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypersubstitution; left-seminearring; complexity ofa hypersubstitution; M-solid variety

Kategorie tematyczne

• 08B15: Lattices of varieties
• 20M07: Varieties and pseudovarieties of semigroups

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae - General Algebra and Applications
• Rocznik: 2003
• Tom: 23
• Numer: 1
• Strony: 31-43

Daty

wydano

2003

otrzymano

2002-11-12

poprawiono

2002-11-18

poprawiono

2003-02-11

Twórcy

autor

Thawhat Changphas

• Universität Potsdam Institut für Mathematik, D-14415 Potsdam, PF 601553, Germany

autor

Klaus Denecke

• Universität Potsdam Institut für Mathematik, D-14415 Potsdam, PF 601553, Germany

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgaa.1062