The subpower membership problem for bands

DOI10.1016/j.jalgebra.2017.06.034zbMath1457.20044arXiv1604.01014OpenAlexW2963946891MaRDI QIDQ1682058

Markus Steindl

Publication date: 28 November 2017

Published in: Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityNP-completenessmembership testquasivarietyidempotent semigroupssubalgebras of powers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Varieties and pseudovarieties of semigroups (20M07) Free semigroups, generators and relations, word problems (20M05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

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

Uses Software

• GAP
• Semigroups

Cites Work

• Unnamed Item
• The variety of idempotent semigroups is inherently non-finitely generated.
• A finite set of functions with an EXPTIME-complete composition problem
• Certain characterizations of varieties of bands
• Varieties of Bands Revisited
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM
• 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: The subpower membership problem for bands