{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:00Z","timestamp":1759637940804},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[1995,6]]},"abstract":"<jats:p> Let (X, F) be a pair consisting of a finite set X and a set F of transformations of X, and, let &lt;F&gt; and F<jats:sup>(l)<\/jats:sup> denote, respectively, the semigroup generated by F and the part of &lt;F&gt; consisting of the transformations determined by a generator sequence of length no more than a given integer l. We show the following: <\/jats:p><jats:p> \u2022 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 &lt;F&gt; is PSPACE-complete. <\/jats:p><jats:p> \u2022 For each fixed r\u22651, it is decidable in a polynomial time, for a given pair (X, F), whether or not &lt;F&gt; 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. <\/jats:p><jats:p> \u2022 For each fixed r\u22651, the problem whether or not, for a given (X, F) and l, there is an idempotent transformation of rank r in F<jats:sup>(l)<\/jats:sup> is NP-complete. <\/jats:p><jats:p> \u2022 For each fixed r\u22652, to decide, for a given (X, F), whether or not &lt;F&gt; contains a transformation of rank r is NP-hard. <\/jats:p>","DOI":"10.1142\/s0218196795000185","type":"journal-article","created":{"date-parts":[[2004,11,10]],"date-time":"2004-11-10T06:14:37Z","timestamp":1100067277000},"page":"309-316","source":"Crossref","is-referenced-by-count":11,"title":["RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS"],"prefix":"10.1142","volume":"05","author":[{"given":"PAVEL","family":"GORAL\u010c\u00cdK","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Rouen, LIR, Facult\u00e9 des Sciences et des Techniques, Place Emile Blondel, 76821 Mont Saint Aignan cedex, France"}]},{"given":"V\u00c1CLAV","family":"KOUBEK","sequence":"additional","affiliation":[{"name":"Charles University, Prague, MFF KU, Malostransk\u00e9 n\u00e1m. 25, 118 00 Praha 1, Czech Republic"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196795000185","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:21:39Z","timestamp":1565169699000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196795000185"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1995,6]]}},"alternative-id":["10.1142\/S0218196795000185"],"URL":"https:\/\/doi.org\/10.1142\/s0218196795000185","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}