PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | 23 | 1 | 31-43
Tytuł artykułu

Complexity of hypersubstitutions and lattices of varieties

Treść / Zawartość
Warianty tytułu
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.
Rocznik
Tom
23
Numer
1
Strony
31-43
Opis fizyczny
Daty
wydano
2003
otrzymano
2002-11-12
poprawiono
2002-11-18
poprawiono
2003-02-11
Twórcy
  • Universität Potsdam Institut für Mathematik, D-14415 Potsdam, PF 601553, Germany
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1062
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.