ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

DOI10.1017/S1446788718000010zbMATH Open1467.20051arXiv1604.01757MaRDI QIDQ4645828FDOQ4645828

Authors: Markus Steindl 

Publication date: 11 January 2019

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Tractability and learnability arising from algebras with few subpowers
• A finite set of functions with an EXPTIME-complete composition problem
• Title not available (Why is that?)
• 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 bands
• The subpower membership problem for Mal'cev algebras
• The subpower membership problem for semigroups

Cited In (7)

• Algebras from congruences
• 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)