Complexity of Finite Semigroups

Abstract

All semigroups considered are of finite order. The results of this paper were announced in [4]. For extensive background see [5]. This paper, however, is reasonably self-contained. (X, S) denotes the finite semigroup S acting faithfully on the right of the finite set X. One of the main problems in the study of finite semigroups is to determine all ways in which coordinates can be entered into X so that the action of S on X is in triangular form. (Precise definitions given below.) An important class of semigroups, namely wreath products, are by definition already in triangular form. Let (Xj, S,) be given for j = 1, n. Let X = X, x ... x X1. Let S be the semigroup of all functions A: X X satisfying the following conditions. Triangular action (1.1). If pk: X Xk denotes the klth projection map, then for each k = 1, *n , n, there exists fk: Xk x * x X, X Xk such that