Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T16:56:44.047Z Has data issue: false hasContentIssue false

ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

Published online by Cambridge University Press:  30 May 2018

MARKUS STEINDL*
Affiliation:
Institute for Algebra, Johannes Kepler University Linz, Altenberger St 69, 4040 Linz, AustriaDepartment of Mathematics, University of Colorado Boulder, Campus Box 395, Boulder, CO 80309-0395, USA email markus.steindl@colorado.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Fix a finite semigroup $S$ and let $a_{1},\ldots ,a_{k},b$ be tuples in a direct power $S^{n}$. The subpower membership problem (SMP) for $S$ asks whether $b$ can be generated by $a_{1},\ldots ,a_{k}$. For combinatorial Rees matrix semigroups we establish a dichotomy result: if the corresponding matrix is of a certain form, then the SMP is in P; otherwise it is NP-complete. For combinatorial Rees matrix semigroups with adjoined identity, we obtain a trichotomy: the SMP is either in P, NP-complete, or PSPACE-complete. This result yields various semigroups with PSPACE-complete SMP including the six-element Brandt monoid, the full transformation semigroup on three or more letters, and semigroups of all $n$ by $n$ matrices over a field for $n\geq 2$.

Information

Type
Research Article
Copyright
© 2018 Australian Mathematical Publishing Association Inc.