Abstract. In this paper we continue the study, initiated in [4], of finite semigroups having a small number of term operations, that is, whose $p_n$-sequences are bounded above by a polynomial function of $n$. We characterize finite semigroups whose $p_n$-sequences are bounded above by a polynomial of a given degree. Further, we show that, given a finite semigroup $S$ with a polynomially bounded $p_n$-sequence, the least natural $k$ for which the inequality $p_n(S)\leq cn^k$ holds is effectively computable in polynomial time. Also, we elaborate the structural features of the considered class of finite semigroups.
AMS Subject Classification
(1991): 08A40, 20M07, 20M10
Keyword(s):
semigroup,
term operation,
p_n,
-sequence
Received September 24, 2001, and in final form January 24, 2002. (Registered under 2829/2009.)
|