Pith. sign in

REVIEW 1 major objections 3 minor 105 references

Membership and Conjugacy in Inverse Semigroups

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every variety of finite inverse semigroups, membership and conjugacy are either easy (NC/NP, or LOGSPACE) or PSPACE-complete, with two tiny Brandt semigroups as the only obstructions.

desk verdict Strong dichotomy paper with a real but repairable gap in the membership-hardness reduction; worth serious refereeing after a fix. read the letter →

arxiv 2502.10103 v2 pith:MTVT323Y submitted 2025-02-14 cs.CC cs.FLmath.GR

Lukas Fleischer , Florian Stober , Alexander Thumm , Armin Wei{ss} This is my paper · ORCID
classification cs.CCcs.FLmath.GR MSC 20M1868Q17
keywords inversesemigroupsmembershipproblemconjugacycomplexitydichotomyBrandtsemigroupstrictPSPACE-completenessNC
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to prove a complete complexity classification of two decision problems for finite inverse semigroups: whether a given element lies in a generated inverse subsemigroup, and whether two elements are conjugate inside it. The classification is parametrized by varieties of finite inverse semigroups (classes closed under products, subsemigroups, and quotients) and by two input models: generators given as partial bijections, or the whole semigroup given by a multiplication table. The central claim is a dichotomy: in the partial bijection model, membership is in NC and conjugacy is in NP exactly for strict inverse semigroups (the smallest variety containing all groups and the five-element combinatorial Brandt semigroup), and both problems are PSPACE-complete for every larger variety; in the Cayley table model, the two problems are in LOGSPACE and NPOLYLOGTIME for Clifford semigroups and LOGSPACE-complete for every variety containing the combinatorial Brandt semigroup B2. This matters because it draws a sharp, structural line between invertible computation that can be solved in parallel or logarithmic space and invertible computation that is as hard as any problem in polynomial space, and it transfers the same line to automata intersection, subpower membership, minimum generating sets, and equations.

What carries the argument

The critical objects are the combinatorial Brandt semigroup B2 (five elements: all partial bijections of a two-element set of rank at most one) and its monoid B1_2 with an identity adjoined. B2 is the obstruction to LOGSPACE-easiness in the Cayley table model; B1_2 is the obstruction to NC/NP-easiness in the partial bijection model. The reduction for strict inverse semigroups is carried by the Munn graph M($\Delta$;Sigma): given a U-invariant set of points $\Delta$, its vertices are idempotents e_Delta u u-bar for those generators u whose domain meets every orbit in $\Delta$, and an edge labeled u joins e_Delta u u-bar to e_Delta u-bar u. Paths in this graph encode conjugation of idempotents, and its connected components correspond to the natural equivalence classes of the semigroup; this lets the authors reduce membership and conjugacy in U to the corresponding problems in a single subgroup, and then to permutation groups. In the Cayley table model the key mechanism is the observation that strongly connected components of the Cayley graph of an inverse semigroup are undirected, reducing to undirected graph accessibility; for Clifford semigroups, polylogarithmic straight-line programs give the NPOLYLOGTIME upper bounds.

What would settle it

Build the reduction of Section 7 on a small PSPACE-complete NCL machine and check, for every pair of configurations, that the two constructed idempotents are conjugate in the generated subsemigroup if and only if the configurations are connected by transitions; any mismatch would refute the gadget behind Theorem 57 and Corollary C. Equally conclusive would be a variety V not contained in SIS for which the partial-bijection membership problem can be solved in NP.

Watch

Extended reading notes

Core claim

The paper's main result is a dichotomy for the partial bijection model (Theorem B). If the variety V of finite inverse semigroups is contained in the variety SIS of strict inverse semigroups, then the membership problem membPB(V) is in NC and the conjugacy problem conjPB(V) is in NP. If V is not contained in SIS, which happens exactly when V contains the six-element combinatorial Brandt monoid B1_2, then both problems are PSPACE-complete. The companion Theorem A gives the Cayley table model: for V contained in the Clifford semigroups (where every element commutes with its inverse) both problems are in NPOLYLOGTIME and in L; otherwise, when V contains B2, both are L-complete. The paper also draws the consequences: intersection non-emptiness for inverse automata is PSPACE-complete even with two states, the subpower membership problem is in NC exactly for strict inverse semigroups and PSPACE-complete otherwise, and minimum generating set and equation satisfiability are in NP for strict inverse semigroups and PSPACE-complete otherwise.

Load-bearing premise

The dichotomy rests on a black-box structural fact: every variety of finite inverse semigroups is either contained in the strict inverse semigroups or contains the six-element combinatorial Brandt monoid, and the paper does not prove that fact itself.

Editorial extensions

If this is right

  • Two-state inverse automata have a PSPACE-complete intersection non-emptiness problem, so the hardness of invertible computation does not require many states.
  • For any inverse semigroup S, the subpower membership problem is solved in NC when S is strict and is PSPACE-complete otherwise; in particular there is no NP-complete intermediate case for inverse semigroups.
  • The minimum generating set problem and the equation satisfiability problem are in NP for varieties of strict inverse semigroups and PSPACE-complete for every other variety.
  • In the Cayley table model, membership and conjugacy are in NPOLYLOGTIME and LOGSPACE for Clifford varieties and LOGSPACE-complete otherwise; a variety of finite inverse semigroups admits polylogarithmic straight-line programs if and only if it consists of Clifford semigroups.
  • Within the easy side of the partial bijection model, the classification refines to AC0 for semilattices, L-completeness for the variety generated by B2, and NC/NP with L-hardness otherwise.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same B1_2 gadget is likely to make many other reachability-style problems over inverse semigroups PSPACE-complete exactly outside SIS, so the dichotomy may extend to rational subset membership and related problems without new ideas.
  • The two-state bound in Corollary C cannot be lowered to one state, since one-state inverse automata do not support the construction; a direct proof of that optimality would close the statement.
  • Making the lattice classification used in Proposition 6 constructive would turn the dichotomy into a decision procedure for the complexity class of a variety, since the algorithmic reductions themselves are already explicit.
  • A similar dichotomy for regular *-semigroups, posed as an open problem in the paper, would likely hinge on finding the analogues of B2 and B1_2 in that richer lattice; the NCL encoding used here is a natural template.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 3 minor

Summary. The paper studies the membership and conjugacy problems for finite inverse semigroups in the Cayley table model and in the partial bijection model, parametrized by varieties of finite inverse semigroups. The main results are dichotomies: in the Cayley table model, both problems are in NPOLYLOGTIME and in L for Clifford varieties and L-complete otherwise (Theorem A); in the partial bijection model, they are in NC (membership) and NP (conjugacy) for strict inverse semigroups and PSPACE-complete otherwise (Theorem B). The proof machinery includes an L-reduction of strict inverse semigroups to groups via Munn graphs, hardness reductions from NCL using the combinatorial Brandt monoid B1_2, and consequences for intersection non-emptiness of two-state inverse automata, subpower membership, minimum generating set, and equation satisfiability.

Significance. If the results stand, the paper provides a nearly complete complexity classification for two central algorithmic problems on finite inverse semigroups, sharpening earlier PSPACE-completeness results of Birget–Margolis and Jack and matching the group bounds of Babai–Luks–Seress. The main theorems come with full proofs, the reductions to ugap, NCL, and permutation-group membership are substantial, and the corollaries concerning two-state inverse automata and subpower membership are independently interesting. The reliance on the published pseudovariety lattice classification (Proposition 6) is a black box, but it is a well-attributed external result and I do not treat it as a gap. However, as detailed below, one load-bearing step in the membership-hardness part of Theorem B is not proved as written, so the dichotomy is not yet fully established.

major comments (1)
  1. [Section 7.1, proof of Theorem 57 (membership half)] The reduction defines U'_Gamma = <Sigma_Gamma x {1}, (e(Cs),0), (e(Ct),1)> and invokes Lemma 55 to conclude that (e(Ct),0) in U'_Gamma iff e(Cs) >=_J^{U_Gamma} e(Ct). Lemma 55, as stated and proved, applies only to a semigroup generated by (es,0) and U x {1}; it does not permit the extra generator (e(Ct),1). Because (e(Ct),1) is present, the converse direction of Lemma 55 yields only a factorization e(Ct)=u e(Cs) v with u,v in <U_Gamma, e(Ct)>^1, not with u,v in U_Gamma^1. Thus the claimed equivalence with the relative J-order in U_Gamma is not established, and the PSPACE-hardness of E-memb^sharp_PB(BM) is unproven as written. This step is load-bearing for the membership lower bound in Theorem B when V is not contained in SIS. Note that the mere fact that e(Cs), e(Ct) need not lie in U_Gamma is not by itself the obstruction: the proof of Lemma 55 actually works for relative J with idempotents of the ambient semigroup. The real issue is the extra generator (e(Ct),1). The gap appears repairable: one can remove the generator (e(Ct),1) and use a relative-J version of Lemma 55, or alternatively derive hardness of membPB(BM) from the independently proved PSPACE-completeness of the subpower membership problem for B1_2 (Theorem 59 / Corollary 61). Please repair the reduction or restructure the proof to make the dependency explicit.
minor comments (3)
  1. [Section 8.1] The introductory paragraph of the minimum generating set section is duplicated almost verbatim; please remove the repetition.
  2. [Section 2.6 and Lemma 55] Lemma 55 is stated with the hypothesis es, et in E(U), but its proof establishes the relative-J version for idempotents of the ambient semigroup; please restate the lemma in the more general form to match its intended use and avoid ambiguity about the J-order being relative to U.
  3. [Propositions 51 and 52] Several displayed formulas involving inverses appear to be missing overbars in the text (e.g., the condition in Proposition 52 should read y u \bar u \bar y t = t). Please ensure all inverse symbols render correctly.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the dichotomy theorems are built on external black-box lattice facts, self-contained Munn-graph reductions, and direct NCL encodings; self-citations are auxiliary, not load-bearing.

full rationale

The paper's central claims are not circular. Theorem A's NPOLYLOGTIME upper bound for Clifford semigroups is imported from Fleischer [35,36], but that is published, independently proved external work, and the paper also re-proves the needed SLP bound as Lemma 24 from Babai–Szemerédi's Reachability Lemma. The L upper bounds and L-hardness for non-Clifford varieties are direct reductions to/from ugap using Green's relations and the Brandt semigroup B2, all self-contained. Theorem B's SIS upper bounds reduce membership and conjugacy to the group case via self-contained Munn-graph machinery (Lemmas 33–47), with no fitted parameter and no target quantity defined in terms of the problem's answer. The PSPACE-hardness half is a direct polynomial-time reduction from NCL to idempotent conjugacy and membership in BM via a local encoding into products of B1_2, not a renaming of a known result. The dichotomy also uses Proposition 6 (Djadchenko/Kleiman/Hall–Johnston) as an external structural classification of inverse-semigroup varieties; this is a black-box lattice fact, but it is not equivalent to the complexity theorem and is not supplied by the present authors. Self-citations to the first author's dissertation and to Collins–Grochow–Levet–Weiss occur, but each is used as an external component with its own proof, so none makes the derivation circular. One possible correctness gap should be weighed separately: in Theorem 57, Section 7.1, the final step applies Lemma 55 with e(Cs), e(Ct) as idempotents of U_Gamma, but those configuration idempotents are elements of S_Gamma and need not lie in U_Gamma; if that gap is real, the PSPACE-hardness proof has a missing argument. This is a proof-completeness and correctness risk, not circularity: it does not identify a predicted quantity with an input by construction. Therefore the circularity score remains low.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claims rest on established results in complexity theory and semigroup theory, most notably Reingold's theorem, the Babai-Luks-Seress NC algorithm, the Babai-Szemeredi Reachability Lemma, the lattice classification of pseudovarieties of inverse semigroups, and the PSPACE-completeness of NCL. No free parameters or new postulated entities appear. The paper's own Munn graph machinery is a proof tool, not an entity with independent falsifiable content.

assumptions (7)
  • standard math Reingold's theorem: undirected graph accessibility ugap is in L.
    Invoked as Theorem 8; used in Propositions 51 and 52 for the L upper bounds, and in Theorem 41 for the L-reduction from SIS to groups.
  • standard math Babai-Luks-Seress: membership in permutation groups is in NC.
    Used in Proposition 16 and Corollary 42 to get membPB(G) in NC and hence membPB(SIS) in NC.
  • standard math Babai-Szemeredi Reachability Lemma: every element of a finite group is computed by an SLP of length O(log^2 |G|).
    Used in Lemma 14 to derive NPOLYLOGTIME upper bounds for groups and Clifford semigroups, and the NP upper bound for conjugacy.
  • standard math Pseudovariety lattice classification: for every variety V of finite inverse semigroups, either BM is contained in V or V is contained in SIS; either BS is contained in V or V is contained in Cl; either Sl is contained in V or V is contained in G.
    Used as Proposition 6 throughout the proofs of Theorems A and B to reduce the analysis to the two extremal cases.
  • standard math Hearn-Demaine: the configuration-to-configuration problem for non-deterministic constraint logic (NCL) is PSPACE-complete.
    Used in Section 7.1 to prove PSPACE-hardness of idempotent membership and conjugacy for BM, and hence for any variety outside SIS.
  • standard math Goldmann-Russell: deciding whether a single equation has a solution over a fixed non-solvable group is NP-complete.
    Used in Section 8.2 to establish NP-hardness of eqn for varieties outside Gsol or BS.
  • standard math Every finite inverse semigroup embeds into the symmetric inverse monoid on its underlying set (Preston-Wagner representation), and the embedding is AC0-computable from the Cayley table.
    Used in Lemma 7 to transfer AC0-reductions from the Cayley table model to the partial bijection model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Membership and Conjugacy in Inverse Semigroups." pith.science (2026). https://pith.science/paper/MTVT323Y

@misc{pith2026250210103,
  author       = {Pith},
  title        = {Pith review of: Membership and Conjugacy in Inverse Semigroups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MTVT323Y}},
  note         = {Machine review of arXiv:2502.10103}
}
read the original abstract

The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the membership problem, as well as the conjugacy problem, for finite inverse semigroups. The closely related membership problem for finite semigroups has been shown to be PSPACE-complete in the transformation model by Kozen (1977) and NL-complete in the Cayley table model by Jones, Lien, and Laaser (1976). In the partial bijection model, the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-complete by Birget and Margolis (2008) and by Jack (2023). Here we present a more detailed analysis of the complexity of the membership and conjugacy problems parametrized by varieties of finite inverse semigroups. We establish dichotomy theorems for the partial bijection model and for the Cayley table model. In the partial bijection model these problems are in NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general LOGSPACE-algorithms as well as NPOLYLOGTIME upper bounds for Clifford semigroups and LOGSPACE-completeness otherwise. Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semi-group and PSPACE-complete otherwise; the minimum generating set and the equation satisfiability problems are in NP for varieties of finite strict inverse semigroups and PSPACE-complete otherwise.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

105 extracted references · 53 canonical work pages

  1. [1]

    J. Almeida. Finite Semigroups and Universal Algebra . World Scientific, Singapore, 1994

    1994

  2. [2]

    Almeida, M

    J. Almeida, M. V. Volkov, and S. V. Goldberg. Complexity of the identity checking problem for finite semigroups. J. Math. Sci. , 158(5):605--614, 2009. https://doi.org/10.1007/s10958-009-9397-z doi:10.1007/s10958-009-9397-z

    work page doi:10.1007/s10958-009-9397-z 2009

  3. [3]

    Araújo, M

    J. Araújo, M. Kinyon, and J. Konieczny. Conjugacy in inverse semigroups. J. Algebra , 533:142--173, 2019. https://doi.org/10.1016/j.jalgebra.2019.05.022 doi:10.1016/j.jalgebra.2019.05.022

    work page doi:10.1016/j.jalgebra.2019.05.022 2019

  4. [4]

    Arora and B

    S. Arora and B. Barak. Computational Complexity -- A Modern Approach . Cambridge University Press, 2009

    2009

  5. [5]

    Arrighi, H

    E. Arrighi, H. Fernau, S. Hoffmann, M. Holzer, I. Jecker, M. de Oliveira Oliveira, and P. Wolf. On the complexity of intersection non-emptiness for star-free language classes. In FSTTCS 2021, Proceedings , volume 213 of LIPIcs , pages 34:1--34:15. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Informatik, 2021. https://doi.org/10.4230/LIPICS.FSTTCS.2021.34 ...

    doi:10.4230/lipics.fsttcs.2021.34 2021

  6. [6]

    Arvind and J

    V. Arvind and J. Tor \' a n. The complexity of quasigroup isomorphism and the minimum generating set problem. In ISAAC 2006, Proceedings , volume 4288 of Lecture Notes in Computer Science , pages 233--242. Springer, 2006. https://doi.org/10.1007/11940128\_25 doi:10.1007/11940128\_25

    doi:10.1007/11940128 2006

  7. [7]

    Babai, E

    L. Babai, E. M. Luks, and \' A . Seress. Permutation groups in NC . In STOC 1987, Proceedings , STOC '87, pages 409--420, 1987. https://doi.org/10.1145/28395.28439 doi:10.1145/28395.28439

    work page arXiv 1987

  8. [8]

    Babai and E

    L. Babai and E. Szemer\'edi. On the complexity of matrix group problems I . In FOCS 1984, Proceedings , pages 229--240, Oct 1984. https://doi.org/10.1109/SFCS.1984.715919 doi:10.1109/SFCS.1984.715919

    work page arXiv 1984

Show all 105 references
  1. [9]

    D. A. M. Barrington, P. Kadau, K.-J. Lange, and P. McKenzie. On the complexity of some problems on groups input as multiplication tables. J. Comput. Syst. Sci. , 63(2):186--200, 2001. https://doi.org/10.1006/jcss.2001.1764 doi:10.1006/jcss.2001.1764

    2001

  2. [10]

    D. A. M. Barrington and P. McKenzie. Oracle branching programs and Logspace versus P . Inform. and Comput. , 95(1):96--115, 1991. https://doi.org/10.1016/0890-5401(91)90017-V doi:10.1016/0890-5401(91)90017-V

    1991 doi

  3. [11]

    D. A. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Th \' e rien. Equation satisfiability and program satisfiability for finite monoids. In MFCS 2000, Proceedings , volume 1893 of Lecture Notes in Computer Science , pages 172--181. Springer, 2000. https://doi.org/10....

    doi

  4. [12]

    M. Beaudry. Membership testing in commutative transformation semigroups. Inf. Comput. , 79(1):84--93, 1988. https://doi.org/10.1016/0890-5401(88)90018-1 doi:10.1016/0890-5401(88)90018-1

    1988 doi

  5. [13]

    M. Beaudry. Membership Testing in Transformation Monoids . PhD thesis, McGill University, Montreal, Quebec, 1988

    1988

  6. [14]

    Beaudry, P

    M. Beaudry, P. McKenzie, and D. Th \' e rien. The membership problem in aperiodic transformation monoids. J. ACM , 39(3):599--616, 1992. https://doi.org/10.1145/146637.146661 doi:10.1145/146637.146661

    1992

  7. [15]

    P. C. Bell, M. Hirvensalo, and I. Potapov. The identity problem for matrix semigroups in SL _2( Z ) is NP -complete. In SODA 2017, Proceedings , pages 187--206. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.13 doi:10.1137/1.9781611974782.13

    2017 doi

  8. [16]

    Birget , S

    J.-C. Birget , S. Margolis , J. Meakin , and P. Weil . PSPACE-completeness of certain algorithmic problems on the subgroups of free groups . In ICALP 1994, Proceedings , volume 820 of Lecture Notes in Computer Science , pages 274--285, Berlin, 1994. Springer. Journal version i...

    1994 doi

  9. [17]

    Birget and S

    J.-C. Birget and S. W. Margolis. Two-letter group codes that preserve aperiodicity of inverse finite automata. Semigroup Forum , 76(1):159--168, 2008. https://doi.org/10.1007/s00233-007-9024-6 doi:10.1007/s00233-007-9024-6

    2008 doi

  10. [18]

    Blondin, A

    M. Blondin, A. Krebs, and P. McKenzie. The complexity of intersecting finite automata having few final states. Electron. Colloquium Comput. Complex. , TR12-090 , 2012. URL: https://eccc.weizmann.ac.il/report/2012/090

    2012

  11. [19]

    Bulatov, M

    A. Bulatov, M. Kozik, P. Mayr, and M. Steindl. The subpower membership problem for semigroups. Int. J. Algebra Comput. , 26(7):1435--1451, 2016. https://doi.org/10.1142/S0218196716500612 doi:10.1142/S0218196716500612

    2016 doi

  12. [20]

    Bulatov, P

    A. Bulatov, P. Mayr, and \' A . Szendrei. The subpower membership problem for finite algebras with cube terms. Log. Methods Comput. Sci. , 15(1), 2019. https://doi.org/10.23638/LMCS-15(1:11)2019 doi:10.23638/LMCS-15(1:11)2019

    2019 doi

  13. [21]

    Choffrut and J

    C. Choffrut and J. Karhum \" a ki. Some decision problems on integer matrices. RAIRO Theor. Informatics Appl. , 39(1):125--131, 2005. https://doi.org/10.1051/ITA:2005007 doi:10.1051/ITA:2005007

    2005 doi

  14. [22]

    A. H. Clifford and G. B. Preston. The algebraic theory of semigroups , volume 1,2. American Mathematical Society, 1961,1967

    1961

  15. [23]

    N. A. Collins, J. A. Grochow, M. Levet, and A. Wei . Constant depth circuit complexity for generating quasigroups. In ISSAC 2024, Proceedings , pages 198--207. ACM , 2024. https://doi.org/10.1145/3666000.3669691 doi:10.1145/3666000.3669691

    2024

  16. [24]

    N. A. Collins, J. A. Grochow, M. Levet, and A. Wei . On the constant-depth circuit complexity of generating quasigroups. CoRR , abs/2402.00133, 2024. https://doi.org/10.48550/ARXIV.2402.00133 doi:10.48550/ARXIV.2402.00133

    2024 doi arXiv

  17. [25]

    S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. J. Algorithms , 8(3):385--394, 1987. https://doi.org/10.1016/0196-6774(87)90018-6 doi:10.1016/0196-6774(87)90018-6

    1987 doi

  18. [26]

    de Oliveira Oliveira and M

    M. de Oliveira Oliveira and M. Wehar. On the fine grained complexity of finite automata non-emptiness of intersection. In DLT 2020, Proceedings , volume 12086 of Lecture Notes in Computer Science , pages 69--82. Springer, 2020. https://doi.org/10.1007/978-3-030-48516-0\_6 doi:...

    2020 doi

  19. [27]

    M. Dehn. Ueber unendliche diskontinuierliche G ruppen. Math. Ann. , 71:116--144, 1911

    1911

  20. [28]

    Diekert, I

    V. Diekert, I. Potapov, and P. Semukhin. Decidability of membership problems for flat rational subsets of GL(2,Z) and singular matrices. SIAM J. Comput. , 2024. To Appear

    2024

  21. [29]

    G. G. Djadchenko. On identities in monogenic inverse semigroups. Algebra and Theory of Numbers, Nal c ik , 2:57--77, 1977

    1977

  22. [30]

    R. Dong. Semigroup algorithmic problems in metabelian groups. In STOC 2024, Proceedings , pages 884--891. ACM , 2024. https://doi.org/10.1145/3618260.3649609 doi:10.1145/3618260.3649609

    2024

  23. [31]

    Eilenberg

    S. Eilenberg. Automata, Languages, and Machines , volume B. Academic Press, New York and London, 1976

    1976

  24. [32]

    Elliott, A

    L. Elliott, A. Levine, and J. D. Mitchell. Computing congruences of finite inverse semigroups. CoRR , abs/2406.09281, 2024. https://doi.org/10.48550/ARXIV.2406.09281 doi:10.48550/ARXIV.2406.09281

    2024 doi

  25. [33]

    Fernau, S

    H. Fernau, S. Hoffmann, and M. Wehar. Finite automata intersection non-emptiness: Parameterized complexity revisited. CoRR , abs/2108.05244, 2021. https://doi.org/10.48550/ARXIV.2108.05244 doi:10.48550/ARXIV.2108.05244

    2021 doi arXiv

  26. [34]

    Fernau and A

    H. Fernau and A. Krebs. Problems on finite automata and the exponential time hypothesis. Algorithms , 10(1):24, 2017. https://doi.org/10.3390/A10010024 doi:10.3390/A10010024

    2017 doi

  27. [35]

    u r F ormale M ethoden der I nformatik, U niversit \

    L. Fleischer. Algorithms and complexity results for finite semigroups . Dissertation, Institut f \"u r F ormale M ethoden der I nformatik, U niversit \"a t S tuttgart, 2019. https://doi.org/10.18419/opus-10339 doi:10.18419/opus-10339

    2019 doi

  28. [36]

    Fleischer

    L. Fleischer. The C ayley semigroup membership problem. Theory Comput. , 18:1--18, 2022. https://doi.org/10.4086/toc.2022.v018a008 doi:10.4086/toc.2022.v018a008

    2022 doi

  29. [37]

    Furst, J

    M. Furst, J. Hopcroft, and E. Luks. Polynomial-time algorithms for permutation groups. In FOCS 1980, Proceedings , pages 36--41, Oct 1980. https://doi.org/10.1109/SFCS.1980.34 doi:10.1109/SFCS.1980.34

    1980 doi

  30. [38]

    M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory , 17(1):13--27, 1984

    1984

  31. [39]

    Földvári and G

    A. Földvári and G. Horváth. The complexity of the equation solvability and equivalence problems over finite groups. Internat. J. Algebra Comput. , 30(03):607--623, 2020. https://doi.org/10.1142/S0218196720500137 doi:10.1142/S0218196720500137

    2020 doi

  32. [40]

    S. Go ab. \"U ber den B egriff der '' P seudogruppe von T ransformationen''. Math. Ann. , 116(1):768--780, 1939. https://doi.org/10.1007/BF01597390 doi:10.1007/BF01597390

    1939 doi

  33. [41]

    Goldmann and A

    M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Inf. Comput. , 178(1):253--262, 2002. https://doi.org/10.1006/inco.2002.3173 doi:10.1006/inco.2002.3173

    2002

  34. [42]

    R. D. Gray. Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups. Invent. Math. , 219:987--1008, 2020. https://doi.org/10.1007/s00222-019-00920-2 doi:10.1007/s00222-019-00920-2

    2020 doi

  35. [43]

    J. A. Green. On the structure of semigroups. Ann.\ Math.\ (2) , 54:163--172, 1951

    1951

  36. [44]

    T. E. Hall and K. G. Johnston. The lattice of pseudovarieties of inverse semigroups. Pacific J. Math. , 138(1):73--88, 1989. URL: http://projecteuclid.org/euclid.pjm/1102650281

    1989

  37. [45]

    J. H stad. Almost optimal lower bounds for small depth circuits. In STOC 1986, Proceedings , STOC '86, pages 6--20, New York, NY, USA, 1986. ACM. https://doi.org/10.1145/12130.12132 doi:10.1145/12130.12132

    1986

  38. [46]

    R. A. Hearn and E. D. Demaine. P SPACE -completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoret. Comput. Sci. , 343(1-2):72--96, 2005. https://doi.org/10.1016/j.tcs.2005.05.008 doi:10.1016/j.tcs.2005.05.008

    2005 doi

  39. [47]

    Holzer and M

    M. Holzer and M. Kutrib. Descriptional and computational complexity of finite automata --- a survey. Inf. Comput. , 209(3):456--470, 2011. https://doi.org/10.1016/j.ic.2010.11.013 doi:10.1016/j.ic.2010.11.013

    2011 doi

  40. [48]

    J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation . Addison-Wesley, 1979

    1979

  41. [49]

    P. M. Idziak, P. Kawalek, J. Krzaczkowski, and A. Wei . Satisfiability problems for finite groups. In ICALP 2022, Proceedings , volume 229 of LIPIcs , pages 127:1--127:20. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Informatik, 2022. https://doi.org/10.4230/LIPICS.ICALP.2022....

    2022 doi

  42. [50]

    P. M. Idziak, P. Kawalek, J. Krzaczkowski, and A. Wei . Equation satisfiability in solvable groups. Theory Comput. Syst. , 68(4):740--757, 2024. https://doi.org/10.1007/S00224-022-10082-Z doi:10.1007/S00224-022-10082-Z

    2024 doi

  43. [51]

    T. Jack. On the complexity of inverse semigroup conjugacy. Semigroup Forum , 106(3):618--632, 2023. https://doi.org/10.1007/s00233-023-10349-y doi:10.1007/s00233-023-10349-y

    2023 doi

  44. [52]

    N. D. Jones and W. T. Laaser. Complete problems for deterministic polynomial time. Theoret. Comput. Sci. , 3(1):105--117, 1976. https://doi.org/10.1016/0304-3975(76)90068-2 doi:10.1016/0304-3975(76)90068-2

    1976 doi

  45. [53]

    N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Math. Syst. Theory , 10(1):1--17, Dec 1976. https://doi.org/10.1007/BF01683259 doi:10.1007/BF01683259

    1976 doi

  46. [54]

    Karakostas, R

    G. Karakostas, R. J. Lipton, and A. Viglas. On the complexity of intersecting finite state automata and NL versus NP . Theor. Comput. Sci. , 302(1-3):257--274, 2003. https://doi.org/10.1016/S0304-3975(02)00830-7 doi:10.1016/S0304-3975(02)00830-7

    2003 doi

  47. [55]

    Kisielewicz

    A. Kisielewicz. Complexity of semigroup identity checking. Internat. J. Algebra Comput. , 14(4):455--464, 2004. https://doi.org/10.1142/S0218196704001840 doi:10.1142/S0218196704001840

    2004 doi

  48. [56]

    E. I. Kleiman. The lattice of varieties of inverse semigroups. Ivz. Vys s . U c bn. Zaved. Mat. , 7:106--109, 1976

    1976

  49. [57]

    E. I. Kleiman. On basis of identities of B randt semigroups. Semigroup Forum , 13:209--218, 1977

    1977

  50. [58]

    E. I. Kleiman. Bases of identities of varieties of inverse semigroups. Sib. Math. J. , 20(4):530--543, 1979. https://doi.org/10.1007/BF00970367 doi:10.1007/BF00970367

    1979 doi

  51. [59]

    Kl \' ma

    O. Kl \' ma. Complexity issues of checking identities in finite monoids. Semigroup Forum , 79(3):435--444, 2009. https://doi.org/10.1007/s00233-009-9180-y doi:10.1007/s00233-009-9180-y

    2009 doi

  52. [60]

    Kl \' ma, P

    O. Kl \' ma, P. Tesson, and D. Th \' e rien. Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst. , 40(3):263--297, 2007. https://doi.org/10.1007/s00224-005-1279-2 doi:10.1007/s00224-005-1279-2

    2007 doi

  53. [61]

    Kompatscher

    M. Kompatscher. The subpower membership problem of 2-nilpotent algebras. In STACS 2024, Proceedings , volume 289 of LIPIcs , pages 46:1--46:17. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Informatik, 2024. https://doi.org/10.4230/LIPICS.STACS.2024.46 doi:10.4230/LIPICS.STACS.2024.46

    2024 doi

  54. [62]

    D. Kozen. Lower bounds for natural proof systems. In FOCS 1977, Proceedings , pages 254--266, Providence, Rhode Island, 1977. IEEE Computer Society Press

    1977

  55. [63]

    M. Kozik. A finite set of functions with an EXPTIME -complete composition problem. Theor. Comput. Sci. , 407(1-3):330--341, 2008. https://doi.org/10.1016/J.TCS.2008.06.057 doi:10.1016/J.TCS.2008.06.057

    2008 doi

  56. [64]

    Lange and P

    K. Lange and P. Rossmanith. The emptiness problem for intersections of regular languages. In MFCS 1992, Proceedings , pages 346--354, 1992. https://doi.org/10.1007/3-540-55808-X_33 doi:10.1007/3-540-55808-X_33

    1992 doi

  57. [65]

    M. V. Lawson. Inverse Semigroups: The Theory of Partial Symmetries . World Scientific, 1999

    1999

  58. [66]

    H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoret. Comput. Sci. , 19(2):161--187, 1982. https://doi.org/10.1016/0304-3975(82)90058-5 doi:10.1016/0304-3975(82)90058-5

    1982 doi

  59. [67]

    Lohrey, A

    M. Lohrey, A. Rosowski, and G. Zetzsche. Membership problems in finite groups. In MFCS 2022, Proceedings , volume 241 of LIPIcs , pages 71:1--71:16. Schloss Dagstuhl -- Leibniz-Zentrum f \" u r Informatik, 2022. https://doi.org/10.4230/LIPICS.MFCS.2022.71 doi:10.4230/LIPICS.MF...

    2022 doi

  60. [68]

    Lucchini and D

    A. Lucchini and D. Thakkar. The minimum generating set problem. J. Algebra , 640:117--128, 2024. https://doi.org/10.1016/j.jalgebra.2023.11.012 doi:10.1016/j.jalgebra.2023.11.012

    2024 doi

  61. [69]

    E. M. Luks. Parallel algorithms for permutation groups and graph isomorphism. In FOCS 1986, Proceedings , pages 292--302. IEEE Computer Society, 1986. https://doi.org/10.1109/SFCS.1986.39 doi:10.1109/SFCS.1986.39

    1986 doi

  62. [70]

    E. M. Luks. Permutation G roups and P olynomial- T ime C omputation. In Groups and computation ( N ew B runswick, NJ , 1991) , volume 11 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci. , pages 139--175. Amer. Math. Soc., Providence, RI, 1993. https://doi.org/10.1090/dimacs...

    1991 doi

  63. [71]

    E. M. Luks and P. McKenzie. Parallel algorithms for solvable permutation groups. J. Comput. Syst. Sci. , 37(1):39--62, 1988. https://doi.org/10.1016/0022-0000(88)90044-X doi:10.1016/0022-0000(88)90044-X

    1988 doi

  64. [72]

    S. W. Margolis and J. C. Meakin . E -unitary inverse monoids and the Cayley graph of a group presentation . J. Pure Appl. Algebra , 58:45--76, 1989

    1989

  65. [73]

    P. Mayr. The subpower membership problem for M al'cev algebras. Int. J. Algebra Comput. , 22(7), 2012. https://doi.org/10.1142/S0218196712500750 doi:10.1142/S0218196712500750

    2012 doi

  66. [74]

    McKenzie and S

    P. McKenzie and S. A. Cook. The parallel complexity of abelian permutation group problems. SIAM J. Comput. , 16(5):880--909, October 1987. https://doi.org/10.1137/0216058 doi:10.1137/0216058

    1987 doi

  67. [75]

    Meakin and M

    J. Meakin and M. Sapir. The word problem in the variety of inverse semigroups with abelian covers. J. Lond. Math. Soc. (2) , 53(1):79--98, 1996

    1996

  68. [76]

    D. D. Miller and A. H. Clifford. Regular D - C lasses in S emigroups. Trans. Amer. Math. Soc. , 82(1):270--280, 1956

    1956

  69. [77]

    W. D. Munn. Free inverse semigroups. Proc. London Math. Soc. , 30:385--404, 1974

    1974

  70. [78]

    Nisan and A

    N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chic. J. Theor. Comput. Sci. , 1995, 1995. URL: http://cjtcs.cs.uchicago.edu/articles/1995/1/contents.html

    1995

  71. [79]

    T. E. Nordahl and H. E. Scheiblich. Regular * semigroups. Semigroup Forum , 16:369--378, 1978. https://doi.org/10.1007/BF02194636 doi:10.1007/BF02194636

    1978 doi

  72. [80]

    Olijnyk, V

    A. Olijnyk, V. I. Sushchansky, and J. K. Slupik. Inverse semigroups of partial automaton permutations. Int. J. Algebra Comput. , 20(7):923--952, 2010. https://doi.org/10.1142/S0218196710005960 doi:10.1142/S0218196710005960

    2010 doi

  73. [81]

    F. Otto. Conjugacy in monoids with a special C hurch- R osser presentation is decidable. Semigroup Forum , 29:223--240, 1984. https://doi.org/10.1007/BF02573327 doi:10.1007/BF02573327

    1984 doi

  74. [82]

    C. H. Papadimitriou. Computational Complexity . Addison Wesley, 1994

    1994

  75. [83]

    C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci. , 53(2):161--170, 1996. https://doi.org/10.1006/JCSS.1996.0058 doi:10.1006/JCSS.1996.0058

    1996

  76. [84]

    M. Petrich. Inverse semigroups . Pure Appl. Math. (N. Y.). John Wiley & Sons, Inc., New York, 1984

    1984

  77. [85]

    J. Pin. On the language accepted by finite reversible automata. In ICALP 1987, Proceedings , volume 267 of Lecture Notes in Computer Science , pages 237--249. Springer, 1987. https://doi.org/10.1007/3-540-18088-5\_19 doi:10.1007/3-540-18088-5\_19

    1987 doi

  78. [86]

    G. B. Preston. Representations of I nverse S emi- G roups. J. Lond. Math. Soc. (1) , 29(4):411--419, 1954. https://doi.org/10.1112/jlms/s1-29.4.411 doi:10.1112/jlms/s1-29.4.411

    1954 doi

  79. [87]

    Radionova and A

    M. Radionova and A. Okhotin. Decision problems for reversible and permutation automata. In CIAA 2024, Proceedings , volume 15015 of Lecture Notes in Computer Science , pages 302--315. Springer, 2024. https://doi.org/10.1007/978-3-031-71112-1\_22 doi:10.1007/978-3-031-71112-1\_22

    2024 doi

  80. [88]

    Rampersad and J

    N. Rampersad and J. O. Shallit. Detecting patterns in finite regular and context-free languages. Inf. Process. Lett. , 110(3):108--112, 2010. https://doi.org/10.1016/J.IPL.2009.11.002 doi:10.1016/J.IPL.2009.11.002

    2010 doi

  81. [89]

    Reingold

    O. Reingold. Undirected connectivity in log-space. J. ACM , 55(4):17:1--17:24, September 2008. https://doi.org/10.1145/1391289.1391291 doi:10.1145/1391289.1391291

    2008

  82. [90]

    Reiterman

    J. Reiterman. The B irkhoff theorem for finite algebras. Algebra Univers. , 14:1--10, 1982

    1982

  83. [91]

    J. L. Rhodes and B. Steinberg. The q -theory of finite semigroups. Springer Monographs in Mathematics. Springer, 2009

    2009

  84. [92]

    W. L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci. , 22(3):365--383, 1981. https://doi.org/10.1016/0022-0000(81)90038-6 doi:10.1016/0022-0000(81)90038-6

    1981 doi

  85. [93]

    S. Seif. The P erkins semigroup has co- NP -complete term-equivalence problem. Internat. J. Algebra Comput. , 15(2):317--326, 2005. https://doi.org/10.1142/S0218196705002293 doi:10.1142/S0218196705002293

    2005 doi

  86. [94]

    Seif and C

    S. Seif and C. Szab\' o . Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields. Semigroup Forum , 72(2):207--222, 2006. https://doi.org/10.1007/s00233-005-0510-4 doi:10.1007/s00233-005-0510-4

    2006 doi

  87. [95]

    C. C. Sims. Computational methods in the study of permutation groups. In Conference on Computational Problems in Abstract Algebra 1967, Proceedings , pages 169--183, New York, 1970. Pergamon. https://doi.org/10.1016/B978-0-08-012975-4.50020-5 doi:10.1016/B978-0-08-012975-4.50020-5

    1967 doi

  88. [96]

    R. E. Stearns, J. Hartmanis, and P. Lewis II . Hierarchies of memory limited computations. In SWCT 1965, Proceedings , pages 179--190. IEEE Computer Society, 1965. https://doi.org/10.1109/FOCS.1965.11 doi:10.1109/FOCS.1965.11

    1965 doi

  89. [97]

    M. Steindl. The subpower membership problem for bands. J. Algebra , 489:529--551, 2017. https://doi.org/10.1016/j.jalgebra.2017.06.034 doi:10.1016/j.jalgebra.2017.06.034

    2017 doi

  90. [98]

    M. Steindl. On semigroups with PSPACE -complete subpower membership problem. J. Aust. Math. Soc. , 106(1):127--142, 2019. https://doi.org/10.1017/S1446788718000010 doi:10.1017/S1446788718000010

    2019 doi

  91. [99]

    L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In STOC 1973, Proceedings , pages 1--9. ACM , 1973. https://doi.org/10.1145/800125.804029 doi:10.1145/800125.804029

    1973

  92. [100]

    Swernofsky and M

    J. Swernofsky and M. Wehar. On the complexity of intersecting regular, context-free, and tree languages. In ICALP 2015, Proceedings, Part II , volume 9135 of Lecture Notes in Computer Science , pages 414--426. Springer, 2015. https://doi.org/10.1007/978-3-662-47666-6\_33 doi:1...

    2015 doi

  93. [101]

    B. Tang. Towards Understanding Satisfiability, Group Isomorphism and Their Connections . PhD thesis, Tsinghua University, 2013

    2013

  94. [102]

    Thierrin

    G. Thierrin. Permutation automata. Math. Syst. Theory , 2(1):83--90, 1968. https://doi.org/10.1007/BF01691347 doi:10.1007/BF01691347

    1968 doi

  95. [103]

    H. Vollmer. Introduction to Circuit Complexity - A Uniform Approach . Texts Theoret. Comput. Sci. EATCS Ser. Springer, 1999. https://doi.org/10.1007/978-3-662-03927-4 doi:10.1007/978-3-662-03927-4

    1999 doi

  96. [104]

    V. V. Wagner. Generalised groups. Dokl. Akad. Nauk SSSR , 84(6):1119--1122, 1952

    1952

  97. [105]

    M. Wehar. Hardness results for intersection non-emptiness. In ICALP 2014, Proceedings, Part II , volume 8573 of Lecture Notes in Computer Science , pages 354--362. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7\_30 doi:10.1007/978-3-662-43951-7\_30

    2014 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.