ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

DOI10.1017/S1446788718000010zbMath1467.20051arXiv1604.01757MaRDI QIDQ4645828

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 complexitymembership testNP-completePSPACE-completesubalgebras of powers

Mathematics Subject Classification ID

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

Related Items (3)

The subpower membership problem for bands ⋮ Algebras from congruences ⋮ Hardness results for the subpower membership problem

Cites Work

• Unnamed Item
• Unnamed Item
• A finite set of functions with an EXPTIME-complete composition problem
• Sur le produit de concatenation non ambigu
• The subpower membership problem for bands
• Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields
• THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS
• The subpower membership problem for semigroups
• Tractability and Learnability Arising from Algebras with Few Subpowers
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

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