Membership and Conjugacy in Inverse Semigroups
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 -complete in the transformation model by Kozen (1977) and -complete in the Cayley table model by Jones, Lien, and Laaser (1976). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be -complete in the partial bijection model 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 (resp. for conjugacy) for strict inverse semigroups and -complete otherwise. In the Cayley table model we obtain general -algorithms as well as upper bounds for Clifford semigroups and -completeness otherwise.
Furthermore, by applying our findings, we show the following: the intersection non-emptiness problem for inverse automata is -complete even for automata with only two states; the subpower membership problem is in for every strict inverse semigroup and -complete otherwise; the minimum generating set and the equation satisfiability problems are in for varieties of finite strict inverse semigroups and -complete otherwise.
Keywords and phrases:
inverse semigroups, membership, conjugacy, finite automataCategory:
Track B: Automata, Logic, Semantics, and Theory of ProgrammingFunding:
Armin Weiß: Supported by the German Research Foundation (DFG) grant WE 6835/1-2.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Algebraic language theory ; Theory of computation Problems, reductions and completeness ; Theory of computation Circuit complexityEditors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
In this work, we study the membership problem for inverse semigroups and some related problems such as the conjugacy problem. The membership problem for semigroups in the transformation model has first been studied by Kozen [40] in 1977. It receives as input a list of functions for some finite set and a target function ; the question is whether can be written as composition of the or, with other words, whether is contained in the subsemigroup generated by . It is closely related to the DFA intersection non-emptiness problem, which receives as input a list of deterministic finite automata (DFAs) and asks whether there is a word accepted by all of the automata. Indeed, Kozen [40] showed that both problems are -complete.
Inverse semigroups have first been studied by Wagner [64] and Preston [54] to describe partial symmetries. They constitute the arguably most natural class of algebraic structures containing groups and being contained in the semigroups. An inverse semigroup is a semigroup equipped with an additional unary operation such that and for all and is unique with that property. This clearly generalizes the inverse operation in groups. Similar to groups being an algebraic abstraction of symmetries and semigroups being an algebraic abstraction of computation, inverse semigroups abstract symmetric computation. This notion of computation, where every computational step is invertible, was introduced by Lewis and Papadimitriou [43] in order to better describe the complexity of the accessibility problem in undirected graphs ugap, which only much later was shown to be in (deterministic logspace) by Reingold [55].
In the setting of inverse semigroups, it is natural to consider the partial bijection model for the membership problem, where the and are partial functions which are injective on their domain. The membership problem for inverse semigroups in the partial bijection model is also -complete – and, thus, as difficult as for arbitrary semigroups – as Jack [33] recently observed. This observation is based on a result by Birget, Margolis, Meakin, and Weil [11] showing that the intersection non-emptiness problem for inverse automata is -complete. Roughly speaking, an inverse automaton is a DFA with a partially defined transition function where every letter induces a partial bijection on the set of states and the action of each letter can be “inverted” by a sequence of letters. Thus, inverse automata can be seen as a generalization of permutation automata, for which the intersection non-emptiness problem is -complete [12]. Interestingly, the corresponding membership problem for permutation groups is even in as shown by Babai, Luks, and Seress [5] after a series of partial results [59, 25, 47, 45, 49, 4].
A different variant of the membership problem has been introduced by Jones, Lien, and Laaser [34] in 1976: for the membership problem in the Cayley table model the ambient semigroup is given as its full multiplication table (a.k.a. Cayley table), i.e., instead of the finite set as above, the input includes a multiplication table of a semigroup and the elements are given as indices to rows/columns of that multiplication table. Clearly, this is a much less compressed form than the membership problem in the transformation or partial bijection model and, indeed, the membership problem in the Cayley table model is -complete [34].
Like in the transformation model, the case of groups appears to be easier than the general case. Indeed, for certain groups the problem can be solved in as shown by Barrington, Kadau, and Lange [9] and extended to further groups by Collins, Grochow, Levet, and the last author [17]. Moreover, in 1991, Barrington and McKenzie [7] observed that the membership problem for groups in the Cayley table model (which they denote by “gen(groups)” and we by memb) can be solved in with an oracle for ugap and speculated about it potentially being -complete. They posed the following question.
Does gen(groups) belong to ? We doubt that this is the case: we believe rather that gen(groups) is complete for the -closure of ugap, though we do not yet see how to apply the techniques in Cook and McKenzie (1987) to prove that gen(groups) is even -hard.
This conjecture has been refuted by the first author of the present article [22, 23] by showing that memb can be solved in (at least if we read completeness with respect to -reductions; when using -reductions, the results in [22, 23] give only a strong indication that the conjecture does not hold). Yet, in this work, we establish that the conjecture actually holds if we replace groups with inverse semigroups.
To find out in which cases the membership and conjugacy problem are easy and in which cases they are difficult, we study these problems restricted to certain varieties of finite inverse semigroups. A variety of finite (inverse) semigroups, frequently called a pseudovariety, is a class of (inverse) semigroups that is closed under finite direct products, (inverse) subsemigroups, and quotients. Important varieties of finite (inverse) semigroups are groups, semilattices, or aperiodic (inverse) semigroups. Varieties of finite semigroups are closely linked to varieties of formal languages (i.e., classes of languages enjoying natural closure properties) by Eilenberg’s Correspondence Theorem [21].
Beaudry, McKenzie, and Thérien [10] classified the varieties of finite aperiodic monoids in terms of the complexity of their membership problem. They found the following five classes: , -complete, -complete, -hard, and -complete. Note that it might seem like a negligible difference whether semigroups or monoids are considered; however, the landscape of varieties of finite semigroup is much richer than the varieties of finite monoids. The aim of this work is to provide a similar classification for inverse semigroups.
Our Contribution.
We consider the membership and conjugacy problems for inverse semigroups parametrized by a variety . For both problems we are given inverse semigroups where is given by generators and . Given an element , the membership problem asks whether . Given elements , the conjugacy problem asks whether and for some . Both problems are examined with respect to two models of input – the Cayley table model and the partial bijection model. We write memb, conj, memb, and conj, accordingly. Regarding further details on the definition we refer to Section 2.4.
Our main result regarding the Cayley table model is the following dichotomy. Herein denotes the variety of finite Clifford semigroups, which is the smallest variety containing all finite groups and semilattices. The class comprises all problems solvable by non-deterministic random access Turing machines in time ; see Section 2.5.
Theorem A (Cayley Table Model).
Let be a variety of finite inverse semigroups.
-
If , then memb and conj are in and in .
-
If , then memb and conj are -complete.
In particular, both problems are in if and only if as the class contains no problem that is hard for (with respect to reductions). Furthermore, ˜A establishes Barrington and McKenzie’s conjecture [7] on -completeness111Recall that by Reingold’s seminal result [55]. of the membership problem – however, for the larger class of inverse semigroups or, more specifically, any variety of finite inverse semigroups not contained in .
The condition in ˜A can be equivalently formulated using the following fact. A variety of finite inverse semigroups is contained in if and only if it does not contain the combinatorial Brandt semigroup . The latter consists of elements where and all of the other products are as one would expect. Hence, by ˜A, the problems memb and conj are -complete if and only if .
We now turn to the partial bijection model. This input model is similar to the transformation model for semigroups considered above – however, the generators and the target elements are partial maps that need to be injective on their domain. Our main result for the partial bijection model is the following dichotomy.
Theorem B (Partial Bijection Model).
Let be a variety of finite inverse semigroups.
-
If , then memb is in and conj is in .
-
If , then memb and conj are -complete.
Herein denotes the variety of strict inverse semigroups, which is the smallest variety containing all groups and the combinatorial Brandt semigroup ; it contains , in particular, all semilattices (denoted as ), and the variety generated by (denoted as ). As such, no longer serves as a key obstruction to an easy membership problem (as was the case in the Cayley table model). This rôle is now played by the combinatorial Brandt monoid . Indeed, a variety of finite inverse semigroups is contained in if and only if .
The case in ˜B can be further refined as follows using [10] and our further results (˜A, Lemma 6, Proposition 11 or [4], and Corollary 22).
-
If , then memb and conj are in by [10].
-
If , then memb and conj are -complete.
-
If , then memb is in and conj is in ; both are hard for .
Note that here and refer to uniform circuit classes and, as such, the three levels of complexity are separated unconditionally [58, 26]. Therefore, in particular, each of the problems memb and conj is in if and only if , and the problem memb is in if and only if .
For we reduce the problems memb and conj to the corresponding problems for the variety of finite groups, matching their complexity. We build on the celebrated result of Babai, Luks, and Seress [5] which states that the membership problem for permutation groups is in , as well as the observation that, due to groups admitting polylogarithmic SLPs, the corresponding conjugacy problem is in .
As outlined above, membership problems are deeply intertwined with intersection non-emptiness problems for the corresponding classes of automata. In 2016, Bulatov, Kozik, Mayr, and Steindl [13] proved that the intersection non-emptiness problem for DFAs remains -complete even if the input automata are restricted to at most three states exactly one of which is accepting. This corresponds to semigroups in the transformation model. Here we obtain a similar result for inverse automata, which corresponds to inverse semigroups in the partial bijection model, using the same reduction as for the hardness part of ˜B.
Corollary C.
The intersection non-emptiness problem for inverse automata is -complete. This holds even if the automata have only two states, one of which is accepting.
The reason that two states suffice to show -hardness is grounded in the fact that inverse automata have partially defined transition functions, whereas the above-mentioned result concerns automata with total transition functions.
In the same work [13] Bulatov, Kozik, Mayr, and Steindl also considered the subpower membership problem and showed that it is -complete for arbitrary semigroups. This problem is natural in the context of universal algebra [48, 14, 39, 41] and has been studied for semigroups also in [61, 62]. As a consequence of ˜B and ˜C, we obtain the following dichotomy for the subpower membership problem for inverse semigroups.
Corollary D.
The subpower membership problem for an inverse semigroup is in if and only if . Otherwise, it is -complete.
Finally, we apply our results to the problems of determining the minimal size of a generating set (mgs) and deciding satisfiability of an equation (eqn) and obtain a similar dichotomy as above. The minimum generating set problem receives as input an inverse semigroup and an integer and asks whether can be generated by at most elements. For eqn the input is an inverse semigroup and a single equation, and the question is whether there is a satisfying assignment of the variables to elements of .
Corollary E.
Let be a variety of finite inverse semigroups.
-
If , then mgs and eqn are in .
-
If , then mgs and eqn are -complete.
Due to space constraints most proofs are omitted from this extended abstract. They can be found in the full version of this paper [24] including extended preliminaries and related work. For important results, we provide short proof sketches.
2 Preliminaries and Notation
2.1 Inverse Semigroups
An inverse semigroup is a semigroup where every possesses a unique inverse , i.e., and hold and is the unique element with this property. In an inverse semigroup all idempotents commute; in particular, its set of idempotents is a subsemigroup and a semilattice. We denote the natural order on the elements of an inverse semigroup by , i.e., if and only if or, equivalently, . For an inverse semigroup and , we denote by the inverse subsemigroup of generated by , i.e., the smallest inverse subsemigroup of containing . The elements of are called generators for . As all elements of can be written as words over , we assume from now on that generating sets are closed under formation of inverses, i.e., . Be aware that, unlike in finite groups, arbitrary subsemigroups of an inverse semigroup need not be inverse semigroups again. For further background on (inverse) semigroups see [16, 1, 57, 53, 42].
Symmetric Inverse Semigroups.
The symmetric inverse semigroup is the inverse semigroup of all partial bijections on a set , i.e., partial maps that induce a bijection from their domain to their range . We write .
For and , we write for the image of under , where means that is undefined. We extend this notation to sets , i.e., .
The Brandt Semigroup.
The (combinatorial) Brandt semigroup on some set is the inverse subsemigroup of . The (combinatorial) Brandt monoid on is the inverse submonoid of . We write and in case . The Brandt semigroup (or monoid) can be thought of as the complete directed graph on vertices together with an additional zero element (and an identity) where the multiplication of edges and is if and otherwise.
2.2 Green’s Relations and Conjugacy
The following relative variants of Green’s relations will be very useful. As usual, given an inverse semigroup , we denote by the smallest inverse monoid containing . However, in a relative context, i.e., for an inverse subsemigroup , we denote by the inverse submonoid . This abuse of notation is employed in the following definition.
Definition 1.
Let . Given elements , we write , , and . Furthermore, we write provided that and ; the Green’s relations and are defined similarly. Finally, we let and .
We recover the usual definition of Green’s relations [28] as and , where or , respectively. Similarly, we will use a relative variant of conjugacy in inverse semigroups defined as follows. Beware that there are other notions of conjugacy frequently considered in the context of semigroup theory; see also [2, 33].
Definition 2.
Let be inverse semigroups. We call conjugate relative to , written , if there exists some such that and .
Conjugacy and -equivalence are closely related for idempotents of inverse semigroups.
Lemma 3.
Let be inverse semigroups, and let . Then holds if and only if for some . If is finite, then if and only if .
2.3 (Pseudo-)Varieties
A class of finite inverse semigroups is called a variety of finite inverse semigroups (a.k.a. pseudovariety) if it is closed under formation of finite direct products and of divisors (quotients of inverse subsemigroups). By Reiterman’s theorem [56], a variety consists of all finite inverse semigroups that satisfy some set of (pseudo-)identities. Moreover, these classes are closely related to certain classes of formal languages via Eilenberg’s Correspondence Theorem [21].
We will use boldface roman letters to denote varieties of finite inverse semigroups and sometimes also give a set of defining inverse semigroup identities for them. An overview of the varieties of finite inverse semigroups most relevant to our work is given in Figure 1.
Variety | Identities | Description |
trivial | ||
inverse semigroups | ||
groups | ||
Clifford semigroups | ||
strict inverse semigroups | ||
semilattices | ||
generated by | ||
not finitely based [37] | generated by | |
aperiodic |
The chain forms the bottom of the lattice of the varieties of finite combinatorial (i.e., aperiodic) inverse semigroups. Herein, and denote the varieties of finite inverse semigroups generated by the (combinatorial) Brandt semigroup and monoid , respectively.
Lemma 4 (Kleiman [36, Lemma 4]).
For every finite set , and .
The bottom of the lattice of varieties of finite inverse semigroups is structured as follows.
Proposition 5 (Djadchenko [20], Kleiman [35, 36]; see also [29]).
Let be a variety of finite inverse semigroups. Then is subject to each of the following alternatives.
-
1.
Either or .
-
2.
Either or .
-
3.
Either or .
Moreover, the intervals (or ) and in the lattice of all varieties of finite inverse semigroups are isomorphic via and (or ).
2.4 Algorithmic Problems
The main focus of this work lies on analyzing the algorithmic complexity of two important decision problems for inverse semigroups, and several variants thereof. The first of these problems is the membership problem (memb); it is defined as follows.
- Input.
-
An inverse semigroup , a subset , and an element .
- Question.
-
Is where ?
The second main decision problem is the conjugacy problem (conj).
- Input.
-
An inverse semigroup , a subset , and elements .
- Question.
-
Is where ?
As with any decision problem, its algorithmic complexity depends substantially on how its input is given. We consider two input models, the Cayley table model () and the partial bijection model (). In the former model, the surrounding inverse semigroup is provided as a complete multiplication table, the so-called Cayley table of . In the partial bijection model, the surrounding inverse semigroup is the symmetric inverse semigroup with provided as part of the input; the elements are given as partial bijections. We denote by membCT and membPB, and by conjCT and conjPB the membership and conjugacy problems in the respective input models. The Preston-Wagner representation [54, 64] of an inverse semigroup is efficiently computable, which leads to the following observation.
Lemma 6.
On input of an inverse semigroup given as a Cayley table, one can compute an embedding in . Hence, and .
To obtain a detailed analysis of the algorithmic complexity, we impose certain restrictions on the allowed inputs. On the one hand, we consider the idempotent membership and idempotent conjugacy problems where we require that . We denote these variants by -membIM and -conjIM where .
The other kind of restriction we impose is on the structure of the inverse subsemigroup under consideration. More specifically, we consider the above problems with confined to some fixed class of finite inverse semigroups. We call these the (idempotent) membership and conjugacy problem for , and denote them by memb and conj where , respectively. Throughout, the class will be some variety of finite inverse semigroups such as, e.g., the variety of finite groups. Be aware that only is restricted to the class , while and the elements can be arbitrary!
We also consider a more restricted variant of the problems, which we denote with a superscript (e.g. memb and conj). For these we require in the Cayley table model that and in the partial bijection model that there is some with such that and (resp. ). For the conjugacy problem we also require that . We use these restricted variants to show stronger statements for our hardness results.
2.5 Complexity
For standard complexity classes such as or see any standard textbook [3, 51]. If and are complexity classes, denotes the class of problems that can be solved in with oracles for a finite set of problems from . The circuit class consists of the problems decidable by polynomial-size, constant-depth Boolean circuits (where gates may have arbitrary fan-in). Likewise -computable functions are defined. For a precise definition, we refer to [63]. We write to denote logarithmic space; for many-one reductions computable in logarithmic space we write -reductions. When talking about -hard problems, throughout we refer to many-one reductions.
Let ugap denote the undirected graph accessibility problem. Its input is an undirected graph and two vertices and and the question is whether and lie in the same connected component. Note that ugap is -hard [19]. We crucially rely on the seminal result due to Reingold [55] showing that and, hence, .
The class consists of the problems decidable by non-deterministic random access Turing machines in time . A random access Turing machines has a separate address tape and a query state; whenever the Turing machine goes into the query state and on the address tape the number is written in binary, the -th symbol of the input is read (the content of the address tape is not deleted after that). Apart from that, random access Turing machines work like regular Turing machines.
For an overview over the complexity classes we use in this paper and their relationships, see Figure 2. We note that, by [58] and the space hierarchy theorem [60], we have . Moreover, by [17], can be simulated by circuits of quasipolynomial size and depth two, i.e., . By [26, 30], does not contain any -hard problem as it cannot compute, for instance, parity.
2.6 Straight-Line Programs
Let be an inverse semigroup and . A straight-line program (SLP) over is a finite sequence such that for all either , or for some , or for some . An SLP as above computes an element if .
We say that a class of finite inverse semigroups admits polylogarithmic SLPs if there exists a polynomial such that, for all and all generating sets , every element is computed by some SLP over of length at most . The analogous property for semigroups and monoids was studied by the first author [23, 22] under the name polylogarithmic circuits property. Using a straight-forward guess-and-check approach, we obtain the following result – for a proof see [22, Corollary 5.2].
Lemma 7 (Fleischer [22, Corollary 5.2]).
Let be a class of finite (inverse) semigroups admitting polylogarithmic SLPs. Then the problem memb is in .
3 Membership and Conjugacy in Groups
Groups are a primary example for inverse semigroups. Therefore, let us start exploring some known result and new observations about the membership and conjugacy problems in groups.
In the Cayley table model, deciding the membership and conjugacy problems for groups is comparatively easy. The best currently known approach [18] is based on the non-deterministic computation of a succinct representation of a target element as a product of generators. We pursue a similar idea here and use SLPs for succinct representation. In the case of groups, this approach is afforded by the following Reachability Lemma.
Lemma 8 (Babai, Szemerédi [6, Theorem 3.1]).
The variety of finite groups admits polylogarithmic SLPs. More precisely, for every group and generating set , every element of is computed by an SLP over of length .
Guessing and then verifying a representation given by an SLP yields the following complexity bounds. For the first part of the following result, see [22].
Proposition 9.
The problems memb and conj are in .
In the partial bijection model, the groups under consideration are permutation groups and it is in this latter setting that the membership and conjugacy problems have been widely studied. However, the problems memb and conj are also subtly different from the corresponding problems for permutation groups simply because the former allow for more possible inputs (partial bijections instead of bijections). In case of the membership problem this distinction is mostly artificial (and can be resolved by appropriate reductions).
Proposition 10 (Babai, Luks, and Seress [5]).
The problem memb is in .
We complement the above with the following hardness result.
Proposition 11.
Let be a variety of finite inverse semigroups containing a non-trivial group. Then memb as well as its restricted variant memb are -hard.
Note that an even stronger statement holds: solving systems of linear equations modulo a prime is hard for the logspace counting class [15] and, in the setting of Proposition 11, this implies hardness for whenever divides the order of some group in . Moreover, if contains all abelian groups, then memb is hard for the complexity class [4].
The complexity of the conjugacy problem for groups is more intricate. On the one hand, the problem is clearly in due to the existence of short SLPs (Lemma 8). This observation holds for permutation groups as well as groups in the partial bijection model. On the other hand, the conjugacy problem is -hard for permutation groups, as was observed by Luks [46]. Luks also exhibited several other problems for permutation groups that are polynomial-time equivalent to conjugacy, among which is the set transporter problem.
- Input.
-
A group given by generators, and sets .
- Question.
-
Does there exist an element such that ?
The conjugacy problem for permutation groups is clearly a special case of the conjugacy problem for in the partial bijection model, and so is the set transporter problem. In fact, the latter is precisely the idempotent conjugacy problem for (recall that the idempotents of the symmetric inverse semigroup are in canonical bijection with the subsets of ).
The above discussion can be summarized as follows.
Proposition 12.
Both of the problems conj and -conj are polynomial-time equivalent to the conjugacy problem for permutation groups; hence, -hard and in .
4 Membership and Conjugacy in Clifford Semigroups
We now turn to Clifford semigroups, which constitute the smallest variety of finite inverse semigroups to properly contain the variety of finite groups . As is the case for groups, every finite Clifford semigroup admits SLPs of length [22, Lemma 4.10].
Proposition 13.
The problems memb and conj are in .
Even in the partial bijection model, the complexity of the membership and conjugacy problems for Clifford semigroups is essentially equivalent to those for groups.
Lemma 14.
Let be generated by . On input and , the minimal idempotent such that can be computed in .
Proposition 15.
If is a variety of finite groups, then the problems memb and conj are -reducible to memb and conj, respectively.
Proof.
Let with generated by . In the case of membership, we are given an additional element . Using Lemma 14, we compute the minimal idempotent with and verify that . Next, we compute the generating set of the -class (which is a group). Then if and only if .
The reduction for the conjugacy problem is similar.
Corollary 16.
The problems memb and conj are in and , respectively.
Choosing as the trivial variety in Proposition 15 yields the result by Beaudry, McKenzie, Thérien [10] that memb is in . Furthermore, by Lemma 6, it follows that also memb is in . On the other hand, the following question remains open.
Question 17.
Are the problems memb and memb in ?
5 Membership and Conjugacy in Strict Inverse Semigroups
In this section we show that, in the partial bijection model, the membership and conjugacy problem for are -reducible to the corresponding problems for . In the Cayley table model these problems are -complete for as we will show in Section 6.
Our reduction is explicit and based on special properties of the representation theory of the variety . Suppose that with . We say that an element is -large for some -invariant subset if its domain or, equivalently, its range intersects every -orbit . Consider the graph which, for each -large , possesses an edge labeled from a vertex associated with the set to a vertex associated with the set . This graph, which we call the Munn graph at and with respect to , is the basis of our reduction. As it turns out, every -class of the strict inverse semigroup is generated (as a groupoid) by a connected component of the Munn graph at some suitably chosen -invariant set .
Lemma 18.
Let be as above and let for some . Then the set is the vertex set of a connected component of .
To decide membership or conjugacy, we identify a suitable set for the -class of containing the potential member or conjugating element, respectively. (E.g., for deciding choose where is the smallest idempotent with .)
Lemma 19.
Given and the minimal with can be computed in and, as part of the computation, one can decide whether .
We then use the Munn graph to reduce the problem to a suitable -class (i.e., a subgroup) of (as in the case of Clifford semigroups) including the computation of a generating set. All these computations can be performed in , with those involving -orbits and the Munn graph crucially relying on the graph accessibility problem (ugap). Alluding to Reingold’s seminal result [55] whereby , we obtain the following.
Theorem 20.
Let be a variety of finite groups. The problems memb and conj are -reducible to memb and conj for , respectively.
Using the facts that memb is in (by [5], see Proposition 10) and conj is in (see Proposition 12), this implies the following upper bounds for .
Corollary 21.
The problem memb is in and conj is in .
The other extreme, i.e., taking to be the trivial variety in Theorem 20, yields the following upper bounds. These are interesting because and are already complete for as we will later show; see Proposition 26.
Corollary 22.
The problems memb and conj are in .
6 Inverse Semigroups in the Cayley Table Model
In this section we complete the proof of ˜A. Recall that the variety of finite Clifford semigroups is the smallest variety containing all groups and semilattices. In Section 4 we have seen that memb and conj are in . Completing the proof of ˜A consists of two steps. In Proposition 25 we establish -algorithms for these problems, and in Proposition 26 we show that the problems are hard for given that . Before we go into the details of our proof, let us explore an interesting consequence.
Corollary 23.
Let be a variety of finite inverse semigroups. The following are equivalent.
-
The class comprises only Clifford semigroups, i.e., .
-
The class admits polylogarithmic SLPs.
-
The problem memb is in .
-
The problem memb is in .
Note that the equivalence of the first two points of Corollary 23 can also be proved directly. Indeed, the first author determined in his dissertation [22] the maximal varieties of finite (not necessarily inverse) monoids admitting polylogarithmic SLPs, viz. the varieties of finite Clifford monoids and of finite commutative monoids. However, the situation for semigroups is considerably more intricate. Therefore, we point out the following open problem.
Question 24.
Which varieties of arbitrary finite semigroups admit polylogarithmic SLPs?
The membership problem for semigroups in the Cayley table model belongs to [34]. Here we go even further and show that this can improved to for inverse semigroups. Recall that is intricately related to directed graph accessibility, while = by Reingold’s result [55] corresponds to undirected graph accessibility.
Proposition 25.
The problems membCT and conjCT are is in .
Proof Sketch.
The problem conjCT is essentially reachability in an undirected graph. To decide whether or not , consider the graph with vertex set and edges whenever there is some such that and . Now, if and only if and are in the same connected component. The latter is an instance of ugap, which by Reingold’s result [55] can be solved in . For membCT, consider as intermediate step the problem of deciding whether for elements . Using the same approach as above, this can be decided in . Now, to decide membCT, we use the following algorithm, where we assume without loss of generality that is a monoid and is a submonoid.
Note that throughout, we keep the invariants that and (i.e., ). Therefore, if our algorithm outputs true, then, indeed, . Moreover, the condition in line 2 implies that . Hence, the algorithm always terminates. Now, if and , the algorithm will repeatedly find and meeting the conditions in line 2 until it eventually terminates with output true.
We now turn to hardness results for the (idempotent) membership and conjugacy problems for inverse semigroups in the Cayley table model. Recall that a variety of finite inverse semigroups satisfies if and only if . The proof of the following proposition is by a direct reduction from ugap. Given a graph , consider the Brandt semigroup , which by Lemma 4 is contained in . For , there is a unique element mapping to , which can be used to encode an edge of . This leads to the following result.
Proposition 26.
Let be a variety of finite inverse semigroups and suppose that . Then the problems and are -hard under -reductions.
7 Inverse Semigroups in the Partial Bijection Model
In this section we finally complete the proof of our dichotomy ˜B regarding the membership and conjugacy problem for inverse semigroups in the partial bijection model. Recall that either or for each variety of finite inverse semigroups by Proposition 5. With the first part of ˜B covered by Corollary 21, it suffices to show that the problems memb and conj are -complete. Moreover, since these problems are clearly contained in , it remains to prove their hardness.
Theorem 27.
The problems -memb and -conj are -complete.
We prove -hardness by a reduction from the decision problem ncl of non-determinstic constraint logic (NCL), which was introduced by Hearn and Demaine [31] and which we briefly describe in the following.
An NCL machine is an edge-weighted simple undirected graph, every vertex of which has degree three, and every edge of which has weight one or two. A configuration of the NCL machine is an orientation of all edges such that the sum of the incoming edge weights (in-flow) at every vertex is at least two. We will denote the set of all configurations by . Two configurations are related by a transition if they differ in the orientation of a single edge.
The decision problem ncl, in the configuration-to-configuration variant, is given as follows.
- Input.
-
An NCL machine , and two configurations .
- Question.
-
Are and related by a sequence of transitions?
This problem is essentially a compressed version of the accessibility problem for undirected graphs, where accessibility is decided on the implicitly given graph of configurations and transitions between these. The problem ncl is complete for [31, Theorem 5].
Crucially, the validity of any configuration of an NCL machine can be verified locally, as the minimum in-flow constraint has to be satisfied at each vertex individually. We call an orientation of all edges incident with a fixed vertex a local configuration at provided that the minimum in-flow constraint at is satisfied. The set of all local configurations at will be denoted by and the corresponding restriction of by .
Proof Sketch for Theorem 27.
We only sketch the reduction from ncl to -conj since and, in general, -conj efficiently reduces to -memb.
Given , we associate to it the inverse semigroup . Every configuration has an idempotent canonically associated to; the projection of onto is given by the idempotent at . Any two such idempotents , are conjugate in . In a similar way, we encode the transitions of as elements of . More precisely, we consider elements acting (via conjugation) as a transition would in those two components where is incident with the reversed edge; and with projections to all other components being trivial, i.e., equal to .
Given , let be the inverse subsemigroup generated by , , and all encoded transitions of . Then the idempotents and are conjugate in if and only if and are related by a sequence of transitions of .
Let us now consider a variation of the above reduction for the intersection non-emptiness problem for inverse automata. An inverse automaton (IA) is a deterministic finite automation222For a definition we refer the reader to standard textbooks (e.g., [32]). (DFA) with a partially defined transition function such that the following conditions are satisfied.
-
For each , the partial map with is injective on its domain.
-
For each , there is a word such that is the identity on , where is the partial map induced by .333We view the maps as elements of and, as such, compose them as operators acting on the right.
Remark 28.
We will only encounter inverse automata over some alphabet endowed with an involution where one can take in the second condition above.
The intersection non-emptiness problem for a class of automata (e.g., or ), which we denote by -int-empty, is the decision problem defined as follows.
- Input.
-
Automata .
- Question.
-
Is non-empty?
The problems dfa-int-empty and ia-int-empty are -complete; see [40] and [11], respectively. We sketch a short proof of these results based on the reduction from ncl.
Theorem 29 (˜C).
The problem ia-int-empty is complete for . Moreover, this holds under the restriction that each automaton provided as part of the input has only two states, one of which is accepting.
Proof Sketch.
Given an NCL machine , we consider the set . Using a one-hot encoding, we embed into the states of many two-state inverse automata. As such, embeds into the states of many two-state inverse automata. The initial states of the automata correspond to and the accepting states to for some . The common alphabet is then used to encode the local effects of the transitions of as in the proof of Theorem 27.
The intersection of the languages accepted by the automata constructed in this way contains precisely the sequences of transitions of transforming into .
Every inverse automaton can be transformed into a complete DFA be introducing one additional state (and transitions to it). As such, Theorem 29 entails the following result of Bulatov, Kozik, Mayr, and Steindl [13]: dfa-int-empty is complete for even if each automaton provided as part of the input has only three states, one of which is accepting.
Next, we derive a corresponding dichotomy result for the subpower membership problem of an inverse semigroup . This problem is defined as follows.444The inverse semigroup is treated as a constant and is not part of the input.
- Input.
-
An integer , a subset , and an element .
- Question.
-
Is where ?
This problem can be seen as a special case of membPB, which, by ˜B implies that it can be solved in and, if , even in . From Theorem 29, it follows easily that the subpower membership problem for is -hard (e.g. using the same argument as [33, Theorem 4.10]). We can build upon this observation and show the following.
Corollary 30 (˜D).
The subpower membership problem of an inverse semigroup is complete for if and only if the Brandt monoid divides ; otherwise, it is in .
8 Further Related Problems
Finally, let us explore the consequences of our results to the minimum generating set problem and the problem of solving equations. The minimum generating set problem has first been considered by Papadimitriou and Yannahakis [52] and, in the Cayley table model, recently shown to be in by Lucchini and Thakkar [44] and even by Collins, Grochow, Levet, and the last author [17]. Yet, the complexity for arbitrary semigroups and also for permutation groups remains wide open. The minimum generating set problem (mgs) is defined as follows.
- Input.
-
An inverse semigroup and an integer .
- Question.
-
Is there some with and ?
Like for the membership problem, we write mgsPB if is given as generators for an inverse subsemigroup of and denote the restriction to a variety by mgs. The crucial connection to the membership problem is as follows.
Lemma 31.
Let be a variety of finite inverse semigroups. Then the restricted membership problem memb is -many-one-reducible to the problem mgs.
Together with the observation that mgs can be solved in and the hardness result Theorem 27, this gives the proof of the first part of ˜E.
Next, let us consider the problem of deciding satisfiability of equations. Let be a set of variables. An equation in an inverse semigroup is given as non-empty words . An assignment is a map , which naturally extends to a homomorphism from . The problem eqn of deciding whether a system of equations has a solution is defined as follows.
- Input.
-
An inverse semigroup , and words .
- Question.
-
Is there a such that for all ?
We denote this problem in the Cayley table model and partial bijection model by eqn and eqn, respectively. The problem of deciding whether a single equation has a solution occurs as a special case when , denoted by eqnCT and eqnPB. Our key lemma on equations is that the -hardness of can be transferred to eqnPB.
Lemma 32.
The problem eqn is hard for whenever .
As for mgs, we observe that eqn is solvable in with an oracle for memb. Thus, by Lemma 32, the problems eqn and eqn are in if and -complete otherwise, which constitutes the second part of ˜E.
In addition, the problems of deciding whether a single equation or a system of equations have a solution are known to be -hard for many fixed inverse semigroups. Indeed, based on [27], [8, Theorem 6], and [38] we obtain the following refined statement, where is a variety of finite inverse semigroups. Here denotes the variety of finite solvable groups and the variety of finite commutative inverse semigroups.
-
The problem eqn is -complete whenever .
-
The problems eqn and eqn are -hard whenever .
-
The problems eqn and eqn are -hard whenever .
9 Discussion and Open Problems
By investigating the membership problem in inverse semigroups, we filled a gap between the rather restricted case of groups and the very general case of arbitrary semigroups. We gave a classification of the complexity of membership and conjugacy in inverse semigroups according to their combinatorial structure. Here the combinatorial Brandt semigroup and monoid are the critical obstructions for the membership problem being easy. Furthermore, by applying these results, we gained new insights on the complexity of closely related problems such as the intersection non-emptiness problem for inverse automata, the minimum generating set problem, and the equation satisfiability problem.
Applying ˜A and ˜B to the case of aperiodic inverse semigroups shows that the membership and conjugacy problems are either in , or -complete, or -complete (with -complete only in the partial bijection model). Thus, in comparison to the classification for varieties of aperiodic monoids [10], we additionally have the -complete case, whereas we do not have the -complete, -complete, and -hard cases.
A corresponding classification of the complexity of the membership problem for varieties of arbitrary semigroups is still a major endeavor. While there is the classification for aperiodic monoids by Beaudry, McKenzie, and Thérien [10] mentioned above, the case for semigroups is considerably more involved as there are many more varieties of finite semigroups than of finite monoids. Moreover, it remains to integrate the case of groups into the consideration.
Open Problem 33.
Give a classification of the varieties of finite semigroups in terms of their complexity for the membership problem.
Another class of structures, situated between inverse semigroups and arbitrary semigroups, that we would like to draw attention to is the class of regular -semigroups introduced by Nordahl and Scheiblich [50]. These are regular semigroups with distinguished inverses such that , , and . The difference to inverse semigroups is that inverses need not be unique or, equivalently, that idempotents need not commute. As such, regular -semigroups admit a far richer combinatorial structure.
Open Problem 34.
Give a classification of the varieties of finite regular -semigroups in terms of their complexity for the membership problem.
Our algorithms for the (resp. ) cases of our dichotomy result for the partial bijection model are very efficient in the sense that they provide reductions computable in and also in linear or quadratic time to ugap as well as to the respective problems for groups. Thus, the only open questions about the complexity of these problems come from the group case. Here, for the membership problem we have the results that memb is in [5] (see Proposition 10) and hard for the logspace counting class [4] (see Proposition 11). This leads to the following question.
Question 35.
What is the precise complexity of memb?
We do not feel confident to make any guess about this question and want to use the present work to foster further research on this topic. On the other hand, we believe that the answer to the following question concerning the Cayley table model is likely to be negative.
Question 36.
Is memb in ?
Another question is whether the bound due to Babai and Szemerédi [6] on the length of straight-line programs in groups of order is asymptotically optimal. In some special cases, like for Abelian groups, an (asymptotically optimal) bound can be obtained instead. Thus, the question here is whether this can be extended to all groups.
For inverse semigroups, we obtained a complete characterization of varieties admitting polylogarithmic SLPs in Corollary 23. A similar result for monoids was obtained by the first author [22]. Therefore, the natural question is to ask for a similar characterization for all semigroups. For some preliminary results in that direction, see also [22].
References
- [1] J. Almeida. Finite Semigroups and Universal Algebra. World Scientific, Singapore, 1994.
- [2] J. Araújo, M. Kinyon, and J. Konieczny. Conjugacy in inverse semigroups. J. Algebra, 533:142–173, 2019. doi:10.1016/j.jalgebra.2019.05.022.
- [3] S. Arora and B. Barak. Computational Complexity – A Modern Approach. Cambridge University Press, 2009.
- [4] V. Arvind and T. C. Vijayaraghavan. Abelian permutation group problems and logspace counting classes. In CCC 2004, Proceedings, pages 204–214. IEEE Computer Society, 2004. doi:10.1109/CCC.2004.1313844.
- [5] L. Babai, E. M. Luks, and Á Seress. Permutation groups in NC. In STOC 1987, Proceedings, STOC ’87, pages 409–420, 1987. doi:10.1145/28395.28439.
- [6] L. Babai and E. Szemerédi. On the complexity of matrix group problems I. In FOCS 1984, Proceedings, pages 229–240, October 1984. doi:10.1109/SFCS.1984.715919.
- [7] D. A. M. Barrington and P. McKenzie. Oracle branching programs and Logspace versus P. Information and Computation, 95(1):96–115, 1991. doi:10.1016/0890-5401(91)90017-V.
- [8] D. A. M. Barrington, P. McKenzie, C. Moore, P. Tesson, and D. Thé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. doi:10.1007/3-540-44612-5_13.
- [9] D. M. Barrington, P. Kadau, K. Lange, and P. McKenzie. On the complexity of some problems on groups input as multiplication tables. Journal of Computer and System Sciences, 63(2):186–200, 2001. doi:10.1006/jcss.2001.1764.
- [10] M. Beaudry, P. McKenzie, and D. Thérien. The membership problem in aperiodic transformation monoids. J. ACM, 39(3):599–616, 1992. doi:10.1145/146637.146661.
- [11] 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 in Theoretical Computer Science, 242:247–281, 2000. doi:10.1007/3-540-58201-0_75.
- [12] 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.
- [13] A. Bulatov, M. Kozik, P. Mayr, and M. Steindl. The subpower membership problem for semigroups. Int. J. Algebra Comput., 26(7):1435–1451, 2016. doi:10.1142/S0218196716500612.
- [14] A. Bulatov, P. Mayr, and Á. Szendrei. The subpower membership problem for finite algebras with cube terms. Log. Methods Comput. Sci., 15(1), 2019. doi:10.23638/LMCS-15(1:11)2019.
- [15] G. Buntrock, C. Damm, U. Hertrampf, and C. Meinel. Structure and importance of logspace-MOD class. Math. Syst. Theory, 25(3):223–237, 1992. doi:10.1007/BF01374526.
- [16] A. H. Clifford and G. B. Preston. The algebraic theory of semigroups, volume 1,2. American Mathematical Society, 1961,1967.
- [17] 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. doi:10.1145/3666000.3669691.
- [18] 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. doi:10.48550/arXiv.2402.00133.
- [19] S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms, 8(3):385–394, 1987. doi:10.1016/0196-6774(87)90018-6.
- [20] G. G. Djadchenko. On identities in monogenic inverse semigroups. Algebra and Theory of Numbers, Nalčik, 2:57–77, 1977.
- [21] S. Eilenberg. Automata, Languages, and Machines, volume B. Academic Press, New York and London, 1976.
- [22] L. Fleischer. Algorithms and complexity results for finite semigroups. Dissertation, Institut für Formale Methoden der Informatik, Universität Stuttgart, 2019. doi:10.18419/opus-10339.
- [23] L. Fleischer. The Cayley semigroup membership problem. Theory Comput., 18:1–18, 2022. doi:10.4086/toc.2022.v018a008.
- [24] L. Fleischer, F. Stober, A. Thumm, and A. Weiß. Membership and conjugacy in inverse semigroups. CoRR, abs/2502.10103, 2025. doi:10.48550/arXiv.2502.10103.
- [25] M. Furst, J. Hopcroft, and E. Luks. Polynomial-time algorithms for permutation groups. In 21st Annual Symposium on Foundations of Computer Science (FOCS 1980), pages 36–41, October 1980. doi:10.1109/SFCS.1980.34.
- [26] M. L. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13–27, 1984. doi:10.1007/BF01744431.
- [27] M. Goldmann and A. Russell. The complexity of solving equations over finite groups. Inf. Comput., 178(1):253–262, 2002. doi:10.1006/inco.2002.3173.
- [28] J. A. Green. On the structure of semigroups. Ann. Math. (2), 54:163–172, 1951.
- [29] 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.
- [30] J. Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, pages 6–20, New York, NY, USA, 1986. ACM. doi:10.1145/12130.12132.
- [31] R. A. Hearn and E. D. Demaine. PSPACE-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. doi:10.1016/j.tcs.2005.05.008.
- [32] J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
- [33] T. Jack. On the complexity of inverse semigroup conjugacy. Semigroup Forum, 106(3):618–632, 2023. doi:10.1007/s00233-023-10349-y.
- [34] N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Mathematical Systems Theory, 10(1):1–17, December 1976. doi:10.1007/BF01683259.
- [35] E. I. Kleiman. The lattice of varieties of inverse semigroups. Ivz. Vysš. Učbn. Zaved. Mat., 7:106–109, 1976.
- [36] E. I. Kleiman. On basis of identities of Brandt semigroups. Semigroup Forum, 13:209–218, 1977.
- [37] E. I. Kleiman. Bases of identities of varieties of inverse semigroups. Sib. Math. J., 20(4):530–543, 1979. doi:10.1007/BF00970367.
- [38] O. Klíma, P. Tesson, and D. Thérien. Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst., 40(3):263–297, 2007. doi:10.1007/s00224-005-1279-2.
- [39] 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ür Informatik, 2024. doi:10.4230/LIPICS.STACS.2024.46.
- [40] D. Kozen. Lower bounds for natural proof systems. In Proc. of the 18th Ann. Symp. on Foundations of Computer Science, FOCS’77, pages 254–266, Providence, Rhode Island, 1977. IEEE Computer Society Press.
- [41] M. Kozik. A finite set of functions with an EXPTIME-complete composition problem. Theor. Comput. Sci., 407(1-3):330–341, 2008. doi:10.1016/J.TCS.2008.06.057.
- [42] M. V. Lawson. Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, 1999.
- [43] H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoret. Comput. Sci., 19(2):161–187, 1982. doi:10.1016/0304-3975(82)90058-5.
- [44] A. Lucchini and D. Thakkar. The minimum generating set problem. Journal of Algebra, 640:117–128, 2024. doi:10.1016/j.jalgebra.2023.11.012.
- [45] E. M. Luks. Parallel algorithms for permutation groups and graph isomorphism. In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 292–302. IEEE Computer Society, 1986. doi:10.1109/SFCS.1986.39.
- [46] E. M. Luks. Permutation Groups and Polynomial-Time Computation. In Groups and computation (New Brunswick, NJ, 1991), volume 11 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 139–175. Amer. Math. Soc., Providence, RI, 1993. doi:10.1090/dimacs/011/11.
- [47] E. M. Luks and P. McKenzie. Parallel algorithms for solvable permutation groups. J. Comput. Syst. Sci., 37(1):39–62, 1988. doi:10.1016/0022-0000(88)90044-X.
- [48] P. Mayr. The subpower membership problem for Mal’cev algebras. Int. J. Algebra Comput., 22(7), 2012. doi:10.1142/S0218196712500750.
- [49] P. McKenzie and S. A. Cook. The parallel complexity of abelian permutation group problems. SIAM J. Comput., 16(5):880–909, October 1987. doi:10.1137/0216058.
- [50] T. E. Nordahl and H. E. Scheiblich. Regular * semigroups. Semigroup Forum, 16:369–378, 1978. doi:10.1007/BF02194636.
- [51] C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
- [52] 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. doi:10.1006/JCSS.1996.0058.
- [53] M. Petrich. Inverse semigroups. Pure Appl. Math. (N. Y.). John Wiley & Sons, Inc., New York, 1984.
- [54] G. B. Preston. Representations of Inverse Semi-Groups. J. Lond. Math. Soc. (1), 29(4):411–419, 1954. doi:10.1112/jlms/s1-29.4.411.
- [55] O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, September 2008. doi:10.1145/1391289.1391291.
- [56] J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Univers., 14:1–10, 1982.
- [57] J. L. Rhodes and B. Steinberg. The -theory of finite semigroups. Springer Monographs in Mathematics. Springer, 2009.
- [58] W. L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22(3):365–383, 1981. doi:10.1016/0022-0000(81)90038-6.
- [59] C. C. Sims. Computational methods in the study of permutation groups. In Proceedings of the Conference on Computational Problems in Abstract Algebra 1967, Oxford, United Kingdom, pages 169–183, New York, 1970. Pergamon. doi:10.1016/B978-0-08-012975-4.50020-5.
- [60] 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. doi:10.1109/FOCS.1965.11.
- [61] M. Steindl. The subpower membership problem for bands. J. Algebra, 489:529–551, 2017. doi:10.1016/j.jalgebra.2017.06.034.
- [62] M. Steindl. On semigroups with PSPACE-complete subpower membership problem. J. Aust. Math. Soc., 106(1):127–142, 2019. doi:10.1017/S1446788718000010.
- [63] H. Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. doi:10.1007/978-3-662-03927-4.
- [64] V. V. Wagner. Generalised groups. Dokl. Akad. Nauk SSSR, 84(6):1119–1122, 1952.