{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T11:01:11Z","timestamp":1758279671536},"reference-count":7,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2016,11]]},"abstract":"<jats:p>Fix a finite semigroup [Formula: see text] and let [Formula: see text] be tuples in a direct power [Formula: see text]. The subpower membership problem (SMP) asks whether [Formula: see text] can be generated by [Formula: see text]. If [Formula: see text] is a finite group, then there is a folklore algorithm that decides this problem in time polynomial in [Formula: see text]. For semigroups this problem always lies in PSPACE. We show that the [Formula: see text] for a full transformation semigroup on [Formula: see text] or more letters is actually PSPACE-complete, while on [Formula: see text] letters it is in P. For commutative semigroups, we provide a dichotomy result: if a commutative semigroup [Formula: see text] embeds into a direct product of a Clifford semigroup and a nilpotent semigroup, then [Formula: see text] is in P; otherwise it is NP-complete.<\/jats:p>","DOI":"10.1142\/s0218196716500612","type":"journal-article","created":{"date-parts":[[2016,9,16]],"date-time":"2016-09-16T06:50:42Z","timestamp":1474008642000},"page":"1435-1451","source":"Crossref","is-referenced-by-count":5,"title":["The subpower membership problem for semigroups"],"prefix":"10.1142","volume":"26","author":[{"given":"Andrei","family":"Bulatov","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, BC, Canada"}]},{"given":"Marcin","family":"Kozik","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Poland"}]},{"given":"Peter","family":"Mayr","sequence":"additional","affiliation":[{"name":"Institute for Algebra, Johannes Kepler University Linz, Austria"},{"name":"Department of Mathematics, CU Boulder, USA"}]},{"given":"Markus","family":"Steindl","sequence":"additional","affiliation":[{"name":"Institute for Algebra, Johannes Kepler University Linz, Austria"},{"name":"Department of Mathematics, CU Boulder, USA"}]}],"member":"219","published-online":{"date-parts":[[2016,11,13]]},"reference":[{"key":"S0218196716500612BIB002","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198511946.001.0001","volume-title":"Fundamentals of Semigroup Theory","author":"Howie J.","year":"1995"},{"key":"S0218196716500612BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/090775646"},{"key":"S0218196716500612BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0218196716500612BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.057"},{"key":"S0218196716500612BIB007","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196712500750"},{"key":"S0218196716500612BIB008","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994"},{"key":"S0218196716500612BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196716500612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T11:30:32Z","timestamp":1718796632000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196716500612"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11]]},"references-count":7,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2016,11,13]]},"published-print":{"date-parts":[[2016,11]]}},"alternative-id":["10.1142\/S0218196716500612"],"URL":"https:\/\/doi.org\/10.1142\/s0218196716500612","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11]]}}}