Efficient Compression in Semigroups

Thumm, Alexander; Weiß, Armin

doi:10.4230/LIPIcs.STACS.2026.80

Efficient Compression in Semigroups

Alexander Thumm

University of Siegen, Germany Armin Weiß

FMI, University of Stuttgart, Germany

Abstract

Straight-line programs are a central tool in several areas of computer science, including data compression, algebraic complexity theory, and the algorithmic solution of algebraic equations. In the algebraic setting, where straight-line programs can be interpreted as circuits over algebraic structures such as semigroups or groups, they have led to deep insights in computational complexity.

A key result by Babai and Szemerédi (1984) showed that finite groups afford efficient compression via straight-line programs, enabling the design of a black-box computation model for groups. Building on their result, Fleischer (2019) placed the Cayley table membership problem for certain classes (pseudovarieties) of finite semigroups in $\mathsf{NPOLYLOGTIME}$ , and in some cases even in $\mathsf{FOLL}$ . He also provided a complete classification of pseudovarieties of finite monoids affording efficient compression.

In this work, we complete this classification program initiated by Fleischer, characterizing precisely those pseudovarieties of finite semigroups that afford efficient compression via straight-line programs. Along the way, we also improve several known bounds on the length and width of straight-line programs over semigroups, monoids, and groups. These results lead to new upper bounds for the membership problem in the Cayley table model: for all pseudovarieties that afford efficient compression and do not contain any nonsolvable group, we obtain $\mathsf{FOLL}$ algorithms. In particular, we resolve a conjecture of Barrington, Kadau, Lange, and McKenzie (2001), showing that the membership problem for all solvable groups is in $\mathsf{FOLL}$ .

Keywords and phrases:

Semigroups, straight-line programs, compression, membership problem

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic language theory ; Theory of computation

\rightarrow

Problems, reductions and completeness ; Theory of computation

\rightarrow

Circuit complexity

Related Version:

Full Version: https://arxiv.org/abs/2601.04747

Acknowledgements:

The authors thank Markus Lohrey and Florian Stober for valuable discussions, and the anonymous referees for their helpful comments and suggestions.

Funding:

This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – LO 748/15-1, WE 6835/1-2.

DOI:

10.4230/LIPIcs.STACS.2026.80

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The membership problem asks, given a (finite) algebraic structure $S$ , a set $\Sigma\subseteq S$ , and a target element $t\in S$ , whether $t$ belongs to the substructure of $S$ generated by $\Sigma$ . Thinking of groups, semigroups, or vector spaces, this is a very fundamental problem in computational algebra with many applications. For permutation groups, Sims gave an efficient solution already in 1967 [34], later refined to an $\mathsf{NC}$ algorithm by Babai, Luks, and Seress [4]. For transformation semigroups, Kozen [24] showed in 1977 that the problem is $\mathsf{PSPACE}$ -complete, as hard as intersection non-emptiness for deterministic finite automata (DFAs).

As a different variant, the membership problem memb_CT in the Cayley table model was introduced by Jones, Lien, and Laaser [22], where the semigroup is given by its multiplication table; here the problem is $\mathsf{NL}$ -complete. For groups, Barrington and McKenzie [8] showed that memb ${}_{\mathbf{CT}}(\mathbf{G})$ can be solved in $\mathsf{L}$ with an oracle to undirected graph reachability [29], and conjectured it might be $\mathsf{L}$ -hard. Fleischer [16, 17] refuted the latter (under $\hbox{\small$\mathsf{AC}$}^{0}$ -reductions) by placing the problem in $\mathsf{NPOLYLOGTIME}$ . His proof is based on straight-line programs (algebraic circuits or context-free grammars producing precisely one word), a tool central in data compression [23, 6], algebraic complexity [11], and in solving algebraic equations [21, 12]. A key feature is their support for efficient manipulation of compressed data [25, 26, 19, 36].

Babai and Szemerédi [5] showed that finite groups afford efficient compression: every element can be expressed by a straight-line program of polylogarithmic length in the size of the group. Fleischer used this to place memb ${}_{\mathbf{CT}}(\mathbf{G})$ in $\mathsf{NPOLYLOGTIME}$ and extended the result to pseudovarieties of monoids: efficient compression occurs precisely for Clifford monoids (which comprise both groups and semilattices) and commutative monoids. In contrast, there is no maximal pseudovariety of semigroups that affords efficient compression.¹¹1At the first glance, the difference between monoids and semigroups might seem negligible; however, the landscape of pseudovarieties of semigroups is much richer than the one of monoids.

The membership problem has also been studied restricted to other pseudovarieties: Beaudry, McKenzie, and Thérien [9] investigated aperiodic monoids, while Fleischer, Stober, and the authors [18] considered inverse semigroups.

An important variant are straight-line programs of polylogarithmic length and bounded width. Fleischer showed that they yield membership algorithms in $\mathsf{FOLL}$ (polynomial-size Boolean circuits of depth $\log\log n$ ), which applies to all commutative semigroups. Earlier, Barrington, Kadau, Lange, and McKenzie [7] placed membership in solvable groups of bounded derived length in $\mathsf{FOLL}$ , and conjectured that the membership problem for all solvable groups may also be in $\mathsf{FOLL}$ . This was partially confirmed by Collins, Grochow, Levet, and the second author [13] showing this to be true for the class of all nilpotent groups.

In this work, we complete Fleischer’s program to characterize pseudovarieties of finite semigroups that afford efficient compression. Moreover, we also improve upon some of the best previously-known length and width bounds for semigroups, monoids, and groups. Finally, we apply our findings to the membership problem, in particular, resolving Barrington, Kadau, Lange, and McKenzie’s conjecture. In more detail, our results are as follows.

Our Contribution.

Our main theorem completely characterizes those pseudovarieties $\mathbf{V}$ of semigroups that afford efficient compression – meaning that, for some $k\in\mathbb{N}$ , all $S\in\mathbf{V}$ of size $\left|S\right|\leqslant N$ admit straight-line programs of length $\mathcal{O}(\smash{\log}^{k}N)$ ; see Section 3. Here, the following three pseudovarieties – each requiring straight-line programs of length $\Omega(\sqrt{N})$ – play a crucial role, since they serve as primary obstructions:

\mathbf{LRB}=\llbracket x^{2}\approx x,xyx\approx xy\rrbracket,\quad\mathbf{% RRB}=\llbracket x^{2}\approx x,xyx\approx yx\rrbracket,\quad\mathbf{T}=% \llbracket x^{2}\approx xyx\approx 0\rrbracket.

Theorem 1.

Let $\mathbf{V}$ be a pseudovariety of semigroups. The following are equivalent.

(1)

The pseudovariety $\mathbf{V}$ affords efficient compression.
(2)

The pseudovariety $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , nor $\mathbf{T}$ .
(3)

The pseudovariety $\mathbf{V}$ admits straight-line programs of length $\mathcal{O}(\smash{\log}^{2}N)$ .

Furthermore, if all groups in $\mathbf{V}$ are solvable, then the above are equivalent to $\mathbf{V}$ admitting straight-line programs of length $\mathcal{O}(\log N)$ as well as of width $\mathcal{O}(1)$ and length $\mathcal{O}(\operatorname{polylog}N)$ .

Moreover, if $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ for some $k\geqslant 1$ , then the pseudovariety admits straight-line programs of bounded width and length. Except in the case that $\mathbf{V}$ contains a nonsolvable group, we show that these bounds are essentially asymptotically optimal. Our proofs are fully constructive and can be found in Sections 4–9.

In Section 10, we apply our findings to the membership problem proving the following result, where memb ${}_{\mathbf{CT}}(\mathbf{V})$ denotes the membership problem for $\mathbf{V}$ in the Cayley table model.

Corollary 2.

Let $\mathbf{V}$ be a pseudovariety of semigroups with $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}\not\subseteq\mathbf{V}$ .

(1)

The membership problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\hbox{\small$\mathsf{NPOLYLOGTIME}$}\subseteq\hbox{\small$\mathsf{qAC}$}^{0}$ .
(2)

If, moreover, $\mathbf{V}$ contains no nonsolvable group, then memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\mathsf{FOLL}$ .

Our results almost completely answer an open problem due to Fleischer [17], who deemed it “interesting to see whether the Cayley semigroup membership problem can be shown to be in $\mathsf{FOLL}$ for all classes of semigroups with the polylogarithmic circuits property.” Moreover, we positively resolve Barrington, Kadau, Lange, and McKenzie’s conjecture [7] concerning the membership problem for the pseudovarierty $\mathbf{G}_{\textup{{sol}}}$ of all finite solvable groups.

Corollary 3.

The problem memb ${}_{\mathbf{CT}}(\mathbf{G}_{\textup{{sol}}})$ is in $\mathsf{FOLL}$ .

Proof Outline.

Our proof of Theorem 1 combines structural results on semigroups with explicit constructions. The negative results for the pseudovarieties $\mathbf{LRB}$ , $\mathbf{RRB}$ , and $\mathbf{T}$ were already established by Fleischer [16]. For the positive direction, we rely on a recent characterization of pseudovarieties $\mathbf{V}$ satisfying $\mathbf{T}\not\subseteq\mathbf{V}$ by first author [35], which shows that any such pseudovariety necessarily falls into one (or both) of the following two classes.

$\blacksquare$

The pseudovariety $\mathbf{V}$ is almost completely regular, meaning that all its members satisfy an identity of the form $x_{1}\cdots x_{n}\approx x_{1}\cdots x_{i-1}(x_{i}\cdots x_{j})^{\omega+1}x_{j% +1}\cdots x_{n}$ . This condition properly generalizes complete regularity (that is, being a union of groups), which is characterized by the identity $x\approx x^{\omega+1}$ . In Section 9 we show that the general problem for almost completely regular pseudovarieties reduces to this special case. If, in addition, the pseudovariety satisfies $\mathbf{LRB},\mathbf{RRB}\not\subseteq\mathbf{V}$ , then the completely regular members of $\mathbf{V}$ are necessarily normal bands of groups [28, Proposition 4]. Exploiting this structural restriction, we further reduce the problem to the group case in Section 8. Combined with Babai and Szemerédi’s result for groups [5], this completes the proof.
$\blacksquare$

The pseudovariety $\mathbf{V}$ is permutative, meaning that an identity $x_{1}\cdots x_{n}\approx x_{\sigma(1)}\cdots x_{\sigma(n)}$ holds for all members of $\mathbf{V}$ , where $\sigma\in\mathrm{Sym}(n)$ is some nontrivial permutation of the symbols $1,\dots,n$ . This notion properly generalizes commutativity, which is characterized by the identity $xy\approx yx$ . In Section 6 we present a direct proof that such pseudovarieties afford efficient compression, refining an earlier argument for commutative semigroups due to Fleischer [16]. Our construction yields straight-line programs of asymptotically optimal length $\mathcal{O}(\log N)$ and width two. (Matching lower bounds are established in Section 5.)

For pseudovarieties in the first class, our reductions are also efficient in that questions about asymptotically optimal straight-line program length (and width) reduce to the group case. The latter is discussed in Section 7, where we additionally present two new constructions for solvable groups, yielding straight-line programs of asymptotically optimal length $\mathcal{O}(\log N)$ but unbounded width, and of polylogarithmic length and bounded width, respectively.

2 Preliminaries

In this section, we provide a very brief overview of the necessary material from semigroup theory and complexity theory, along with a summary of the notational conventions used throughout this paper. For background on group theory, we refer the reader to Section 7.

2.1 Semigroups

We assume that the reader is familiar with the theory of finite semigroups, and we refer to the excellent treatments of the subject by Almeida [1], and Rhodes and Steinberg [31] for relevant background material as well as any undefined terms.

Given a semigroup $S$ , we write $T\leqslant S$ to indicate that $T\subseteq S$ is a subsemigroup. For an arbitrary subset $\Sigma\subseteq S$ , we denote by $\langle\Sigma\rangle$ the subsemigroup generated by $\Sigma$ , consisting of all elements of $S$ expressible as a product of elements of $\Sigma$ . We write $\Sigma^{\leqslant k}$ for the set of all elements expressible in this way by a product of length at most $k$ . The set of completely regular elements of a finite semigroup $S$ is denoted by $I(S)=\{s\in S:s^{\omega+1}=s\}$ where, as usual, $s^{\omega}$ denotes the unique idempotent power of an element $s$ of a finite semigroup.

Table 1: Important pseudovarieties (left) and their relationships (right).

Symbol	Identities	Description
$\mathbf{S}$	–	all semigroups
$\mathbf{B}$	$x^{2}\approx x$	bands (idempotent semigroups)
$\mathbf{I}$	$x\approx y$	trivial semigroups
$\mathbf{CR}$	$x^{\omega+1}\approx x$	completely regular semigroups
$\mathbf{G}$	$x^{\omega}\approx 1$	groups
$\mathbf{A}$	$x^{\omega+1}\approx x^{\omega}$	aperiodic semigroups
$\mathbf{N}$	$x^{\omega}\approx 0$	nilpotent semigroups
$\mathbf{Com}$	$xy\approx yx$	commutative semigroups

Most of our analysis will concern pseudovarieties – that is, classes of finite semigroups closed under formation of finite direct products, subsemigroups, and homomorphic images. According to Reitermann [30, Theorem 3.1], such a class consists of all finite semigroups satisfying some set of profinite identities. Pseudovarieties are also closely connected to classes of regular languages exhibiting natural closure properties, as established by Eilenberg [14].

Throughout, we use boldface type to denote pseudovarieties and specify defining sets of (profinite) identities using double-struck square brackets. For example, $\mathbf{Com}=\llbracket xy\approx yx\rrbracket$ indicates that $\mathbf{Com}$ is the pseudovariety consisting of all finite semigroups satisfying the identity $xy\approx yx$ , that is, all finite commutative semigroups. Some important pseudovarieties, which serve as convenient reference points, are listed in Table 1.

Central in this work, as they form primary obstructions, are the following pseudovarieties:

\mathbf{LRB}=\llbracket x^{2}\approx x,xyx\approx xy\rrbracket,\quad\mathbf{% RRB}=\llbracket x^{2}\approx x,xyx\approx yx\rrbracket,\quad\mathbf{T}=% \llbracket x^{2}\approx xyx\approx 0\rrbracket.

For reference, $\mathbf{T}$ is a pseudovariety of nilpotent semigroups (that is, $\mathbf{T}\subseteq\mathbf{N}$ ), while the classes $\mathbf{LRB}$ and $\mathbf{RRB}$ consist of all finite left-regular and right-regular bands, respectively.

Other pseudovarieties of bands that we consider here are $\mathbf{RB}=\llbracket x^{2}\approx x,xyz\approx xz\rrbracket$ , comprising rectangular bands;²²2Be aware that in the literature $\mathbf{RB}$ sometimes denotes the pseudovariety of regular bands instead. $\mathbf{Sl}=\mathbf{B}\cap\mathbf{Com}=\llbracket x^{2}\approx x,xy\approx yx\rrbracket$ , comprising semilattices; and $\mathbf{NB}=\llbracket x^{2}\approx x,uxyv\approx uyxv\rrbracket$ , comprising normal bands. The (pseudo-)varieties of bands have been completely classified by Biryukov [10], Fennemore [15], and Gerhard [20].

In addition, we consider pseudovarieties defined in terms of extensions by nilpotent semigroups, which are most conveniently expressed as Mal’cev products (though used here only for notation). Given a pseudovariety $\mathbf{V}$ , we write $\mathbf{V}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}$ for the pseudovariety with $S\in\mathbf{V}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}$ if and only if the ideal $S^{k}\leqslant S$ belongs to $\mathbf{V}$ for some $k\geqslant 1$ – that is, the semigroup $S$ is an extension of $S^{k}\in\mathbf{V}$ by the Rees quotient $S/S^{k}\in\mathbf{N}$ , which is obtained by identifying all elements of $S^{k}$ . Fixing $k\geqslant 1$ yields the pseudovariety $\mathbf{V}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ instead, where $\mathbf{N}_{k}=\llbracket x_{1}\cdots x_{k}\approx 0\rrbracket$ refers to the pseudovariety of finite $k$ -nilpotent semigroups.

2.2 Complexity

We assume that the reader is familiar with standard complexity classes such as $\mathsf{L}$ , $\mathsf{NL}$ , $\mathsf{NC}$ , $\mathsf{P}$ , $\mathsf{NP}$ , and $\mathsf{PSPACE}$ ; see, for example, [3]. Throughout, we write $\operatorname{polylog}n$ for $\log^{\mathcal{O}(1)}n$ .

For sublinear time classes, we use random-access Turing machines meaning that the Turing machine has a separate address tape and a query state; whenever the Turing machine goes into the query state and the address tape contains the number $i$ in binary, the $i$ 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 functions $t(n),s(n)\in\Omega(\log n)$ , the classes $\hbox{\small$\mathsf{DTISP}$}(t(n),s(n))$ and $\hbox{\small$\mathsf{NTISP}$}(t(n),s(n))$ consist of the problems decidable by (non-)deterministic, $\mathcal{O}(t(n))$ -time and $\mathcal{O}(s(n))$ -space bounded, random-access Turing machines. Be aware that there must be one Turing machine that simultaneously satisfies the time and space bound. Without restricting the available space one obtains the classes $\hbox{\small$\mathsf{DTIME}$}(t(n))$ and $\hbox{\small$\mathsf{NTIME}$}(t(n))$ . We also define

\hbox{\small$\mathsf{NPOLYLOGTIME}$}=\hbox{\small$\mathsf{NTIME}$}(% \operatorname{polylog}n)=\bigcup_{\smash{c\geqslant 1}}\hbox{\small$\mathsf{% NTIME}$}(\log^{c}n).

The class $\hbox{\small$\mathsf{AC}$}^{0}$ is defined as the class of problems decidable by polynomial-size, constant-depth Boolean circuits where all gates may have arbitrary fan-in. The classes $\mathsf{FOLL}$ and $\hbox{\small$\mathsf{qAC}$}^{0}$ are defined analogously but allowing for circuits of polynomial size and depth $\mathcal{O}(\log\log n)$ , and for quasipolynomial size (i.e., $2^{\operatorname{polylog}n}$ ) and constant depth, respectively. Throughout, we consider only uniform circuit classes (specifically, $\hbox{\small$\mathsf{DTIME}$}(\log n)$ -uniform circuits for $\hbox{\small$\mathsf{AC}$}^{0}$ and $\mathsf{FOLL}$ , and $\hbox{\small$\mathsf{DTIME}$}(\operatorname{polylog}n)$ -uniform circuits for $\hbox{\small$\mathsf{qAC}$}^{0}$ ), meaning that the circuits can be constructed (or verified) efficiently; see [38] for details.

3 Compression via Straight-Line Programs

In this work, we are interested in the efficient representation of semigroup elements using straight-line programs. These are commonly defined as circuits over the algebraic structure (e.g. [26]), via context-free grammars that generate a single word (e.g. [25]) or, in some cases, as sequences of elements corresponding to intermediate values of the former (e.g. [5]).

Here we take a pragmatic point of view. Given a semigroup $S$ , a straight-line program $\mathcal{A}$ over a set $\Sigma\subseteq S$ is a finite sequence of instructions to be executed in order (that is, without branches or loops) and operating on a potentially unbounded set of registers $\{r_{1},r_{2},\dots\}$ . Each register $r_{k}$ can store a single element of the semigroup $S$ , and the straight-line program may use the following two instruction types to alter the contents of the registers.

$\blacksquare$

Assign the fixed element $s\in\Sigma$ to the register $r_{k}$ . $\vphantom{x}\smash{r_{k}\leftarrow s}$
$\blacksquare$

Assign the product of the registers $r_{i},r_{j}$ to the register $r_{k}$ . $\vphantom{x}\smash{r_{k}\leftarrow r_{i}\cdot r_{j}}$

In the second type of instruction, the registers $r_{i}$ , $r_{j}$ , and $r_{k}$ are not necessarily distinct, but we require that the input registers $r_{i}$ and $r_{j}$ were each assigned in some previous instruction.

The straight-line program $\mathcal{A}$ is said to compute a semigroup element $t\in S$ if, upon completion of execution, some register $r_{k}$ contains the value $t$ . More generally, $\mathcal{A}$ computes some set $T\subseteq S$ if it computes every $t\in T$ , and the largest such set is the value set $V(\mathcal{A})$ .

The length $\ell({\mathcal{A}})$ and width $w(\mathcal{A})$ of the straight-line program $\mathcal{A}$ are the number of its instructions and the number of registers it operates on, respectively. Intuitively, the length and width of a straight-line program measure the time and space required to execute it.

Let $S$ be a finite semigroup and $\Sigma\subseteq S$ . Given a set $T\subseteq S$ and a width bound $2\leqslant w\leqslant\infty$ , we define the straight-line cost of $T$ over $\Sigma$ to be the quantity

c^{w}_{S}(T;\Sigma)\coloneqq\min\bigg\{\,\ell(\mathcal{A})\,:\text{$\mathcal{A% }$ is a straight-line program over $\Sigma$ with $T\subseteq V(\mathcal{A})$ % and $w(\mathcal{A})\leqslant w$}\bigg\}.

The straight-line cost of an element $t\in S$ , written $c^{w}_{S}(t;\Sigma)$ , is defined analogously. Sometimes we employ more general terminology and refer to either straight-line programs of bounded width, corresponding to arbitrary $w<\infty$ , or unbounded width, in the case where $w=\infty$ .

As with conventional programs, straight-line programs can be composed sequentially and invoked as subroutines, modulo simple modifications such as register renaming. Applying such composition techniques leads to the following estimates.

Lemma 4.

Let $S$ be a finite semigroup, $\Sigma,\Delta\subseteq S$ , and $t\in S$ . Then, for all $2\leqslant w,\delta\leqslant\infty$ ,

c^{w+\delta}_{S}(t;\Sigma)\leqslant c^{w}_{S}(t;\Sigma\cup\Delta)+c^{\delta}_{% S}(\Delta;\Sigma)\quad\text{and}\quad c^{w+\delta-1}_{S}(t;\Sigma)\leqslant c^% {w}_{S}(t;\Sigma\cup\Delta)\cdot\max_{t^{\prime}\in\Delta}c^{\delta}_{S}(t^{% \prime};\Sigma).

A fundamental subroutine, which we often employ without explicit reference, is fast exponentiation via repeated squaring. In the context of straight-line programs, this technique dates back at least to 1937, when Scholz presented it as an application of addition chains [33].

Observation 5.

Let $S$ be a finite semigroup, $t\in S$ , and $n\geqslant 1$ . Then $c_{S}^{2}(t^{n};\{t\})\in\mathcal{O}(\log n)$ .

One of our primary concerns are worst-case bounds for $c^{w}_{S}(t;\Sigma)$ as $\Sigma\subseteq S$ and $t\in S$ vary; that is, in the quantity $C_{S}^{w}\coloneqq\max\big\{c^{w}_{S}(t;\Sigma):t\in\langle\Sigma\rangle% \subseteq S\big\}$ . More specifically, we seek to asymptotically bound $C^{w}_{S}$ in the size of the semigroup $S$ as the latter ranges over the members of a given pseudovariety $\mathbf{V}$ . To this end, let us define $C^{w}_{\mathbf{V}}\colon\mathbb{N}\to\mathbb{N}$ by

C^{w}_{\mathbf{V}}(N)\coloneqq\max\big\{C^{w}_{S}:S\in\mathbf{V},\left|S\right% |\leqslant N\big\}.

We then say that $\mathbf{V}$ admits straight-line programs of width $w$ and length $\mathcal{O}(f(N))$ provided that $C^{w}_{\mathbf{V}}(N)\in\mathcal{O}(f(N))$ and, conversely, that $\mathbf{V}$ requires straight-line programs of length $\Omega(f(N))$ provided that $C^{\infty}_{\mathbf{V}}(N)\in\Omega(f(N))$ . Finally, we say that a pseudovariety $\mathbf{V}$ affords efficient compression (via straight-line programs) if $C^{\infty}_{\mathbf{V}}(N)\in\mathcal{O}(\operatorname{polylog}N)$ .

4 Obstructions to Efficient Compression

As mentioned in the introduction, the following three pseudovarieties constitute the primary obstructions to efficient compression in semigroups via straight-line programs:

\mathbf{LRB}=\llbracket x^{2}\approx x,xyx\approx xy\rrbracket,\quad\mathbf{% RRB}=\llbracket x^{2}\approx x,xyx\approx yx\rrbracket,\quad\mathbf{T}=% \llbracket x^{2}\approx xyx\approx 0\rrbracket.

A simple consequence of their defining identities is that representing elements of their members in terms of generators essentially requires injective words, that is, words in which each generator appears at most once. Indeed, for $\mathbf{T}$ , all nonzero elements must be represented this way, while for $\mathbf{LRB}$ and $\mathbf{RRB}$ , any word in generators defines the same element as the word obtained by keeping only the first or last occurrence of each generator, respectively.

Intuitively, since injective words contain no repeated factors, they cannot be efficiently compressed via straight-line programs (or any compression method relying on such repetitions). However, because we measure efficiency relative to the size of the semigroup, a formal proof requires exhibiting members of these pseudovarieties in which some element cannot be expressed using few generators, as done by Fleischer [16, Lemma 4.11, Lemma 4.15].

Lemma 6 (Fleischer).

Let $\mathbf{V}$ be a pseudovariety that contains $\mathbf{LRB}$ , $\mathbf{RRB}$ , or $\mathbf{T}$ . Then, for every $N\geqslant 1$ , there exist $S\in\mathbf{V}$ with $\left|S\right|\leqslant N$ , a generating set $\Sigma\subseteq S$ with $\left|\Sigma\right|\in\Omega(\sqrt{N})$ , and an element $t\in S$ such that no subsemigroup generated by a proper subset of $\Sigma$ contains $t$ .

In particular, $C^{\infty}_{\mathbf{V}}(N)\in\Omega(\sqrt{N})$ ; that is, $\mathbf{V}$ requires straight-line programs of length $\Omega(\sqrt{N})$ .

5 Semigroups of Bounded Diameter

In this section, we classify pseudovarieties where every semigroup element can be written as a product of bounded length over any generating set (see Theorem 10) and show that all other pseudovarieties require straight-line programs of length $\Omega(\log N)$ .

Definition 7.

Let $\mathbf{V}$ be a pseudovariety. We say that $\mathbf{V}$ has bounded diameter if there is a constant $D\geqslant 1$ such that, for every $S\in\mathbf{V}$ and generating set $\Sigma\subseteq S$ , it holds that $\Sigma^{\leqslant D}=S$ ; that is, every element $t\in S$ is a product of generators from $\Sigma$ of length at most $D$ .

Clearly, if $\mathbf{V}$ has bounded diameter, then $C^{2}_{\mathbf{V}}(N)\leqslant 2D-1$ (with $D$ as above); and, conversely, if $C^{\infty}_{\mathbf{V}}(N)\leqslant C$ for some constant $C$ , then $\mathbf{V}$ has bounded diameter (with $D=2^{C}$ ). In other words, the pseudovarieties of bounded diameter are precisely the pseudovarieties admitting straight-line programs of length (and width) $\mathcal{O}(1)$ . An obvious example of such a pseudovariety is $\mathbf{N}_{k}=\llbracket x_{1}\cdots x_{k}\approx 0\rrbracket$ , which consists of all finite $k$ -nilpotent semigroups.

The following result, which will also be of use in the proof of our main theorem, generalizes this example to Mal’cev products of the form $\mathbf{V}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ . (Indeed, it applies to $\mathbf{N}_{k}=\mathbf{I}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ where $\mathbf{I}=\llbracket x\approx 1\rrbracket$ is the trivial pseudovariety.) Recall that a finite semigroup $S$ belongs to the pseudovariety $\mathbf{V}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ if and only if its ideal $S^{k}\leqslant S$ belongs to $\mathbf{V}$ .

Lemma 8.

Let $\mathbf{V}\subseteq\mathbf{V}^{\prime}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N% }_{k}$ for a pseudovariety $\mathbf{V}^{\prime}$ and $k\geqslant 1$ . Then, for all $2\leqslant w\leqslant\infty$ ,

C^{w+1}_{\mathbf{V}}(N)\leqslant C^{w}_{\mathbf{V}^{\prime}}(N)\cdot(4k-3).

Herein, the factor $4k-3$ is a constant and, hence, suppressed in Landau notation, in which the bound reads $C^{w+1}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{V}^{\prime}}(N))$ . However, be aware that $\mathbf{N}=\bigcup_{k}\mathbf{N}_{k}$ , which consists of all finite nilpotent semigroups, does not afford efficient compression since $\mathbf{T}\subseteq\mathbf{N}$ .

Proof.

Consider a semigroup $S\in\mathbf{V}$ , a generating set $\Sigma\subseteq S$ , and an element $t\in S$ . If the element $t$ is not contained in the ideal $S^{k}\leqslant S$ , then it can be written as a product of generators from $\Sigma$ of length less than $k$ ; hence $c^{2}_{S}(t;\Sigma)\leqslant 2k-3$ . Otherwise, since $S^{k}\in\mathbf{V}^{\prime}$ is generated by the set $\Delta=\Sigma^{\leqslant 2k-1}\cap S^{k}$ , the second inequality of Lemma 4 yields

c^{w+1}_{S}(t;\Sigma)\leqslant c^{w}_{S^{k}}(t;\Delta)\cdot\max_{t^{\prime}\in% \Delta}c^{2}_{S}(t^{\prime};\Sigma)\leqslant C^{w}_{\mathbf{V}^{\prime}}(\left% |S\right|)\cdot(4k-3).\

$\hfill\blacktriangleleft$

Another example of bounded diameter is given by $\mathbf{RB}=\llbracket x^{2}\approx x,xyz\approx xz\rrbracket$ , which consists of all finite rectangular bands, and satisfies $C^{2}_{\mathbf{RB}}(N)\leqslant 3$ . Combining the latter with Lemma 8 yields $C^{3}_{\mathbf{V}}(N)\leqslant 12k-9$ for every pseudovariety $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ . Using a direct argument (which is straight-foreword and, therefore, omitted), this can be slightly improved.

Lemma 9.

If $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ for some $k\geqslant 1$ , then $C^{2}_{\mathbf{V}}(N)\leqslant 6k-3$ .

Fleischer showed that the pseudovariety $\mathbb{L}\mathbf{I}_{k}=\llbracket x_{1}\cdots x_{k}yz_{1}\cdots z_{k}\approx x% _{1}\cdots x_{k}z_{1}\cdots z_{k}\rrbracket$ has bounded diameter for all $k\geqslant 1$ [16, Proposition 4.5]. However, since $\mathbb{L}\mathbf{I}_{k}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}% \mathbf{N}_{2k}\subseteq\mathbb{L}\mathbf{I}_{3k}$ holds for every $k\geqslant 1$ , this is equivalent to the above. As it turns out, every pseudovariety of bounded diameter is contained in $\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ or, equivalently, in $\mathbb{L}\mathbf{I}_{k}$ for some $k\geqslant 1$ .

Theorem 10.

Let $\mathbf{V}$ be a pseudovariety. Then exactly one of the following holds.

$\blacksquare$

The pseudovariety $\mathbf{V}$ has bounded diameter. In particular, $C^{2}_{\mathbf{V}}(N)\in\mathcal{O}(1)$ .
$\blacksquare$

The pseudovariety $\mathbf{V}$ requires straight-line programs of length $\Omega(\log N)$ .

Moreover, the former is the case if and only if $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ for some $k\geqslant 1$ .

Before we prove Theorem 10 in its full generality, let us first establish the lower bound asserted by the second alternative. We will distinguish between two cases, depending on how the pseudovariety in question is situated relative to pseudovarieties $\mathbb{L}\mathbf{I}$ and $\mathbf{U}$ .

The first case concerns the pseudovariety $\mathbb{L}\mathbf{I}=\llbracket x^{\omega}yx^{\omega}\approx x^{\omega}\rrbracket$ of locally trivial semigroups, that is, semigroups having only trivial submonoids. By [1, Exercise 6.4.2], it satisfies

\mathbb{L}\mathbf{I}=\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}=% \bigcup_{k\geqslant 1}\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}% =\bigcup_{k\geqslant 1}\mathbb{L}\mathbf{I}_{k}.

The following observation is also contained in Fleischer’s dissertation [16, Proposition 4.7].

Lemma 11 (Fleischer).

Let $\mathbf{V}$ be a pseudovariety with $\mathbf{V}\not\subseteq\mathbb{L}\mathbf{I}$ . Then $C^{\infty}_{\mathbf{V}}(N)\in\Omega(\log N)$ .

The second case concerns the pseudovariety $\mathbf{U}=\mathbf{T}\cap\mathbf{Com}=\llbracket xy\approx yx,x^{2}\approx 0\rrbracket$ , which serves as a direct obstruction to the property of having bounded diameter.

Lemma 12.

Let $\mathbf{V}$ be a pseudovariety with $\mathbf{U}\subseteq\mathbf{V}$ . Then $C^{\infty}_{\mathbf{V}}(N)\in\Omega(\log N)$ .

Proof.

For every $n\geqslant 1$ , the semigroup $S=\langle s_{1},\dots,s_{n}:s_{i}s_{j}=s_{j}s_{i},\,s_{i}^{2}s_{j}=s_{i}^{2}\;% (1\leqslant i,j\leqslant k)\rangle$ is contained in $\mathbf{U}\subseteq\mathbf{V}$ . Indeed, the defining relations imply $\smash{s_{i}^{2}=s_{i}^{2}s_{j}^{2}=s_{j}^{2}}$ , so that $s^{2}$ is the zero element of $S$ for every $s\in S$ . The semigroup $S$ contains exactly $2^{n}$ elements, namely the zero element and every product of distinct elements from $\Sigma\coloneqq\{s_{1},\dots,s_{n}\}$ .

Since the element $t=s_{1}\cdots s_{n}\in S$ is not contained in the subsemigroup generated by any proper subset of $\Sigma$ , it follows that every generator must appear in every straight-line program computing $t$ over $\Sigma$ ; hence, $c^{\infty}_{S}(t;\Sigma)\in\Omega(\log\left|S\right|)$ . $\hfill\blacktriangleleft$

Proof of Theorem 10.

In view of Lemma 9 as well as Lemmas 11 and 12, it suffices to show that if $\mathbf{V}\subseteq\mathbb{L}\mathbf{I}$ and $\mathbf{U}\not\subseteq\mathbf{V}$ , then $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ for some $k\geqslant 1$ . To this end, let us first note that $\mathbb{L}\mathbf{I}=\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}$ ; see [1, Exercise 6.4.2]. Assuming $\mathbf{V}\subseteq\mathbb{L}\mathbf{I}$ , we therefore have that $\mathbf{V}\subseteq\mathbf{RB}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ if and only if $\mathbf{V}\cap\mathbf{N}\subseteq\mathbf{N}_{k}$ . Almeida and Reilly [2, Proposition 4.4] have shown that the latter is equivalent to the condition $\mathbf{U}_{k+1}\not\subseteq\mathbf{V}\cap\mathbf{N}$ where $\mathbf{U}_{k+1}=\mathbf{U}\cap\mathbf{N}_{k+1}$ . Since $\bigcup_{k\geqslant 1}\mathbf{U}_{k}=\mathbf{U}\subseteq\mathbf{N}$ , this condition holds for some $k\geqslant 1$ provided that $\mathbf{U}\not\subseteq\mathbf{V}$ . $\hfill\blacktriangleleft$

6 Permutative Semigroups

In this section, we examine efficient compression in pseudovarieties where every member satisfies a common permutation identity – that is, an identity $x_{1}\cdots x_{n}\approx x_{\sigma(1)}\cdots x_{\sigma(n)}$ where $\sigma\in\mathrm{Sym}(n)$ is a nontrivial permutation of the symbols $1,\dots,n$ . We refer to such pseudovarieties, and their members, as permutative.³³3Be aware that some authors define a permutative pseudovariety as a pseudovariety consisting of permutative semigroups, meaning that the permutation identity may differ between its members. This notion generalizes commutativity, which corresponds to the identity $xy\approx yx$ , and is equivalent to it for monoids.

Proposition 13.

Let $\mathbf{V}$ be a permutative pseudovariety. Then $C_{\mathbf{V}}^{2}(N)\in\mathcal{O}(\log N)$ .

This improves upon an upper bound previously established by Fleischer [16, Lemma 4.9], which shows that commutative semigroups admit straight-line programs of width three and length $\mathcal{O}(\smash{\log}^{2}N)$ . In view of Theorem 10, our bound is asymptotically optimal.

Proof.

According to Putcha and Yaqub [27, Theorem 1], every permutation identity implies the identity $u_{1}\cdots u_{k}xyv_{1}\cdots v_{k}\approx u_{1}\cdots u_{k}yxv_{1}\cdots v_{k}$ for each sufficiently large $k\geqslant 0$ . In the following, we fix some $k\geqslant 1$ such that $\mathbf{V}$ satisfies this identity.

Consider a semigroup $S\in\mathbf{V}$ , a generating set $\Sigma\subseteq S$ , and some element $t\in S$ . Without loss of generality, the element $t$ is not a product of generators with $2k$ or fewer factors. Under these assumptions, the element $t$ can then be written as

t=u\,s_{1}^{\nu_{1}}\cdots\,s_{n}^{\nu_{n}}\,v\qquad\text{with }s_{1},\dots,s_% {n}\in\Sigma\text{, }u,v\in\Sigma^{k}\text{, and }\nu_{1},\dots,\nu_{n}% \geqslant 0.

(1)

Fix the elements $s_{1},\dots,s_{n}\in\Sigma$ and $u,v\in\Sigma^{k}$ involved in such an expression. Once these are fixed, we associate to each $\mu=(\mu_{1},\dots,\mu_{n})\in\mathbb{N}^{n}$ the element $s^{\mu}\coloneqq s_{1}^{\mu_{1}}\cdots\,s_{n}^{\mu_{n}}\in S\cup\{1\}$ . We then also fix the lexicographically minimal tuple of exponents $\nu\in\mathbb{N}^{n}$ such that $t=u\,s^{\nu}\,v$ .

Suppose given $\xi,\eta\in\mathbb{N}^{n}$ such that $\xi,\eta\leqslant\nu$ in the component-wise order. We claim that, under these conditions, $u\,s^{\xi}=u\,s^{\eta}$ implies $\xi=\eta$ . Indeed, if $\xi\leqslant_{\text{lex}}\eta$ , then

t=u\,s^{\nu}\,v=u\,s^{\eta}s^{\nu-\eta}\,v=u\,s^{\xi}s^{\nu-\eta}\,v=u\,s^{\nu% -\eta+\xi}\,v

and, clearly, $\nu-\eta+\xi\leqslant_{\text{lex}}\nu$ ; hence, $\xi=\eta$ by minimality of $\nu$ . This establishes our claim, which implies $(\nu_{1}+1)\cdot\ldots\cdot(\nu_{n}+1)\leqslant\left|S\right|$ and, hence, $\log(\nu_{1}+1)+\ldots+\log(\nu_{n}+1)\leqslant\log\left|S\right|$ .

Computing $t$ as in the expression (1) and using fast exponentiation yields a straight-line program of width three and length $\mathcal{O}(\log\left|S\right|)$ – the latter being due to the above inequality. Using a simultaneous variant of fast exponentiation, this can be done with two registers. $\hfill\blacktriangleleft$

Combining Lemma 6 and Proposition 13, we arrive at the following characterization for pseudovarieties of aperiodic semigroups, i.e., for subpseudovarieties of $\mathbf{A}=\llbracket x^{\omega+1}\approx x^{\omega}\rrbracket$ .

Theorem 14.

Let $\mathbf{V}\subseteq\mathbf{A}$ be a pseudovariety. The following are equivalent.

(1)

The pseudovariety $\mathbf{V}$ affords efficient compression.
(2)

The pseudovariety $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , nor $\mathbf{T}$ .
(3)

The pseudovariety $\mathbf{V}$ is permutative.
(4)

The pseudovariety $\mathbf{V}$ admits straight-line programs of width two and length $\mathcal{O}(\log N)$ .

Proof.

See Lemma 6 for $(1)\Rightarrow(2)$ , Proposition 13 entails $(3)\Rightarrow(4)$ , and $(4)\Rightarrow(1)$ holds by definition. For the implication $(2)\Rightarrow(3)$ we refer to [35, Corollary 16]. $\hfill\blacktriangleleft$

7 Groups

Having just established our main theorem for the case of aperiodic semigroups (Theorem 14), we now turn our attention to the pseudovarieties of groups.

Most of our group theory notation follows Robinson’s book [32]. In particular, $N\trianglelefteq G$ denotes that $N$ is a normal subgroup of a group $G$ . Furthermore, $g^{h}=h^{-1}gh$ denotes the conjugate of $g\in G$ by $h\in G$ and, for $\Delta,\Sigma\subseteq G$ , we write $[\Delta,\Sigma]$ for the subgroup generated by all commutators $[g,h]=g^{-1}h^{-1}gh$ with $g\in\Delta$ and $h\in\Sigma$ . We differ from the notation in Robinson’s book, however, by writing $\langle\!\langle\Sigma\rangle\!\rangle$ to denote the normal subgroup generated by $\Sigma$ ; that is, $\langle\!\langle\Sigma\rangle\!\rangle=\langle g^{h}:g\in\Sigma,h\in G\rangle$ . Note that, since we only consider finite groups, the subgroup generated by a (nonempty) set $\Sigma$ coincides with the subsemigroup generated by it.

By Lagrange’s theorem, we have the following well-known and straight-forward observation, which will be used in the following without further reference.

Observation 15.

7.1 General Groups

When considering a group $G$ , we allow for the formation inverses in straight-line programs; that is, a group straight-line program over $\Sigma\subseteq G$ may use the following instruction types.

$\blacksquare$

Assign the fixed element $g\in\Sigma$ to the register $r_{k}$ . $\vphantom{x}\smash{r_{k}\leftarrow g}$
$\blacksquare$

Assign the product of the registers $r_{i},r_{j}$ to the register $r_{k}$ . $\vphantom{x}\smash{r_{k}\leftarrow r_{i}\cdot r_{j}}$
$\blacksquare$

Assign the inverse of the registers $r_{i}$ to the register $r_{k}$ . $\vphantom{x}\smash{r_{k}\leftarrow r_{i}^{-1}}$

This modification does not increase the expressiveness for finite groups compared to ordinary (semigroup) straight-line programs, since one can compute the inverse of a group element $g$ as $g^{-1}=g^{\omega-1}$ . The following observation shows that the decrease in cost afforded by the extra instruction type is often negligible as well. Therein, and throughout this section, the group straight-line costs, which are defined just as in Section 3, are marked with a tilde.

Lemma 16.

Let $\mathbf{H}\subseteq\mathbf{G}$ be a pseudovariety of groups. Then, for all $2\leqslant w\leqslant\infty$ ,

C^{\infty}_{\mathbf{H}}(N)\leqslant 2\cdot\tilde{C}^{\infty}_{\mathbf{H}}(N)+% \mathcal{O}(\log N)\quad\text{and}\quad C^{w+1}_{\mathbf{H}}(N)\leqslant\tilde% {C}^{w}_{\mathbf{H}}(N)\cdot\mathcal{O}(\log N).

Proof Sketch.

The second inequality arises from the on-the-fly computation of inverses via fast exponentiation. To see the first, the crucial step is to note that $c^{\infty}_{G}(\Sigma^{-1};\Sigma)\in\mathcal{O}(\log\left|G\right|)$ for all $\Sigma\subseteq G$ with $\left|\Sigma\right|\leqslant\log\left|G\right|$ . Indeed, one can compute the product of all $g\in\Sigma$ , then invert this product using fast exponentiation and, finally, extract the inverses of the individual generators from the result. From there, we can emulate group straight-line programs over $\Sigma$ by using a separate register $\bar{r}$ for each register $r$ to simultaneously compute inverses. $\hfill\blacktriangleleft$

Due to the above, the following well-known result by Babai and Szemerédi [5, Theorem 3.1], which was originally stated for groups, can also be utilized in the semigroup setting.

Reachability Lemma (Babai, Szemerédi).

The pseudovariety $\mathbf{G}=\llbracket x^{\omega}\approx 1\rrbracket$ , which consists of all finite groups, admits straight-line programs of width⁴⁴4While Babai and Szemerédi [5] do not discuss width bounds, this follows easily from their proof. $\mathcal{O}(\log N)$ and length $\mathcal{O}(\smash{\log}^{2}N)$ .

Note that the bounds presented by Babai and Szemerédi are not necessarily optimal. For instance, Proposition 13 implies that the pseudovariety $\mathbf{G}_{\textup{{Ab}}}$ , which consists of all finite Abelian groups, satisfies $C^{2}_{\mathbf{G}_{\textup{{Ab}}}}(N)\in\mathcal{O}(\log N)$ . In the following, we present some techniques that might aid in future improvements of the bounds for general groups. The techniques will then be applied in Section 7.2 to obtain such improvements for solvable groups.

Definition 17.

Let $G$ be a group. We call a generating set $\Sigma\subseteq G$ adapted to a subnormal series⁵⁵5Recall that $G=G_{0}\geqslant\dots\geqslant G_{n}=1$ is a subnormal series if $G_{i}$ is normal in $G_{i-1}$ for all $1\leqslant i\leqslant n$ . $G=G_{0}\trianglerighteq\dots\trianglerighteq G_{n}=1$ provided that $\Sigma\cap G_{i-1}$ generates $G_{i-1}$ for all $1\leqslant i\leqslant n$ .

Moreover, we say that $\Sigma\subseteq G$ is a polycyclic generating set if it is adapted to a subnormal series $G=G_{0}\trianglerighteq\dots\trianglerighteq G_{n}=1$ with $G_{i-1}/G_{i}$ cyclic for all $1\leqslant i\leqslant n$ . Note that, as every generating set of an Abelian group is polycyclic, it follows that $\Sigma\subseteq G$ is a polycyclic generating set if and only if it is adapted to a subnormal series with Abelian quotients.

If a generating set $\Sigma\subseteq G$ is adapted to a subnormal series, then the associated straight-line costs $c^{w}_{G}(t;\Sigma)$ are essentially dominated by those in the consecutive quotients.

Lemma 18.

Let $G$ be a group generated by a set $\Sigma\subseteq G$ , and let $\mathbf{H}\subseteq\mathbf{G}$ .⁶⁶6Here, we allow $\mathbf{H}\subseteq\mathbf{G}$ to be an arbitrary class of finite groups. Furthermore, suppose that $\Sigma$ is adapted to a subnormal series $G=G_{0}\trianglerighteq\dots\trianglerighteq G_{n}=1$ with $H_{i}\coloneqq G_{i-1}/G_{i}$ satisfying $H_{i}\in\mathbf{H}$ for all $1\leqslant i\leqslant n$ . Then, for all $t\in G$ and $2\leqslant w\leqslant\infty$ ,

c^{w+1}_{G}(t;\Sigma)\leqslant C^{w}_{\mathbf{H}}(\left|H_{1}\right|)+\ldots+C% ^{w}_{\mathbf{H}}(\left|H_{n}\right|)+n-1.

In particular, if $C^{w}_{\mathbf{H}}(N)\in\mathcal{O}(\log^{c}N)$ for some $c\geqslant 1$ , then $c^{w+1}_{G}(t;\Sigma)\in\mathcal{O}(\log^{c}\left|G\right|)$ .

Note that this yields yet another proof that the pseudovariety $\mathbf{G}_{\textup{{Ab}}}$ of finite Abelian groups admits straight-line programs of bounded width and logarithmic length. Indeed, we can simply take $\mathbf{H}$ to be the class of all finite cyclic groups, which satisfies $C^{2}_{\mathbf{H}}(N)\in\mathcal{O}(\log N)$ .

Proof.

In the additional register, we accumulate $t=t_{1}\cdots t_{n}$ with $t_{i}\in G_{i-1}$ . Specifically, suppose that $t^{\prime}_{i}=(t_{1}\cdots t_{i-1})^{-1}t\in G_{i-1}$ is already determined. Lifting an appropriately chosen straight-line program computing $\pi_{i}(t^{\prime}_{i})\in H_{i}$ over $\pi_{i}(\Sigma\cap G_{i-1})$ – where $\pi_{i}\colon G_{i-1}\to H_{i}$ denotes the quotient homomorphism – yields a straight-line program computing $t_{i}\in G_{i-1}$ over $\Sigma\cap G_{i-1}$ with $\pi_{i}(t_{i})=\pi_{i}(t^{\prime}_{i})$ . Since the latter implies $t^{\prime}_{i+1}\in G_{i}$ , we may continue the process until we eventually arrive at $t^{\prime}_{n+1}\in G_{n}=1$ ; hence, $t=t_{1}\cdots t_{n}$ .

For the addendum we assume, without loss of generality, that $H_{i}\neq 1$ for all $1\leqslant i\leqslant n$ , so that $\left|H_{1}\right|,\dots,\left|H_{n}\right|\geqslant 2$ . Then, since $\left|H_{1}\right|\cdot\ldots\cdot\left|H_{n}\right|=\left|G\right|$ by Lagrange’s theorem, we obtain the equality $\log\left|H_{1}\right|+\ldots+\log\left|H_{n}\right|=\log\left|G\right|$ and the bound $n\leqslant\log\left|G\right|$ . This implies desired bound on $c^{w+1}_{G}(t;\Sigma)$ by superaditivity of the function $\log^{c}\colon[1,\infty)\to[0,\infty)$ . $\hfill\blacktriangleleft$

7.2 Solvable Groups

Let us now turn our attention to solvable groups; that is, to groups admitting a subnormal series with Abelian consecutive quotients. The finite such groups form the pseudovariety $\mathbf{G}_{\textup{{sol}}}$ .

Theorem 19.

Let $\mathbf{H}$ be a pseudovariety with $\mathbf{H}\subseteq\mathbf{G}_{\textup{{sol}}}$ . Then

C^{\infty}_{\mathbf{H}}(N)\in\mathcal{O}(\log N)\quad\text{and}\quad C^{4}_{% \mathbf{H}}(N)\in\mathcal{O}(\log^{3}N).

We suspect that it is also possible to show that $C_{\mathbf{H}}^{w}(N)\in\mathcal{O}(\log^{2}N)$ for some slightly larger width bound $w<\infty$ using similar techniques. On the other hand, to answer whether or not the bound $C_{\mathbf{H}}^{w}(N)\in\mathcal{O}(\log N)$ holds for some $w<\infty$ is likely to require new ideas.

In the following, we prove Theorem 19 by providing efficient constructions of polycyclic generating sets for solvable groups – the unbounded and bounded width cases being treated separately. Throughout, we write $G=G^{(0)}\trianglerighteq G^{(1)}\trianglerighteq\dots$ for the derived series of a group $G$ where $G^{(k)}=[G^{(k-1)},G^{(k-1)}]$ and abbreviate $G^{\prime}\coloneqq G^{(1)}$ and $G^{\prime\prime}\coloneqq G^{(2)}$ .

Lemma 20.

Let $G$ be a group, $N\trianglelefteq G$ a normal subgroup, and $\Delta\subseteq N$ . Then

N=\langle\Delta\rangle N^{\prime\prime}\implies N^{\prime}=\langle\!\langle[% \Delta,\Delta]\rangle\!\rangle N^{\prime\prime}\quad\text{and}\quad N=\langle% \Delta\rangle N^{\prime}\implies N=\langle\!\langle\Delta\rangle\!\rangle N^{% \prime\prime}.

In particular, if $N$ is a solvable group, then $N=\langle\Delta\rangle N^{\prime}\implies N=\langle\!\langle\Delta\rangle\!\rangle$ .

Proof.

The first implication can be found in Robinson’s book [32, 5.1.7]. For the second implication, note that if $N=\langle\Delta\rangle N^{\prime}$ , then $N=\langle\Delta\rangle\,[\langle\Delta\rangle N^{\prime},\langle\Delta\rangle N% ^{\prime}]$ and, hence,

N\subseteq\langle\!\langle\Delta\rangle\!\rangle\,[\langle\!\langle\Delta% \rangle\!\rangle N^{\prime},\langle\!\langle\Delta\rangle\!\rangle N^{\prime}]% =\langle\!\langle\Delta\rangle\!\rangle\,[\langle\!\langle\Delta\rangle\!% \rangle,\langle\!\langle\Delta\rangle\!\rangle]\,[\langle\!\langle\Delta% \rangle\!\rangle,N^{\prime}]\,[N^{\prime},N^{\prime}]=\langle\!\langle\Delta% \rangle\!\rangle N^{\prime\prime}

where the second equality is due to well-known commutator identities; see [32, 5.1.5].

The addendum follows by induction on the derived length of $N$ . We omit the details. $\hfill\blacktriangleleft$

Given subsets $\Delta,\Sigma\subseteq G$ and $k\geqslant 0$ , we write $\operatorname{NC}_{k}(\Delta;\Sigma)=\{g^{h}:g\in\Delta,h\in\Sigma^{\leqslant k}\}$ and, in case $\Delta$ consists of a single element $g\in G$ , we abbreviate this to $\operatorname{NC}_{k}(g;\Sigma)$ . This construction can be used to efficiently construct a generating set of the normal closure.

Lemma 21.

Let $G$ be a group, $\Sigma\subseteq G$ a generating set, and $\Delta\subseteq G$ . If $k\geqslant\log\left|\langle\!\langle\Delta\rangle\!\rangle/\langle\Delta% \rangle\right|$ , then there exists some $\Xi\subseteq\operatorname{NC}_{k}(\Delta;\Sigma)$ with $\langle\!\langle\Delta\rangle\!\rangle=\langle\Delta\cup\Xi\rangle$ and $\tilde{c}^{\infty}_{G}(\Xi;\Delta\cup\Sigma)\leqslant 5k$ .

Proof.

To an initially empty set $\Xi$ , we successively add elements $g^{h}$ with $g\in\Delta\cup\Xi$ , $h\in\Sigma$ , and such that (the size of) the group $\langle\Delta\cup\Xi\rangle$ increases in every step. Since $\Delta\cup\Xi\subseteq\langle\!\langle\Delta\rangle\!\rangle$ , this process terminates after at most $\log\left|\langle\!\langle\Delta\rangle\!\rangle/\langle\Delta\rangle\right|\leqslant k$ steps. Hence, $\Xi\subseteq\operatorname{NC}_{k}(\Delta;\Sigma)$ and, clearly, $\tilde{c}^{\infty}_{G}(\Xi;\Delta\cup\Sigma)\leqslant 5k$ . We show that $\langle\!\langle\Delta\rangle\!\rangle=\langle\Delta\cup\Xi\rangle$ holds eventually.

Suppose that $g^{h}\not\in\langle\Delta\cup\Xi\rangle$ for some $g\in\langle\Delta\cup\Xi\rangle$ and $h\in G$ . Since $\Sigma$ generates $G$ as a semigroup, we may assume that $h\in\Sigma$ . Moreover, writing $g=g_{1}\cdots g_{n}$ with $g_{1},\dots,g_{n}\in\Delta\cup\Xi$ , we see that $g_{i}^{h}\not\in\langle\Delta\cup\Xi\rangle$ for some $1\leqslant i\leqslant n$ , for otherwise $g^{h}=g_{1}^{h}\cdots g_{n}^{h}\in\langle\Delta\cup\Xi\rangle$ . It follows that we may still add the element $g_{i}^{h}$ to the set $\Xi$ , thereby continuing the process. $\hfill\blacktriangleleft$

Combining the above Lemmas 20 and 21, we arrive at the following result. Together with Lemma 18, it implies the assertion of Theorem 19 for unbounded width.

Proposition 22.

Let $G$ be a solvable group with a generating set $\Sigma$ . Then there exists a generating set $\Delta\subseteq G$ adapted to the derived series of $G$ with $\tilde{c}^{\infty}_{G}(\Delta;\Sigma)\in\mathcal{O}(\log\left|G\right|)$ .

Proof.

For every $i\geqslant 0$ , we will construct a set $\Delta_{i}\subseteq G^{(i)}$ with $G^{(i)}=\langle\Delta_{i}\rangle G^{(i+1)}$ and such that $\tilde{c}^{\infty}_{G}(\Delta_{0};\Sigma)\leqslant\log{\lvert G^{(0)}/G^{(1)}\rvert}$ and $\tilde{c}^{\infty}_{G}(\Delta_{i};\Delta_{i-1}\cup\Sigma)\leqslant 17\cdot\log% {\lvert G^{(i-1)}/G^{(i+1)}\rvert}$ for $i\geqslant 1$ . In particular, the union $\Delta=\bigcup_{i\geqslant 0}\Delta_{i}$ will have the required properties, as

\tilde{c}^{\infty}_{G}(\Delta;\Sigma)\leqslant\tilde{c}^{\infty}_{G}(\Delta_{0% };\Sigma)+\sum_{\smash{i\geqslant 1}}\tilde{c}^{\infty}_{G}(\Delta_{i};\Delta_% {i-1}\cup\Sigma)\leqslant 18\cdot\log\left|G\right|+17\cdot\log\left|G^{\prime% }\right|\in\mathcal{O}(\log\left|G\right|).

To begin the construction, we choose any $\Delta_{0}\subseteq\Sigma$ of size $\left|\Delta_{0}\right|\leqslant{\lvert G^{(0)}/G^{(1)}\rvert}$ with the property that $G=\langle\Delta_{0}\rangle G^{\prime}$ . Now suppose that we have already constructed $\Delta_{0},\dots,\Delta_{i-1}$ . To construct $\Delta_{i}$ for $i\geqslant 1$ , we proceed as follows. First, using Lemma 21, choose $\Xi\subseteq G^{(i-1)}$ such that $\langle\!\langle\Delta_{i-1}\rangle\!\rangle G^{(i+1)}=\langle\Delta_{i-1}\cup% \Xi\rangle G^{(i+1)}$ and $\tilde{c}^{\infty}_{G}(\Xi;\Delta_{i-1}\cup\Sigma)\leqslant 5\cdot\log{\lvert G% ^{(i-1)}/G^{(i+1)}\rvert}$ . We then have $G^{(i-1)}=\langle\!\langle\Delta_{i-1}\rangle\!\rangle G^{(i+1)}=\langle\Delta% _{i-1}\cup\Xi\rangle G^{(i+1)}$ by Lemma 20.

As the next step, we choose $\Theta\subseteq\{[g,h]:g,h\in\Delta_{i-1}\cup\Xi\}$ minimally with the property that $\langle\Theta\rangle G^{(i+1)}=[\Delta_{i-1}\cup\Xi,\Delta_{i-1}\cup\Xi]G^{(i+% 1)}$ and, hence, $G^{(i)}=\langle\!\langle\Theta\rangle\!\rangle G^{(i+1)}$ by Lemma 20. By minimality of $\Theta$ , we have $\left|\Theta\right|\leqslant\log{\lvert G^{(i)}/G^{(i+1)}\rvert}$ . Moreover, since $\tilde{c}^{\infty}_{G}(t;\Delta_{i-1}\cup\Xi)\leqslant 7$ for every $t\in\Theta$ , this yields $\tilde{c}^{\infty}_{G}(\Theta;\Delta_{i-1}\cup\Xi)\leqslant 7\cdot\log{\lvert G% ^{(i)}/G^{(i+1)}\rvert}$ .

Finally, we use Lemma 21 to obtain $\Delta_{i}\subseteq G^{(i)}$ with $\langle\Delta_{i}\rangle G^{(i+1)}=\langle\!\langle\Theta\rangle\!\rangle G^{(% i+1)}=G^{(i)}$ and $\tilde{c}^{\infty}_{G}(\Delta_{i};\Theta\cup\Sigma)\leqslant 5\cdot\log{\lvert G% ^{(i)}/G^{(i+1)}\rvert}$ . Combining the straight-line costs yields

\begin{multlined}\tilde{c}^{\infty}_{G}(\Delta_{i};\Delta_{i-1}\cup\Sigma)% \leqslant\tilde{c}^{\infty}_{G}(\Delta_{i};\Theta\cup\Sigma)+\tilde{c}^{\infty% }_{G}(\Theta;\Xi\cup\Sigma)+\tilde{c}^{\infty}_{G}(\Xi;\Delta_{i-1}\cup\Sigma)% \\ \leqslant 12\cdot\log{\lvert G^{(i)}/G^{(i+1)}\rvert}+5\cdot\log{\lvert G^{(i-% 1)}/G^{(i+1)}\rvert}\leqslant 17\cdot\log{\lvert G^{(i-1)}/G^{(i+1)}\rvert}.% \end{multlined}\tilde{c}^{\infty}_{G}(\Delta_{i};\Delta_{i-1}\cup\Sigma)% \leqslant\tilde{c}^{\infty}_{G}(\Delta_{i};\Theta\cup\Sigma)+\tilde{c}^{\infty% }_{G}(\Theta;\Xi\cup\Sigma)+\tilde{c}^{\infty}_{G}(\Xi;\Delta_{i-1}\cup\Sigma)% \\ \leqslant 12\cdot\log{\lvert G^{(i)}/G^{(i+1)}\rvert}+5\cdot\log{\lvert G^{(i-% 1)}/G^{(i+1)}\rvert}\leqslant 17\cdot\log{\lvert G^{(i-1)}/G^{(i+1)}\rvert}.\

$\hfill\blacktriangleleft$

Unfortunately, the construction in Proposition 22 does not seem to adapt well to the case of bounded width straight-line programs. The problem is that the commutators $[g,h]$ formed in the construction have arguments $g$ and $h$ that are essentially independent of one another. Since the arguments $g$ and $h$ may themselves be commutators, nested to potentially unbounded depth, this rules out computation with a bounded number of registers.

This issue may be circumvented with an alternative construction: given subsets $\Delta,\Sigma\subseteq G$ with $\Sigma$ generating $G$ , we let $k=\big\lceil\log\left|G\right|\big\rceil$ and define sets

\operatorname{PCC}_{i+1}(\Delta;\Sigma)=\operatorname{NC}_{k}(\{[g,\tilde{g}]:% g\in\operatorname{PCC}_{i}(\Delta;\Sigma),\tilde{g}\in\operatorname{NC}_{k}(g;% \Sigma)\};\Sigma)

for $i\geqslant 0$ with $\operatorname{PCC}_{0}(\Delta;\Sigma)=\operatorname{NC}_{k}(\Delta;\Sigma)$ . Recall from Lemma 21 that $\operatorname{PCC}_{0}(\Delta;\Sigma)$ generates the normal subgroup $\langle\!\langle\Delta\rangle\!\rangle$ and, hence, so does the union $\operatorname{PCC}_{\ast}(\Delta;\Sigma)=\bigcup_{i\geqslant 0}\operatorname{% PCC}_{i}(\Delta;\Sigma)$ .

Note also that $\operatorname{PCC}_{i}(\Delta;\Sigma)\subseteq G^{(i)}$ . Therefore, if $G$ is solvable, then $\operatorname{PCC}_{i}(\Delta;\Sigma)=1$ for all $i\geqslant k$ , so that we then have $\operatorname{PCC}_{\ast}(\Delta;\Sigma)=\operatorname{PCC}_{0}(\Delta;\Sigma)% \cup\dots\cup\operatorname{PCC}_{k}(\Delta;\Sigma)$ .

Lemma 23.

If $G$ is solvable, then $c^{3}_{G}(t;\Delta\cup\Sigma)\in\mathcal{O}(\log^{2}\left|G\right|)$ for all $t\in\operatorname{PCC}_{\ast}(\Delta;\Sigma)$ .

Proof.

Let $t=[g,\tilde{g}]^{u}\in\operatorname{PCC}_{i}(\Delta;\Sigma)$ where $g\in\operatorname{PCC}_{i-1}(\Delta;\Sigma)$ and $\tilde{g}=g^{v}$ with $u,v\in\Sigma^{\leqslant k}$ .

To prove the required bound on the straight-line cost, it suffices to show that $t$ can be computed by a straight-line program over $\Delta\cup\Sigma$ of width three and length $\mathcal{O}(\log\left|G\right|)$ under the additional premiss that $g$ is already contained in one of the registers. To do so, we always keep $g$ in this register $r_{g}$ . We use one further register $r_{a}$ as an accumulator, which should hold the value $t$ at the end of execution. The third register $r_{u}$ is a utility register used for loading generators and for fast exponentiation (in particular, the computation of inverses). We allow for $r_{a}$ and $r_{u}$ to exchange these roles during the computation as necessary.

It remains to observe that $t=u^{-1}g^{-1}v^{-1}g^{-1}vgv^{-1}gvu$ can be computed from $g$ and $\Sigma$ by successively inverting the accumulator or multiplying the accumulator from the left or right by $g$ or elements from $\Sigma$ , and this requires only a constant number of inversions. $\hfill\blacktriangleleft$

Lemma 24.

If $G$ is solvable, then $\operatorname{PCC}_{\ast}(\Delta;\Sigma)$ is a polycyclic generating set of $\langle\!\langle\Delta\rangle\!\rangle$ .

Proof.

We proceed by induction on the size of the group $\langle\!\langle\Delta\rangle\!\rangle$ . We have $\langle\!\langle\Delta\rangle\!\rangle=\prod_{g\in\Delta}\langle\!\langle g% \rangle\!\rangle$ , and if $\langle\!\langle\Delta\rangle\!\rangle\neq\langle\!\langle g\rangle\!\rangle$ for some $g\in\Delta$ , then $\operatorname{PCC}_{\ast}(\{g\};\Sigma)$ is a polycyclic generating set of the normal subgroup $\langle\!\langle g\rangle\!\rangle$ by induction. Hence, if $\langle\!\langle\Delta\rangle\!\rangle\neq\langle\!\langle g\rangle\!\rangle$ holds for all $g\in\Delta$ , then $\operatorname{PCC}_{\ast}(\Delta;\Sigma)=\bigcup_{g\in\Delta}\operatorname{PCC% }_{\ast}(\{g\};\Sigma)$ is a polycyclic generating set of $\langle\!\langle\Delta\rangle\!\rangle$ . Otherwise, we may as well assume that $\Delta=\{g\}$ . By Lemma 21, $N\coloneqq\langle\!\langle g\rangle\!\rangle$ is generated by $\operatorname{NC}_{k}(g;\Sigma)$ . Hence, $N^{\prime}=\langle\!\langle[\operatorname{NC}_{k}(g;\Sigma),\operatorname{NC}_% {k}(g;\Sigma)]\rangle\!\rangle$ by Lemma 20 and, therefore, the set

\Delta^{\prime}\coloneqq\big\{[h,\tilde{h}]:h\in\operatorname{PCC}_{0}(\{g\};% \Sigma),\tilde{h}\in\operatorname{NC}_{k}(g;\Sigma)\big\}\supseteq\big\{[h,h^{% \prime}]:h,h^{\prime}\in\operatorname{NC}_{k}(g;\Sigma)\big\}

satisfies $N^{\prime}=\langle\!\langle\Delta^{\prime}\rangle\!\rangle$ . By induction, $\operatorname{PCC}_{\ast}(\Delta^{\prime};\Sigma)$ is a polycyclic generating set of $N^{\prime}$ . Now, observe that $\operatorname{PCC}_{0}(\Delta^{\prime};\Sigma)=\operatorname{NC}_{k}(\Delta^{% \prime};\Sigma)=\operatorname{PCC}_{1}(\Delta;\Sigma)$ . Therefore, the set $\operatorname{PCC}_{\ast}(\Delta;\Sigma)=\operatorname{PCC}_{0}(\Delta;\Sigma)% \cup\operatorname{PCC}_{\ast}(\Delta^{\prime};\Sigma)$ is indeed a polycyclic generating set of $N=\langle\!\langle\Delta\rangle\!\rangle$ . $\hfill\blacktriangleleft$

Proof of Theorem 19.

Let $G\in\mathbf{H}\subseteq\mathbf{G}_{\textup{{sol}}}$ , $\Sigma\subseteq G$ a generating set, and $t\in G$ . For the case of straight-line programs of unbounded width, Proposition 22 yields a polycyclic generating set $\Delta\subseteq G$ with $\tilde{c}^{\infty}_{G}(\Delta;\Sigma)\in\mathcal{O}(\log\left|G\right|)$ . By Lemma 18, applied with Abelian subquotients, we obtain $c^{\infty}_{G}(t;\Delta)\in\mathcal{O}(\log\left|G\right|)$ . Hence, $\tilde{c}^{\infty}_{G}(t;\Sigma)\leqslant c^{\infty}_{G}(t;\Delta)+\tilde{c}^{% \infty}_{G}(\Delta;\Sigma)\in\mathcal{O}(\log\left|G\right|)$ . This results in the estimate $\tilde{C}^{\infty}_{\mathbf{H}}(N)\in\mathcal{O}(\log N)$ . In turn, Lemma 16 yields $C^{\infty}_{\mathbf{H}}(N)\in\mathcal{O}(\log N)$ .

For bounded width, $\Delta=\operatorname{PCC}_{\ast}(\Sigma;\Sigma)$ is a polycyclic generating set of $G$ by Lemma 24. By Lemma 18, applied with cyclic subquotients, we obtain $c^{3}_{G}(t;\Delta)\in\mathcal{O}(\log\left|G\right|)$ . Hence,

c^{5}_{G}(t;\Sigma)\leqslant c^{3}_{G}(t;\Delta)\cdot\max_{t^{\prime}\in\Delta% }c^{3}_{G}(t^{\prime};\Delta)\in\mathcal{O}(\log\left|G\right|)\cdot\mathcal{O% }(\log^{2}\left|G\right|)\subseteq\mathcal{O}(\log^{3}\left|G\right|)

where the first inequality is due to Lemma 4 and the second uses Lemma 23. In fact, we can obtain $c^{4}_{G}(t;\Sigma)\in\mathcal{O}(\log^{3}\left|G\right|)$ by reusing registers between Lemma 23 and Lemma 18. $\hfill\blacktriangleleft$

8 Completely Regular Semigroups

In this section, we classify the pseudovarieties of completely regular semigroups that afford efficient compression. Recall that a semigroup $S$ is completely regular if $S$ is a union of groups, and that finite such semigroups form a pseudovariety, which we denote by $\mathbf{CR}=\llbracket x\approx x^{\omega+1}\rrbracket$ .

A semigroup $S$ is a band of groups if, for some band $B$ , there is a partition $S=\bigcup_{\alpha\in B}S_{\alpha}$ into disjoint subgroups $S_{\alpha}\leqslant S$ such that $S_{\alpha}S_{\beta}\subseteq S_{\alpha\beta}$ for all $\alpha,\beta\in B$ . Bands of groups form an important subclass of the completely regular semigroups. Imposing restrictions on the band $B$ involved in the above decomposition naturally leads to the classes of semilattices of groups – commonly referred to as Clifford semigroups – and normal bands of groups.

The pseudovariety of normal bands $\mathbf{NB}=\llbracket x^{2}\approx x,uxyv\approx uyxv\rrbracket$ plays an important role here, as it is the largest permutative pseudovariety of bands [39, Theorem 10] and the largest pseudovariety of bands containing neither of the obstructions $\mathbf{LRB}$ nor $\mathbf{RRB}$ [10, 15, 20].

The finite normal bands of groups form a pseudovariety, which we denote by $\mathbf{G}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ .⁷⁷7We will only make use of this description as a Mal’cev product for notational purposes. If the involved groups are moreover confined to some pseudovariety $\mathbf{H}\subseteq\mathbf{G}$ , then we obtain the pseudovariety $\mathbf{H}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ consisting of all finite normal bands of $\mathbf{H}$ -groups. Crucially, results on efficient compression for groups in $\mathbf{H}$ transfer to semigroups in $\mathbf{H}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ .

Proposition 25.

Let $\mathbf{V}\subseteq\mathbf{H}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ for some pseudovariety $\mathbf{H}\subseteq\mathbf{G}$ . For all $2\leqslant w\leqslant\infty$ ,

C^{w+2}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)+\log N)\quad\text{% and}\quad C^{w+1}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)\cdot\log N).

Note that the first of these bounds is, except for the increase in width, essentially optimal. Indeed, if $\mathbf{H}\subseteq\mathbf{G}$ is not the trivial pseudovariety, then $C^{\infty}_{\mathbf{H}}(N)\in\Omega(\log N)$ by Lemma 11.

For normal bands of solvable groups, we obtain the following due to Theorem 19.

Corollary 26.

Let $\mathbf{V}\subseteq\mathbf{G}_{\textup{{sol}}}\mathbin{\raisebox{0.4pt}{{ⓜ}}}% \mathbf{NB}$ be a pseudovariety. Then

C^{\infty}_{\mathbf{V}}(N)\in\mathcal{O}(\log N)\quad\text{and}\quad C^{6}_{% \mathbf{V}}(N)\in\mathcal{O}(\log^{3}N),\;C^{5}_{\mathbf{V}}(N)\in\mathcal{O}(% \log^{4}N).

Our proof of Proposition 25 relies on the following construction of generating sets for the subgroups involved in a decomposition as a normal band of groups.

Lemma 27.

Let $S=\bigcup_{\alpha\in B}S_{\alpha}$ be a finite normal band of groups generated by a set $\Sigma\subseteq S$ . Then $S_{\alpha}$ is generated by $\Sigma_{\alpha}=\{e_{\alpha}se_{\alpha}\in S:s\in\Sigma^{\leqslant 2},s% \geqslant_{\mathcal{J}}e_{\alpha}\}$ where $e_{\alpha}=e^{2}_{\alpha}\in S_{\alpha}$ .

In the above, $s\geqslant_{\mathcal{J}}e_{\alpha}$ refers to Green’s preorder $\geqslant_{\mathcal{J}}$ , meaning that $e_{\alpha}=usv$ holds for some $u,v\in S\cup\{1\}$ . Note that $s\in S_{\beta}$ satisfies $s\geqslant_{\mathcal{J}}e_{\alpha}$ if and only if $\beta\geqslant_{\mathcal{J}}\alpha$ in $B$ . Since $B$ is a normal band, this is furthermore equivalent to $\alpha\beta\alpha=\alpha$ . Hence, $\Sigma_{\alpha}\subseteq S_{\alpha}$ .

Proof.

Suppose that $t\in S_{\alpha}$ and $t=s_{1}\cdots s_{n}$ with $s_{1},\dots,s_{n}\in\Sigma$ . Then $e_{\alpha}\mathrel{\mathcal{H}}t\leqslant_{\mathcal{J}}s_{i}$ and, thus, $e_{\alpha}\leqslant_{\mathcal{J}}s_{i}$ for all $1\leqslant i\leqslant n$ . Considering the expression $t=e_{\alpha}s_{1}\cdots s_{n}e_{\alpha}$ , we note that every prefix of the form $e_{\alpha}s_{1}\cdots s_{i}$ belongs to $S_{\alpha\beta_{i}}$ where $s_{i}\in S_{\beta_{i}}$ and, similarly, that every suffix of the form $s_{i}\cdots s_{n}e_{\alpha}$ belongs to $S_{\beta_{i}\alpha}$ . Upon inserting the elements $e_{\alpha\beta_{i}}$ and $e_{\beta_{i}\alpha}$ , we obtain the expression $t=e_{\alpha}s_{1}e_{\alpha\beta_{1}}\cdots e_{\beta_{i}\alpha}s_{i}e_{\alpha% \beta_{i}}\cdots e_{\beta_{n}\alpha}s_{n}e_{\alpha},$ wherein the pre- and suffixes of the form $e_{\alpha}\cdots e_{\beta_{i}\alpha}$ and $e_{\alpha\beta_{i}}\cdots e_{\alpha}$ belong to $S_{\alpha}$ . Inserting the element $e_{\alpha}$ yields

t=(e_{\alpha}s_{1}e_{\alpha})e_{\alpha\beta_{1}}\cdots e_{\beta_{i}\alpha}(e_{% \alpha}s_{i}e_{\alpha})e_{\alpha\beta_{i}}\cdots e_{\beta_{n}\alpha}(e_{\alpha% }s_{n}e_{\alpha}).

We have thus written $t$ as a product of elements $e_{\alpha}s_{i}e_{\alpha}\in\Sigma_{\alpha}$ as well as elements of the form $e_{\alpha\beta_{i}}e_{\beta_{j}\alpha}$ . The latter also belong to $\langle\Sigma_{\alpha}\rangle\subseteq S_{\alpha}$ , as such an element can be written as

\displaystyle e_{\alpha\beta_{i}}e_{\beta_{j}\alpha}=(e_{\alpha}s_{i})^{\omega% }(s_{j}e_{\alpha})^{\omega}

\displaystyle=(e_{\alpha}s_{i}e_{\alpha})^{\omega-1}(e_{\alpha}s_{i}s_{j}e_{% \alpha})(e_{\alpha}s_{j}e_{\alpha})^{\omega-1}.\

$\hfill\blacktriangleleft$

Proof of Proposition 25.

Consider a semigroup $S\in\mathbf{V}$ , a generating set $\Sigma\subseteq S$ , and some element $t\in S$ . Since $\mathbf{V}\subseteq\mathbf{H}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ , the semigroup $S$ admits a decomposition $S=\bigcup_{\alpha\in B}S_{\alpha}$ into subgroups $S_{\alpha}\leqslant S$ belonging to $\mathbf{H}$ for some normal band $B$ such that the map $\pi\colon S\to B$ sending every element of a subgroup $S_{\alpha}$ to the corresponding $\alpha\in B$ is a homomorphism.

Let $e_{\alpha}$ be the neutral element the subgroups $S_{\alpha}\leqslant S$ for some $\alpha\in B$ . We claim that this element can be efficiently computed by a straight-line program, viz., $c^{2}_{S}(e_{\alpha};\Sigma)\in\mathcal{O}(\log\left|S\right|)$ . To see this, first note that the pseudovariety $\mathbf{NB}=\llbracket x^{2}\approx x,uxyv\approx uyxv\rrbracket$ is permutative and, therefore, $c^{2}_{B}(\alpha;\pi(\Sigma))\in\mathcal{O}(\log\left|B\right|)\subseteq% \mathcal{O}(\log\left|S\right|)$ by Proposition 13. Next, take any straight-line program in $B$ over $\pi(\Sigma)$ that achieves this bound and lift it to a straight-line program in $S$ over $\Sigma$ . The lifted straight-line program computes some element $t_{\alpha}\in S_{\alpha}$ , and we then obtain $e_{\alpha}=t_{\alpha}^{\omega}$ using fast exponentiation in $\mathcal{O}(\log\left|S_{\alpha}\right|)\subseteq\mathcal{O}(\log\left|S\right|)$ instructions.

Let us now fix the unique $\alpha\in B$ with $t\in S_{\alpha}$ , and denote by $\Sigma_{\alpha}$ the generating set of $S_{\alpha}$ from Lemma 27. Further, let us fix a straight-line program $\mathcal{A}$ computing $t$ over $\Sigma_{\alpha}\subseteq S_{\alpha}$ of width at most $w$ and length $c^{w}_{S_{\alpha}}(t;\Sigma_{\alpha})$ . For the case that two additional registers are permitted, we modify this straight-line program as follows. First, we compute $e_{\alpha}\in S_{\alpha}$ as described above, and keep it in one of the additional registers throughout the computation. From this point on, we emulate $\mathcal{A}$ on the original registers and, whenever we encounter an assignment $r_{i}\leftarrow s$ for some generator $s\in\Sigma_{\alpha}$ , we use the register $r_{i}$ and the additional register not holding $e_{\alpha}$ to compute $s=e_{\alpha}s_{1}e_{\alpha}$ or $s=e_{\alpha}s_{1}s_{2}e_{\alpha}$ with $s_{1},s_{2}\in\Sigma$ as appropriate. This yields the estimate $c^{w+2}_{S}(t;\Sigma)\leqslant 5\cdot c^{w}_{S_{\alpha}}(t;\Sigma_{\alpha})+% \mathcal{O}(\log\left|S\right|)$ .

We proceed similarly if only one additional register is permitted, but temporarily overwrite the element $e_{\alpha}$ when producing a generator of the form $e_{\alpha}s_{1}s_{2}e_{\alpha}$ with $s_{1},s_{2}\in\Sigma$ . $\hfill\blacktriangleleft$

Summarizing the preceding results, we arrive at the following characterization for pseudovarieties of completely regular semigroups with efficient compression.

Theorem 28.

Let $\mathbf{V}\subseteq\mathbf{CR}$ be a pseudovariety. The following are equivalent.

(1)

The pseudovariety $\mathbf{V}$ affords efficient compression.
(2)

The pseudovariety $\mathbf{V}$ contains neither $\mathbf{LRB}$ nor $\mathbf{RRB}$ .
(3)

The pseudovariety $\mathbf{V}$ comprises only normal bands of groups; that is, $\mathbf{V}\subseteq\mathbf{G}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ .
(4)

The pseudovariety $\mathbf{V}$ admits straight-line programs of length $\mathcal{O}(\smash{\log}^{2}N)$ .

Proof.

Lemma 6 shows that $(1)\Rightarrow(2)$ . The implication $(2)\Rightarrow(3)$ is a well-known result by Rasin [28, Proposition 4]: If $\mathbf{V}\subseteq\mathbf{CR}$ and $\mathbf{V}\cap\mathbf{B}\subseteq\mathbf{NB}$ , then $\mathbf{V}\subseteq\mathbf{G}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ . (Recall that for any pseudovariety $\mathbf{W}\subseteq\mathbf{B}$ either $\mathbf{W}\subseteq\mathbf{NB}$ holds, or $\mathbf{W}$ contains $\mathbf{LRB}$ or $\mathbf{RRB}$ .)

Proposition 25 and the Reachability Lemma of Babai and Szemerédi [5, Theorem 3.1] combine to show the implication $(3)\Rightarrow(4)$ . Finally, $(4)\Rightarrow(1)$ holds by definition. $\hfill\blacktriangleleft$

9 General Semigroups

In this section, we finally prove our main theorem (Theorem 1). The following restatement also reveals the close connection between the semigroup and group cases.

Theorem 29.

Let $\mathbf{V}$ be a pseudovariety, and let $\mathbf{H}=\mathbf{V}\cap\mathbf{G}$ . The following are equivalent.

(1)

The pseudovariety $\mathbf{V}$ affords efficient compression.
(2)

The pseudovariety $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , nor $\mathbf{T}$ .
(3)

The pseudovariety $\mathbf{V}$ satisfies the following for every $2\leqslant w\leqslant\infty$ :

$C^{w+3}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)+\log N)\quad\text{% and}\quad C^{w+2}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)\cdot\log N).$

In particular, $\mathbf{V}$ admits straight-line programs of length $\mathcal{O}(\smash{\log}^{2}N)$ .

Our proof of Theorem 29 is based on an observation on the structure of a pseudovariety $\mathbf{V}$ with $\mathbf{T}\not\subseteq\mathbf{V}$ that was recently obtained by the first author [35, Theorem A, Theorem B].

Theorem 30.

Let $\mathbf{V}$ be a pseudovariety. If $\mathbf{T}\not\subseteq\mathbf{V}$ , then one of the following holds.

(1)

There exist $1\leqslant i\leqslant j\leqslant n$ such that $\mathbf{V}\models x_{1}\cdots x_{n}\approx x_{1}\cdots x_{i-1}(x_{i}\cdots x_{% j})^{\omega+1}x_{j+1}\cdots x_{n}$ .
(2)

There exists $\sigma\in\mathrm{Sym}(n)$ with $\sigma\neq\mathrm{id}$ such that $\mathbf{V}\models x_{1}\cdots x_{n}\approx x_{\sigma(1)}\cdots x_{\sigma(n)}$ .

Notably, for monoids all identities in the first item of Theorem 30 are equivalent to the defining identity $x\approx x^{\omega+1}$ of completely regular monoids, and all identities in the second item are equivalent to the defining identity $xy\approx yx$ of commutative monoids. Additionally excluding $\mathbf{LRB}$ and $\mathbf{RRB}$ narrows the first item to the pseudovarieties of Clifford monoids by Rasin’s result [28, Proposition 4]. In this way, we obtain an alternative proof of Fleischer’s classification of pseudovarieties of monoids affording efficient compression [16, Theorem 4.13].

For semigroups, we will also need the following observation, which is a direct consequence of Volkov’s characterization [37, Theorem 1.1] (see also [35, Lemma 18]).

Lemma 31.

Let $\mathbf{V}$ be a pseudovariety with $\mathbf{T}\not\subseteq\mathbf{V}$ . For every semigroup $S\in\mathbf{V}$ , the set of its completely regular elements $I(S)=\{s\in S:s=s^{\omega+1}\}$ is a subsemigroup of $S$ .

Proof of Theorem 29.

Lemma 6 shows that $(1)\Rightarrow(2)$ . Since the addendum in item $(3)$ follows from Babai and Szemerédi’s Reachability Lemma, we have that $(3)\Rightarrow(1)$ by definition.

Let us thus assume that $(2)$ holds. Recall from Theorem 30 that $\mathbf{V}$ satisfies the identity

x_{1}\cdots x_{n}\approx x_{1}\cdots x_{i-1}(x_{i}\cdots x_{j})^{\omega+1}x_{j% +1}\cdots x_{n}

for some parameters $1\leqslant i\leqslant j\leqslant n$ , or is permutative otherwise. We may assume the former, since otherwise $C^{2}_{\mathbf{V}}(N)\in\mathcal{O}(\log N)$ holds by Proposition 13 and this clearly implies $(3)$ .

Under this assumption, we have $\mathbf{V}\subseteq\llbracket xyz\approx xy^{\omega+1}z\rrbracket\mathbin{% \raisebox{0.4pt}{{ⓜ}}}\mathbf{N}_{k}$ for a sufficiently large $k\geqslant 1$ . Let $\mathbf{V}^{\prime}=\mathbf{V}\cap\llbracket xyz\approx xy^{\omega+1}z\rrbracket$ , and note that $\mathbf{V}^{\prime}\subseteq\mathbf{V}$ and $\mathbf{V}\subseteq\mathbf{V}^{\prime}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{N% }_{k}$ . Thus, $\mathbf{V}^{\prime}$ also satisfies $(2)$ and, in light of Lemma 8, it suffices to prove that, for all $2\leqslant w\leqslant\infty$ ,

C^{w+2}_{\mathbf{V}^{\prime}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)+\log N)% \quad\text{and}\quad C^{w+1}_{\mathbf{V}^{\prime}}(N)\in\mathcal{O}(C^{w}_{% \mathbf{H}}(N)\cdot\log N).

Consider a semigroup $S\in\mathbf{V}^{\prime}$ , a generating set $\Sigma\subseteq S$ , and some element $t\in S$ . Without loss of generality, the element $t$ is not a product of generators with two or fewer factors. Under these assumptions, the element $t$ can be written as $t=u\,s_{1}\cdots s_{n}\,v$ with $u,s_{1},\dots,s_{n},v\in\Sigma$ .

For $1\leqslant i\leqslant n$ , let $\tilde{s}_{i}=s_{i}^{\omega+1}$ and note that $\tilde{s}_{i}\in I(S)$ . Further, let $\tilde{S}\leqslant S$ be the subsemigroup generated by the set $\tilde{\Sigma}=\{\tilde{s}_{1},\dots,\tilde{s}_{n}\}$ . Since $\tilde{\Sigma}\subseteq I(S)$ and the latter is a subsemigroup of $S$ by Lemma 31, we in fact have $\tilde{S}\leqslant I(S)\leqslant S$ and, therefore, $\tilde{S}\in\mathbf{V}^{\prime}\cap\mathbf{CR}$ .

By Theorem 28, $\tilde{S}\in\mathbf{G}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ . Moreover, since $\mathbf{V^{\prime}}\cap\mathbf{G}\subseteq\mathbf{H}$ , we have that $\tilde{S}\in\mathbf{H}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ . By Proposition 25, for every $2\leqslant w\leqslant\infty$ , there is a straight-line program $\smash{\tilde{\mathcal{A}}}$ computing $\tilde{s}\in\tilde{S}$ over $\tilde{\Sigma}\subseteq\tilde{S}$ with $w(\smash{\tilde{\mathcal{A}}})=w+2$ (or $w+1$ ) and $\ell(\smash{\tilde{\mathcal{A}}})\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)+\log N)$ (resp. $\mathcal{O}(C^{w}_{\mathbf{H}}(N)\cdot\log N)$ ) where $N=\lvert\tilde{S}\rvert\leqslant\left|S\right|$ . We modify the straight-line program $\smash{\tilde{\mathcal{A}}}$ by replacing every instruction $r_{k}\leftarrow\tilde{s}_{i}$ with $\tilde{s}_{i}\in\tilde{\Sigma}$ by the instruction $r_{k}\leftarrow s_{i}$ where $s_{i}\in\Sigma$ with $s_{i}^{\omega+1}=\tilde{s}_{i}$ . (In case $s_{i}\neq s_{i^{\prime}}$ satisfy $s_{i}^{\omega+1}=s_{i^{\prime}}^{\omega+1}$ , we choose arbitrarily between $s_{i}$ and $s_{i^{\prime}}$ .) The result of this modification is a straight-line program $\mathcal{A}$ over $\Sigma\subseteq S$ of the same length and width as $\smash{\tilde{\mathcal{A}}}$ . Let $s\in S$ be the element computed by $\mathcal{A}$ corresponding to $\tilde{s}\in\tilde{S}$ . We claim that $t=u\,s\,v$ .

To see this claim to be true, note that there is a word $\rho(x_{1},\dots,x_{n})$ over $\{x_{1},\dots,x_{n}\}$ that evaluates to $\rho(s_{1},\dots,s_{n})=s$ and $\rho(\tilde{s}_{1},\dots,\tilde{s}_{n})=\tilde{s}$ . Due to the identity $xyz\approx xy^{\omega+1}z$ ,

t=u\,s_{1}\cdots s_{n}\,v=u\,\tilde{s}_{1}\cdots\tilde{s}_{n}\,v=u\,\tilde{s}% \,v=u\,\rho(\tilde{s}_{1},\dots,\tilde{s}_{n})\,v=u\,\rho(s_{1},\dots,s_{n})\,% v=u\,s\,v

as required. Since, moreover, $t=u\,s\,v$ can be computed from $s$ using no additional registers, since $w(\mathcal{A})\geqslant 2$ , and at most four additional instructions, this completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 32.

By reusing one of the additional registers between the constructions in Lemma 8 and Proposition 25, the above bounds can be slightly improved to

C^{w+2}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)+\log N)\quad\text{% and}\quad C^{w+1}_{\mathbf{V}}(N)\in\mathcal{O}(C^{w}_{\mathbf{H}}(N)\cdot\log N).

Incorporating this improvement, we obtain the following due to Corollary 26.

Corollary 33.

Let $\mathbf{V}$ be a pseudovariety, $\mathbf{LRB},\mathbf{RRB},\mathbf{T}\not\subseteq\mathbf{V}$ , and $\mathbf{V}\cap\mathbf{G}\subseteq\mathbf{G}_{\textup{{sol}}}$ . Then

C^{\infty}_{\mathbf{V}}(N)\in\mathcal{O}(\log N)\quad\text{and}\quad C^{6}_{% \mathbf{V}}(N)\in\mathcal{O}(\log^{3}N),\;C^{5}_{\mathbf{V}}(N)\in\mathcal{O}(% \log^{4}N).

10 The Membership Problem

The membership problem is one of the most fundamental decision problems for algebraic structures. In the case of semigroups, this problem is given as follows.

Input.Question.: A semigroup $S$ , a subset $\Sigma\subseteq S$ , and an element $t\in S$ .
Question.: Is $t$ a member of the subsemigroup $\langle\Sigma\rangle\leqslant S$ ?

Here, we consider a restricted variant memb ${}_{\mathbf{}}(\mathbf{V})$ with the additional promise that the subsemigroup⁸⁸8Be aware that in some related work, including [16, 17], not only the subsemigroup $\langle\Sigma\rangle$ is restricted to the pseudovariety $\mathbf{V}$ , but also the surrounding semigroup $S$ . As we require a weaker promise, we obtain a stronger algorithmic result (Corollary 35) than with the formulation from [16, 17]. $\langle\Sigma\rangle\leqslant S$ belongs to some fixed pseudovariety $\mathbf{V}$ . This includes the general problem as memb ${}_{\mathbf{}}(\mathbf{S})$ and allows for a more fine-grained analysis of the problem’s complexity.

There are different ways to represent the semigroup $S$ and its elements as part of the input. Our main focus is on the Cayley table model where $S$ is given as multiplication table and its elements as indices into its rows and columns; in this case, we denote the membership problem by memb ${}_{\mathbf{CT}}(\mathbf{V})$ . Other forms of input are considered at the end of this section.

Note that, in general, the membership problem memb ${}_{\mathbf{CT}}(\mathbf{S})$ is $\mathsf{NL}$ -complete [22]; in fact, this already holds for memb ${}_{\mathbf{CT}}(\mathbf{T})$ [16, Theorem 5.6]. On the other hand, our results – see Corollary 35 below – imply that, for any pseudovariety $\mathbf{V}$ with $\mathbf{LRB},\mathbf{RRB},\mathbf{T}\not\subseteq\mathbf{V}$ , the corresponding membership problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ cannot even be hard under $\hbox{\small$\mathsf{AC}$}^{0}$ -reductions for any complexity class containing parity – such as $\mathsf{NL}$ .

The following observation shows that efficient compression via straight-line programs gives rise to nontrivial complexity upper bounds for the membership problem. Both items can be found in the dissertation of Fleischer [16, Corollary 5.2, Corollary 5.3]. However, using the techniques by Collins, Grochow, Levet, and the second author [13] (where this fact has also been used implicitly), we can give a simpler proof of the second item.

Lemma 34 (Fleischer).

Let $\mathbf{V}$ be a pseudovariety, and let $2\leqslant w<\infty$ .

(1)

If $C^{\infty}_{\mathbf{V}}(N)\in\mathcal{O}(\operatorname{polylog}N)$ , then memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\hbox{\small$\mathsf{NPOLYLOGTIME}$}\subseteq\hbox{\small$\mathsf{qAC}$}^{0}$ .
(2)

If $C^{w}_{\mathbf{V}}(N)\in\mathcal{O}(\operatorname{polylog}N)$ , then memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\hbox{\small$\mathsf{NTISP}$}(\operatorname{polylog}n,\log n)\subseteq\hbox{% \small$\mathsf{FOLL}$}$ .

Proof.

To certify membership of an element $t\in S$ in a subsemigroup $\langle\Sigma\rangle\leqslant S$ , we can use a suitable straight-line program $\mathcal{A}$ over $\Sigma$ computing $t$ . We guess and execute $\mathcal{A}$ , instruction by instruction, on the random access machine and accept once some register is assigned $t$ .

For the bounded-width case, observe that we only need to store a bounded number of elements, which only requires logarithmic space. In this case, the membership problem can thus be solved in $\hbox{\small$\mathsf{NTISP}$}(\operatorname{polylog}n,\log n)$ , which is a subset of $\mathsf{FOLL}$ [13, Lemma 2.6]. $\hfill\blacktriangleleft$

Using this lemma, we obtain the following from Theorem 29 (thus, proving Corollary 2).

Corollary 35.

Let $\mathbf{V}$ be a pseudovariety. The following are equivalent.

(1)

The pseudovariety $\mathbf{V}$ affords efficient compression.
(2)

The pseudovariety $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , nor $\mathbf{T}$ .
(3)

The membership problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\mathsf{NPOLYLOGTIME}$ .

Furthermore, if $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}$ , nor any nonsolvable group, then the membership problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\hbox{\small$\mathsf{NTISP}$}(\operatorname{polylog}n,\log n)$ and, hence, in $\mathsf{FOLL}$ .

Note that in some cases even smaller bounds are known: if $\mathbf{V}\subseteq\mathbb{L}\mathbf{I}_{k}$ or $\mathbf{V}\subseteq\mathbf{NB}$ , then the membership problem is in $\hbox{\small$\mathsf{AC}$}^{0}$ [16, Proposition 4.5 and Corollary 5.2, Theorem 5.12].

Proof.

The first two items are equivalent by Theorem 29 and imply the third by Lemma 34.

On the other hand, if the problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\mathsf{NPOLYLOGTIME}$ , then for any fixed semigroup $S\in\mathbf{V}$ and generating set $\Sigma\subseteq S$ , a target element $t\in S$ can only depend on a polylogarithmic number of generators as in one computation path the algorithm cannot access more elements during its running time – meaning that $t\in\langle\Sigma^{\prime}\rangle$ for some $\Sigma^{\prime}\subseteq\Sigma$ of polylogarithmic size. In turn, this implies that $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}\not\subseteq\mathbf{V}$ by Lemma 6.

Finally, if $\mathbf{V}$ contains neither $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}$ , nor any nonsolvable group, then the problem memb ${}_{\mathbf{CT}}(\mathbf{V})$ is in $\hbox{\small$\mathsf{NTISP}$}(\operatorname{polylog}n,\log n)\subseteq\hbox{% \small$\mathsf{FOLL}$}$ by Corollary 33 and Lemma 34. $\hfill\blacktriangleleft$

Corollary 35 confirms, in particular, the conjecture by Barrington, Kadau, Lange, and McKenzie [7] that solvable groups have their membership problem in $\mathsf{FOLL}$ . Moreover, it completely reduces Fleischer’s question [17] whether all classes of semigroups that afford efficient compression have their membership problem in $\mathsf{FOLL}$ to the case of groups.

For membership in the transformation model, the semigroup $S$ is the semigroup $\mathcal{T}_{X}$ of all maps from some finite set $X$ to itself, with elements given in a point-wise representation.

Corollary 36.

Let $\mathbf{V}$ be a pseudovariety of semigroups with $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}\not\subseteq\mathbf{V}$ . Then the membership problem for $\mathbf{V}$ -semigroups in the transformation model is in $\mathsf{NP}$ .

Note that this corollary is far from being optimal. Indeed, it should be rather easy to show that for $\mathbf{G}\mathbin{\raisebox{0.4pt}{{ⓜ}}}\mathbf{NB}$ the membership problem in the transformation model is in $\mathsf{NC}$ (building on [4]). Moreover, Fleischer, Stober, and the authors already showed that this holds for Clifford semigroups and, more generally, for strict inverse semigroups [18, Theorem B].

On the other hand, Corollary 36 has some interesting consequences to the minimum generating set problem (given a semigroup and a number $k$ , decide whether the semigroup can be generated by at most $k$ elements), the problem of solving equations, and the isomorphism problem. Indeed, if $\mathbf{LRB}$ , $\mathbf{RRB}$ , $\mathbf{T}\not\subseteq\mathbf{V}$ , then the former two problems can be solved in $\mathsf{NP}$ for semigroups from $\mathbf{V}$ by simply guessing a suitable generating set (resp. a solution to the equations) and then checking its validity using the algorithm for the membership problem. Moreover, using a similar approach the isomorphism problem can be solved in $\hbox{\small$\mathsf{\Sigma}$}_{2}\hbox{\small$\mathsf{P}$}$ , that is, in the second level of the polynomial-time hierarchy.

11 Conclusion

In this work, we classified those pseudovarieties of semigroups that afford efficient compression via straight-line programs and also considered the case of efficient compression via bounded-width straight-line programs. In the absence of nonsolvable groups, we obtained $\mathsf{FOLL}$ algorithms for the membership problem for such pseudovarieties, thereby solving open problems from [17] and [7]. We conclude with the following questions.

Question 37.

Suppose that the pseudovariety $\mathbf{V}$ affords efficient compression.

$\blacksquare$

Does $\mathbf{V}$ admit straight-line program of logarithmic length and unbounded width?
$\blacksquare$

Does $\mathbf{V}$ admit straight-line program of polylogarithmic length and bounded width?
$\blacksquare$

Does $\mathbf{V}$ admit straight-line program of logarithmic length and bounded width?

We note that Theorem 29 reduces all three of these questions to pseudovarieties of groups. The second one is particularly interesting, as an affirmative answer would imply that all such pseudovarieties admit $\mathsf{FOLL}$ algorithms for their membership problem.

Question 38.

Which pseudovarieties have their membership problem in $\hbox{\small$\mathsf{AC}$}^{0}$ ?

We suspect that some of our results and techniques (in particular, Lemma 8 and Theorem 10) might be useful in making progress towards resolving this question. In contrast, addressing the following question appears to be a significantly more ambitious endeavor.

Question 39.

Does the membership problem exhibit a $\hbox{\small$\mathsf{qAC}$}^{0}$ vs. $\mathsf{NL}$ -complete dichotomy?

Finally, we want to ask to what extent the methods of this work can be transferred to study compression in other algebraic structures such as rings and quasigroups.

References

[1] J. Almeida. Finite Semigroups and Universal Algebra, volume 3 of Ser. Algebra. World Scientific Publishing Co., Inc., River Edge, NJ, 1994. doi:10.1142/2481.
[2] J. Almeida and N. R. Reilly. Generalized varieties of commutative and nilpotent semigroups. Semigroup Forum, 30(1):77–98, 1984. doi:10.1007/BF02573439.
[3] S. Arora and B. Barak. Computational Complexity – A Modern Approach. Cambridge University Press, 2009.
[4] 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.
[5] 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.
[6] H. Bannai. Grammar compression. In Encyclopedia of Algorithms, pages 861–866. Springer New York, 2016. doi:10.1007/978-1-4939-2864-4_635.
[7] 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. doi:10.1006/jcss.2001.1764.
[8] D. A. M. Barrington and P. McKenzie. Oracle branching programs and Logspace versus P. Inform. and Comput., 95(1):96–115, 1991. doi:10.1016/0890-5401(91)90017-V.
[9] 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.
[10] A. P. Biryukov. Varieties of idempotent semigroups. Algebra Logic, 9(3):153–164, 1970. doi:10.1007/BF02218673.
[11] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.
[12] L. Ciobanu, V. Diekert, and M. Elder. Solution sets for equations over free groups are EDT0L languages. Int. J. Algebra Comput., 26(5):843–886, 2016. doi:10.1142/S0218196716500363.
[13] N. A. Collins, J. A. Grochow, M. Levet, and A. Weiß. On the constant-depth circuit complexity of generating quasigroups. TheoretiCS, Volume 4, 2025. doi:10.46298/theoretics.25.19.
[14] S. Eilenberg. Automata, languages, and machines. Vol. B. Pure and Applied Mathematics, Vol. 59. Academic Press, New York-London, 1976.
[15] C. F. Fennemore. All varieties of bands I, II. Math. Nachr., 48(1-6):237–252; ibid., 253–262, 1971. doi:10.1002/mana.19710480118.
[16] 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.
[17] L. Fleischer. The Cayley semigroup membership problem. Theory Comput., 18:1–18, 2022. Conference version at CCC 2018. doi:10.4086/toc.2022.v018a008.
[18] L. Fleischer, F. Stober, A. Thumm, and A. Weiß. Membership and conjugacy in inverse semigroups. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, volume 334 of LIPIcs, pages 156:1–156:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.156.
[19] M. Ganardi, A. Jez, and M. Lohrey. Balancing straight-line programs. In D. Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1169–1183. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00073.
[20] J. A. Gerhard. The lattice of equational classes of idempotent semigroups. J. Algebra, 15(2):195–224, 1970. doi:10.1016/0021-8693(70)90073-6.
[21] A. Jez. Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms, 11(3):20:1–20:43, 2015. doi:10.1145/2631920.
[22] N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Math. Syst. Theory, 10(1):1–17, December 1976. doi:10.1007/BF01683259.
[23] J. C. Kieffer and E.-H. Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46(3):737–754, 2000. doi:10.1109/18.841160.
[24] D. Kozen. Lower bounds for natural proof systems. In FOCS 1977, Proceedings, pages 254–266, Providence, Rhode Island, 1977. IEEE Computer Society Press.
[25] M. Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology, 4:241–299, 2012. doi:10.1515/gcc-2012-0016.
[26] M. Lohrey. The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, 2014. doi:10.1007/978-1-4939-0748-9.
[27] M. S. Putcha and A. Yaqub. Semigroups satisfying permutation identities. Semigroup Forum, 3(1):68–73, 1971/72. doi:10.1007/BF02572944.
[28] V. V. Rasin. On the varieties of Cliffordian Semigroups. Semigroup Forum, 23(1):201–220, 1981. doi:10.1007/BF02676644.
[29] O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, September 2008. doi:10.1145/1391289.1391291.
[30] J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14(1):1–10, 1982. doi:10.1007/BF02483902.
[31] J. Rhodes and B. Steinberg. The $q$ -theory of Finite Semigroups. Springer Monogr. Math. Springer, New York, NY, 2009. doi:10.1007/b104443.
[32] D. J. S. Robinson. A course in the theory of groups, volume 80 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996. doi:10.1007/978-1-4419-8594-1.
[33] A. Scholz. In: Aufgaben und Lösungen. Jahresber. Deutsch. Math.-Verein., 47:41–42, 1937.
[34] 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. doi:10.1016/B978-0-08-012975-4.50020-5.
[35] A. Thumm. Finite semigroups satisfying an identity $x_{1}\cdots x_{n}\approx\rho(x_{1},\dots,x_{n})$ . Preprint, 2025. arXiv:2509.19216.
[36] J. van der Hoeven and G. Lecerf. Towards a library for straight-line programs. Preprint, 2025. URL: https://hal.science/hal-05075591.
[37] M. V. Volkov. “Forbidden divisor” characterizations of epigroups with certain properties of group elements. RIMS Kokyuroku, 1166:226–234, 2000.
[38] H. Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts Theoret. Comput. Sci. EATCS Ser. Springer, 1999. doi:10.1007/978-3-662-03927-4.
[39] M. Yamada and N. Kimura. Note on idempotent semigroups. II. Proc. Japan Acad., 34:110–112, 1958. doi:10.3792/pja/1195524790.

[bib.bib1] [1] J. Almeida. Finite Semigroups and Universal Algebra, volume 3 of Ser. Algebra. World Scientific Publishing Co., Inc., River Edge, NJ, 1994. doi:10.1142/2481.

[bib.bib2] [2] J. Almeida and N. R. Reilly. Generalized varieties of commutative and nilpotent semigroups. Semigroup Forum, 30(1):77–98, 1984. doi:10.1007/BF02573439.

[bib.bib3] [3] S. Arora and B. Barak. Computational Complexity – A Modern Approach. Cambridge University Press, 2009.

[bib.bib4] [4] 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.

[bib.bib5] [5] 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.

[bib.bib6] [6] H. Bannai. Grammar compression. In Encyclopedia of Algorithms, pages 861–866. Springer New York, 2016. doi:10.1007/978-1-4939-2864-4_635.

[bib.bib7] [7] 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. doi:10.1006/jcss.2001.1764.

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

[bib.bib9] [9] 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.

[bib.bib10] [10] A. P. Biryukov. Varieties of idempotent semigroups. Algebra Logic, 9(3):153–164, 1970. doi:10.1007/BF02218673.

[bib.bib11] [11] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer, 1997.

[bib.bib12] [12] L. Ciobanu, V. Diekert, and M. Elder. Solution sets for equations over free groups are EDT0L languages. Int. J. Algebra Comput., 26(5):843–886, 2016. doi:10.1142/S0218196716500363.

[bib.bib13] [13] N. A. Collins, J. A. Grochow, M. Levet, and A. Weiß. On the constant-depth circuit complexity of generating quasigroups. TheoretiCS, Volume 4, 2025. doi:10.46298/theoretics.25.19.

[bib.bib14] [14] S. Eilenberg. Automata, languages, and machines. Vol. B. Pure and Applied Mathematics, Vol. 59. Academic Press, New York-London, 1976.

[bib.bib15] [15] C. F. Fennemore. All varieties of bands I, II. Math. Nachr., 48(1-6):237–252; ibid., 253–262, 1971. doi:10.1002/mana.19710480118.

[bib.bib16] [16] 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.

[bib.bib17] [17] L. Fleischer. The Cayley semigroup membership problem. Theory Comput., 18:1–18, 2022. Conference version at CCC 2018. doi:10.4086/toc.2022.v018a008.

[bib.bib18] [18] L. Fleischer, F. Stober, A. Thumm, and A. Weiß. Membership and conjugacy in inverse semigroups. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, volume 334 of LIPIcs, pages 156:1–156:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.ICALP.2025.156.

[bib.bib19] [19] M. Ganardi, A. Jez, and M. Lohrey. Balancing straight-line programs. In D. Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1169–1183. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00073.

[bib.bib20] [20] J. A. Gerhard. The lattice of equational classes of idempotent semigroups. J. Algebra, 15(2):195–224, 1970. doi:10.1016/0021-8693(70)90073-6.

[bib.bib21] [21] A. Jez. Faster fully compressed pattern matching by recompression. ACM Trans. Algorithms, 11(3):20:1–20:43, 2015. doi:10.1145/2631920.

[bib.bib22] [22] N. D. Jones, Y. E. Lien, and W. T. Laaser. New problems complete for nondeterministic log space. Math. Syst. Theory, 10(1):1–17, December 1976. doi:10.1007/BF01683259.

[bib.bib23] [23] J. C. Kieffer and E.-H. Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Trans. Inf. Theory, 46(3):737–754, 2000. doi:10.1109/18.841160.

[bib.bib24] [24] D. Kozen. Lower bounds for natural proof systems. In FOCS 1977, Proceedings, pages 254–266, Providence, Rhode Island, 1977. IEEE Computer Society Press.

[bib.bib25] [25] M. Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology, 4:241–299, 2012. doi:10.1515/gcc-2012-0016.

[bib.bib26] [26] M. Lohrey. The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer, 2014. doi:10.1007/978-1-4939-0748-9.

[bib.bib27] [27] M. S. Putcha and A. Yaqub. Semigroups satisfying permutation identities. Semigroup Forum, 3(1):68–73, 1971/72. doi:10.1007/BF02572944.

[bib.bib28] [28] V. V. Rasin. On the varieties of Cliffordian Semigroups. Semigroup Forum, 23(1):201–220, 1981. doi:10.1007/BF02676644.

[bib.bib29] [29] O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, September 2008. doi:10.1145/1391289.1391291.

[bib.bib30] [30] J. Reiterman. The Birkhoff theorem for finite algebras. Algebra Universalis, 14(1):1–10, 1982. doi:10.1007/BF02483902.

[bib.bib31] [31] J. Rhodes and B. Steinberg. The $q$ -theory of Finite Semigroups. Springer Monogr. Math. Springer, New York, NY, 2009. doi:10.1007/b104443.

[bib.bib32] [32] D. J. S. Robinson. A course in the theory of groups, volume 80 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1996. doi:10.1007/978-1-4419-8594-1.

[bib.bib33] [33] A. Scholz. In: Aufgaben und Lösungen. Jahresber. Deutsch. Math.-Verein., 47:41–42, 1937.

[bib.bib34] [34] 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. doi:10.1016/B978-0-08-012975-4.50020-5.

[bib.bib35] [35] A. Thumm. Finite semigroups satisfying an identity $x_{1}\cdots x_{n}\approx\rho(x_{1},\dots,x_{n})$ . Preprint, 2025. arXiv:2509.19216.

[bib.bib36] [36] J. van der Hoeven and G. Lecerf. Towards a library for straight-line programs. Preprint, 2025. URL: https://hal.science/hal-05075591.

[bib.bib37] [37] M. V. Volkov. “Forbidden divisor” characterizations of epigroups with certain properties of group elements. RIMS Kokyuroku, 1166:226–234, 2000.

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

[bib.bib39] [39] M. Yamada and N. Kimura. Note on idempotent semigroups. II. Proc. Japan Acad., 34:110–112, 1958. doi:10.3792/pja/1195524790.

Efficient Compression in Semigroups

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Contribution.

Theorem 1.

Corollary 2.

Corollary 3.

Proof Outline.

2 Preliminaries

2.1 Semigroups

2.2 Complexity

3 Compression via Straight-Line Programs

Lemma 4.

Observation 5.

4 Obstructions to Efficient Compression

Lemma 6 (Fleischer).

5 Semigroups of Bounded Diameter

Definition 7.

Lemma 8.

Proof.

Lemma 9.

Theorem 10.

Lemma 11 (Fleischer).

Lemma 12.

Proof.

Proof of Theorem 10.

6 Permutative Semigroups

Proposition 13.

Proof.

Theorem 14.

Proof.

7 Groups

Observation 15.

7.1 General Groups

Lemma 16.

Proof Sketch.

Reachability Lemma (Babai, Szemerédi).

Definition 17.

Lemma 18.

Proof.

7.2 Solvable Groups

Theorem 19.

Lemma 20.

Proof.

Lemma 21.

Proof.

Proposition 22.

Proof.

Lemma 23.

Proof.

Lemma 24.

Proof.

Proof of Theorem 19.

8 Completely Regular Semigroups

Proposition 25.

Corollary 26.

Lemma 27.

Proof.

Proof of Proposition 25.

Theorem 28.

Proof.

9 General Semigroups

Theorem 29.

Theorem 30.

Lemma 31.

Proof of Theorem 29.

▶ Remark 32.

Corollary 33.

10 The Membership Problem

Lemma 34 (Fleischer).

$\blacktriangleright$ Remark 32.