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