Goralčík, Pavel; Koubek, Václav Rank problems for composite transformations. (English) Zbl 0831.20089 Int. J. Algebra Comput. 5, No. 3, 309-316 (1995). 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. Reviewer: P.Goralčík (Mont Saint Aignan) Cited in 9 Documents 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.) Keywords:decidable in polynomial time; generator sequences; idempotent transformations PDFBibTeX XMLCite \textit{P. Goralčík} and \textit{V. Koubek}, Int. J. Algebra Comput. 5, No. 3, 309--316 (1995; Zbl 0831.20089) Full Text: DOI