ON THE NUMBER OF OPERATIONS IN A CLONE

A clone C on a set A is a set of operations on A containing the projec tion operations and closed under composition. A combinatorial invarian t of a clone is its p(n)-sequence <p0(C), p(1)(C),...>,where p(n)(C) i s the number of essentially n-ary operations in C. We investigate the links between this invariant and structural properties of clones. It h as been conjectured that the p(n)-sequence of a clone on a finite set is either eventually strictly increasing or is bounded above by a fini te constant. We verify this conjecture for a large family of clones. A special role in our work is played by totally symmetric operations an d totally symmetric clones. We show that every totally symmetric clone on a finite set has a bounded p(n)-sequence and that it is decidable if a clone is totally symmetric.