## Rank problems for composite transformations.(English)Zbl 0831.20089

Let $$(X,F)$$ be a pair consisting of a finite set $$X$$ and a set $$F$$ of transformations of $$X$$, and let $$\langle F\rangle$$ and $$F^{(l)}$$ denote, respectively, the semigroup generated by $$F$$ and the part of $$\langle F\rangle$$ consisting of the transformations determined by a generator sequence of length no more than a given integer $$l$$. We show the following:
$$\bullet$$ The problem whether or not, for a given pair $$(X,F)$$ and a given integer $$r$$, there is an idempotent transformation of rank $$r$$ in $$\langle F\rangle$$ is PSPACE-complete.
$$\bullet$$ For each fixed $$r\geq 1$$, it is decidable in a polynomial time, for a given pair $$(X,F)$$, whether or not $$\langle F\rangle$$ contains an idempotent transformation of rank $$r$$, and if yes then a generator sequence of polynomial length composing to an idempotent transformation of rank $$r$$ can be obtained in a polynomial time.
$$\bullet$$ For each fixed $$r\geq 1$$, the problem whether or not, for a given $$(X,F)$$ and $$l$$, there is an idempotent transformation of rank $$r$$ in $$F^{(l)}$$ is NP-complete.
$$\bullet$$ For each fixed $$r\geq 2$$, to decide, for a given $$(X,F)$$, whether or not $$\langle F\rangle$$ contains a transformation of rank $$r$$ is NP-hard.

### MSC:

 20M20 Semigroups of transformations, relations, partitions, etc. 20M05 Free semigroups, generators and relations, word problems 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: