ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

DOI10.1017/S1446788718000010MaRDI QIDQ4645828zbMATH OpenFDO

Authors Markus Steindl

Publication date 11 January 2019

Published in Journal of the Australian Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.01757

zbMATH Keywords

computational complexityNP-completePSPACE-completemembership testsubalgebras of powers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) General structure theory for semigroups (20M10)

Abstract: 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 $6$-element Brandt monoid, the full transformation semigroup on $3$ or more letters, and semigroups of all $n$ by $n$ matrices over a field for $nge2$.

Recommendations

• The subpower membership problem for semigroups
• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
• scientific article; zbMATH DE number 1972795
• On the membership problem for pseudovarieties of commutative semigroups
• Powers of subsets in a finite semigroup
• On subsemigroups of finitely presented semigroups
• scientific article; zbMATH DE number 1500121
• On semicomplete finite \(p\)-groups
• Subsemigroups and complexity via the presentation lemma

Cites work

• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• A finite set of functions with an EXPTIME-complete composition problem
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• Sur le produit de concatenation non ambigu
• The subpower membership problem for Mal'cev algebras
• The subpower membership problem for bands
• The subpower membership problem for semigroups
• Tractability and learnability arising from algebras with few subpowers

Cited in

(9)

• Algebras from congruences
• scientific article; zbMATH DE number 7250165 (Why is no real title available?)
• The Cayley semigroup membership problem
• THE PERKINS SEMIGROUP HAS CO-NP-COMPLETE TERM-EQUIVALENCE PROBLEM
• The subpower membership problem for semigroups
• COMBINATORIAL REES–SUSHKEVICH VARIETIES THAT ARE CROSS, FINITELY GENERATED, OR SMALL
• The subpower membership problem for bands
• Hardness results for the subpower membership problem
• The subpower membership problem for finite algebras with cube terms

This page was built for publication: ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645828)