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). More recently, both the membership and the conjugacy problem for finite inverse semigroups were shown to be PSPACE-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 NC (resp. NP for conjugacy) for strict inverse semigroups and PSPACE-complete otherwise. In the Cayley table model we obtain general 𝖫-algorithms as well as NPOLYLOGTIME 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 PSPACE-complete even for automata with only two states; the subpower membership problem is in NC for every strict inverse semigroup 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.

We investigate the complexity of deciding, given a multiplication table representing a semigroup S, a subset X of S and an element t of S, whether t can be expressed as a product of elements of X. It is well-known that this problem is NL-complete and that the more general Cayley groupoid membership problem, where the multiplication table is not required to be associative, is P-complete. For groups, the problem can be solved in deterministic log-space which raised the question of determining the exact complexity of this variant. Barrington, Kadau, Lange and McKenzie showed that for Abelian groups and for certain solvable groups, the problem is contained in the complexity class FOLL and they concluded that these variants are not hard for any complexity class containing PARITY. The more general case of arbitrary groups remained open. In this work, we show that for both groups and for commutative semigroups, the problem is solvable in qAC^0 (quasi-polynomial size circuits of constant depth with unbounded fan-in) and conclude that these variants are also not hard for any class containing PARITY. Moreover, we prove that NL-completeness already holds for the classes of 0-simple semigroups and nilpotent semigroups. Together with our results on groups and commutative semigroups, we prove the existence of a natural class of finite semigroups which generates a variety of finite semigroups with NL-complete Cayley semigroup membership, while the Cayley semigroup membership problem for the class itself is not NL-hard. We also discuss applications of our technique to FOLL.

Piecewise testable languages are a subclass of the regular languages. There are many equivalent ways of defining them; Simon's congruence ~_k is one of the most classical approaches. Two words are ~_k-equivalent if they have the same set of (scattered) subwords of length at most k. A language L is piecewise testable if there exists some k such that L is a union of ~_k-classes. For each equivalence class of ~_k, one can define a canonical representative in shortlex normal form, that is, the minimal word with respect to the lexicographic order among the shortest words in ~_k. We present an algorithm for computing the canonical representative of the ~_k-class of a given word w in A^* of length n. The running time of our algorithm is in O(|A| n) even if k <= n is part of the input. This is surprising since the number of possible subwords grows exponentially in k. The case k>n is not interesting since then, the equivalence class of w is a singleton. If the alphabet is fixed, the running time of our algorithm is linear in the size of the input word. Moreover, for fixed alphabet, we show that the computation of shortlex normal forms for ~_k is possible in deterministic logarithmic space. One of the consequences of our algorithm is that one can check with the same complexity whether two words are ~_k-equivalent (with k being part of the input).

We investigate the intersection problem for finite monoids, which asks for a given set of regular languages, represented by recognizing morphisms to finite monoids from a variety V, whether there exists a word contained in their intersection. Our main result is that the problem is PSPACE-complete if V is contained in DS and NP-complete if V is non-trivial and contained in DO. Our NP-algorithm for the case that V is contained in DO uses novel methods, based on compression techniques and combinatorial properties of DO. We also show that the problem is log-space reducible to the intersection problem for deterministic finite automata (DFA) and that a variant of the problem is log-space reducible to the membership problem for transformation monoids. In light of these reductions, our hardness results can be seen as a generalization of both a classical result by Kozen and a theorem by Beaudry, McKenzie and Thérien.