The subpower membership problem for semigroups

DOI10.1142/S0218196716500612zbMath1395.20033arXiv1603.09333MaRDI QIDQ5298321

Markus Steindl, Andrei A. Bulatov, Peter Mayr, Marcin Kozik

Publication date: 14 December 2016

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

semigroupmembership problemdirect power

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 (5)

The subpower membership problem for bands ⋮ Algebras from congruences ⋮ ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM ⋮ Hardness results for the subpower membership problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relationships between nondeterministic and deterministic tape complexities
• THE SUBPOWER MEMBERSHIP PROBLEM FOR MAL'CEV ALGEBRAS
• Tractability and Learnability Arising from Algebras with Few Subpowers

This page was built for publication: The subpower membership problem for semigroups