×

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.)
PDF BibTeX XML Cite
Full Text: DOI