The Cayley semigroup membership problem

DOI10.4086/TOC.2022.V018A008MaRDI QIDQ5077150zbMATH OpenOpenAlexFDO

Authors Lukas Fleischer

Publication date 18 May 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2022.v018a008

zbMATH Keywords

completenessFOLLgeneratorsmultiplication tablequasi-polynomial-size circuitssubsemigroup

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 7250165
• On the complexity of some problems on groups input as multiplication tables
• The subpower membership problem for semigroups
• The complexity of properties of transformation semigroups
• ON SEMIGROUPS WITH PSPACE-COMPLETE SUBPOWER MEMBERSHIP PROBLEM

Cited in

(3)

• The subpower membership problem for semigroups
• On the constant-depth circuit complexity of generating quasigroups
• Constant depth circuit complexity for generating quasigroups

This page was built for publication: The Cayley semigroup membership problem

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