# Recent advances in algorithmic problems for semigroups

Ruiwen Dong  Department of Computer Science, University of Oxford

###### Abstract

In this article we survey recent progress in the algorithmic theory of matrix
semigroups. The main objective in this area of study is to construct
algorithms that decide various properties of finitely generated subsemigroups
of an infinite group $G$, often represented as a matrix group. Such problems
might not be decidable in general. In fact, they gave rise to some of the
earliest undecidability results in algorithmic theory. However, the situation
changes when the group $G$ satisfies additional constraints. In this survey,
we give an overview of the decidability and the complexity of several
algorithmic problems in the cases where $G$ is a low-dimensional matrix group,
or a group with additional structures such as commutativity, nilpotency and
solvability.

##  1 Introduction

It has been known since the work of Church and Turing from the 1930s that
certain decision problems in mathematical logic do not admit algorithmic
solutions. For a long period of time, all examples of undecidable problems
were derived directly from mathematical logic or the theory of computing, and
the notion of undecidability seemed intangible for most mathematicians. It was
not until the late 1940s that the Soviet mathematician Andrey Markov produced
a concrete undecidable problem using linear algebra. In his seminal work _“On
certain insoluble problems concerning matrices”_ [Markov (1947)], Markov
studied the following decision problem. Its input is a finite set of square
matrices $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ and a matrix $T$, and the
problem is whether or not there exist an integer $p\geq 1$ and a sequence
$A_{i_{1}},\ldots,A_{i_{p}}$ of matrices in $\mathcal{G}$ such that
$T=A_{i_{1}}A_{i_{2}}\cdots A_{i_{p}}$. Markov showed this problem to be
undecidable for integer matrices of dimension at least six, thus marking the
first undecidability result obtained outside of mathematical logic and the
theory of computing.

Markov’s work falls into the area of computational group theory, which is one
of the oldest and most well-developed parts of computational algebra. The
“official” start of computational group theory dates back to 1911, when Max
Dehn formulated three basic problems that would become its foundation. Given a
finite presentation of a group $G$, it is asked whether there are algorithms
that solve the _Word Problem_ (whether an element is the neutral element), the
_Conjugacy Problem_ (whether two elements are conjugate in $G$), and the
_Isomorphism Problem_ (whether $G$ is isomorphic to another finitely presented
group). It was not until the 1950s that the three problem were shown to be
undecidable in general groups [Novikov (1955), Adyan (1955)].

Using the language of computational group theory, Markov’s problem can be
reformulated as deciding _Semigroup Membership_ in a matrix (semi)group. For a
finite subset $\mathcal{G}$ of a group $G$, denote by
$\langle\mathcal{G}\rangle$ the subsemigroup generated by $\mathcal{G}$. Then
the Semigroup Membership problem can be formulated as follows.

  1. (i)

(Semigroup Membership) given a finite set $\mathcal{G}$ and an element $T$ in
$G$, decide whether $T\in\langle\mathcal{G}\rangle$.

Markov’s undecidability result as well as the subsequent undecidability
results for Dehn’s problems generated a surge of research interest in
computational group theory. In the 1960s, Mikhailova introduced the group
version of Semigroup Membership. For a finite subset $\mathcal{G}$ of a group
$G$, denote by $\langle\mathcal{G}\rangle_{grp}$ the sub _group_ generated by
$\mathcal{G}$.

  1. (ii)

(Group Membership) given a finite set $\mathcal{G}$ and an element $T$ in $G$,
decide whether $T\in\langle\mathcal{G}\rangle_{grp}$.

[Mikhailova (1966)] showed undecidability of Group Membership when $G$ is the
group $\mathsf{SL}(4,\mathbb{Z})$ of $4\times 4$ integer matrices with
determinant one. One may note that undecidability of Group Membership subsumes
that of Semigroup Membership by including the inverse of the elements in
$\mathcal{G}$.

There has been a steady growth in research intensity for Group and Semigroup
Membership problems as they establish important connections between algebra
and logic. These problems now play an essential role in analysing system
dynamics and program termination, and have numerous applications in automata
theory, complexity theory, and interactive proof systems [Beals and Babai
(1993), Blondel et al. (2005), Derksen et al. (2005), Hrushovski et al.
(2018)]. It is worth noting that membership problems are in fact decidable for
many classes of groups, such as abelian groups and low dimensional matrix
groups [Babai et al. (1996), Choffrut and Karhumäki (2005)]. For example, in
the matrix group $\mathsf{SL}(2,\mathbb{Z})$, Semigroup Membership is
decidable by a classic result of [Choffrut and Karhumäki (2005)], and Group
Membership is decidable in polynomial time (PTIME) by a recent result of
[Lohrey (2023)]. Our interest in computational group theory is two-fold. From
an application point of view, we are interested in developing practical
algorithms for specific classes of groups. From a theory point of view, we aim
to close the gap between decidability and undecidability.

For most classes of groups, Group Membership is much more tractable than
Semigroup Membership. For example, Group Membership is decidable in the class
of _polycyclic groups_ [Kopytov (1968)]; whereas Semigroup Membership is
undecidable even in the subclass of _nilpotent groups_ [Roman’kov (2022)].
This gap motivated the introduction of two intermediate problems in [Choffrut
and Karhumäki (2005)]:

  1. (iii)

(Identity Problem) given a finite subset $\mathcal{G}$ of $G$, decide whether
$\langle\mathcal{G}\rangle$ contains the neutral element of $G$.

  2. (iv)

(Group Problem) given a finite subset $\mathcal{G}$ of $G$, decide whether
$\langle\mathcal{G}\rangle=\langle\mathcal{G}\rangle_{grp}$.

In other words, the Identity Problem asks whether there exists a non-empty
sequence of elements from $\mathcal{G}$ whose product is the neutral element;
and the Group Problem asks whether the semigroup $\langle\mathcal{G}\rangle$
is a group.

The Group Problem is crucial in determining structural properties of a
semigroup. For example, given a decision procedure for the Group Problem, one
can compute a generating set for the _group of units_ of a finitely generated
semigroup $\langle\mathcal{G}\rangle$. We also point out that there are
significantly more available algorithms for groups than there are for
semigroups. Therefore performing preliminary checks using the Group Problem
can help decide Semigroup Membership in many special cases. Using the Group
Problem, one can also decide the lesser known _Inverse Problem_ : given a
finite set $\mathcal{G}$ and an element $a\in\mathcal{G}$, decide whether
$a^{-1}\in\langle\mathcal{G}\rangle$. The solution for the Identity Problem is
usually the most essential special case on the way to building an algorithm
for Semigroup Membership.

Unfortunately, decidability of these two intermediate problems remains open
for most classes of groups, even in cases where decidability of Group and
Semigroup Membership already have definitive answers. Notable examples include
nilpotent groups, polycyclic groups and metabelian groups.

Beyond the membership problems and the intermediate problems, another classic
problem is _Semigroup Intersection_ :

  1. (v)

(Semigroup Intersection) given two finite subsets $\mathcal{G},\mathcal{H}$ of
$G$, decide whether
$\langle\mathcal{G}\rangle\cap\langle\mathcal{H}\rangle=\emptyset$.

In the seminal paper where Markov demonstrated undecidabilty of Semigroup
Membership, he also showed undecidability of Semigroup Intersection for
integer matrix groups of dimension at least four [Markov (1947)]. Markov’s
idea is to encode the famous _Post Correspondence Problem_ , which can be
reformulated as Semigroup Intersection in a direct product of two free
monoids.

We may note that some algorithmic problems are intrinsically more difficult
than others. For example, Semigroup Membership subsumes Group Membership by
including the inverses of the generators. In terms of decidability, both
Semigroup Membership and Semigroup Intersection subsume the Group Problem,
which itself subsumes the Identity Problem [Bell and Potapov (2010)]. We also
point out that all five problems are special cases of the more general
_Rational Subset Membership_ problem, which asks whether an element $T$ is
contained in a given _rational subset_ of $G$ (a subset defined by a rational
expression over the generators of $G$). Rational Subset Membership is beyond
the scope of this article, and we refer interested readers to [Lohrey (2013)]
for a survey on this problem. See also [Lohrey et al. (2015), Chistikov and
Haase (2016), Cadilhac et al. (2020)] for recent advances. Reductions in terms
of decidability between the different algorithmic problems is summarized in
Figure 1.

Rational Subset MembershipSemigroup MembershipSemigroup IntersectionGroup
MembershipGroup ProblemIdentity Problem Figure 1: Reductions between different
algorithmic problems.

### Example: the case of $\mathbb{Z}^{d}$

We end this introduction with an example to illustrate why the above
algorithmic problems can be considered fundamental in computational group
theory.

Let the ambient group $G$ be the abelian group $\mathbb{Z}^{d}$ for some
$d\in\mathbb{N}$, where the group law “$+$” is coordinate-wise addition:
$(a_{1},\ldots,a_{d})+(b_{1},\ldots,b_{d})=(a_{1}+b_{1},\ldots,a_{d}+b_{d})$.
We show that the above algorithmic problems in the group $\mathbb{Z}^{d}$
correspond to several classic problems in computer science.

Consider Semigroup Membership in $\mathbb{Z}^{d}$. Let
$\mathcal{G}\coloneqq\\{(a_{11},\ldots,a_{1d}),\ldots,(a_{K1},\ldots,a_{Kd})\\}$
and $T\coloneqq(b_{1},\ldots,b_{d})$ be the input of Semigroup Membership.
Recall that we want to decide whether $T$ is contained in the semigroup
$\langle\mathcal{G}\rangle$. Since $G=\mathbb{Z}^{d}$ is abelian, the
semigroup $\langle\mathcal{G}\rangle$ can be explicitly described as follows:

$\langle\mathcal{G}\rangle=\left\\{n_{1}\cdot(a_{11},\ldots,a_{1d})+\cdots+n_{K}\cdot(a_{K1},\ldots,a_{Kd})\;\middle|\;(n_{1},\ldots,n_{K})\in\mathbb{N}^{K}\setminus\\{0^{K}\\}\right\\}.$
(1)

Then, deciding whether $T\in\langle\mathcal{G}\rangle$ corresponds to deciding
whether the system of linear equations

$\displaystyle n_{1}a_{11}+\cdots+n_{K}a_{K1}=b_{1},$ $\displaystyle
n_{1}a_{12}+\cdots+n_{K}a_{K2}=b_{2},$ $\displaystyle\quad\vdots$
$\displaystyle n_{1}a_{1d}+\cdots+n_{K}a_{Kd}=b_{d},$

admits a non-negative solution
$(n_{1},\ldots,n_{K})\in\mathbb{N}^{K}\setminus\\{0^{K}\\}$. This is
equivalent to the fundamental problem of _Integer Programming_ and is
therefore NP-complete.

Similarly, consider the problem of Group Membership in $\mathbb{Z}^{d}$, that
is, whether $T$ is contained in the group $\langle\mathcal{G}\rangle_{grp}$
generated by the set $\mathcal{G}$. The group
$\langle\mathcal{G}\rangle_{grp}$ can be explicitly described as follows:

$\langle\mathcal{G}\rangle_{grp}=\left\\{n_{1}\cdot(a_{11},\ldots,a_{1d})+\cdots+n_{K}\cdot(a_{K1},\ldots,a_{Kd})\;\middle|\;(n_{1},\ldots,n_{K})\in\mathbb{Z}^{K}\right\\}.$
(2)

The difference of the _group_ $\langle\mathcal{G}\rangle_{grp}$ from the
_semigroup_ $\langle\mathcal{G}\rangle$ is that we allow inverses of the
generators to appear in the sum, hence the tuple $(n_{1},\ldots,n_{K})$ now
takes value in $\mathbb{Z}^{K}$ instead of
$\mathbb{N}^{K}\setminus\\{0^{K}\\}$. Therefore, Group Membership is
equivalent to deciding whether the system of linear equations

$\displaystyle n_{1}a_{11}+\cdots+n_{K}a_{K1}=b_{1},$ $\displaystyle
n_{1}a_{12}+\cdots+n_{K}a_{K2}=b_{2},$ $\displaystyle\quad\vdots$
$\displaystyle n_{1}a_{1d}+\cdots+n_{K}a_{Kd}=b_{d},$

admits an integer solution $(n_{1},\ldots,n_{K})\in\mathbb{Z}^{K}$. This
becomes the classic problem of solving linear equations over $\mathbb{Z}$, and
is decidable in polynomial (less then cubic) time.

Consider now the Identity Problem in $\mathbb{Z}^{d}$. Specializing Semigroup
Membership by taking $T$ to be the neutral element $(0,\ldots,0)$, the
Identity Problem is equivalent to deciding whether the system of _homogeneous_
linear equations

$\displaystyle n_{1}a_{11}+\cdots+n_{K}a_{K1}=0,$ $\displaystyle
n_{1}a_{12}+\cdots+n_{K}a_{K2}=0,$ $\displaystyle\quad\vdots$ $\displaystyle
n_{1}a_{1d}+\cdots+n_{K}a_{Kd}=0,$

admits a non-trivial solution
$(n_{1},\ldots,n_{K})\in\mathbb{N}^{K}\setminus\\{0^{K}\\}$. By scaling the
solution, this is equivalent to deciding whether the system admits a non-
trivial solution over the non-negative _rationals_
$(n_{1},\ldots,n_{K})\in\mathbb{Q}_{\geq 0}^{K}\setminus\\{0^{K}\\}$. Since
the system only admits integer coefficients, it admits a non-trivial solution
over the non-negative rationals if and only if it admits a non-trivial
solution over the non-negative _reals_. Hence, the Identity Problem becomes
the famous _Linear Programming_ problem, which is known to be decidable in
polynomial time.

The Group Problem is perhaps less intuitive in terms of systems of linear
equations. However it becomes clearer from a geometric point of view. Indeed,
the semigroup $\langle\mathcal{G}\rangle$ can be understood as the cone
generated by the elements $\mathcal{G}$ in the space $\mathbb{Z}^{d}$, whereas
the group $\langle\mathcal{G}\rangle_{grp}$ can be understood as the linear
space generated by the elements $\mathcal{G}$. Therefore the Group Problem can
be reformulated as deciding whether a finitely generated cone is actually a
linear space.

For Semigroup Intersection, write
$\mathcal{G}\coloneqq\\{(a_{11},\ldots,a_{1d}),\ldots,(a_{K1},\ldots,a_{Kd})\\}$
and
$\mathcal{H}\coloneqq\\{(c_{11},\ldots,c_{1d}),\ldots,(c_{M1},\ldots,c_{Md})\\}$.
Then deciding whether
$\langle\mathcal{G}\rangle\cap\langle\mathcal{H}\rangle=\emptyset$ is
equivalent to deciding whether the system of homogeneous linear equations

$\displaystyle
n_{1}a_{11}+\cdots+n_{K}a_{K1}=\ell_{1}c_{11}+\cdots+\ell_{M}c_{M1},$
$\displaystyle
n_{1}a_{12}+\cdots+n_{K}a_{K2}=\ell_{1}c_{12}+\cdots+\ell_{M}c_{M2},$
$\displaystyle\quad\vdots$ $\displaystyle
n_{1}a_{1d}+\cdots+n_{K}a_{Kd}=\ell_{1}c_{1d}+\cdots+\ell_{M}c_{Md},$

admits a pair of non-trivial solutions
$(n_{1},\ldots,n_{K})\in\mathbb{N}^{K}\setminus\\{0^{K}\\},(\ell_{1},\ldots,\ell_{M})\in\mathbb{N}^{M}\setminus\\{0^{M}\\}$.
This is again solvable by Linear Programming by scaling the solutions to
$\mathbb{Q}_{\geq 0}$. In particular, since we are working in the abelian
group $\mathbb{Z}^{d}$, commutativity allows us to freely permute elements in
the sum, and move terms between the two sides of an equation. Hence Semigroup
Intersection becomes similar to the Identity Problem. However, when we work in
groups with more complex structures (namely non-abelian groups), this
equivalence will fail, and Semigroup Intersection can become much more
difficult than the Identity Problem.

Lastly, we mention that Rational Subset Membership in $\mathbb{Z}^{d}$
corresponds to the notion of computing _semilinear sets_. See [Chistikov and
Haase (2016)] for a proof of decidability and its complexity analysis.

##  2 Notes for the reader

It is clear from the introduction that the complexity and decidability of
semigroup algorithmic problems greatly depend on the ambient group $G$. As
shown in the last example, the case where $G=\mathbb{Z}^{d}$ is relatively
simple. On the contrary, when the group $G$ is an arbitrary (non-commutative)
group, the algorithmic problems we consider become much more complex and even
undecidable. To achieve decidability, one must assume additional structure on
the group $G$. The aim of this article is to give an overview of recent
advances in the decidability and complexity of the aforementioned algorithmic
problems in different classes of groups $G$, as well as point out various open
problems. Section 3 is about low-dimensional matrix groups as well as their
subgroups and extensions, whereas in Section 4 we consider groups with
additional structures such as nilpotency and being metabelian. In Section 5 we
mention some other related algorithmic problems in groups and semigroups.

For the most part of this article, the group $G$ is explicitly given as a
matrix group (such as $\mathsf{SL}(n,\mathbb{Z})$). In this case, the elements
of $G$ are represented as matrices with _binary encoded entries_.
Nevertheless, many of the results stated in this article can be extended to
the case where $G$ is given as an abstract group, which is usually embeddable
in some well-studied matrix group.

##  3 Low-dimensional matrix groups

This section contains results for low-dimensional matrix groups. In
particular, we are interested in the _special linear groups_
$\mathsf{SL}(n,\mathbb{Z})$ as well as their subgroups and extensions.

######  Definition 3.1 (Special linear groups).

Let $n\in\mathbb{N}$. The _special linear group_ $\mathsf{SL}(n,\mathbb{Z})$
is the group of $n\times n$ integer matrices with determinant one:

$\mathsf{SL}(n,\mathbb{Z})\coloneqq\\{A\in\mathbb{Z}^{n\times
n}\mid\det(A)=1\\}.$

Semigroups are closely related to the notion of _words_ over an alphabet:

######  Definition 3.2 (Words over an alphabet).

By an _alphabet_ , we mean a finite set $\Sigma$. Elements of an alphabet are
called _letters_. A _word_ over an alphabet $\Sigma$ is a finite string of
letters, possibly empty. In particular, the empty string is called the _empty
word_ , usually denoted by $\epsilon$. Given any alphabet $\Sigma$, we denote
by $\Sigma^{*}$ the set of words over $\Sigma$:

$\Sigma^{*}\coloneqq\left\\{a_{1}a_{2}\cdots a_{m}\mid m\geq 0,a_{1},\ldots
a_{m}\in\Sigma\right\\}.$

For two words $v,w\in\Sigma^{*}$, we denote by $v\cdot w$ or simply $vw$ the
concatenation of $v$ and $w$, it is again a word over $\Sigma$. The operation
of concatenation gives the sets $\Sigma^{*}$ and
$\Sigma^{*}\setminus\\{\epsilon\\}$ the structure of semigroups.

For example, Semigroup Membership can now be reformulated as asking whether
there exists a word $w\in\mathcal{G}^{*}\setminus\\{\epsilon\\}$, whose
product in $G$ is equal to $T$; and Semigroup Intersection can be reformulated
as asking whether there exists two words
$w\in\mathcal{G}^{*}\setminus\\{\epsilon\\},v\in\mathcal{H}^{*}\setminus\\{\epsilon\\}$,
such that the products of $w$ and $v$ in $G$ are equal.

###  3.1 Dimension two

The group $\mathsf{SL}(2,\mathbb{Z})$ has been a classic object of study. It
is closely related to various areas in mathematics such as hyperbolic
geometry, modular forms, and dynamical systems [Bruinier et al. (2008), Newman
(1962), Polterovich and Rudnick (2004)].

The key to solving algorithmic problems in $\mathsf{SL}(2,\mathbb{Z})$ is the
fact that $\mathsf{SL}(2,\mathbb{Z})$ is _virtually free_ , meaning it
contains a _free_ subgroup of finite index.

######  Definition 3.3 (Free group).

Given an alphabet $\Sigma$, define the corresponding group alphabet
$\Sigma^{\pm}\coloneqq\Sigma\cup\\{a^{-1}\mid a\in\Sigma\\}$, where $a^{-1}$
is a new letter for each $a\in\Sigma$. There is a natural involution
$(\cdot)^{-1}$ over the set of words $\left(\Sigma^{\pm}\right)^{*}$ defined
by $(a^{-1})^{-1}=a$ and $(a_{1}a_{2}\cdots a_{m})^{-1}=a_{m}^{-1}\cdots
a_{2}^{-1}a_{1}^{-1}$. A word over the alphabet $\Sigma^{\pm}$ is called
_reduced_ if it does not contain consecutive letters $aa^{-1}$ or $a^{-1}a$,
$a\in\Sigma$. For a word $w$, define $\operatorname{red}(w)$ to be the reduced
word obtained by iteratively replacing consecutive letters $aa^{-1}$ and
$a^{-1}a$ with the empty string. The _free group_ $F(\Sigma)$ over $\Sigma$ is
then defined as the set of reduced words in $\left(\Sigma^{\pm}\right)^{*}$,
where multiplication is given by $v\cdot w=\operatorname{red}(vw)$, inversion
is given by the involution $(\cdot)^{-1}$, and the neutral element is the
empty word $\epsilon$.

If we take $\Sigma=\\{a,b\\}$, then the group $F(\Sigma)$ is the free group
over two generators, and is denoted by $F_{2}$. For example, in $F(\\{a,b\\})$
we have $(aaba^{-1})^{-1}=ab^{-1}a^{-1}a^{-1}$, and $aaba^{-1}\cdot
ab=\operatorname{red}(aaba^{-1}ab)=aabb$.

In particular, the subgroup of $\mathsf{SL}(2,\mathbb{Z})$ generated by
$A\coloneqq\begin{pmatrix}1&2\\\ 0&1\\\ \end{pmatrix}$ and
$B\coloneqq\begin{pmatrix}1&0\\\ 2&1\\\ \end{pmatrix}$ is a free group [Druţu
and Kapovich (2018), Example 7.63]. It is of index 12, meaning the quotient
$\mathsf{SL}(2,\mathbb{Z})/\langle A,B\rangle_{grp}$ is a set with 12 elements
[Rüping (2010)].

Algorithmic problems in free groups have been extensively studied since the
1950s [Howson (1954)]. A classic tool for solving algorithmic problem in free
groups is the automata-inspired _Stallings foldings_. The idea of using
automata-based approaches to deal with free groups can be traced back to
[Benois (1969)] who showed decidability of Rational Subset Membership in
finitely generated free groups. We recommend [Kapovich and Myasnikov (2002)]
for an introduction on Stallings foldings as well as their applications in
algorithmic problems in free groups.

While Stallings foldings are initially proposed to deal with free groups, they
are easily generalizable to virtually free groups, notably
$\mathsf{SL}(2,\mathbb{Z})$. This becomes the foundation of several results
concerning decidability and complexity of algorithmic problems in
$\mathsf{SL}(2,\mathbb{Z})$:

######  Theorem 3.4.

In the group $\mathsf{SL}(2,\mathbb{Z})$:

  1. (i)

[Choffrut and Karhumäki (2005)] Rational Subset Membership is decidable.

  2. (ii)

[Bell et al. (2017), Bell et al. (2023)] Semigroup Membership, the Identity
Problem and the Group Problem are decidable and NP-complete.

  3. (iii)

[Lohrey (2023)] Group Membership is decidable in PTIME.

### Example: Semigroup Membership in the free group $F_{2}$

We give an example of the decision procedure for Semigroup Membership in the
free group $F_{2}$ to show some of the techniques involved. This is very
similar to the decision procedure for $\mathsf{SL}(2,\mathbb{Z})$ (which
contains $F_{2}$ as a finite index subgroup), but is easier to describe.

Working in the group $F_{2}=F(\\{a,b\\})$, suppose we want to decide whether
$T\coloneqq a$ is in the semigroup generated by the set
$\mathcal{G}\coloneqq\\{aab,b^{-1}a^{-1}\\}$. In other words, we want to
decide whether there is an expression of the form $w=w_{1}w_{2}\cdots
w_{p},p\geq 1,w_{1},\ldots,w_{p}\in\\{aab,b^{-1}a^{-1}\\}$, such that
$\operatorname{red}(w)=a$ (recall the definition of
$\operatorname{red}(\cdot)$ from Definition 3.3). Since $a\neq\epsilon$, we
can without loss of generality include the case $p=0$. Therefore, deciding
whether $a\in\langle aab,b^{-1}a^{-1}\rangle$ is equivalent to deciding
whether there exists an expression of the form $v=a^{-1}w_{1}w_{2}\cdots
w_{p},\;p\geq 0,w_{1},\ldots,w_{p}\in\\{aab,b^{-1}a^{-1}\\}$, such that
$\operatorname{red}(v)=\epsilon$.

We can construct an automaton $\mathcal{A}$ that recognizes the set of words

$\mathcal{L}\coloneqq\big{\\{}a^{-1}w_{1}w_{2}\cdots w_{p}\;\big{|}\;p\geq
0,w_{1},\ldots,w_{p}\in\\{aab,b^{-1}a^{-1}\\}\big{\\}}.$

See Figure 3 for an illustration of the automaton $\mathcal{A}$. In
particular, every path starting from the initial state $q_{I}$ and ending at
the accepting state $q_{F}$ represents a word in the language $\mathcal{L}$;
and every word in $\mathcal{L}$ can be represented as a path from $q_{I}$ to
$q_{F}$. For example, the word $a^{-1}\cdot aab\cdot
b^{-1}a^{-1}\in\mathcal{L}$ corresponds to the path $q_{I}\rightarrow
q_{F}\rightarrow q_{11}\rightarrow q_{12}\rightarrow q_{F}\rightarrow
q_{21}\rightarrow q_{F}$.

$q_{I}$start$q_{F}$$q_{11}$$q_{12}$$q_{21}$$a^{-1}$$a$$a$$b$$b^{-1}$$a^{-1}$
Figure 2: An automaton $\mathcal{A}$ that recognizes the language
$\mathcal{L}$.

$q_{I}$start$q_{F}$$q_{11}$$q_{12}$$q_{21}$$a^{-1}$$a$$a$$b$$b^{-1}$$a^{-1}$$\epsilon$$\epsilon$$\epsilon$$\epsilon$$\epsilon$
Figure 3: The saturated automaton $\mathcal{A}_{0}$.

However, it is not clear from the automaton $\mathcal{A}$ whether
$\mathcal{L}$ contains a word $v$ such that $\operatorname{red}(v)=\epsilon$.
The idea is to now “saturate” the automaton $\mathcal{A}$ to include words
obtained from reducing words in $\mathcal{L}$. To be precise, we want to
construct an automaton $\mathcal{A}_{0}$ that recognizes a language
$\mathcal{L}_{0}$, such that the reduced words in $\mathcal{L}_{0}$ are
exactly the set $\\{\operatorname{red}(v)\mid v\in\mathcal{L}\\}$.

A construction of the automaton $\mathcal{A}_{0}$ is illustrated in Figure 3.
Starting with $\mathcal{A}$, we add the edge
$q_{12}\xrightarrow{\epsilon}q_{21}$ because any path containing the subpath
$q_{12}\xrightarrow{b}q_{F}\xrightarrow{b^{-1}}q_{21}$ results in $bb^{-1}$
which can be reduced to $\epsilon$. Similarly, we add the edge
$q_{11}\xrightarrow{\epsilon}q_{F}$ thanks to the path
$q_{11}\xrightarrow{a}q_{12}\xrightarrow{\epsilon}q_{21}\xrightarrow{a^{-1}}q_{F}$
resulting in $aa^{-1}$; we add the edge $q_{21}\xrightarrow{\epsilon}q_{11}$
thanks to the path $q_{21}\xrightarrow{a^{-1}}q_{F}\xrightarrow{a}q_{11}$; and
we add the edge $q_{I}\xrightarrow{\epsilon}q_{11}$ thanks to the path
$q_{I}\xrightarrow{a^{-1}}q_{F}\xrightarrow{a}q_{11}$. Finally, we add the
edge $q_{I}\xrightarrow{\epsilon}q_{F}$ thanks to the path
$q_{I}\xrightarrow{\epsilon}q_{11}\xrightarrow{\epsilon}q_{F}$. As a
conclusion, we can pass from $q_{I}$ to $q_{F}$ using a path which reduces to
$\epsilon$. Therefore $T\coloneqq a$ is indeed contained in the semigroup
generated by the set $\mathcal{G}\coloneqq\\{aab,b^{-1}a^{-1}\\}$.

Note that this process of adding $\epsilon$-transitions always finishes in
finitely many steps because there are only a finite number of states in
$\mathcal{A}$. In general, if after the process there is an
$\epsilon$-transition from $q_{I}$ to $q_{F}$ then we conclude that
$T\in\langle\mathcal{G}\rangle$; otherwise we conclude
$T\not\in\langle\mathcal{G}\rangle$. Note that the termination of this process
relies on the fact that $\operatorname{red}(\cdot)$ is _deterministic_ ,
meaning for every $v$ the image $\operatorname{red}(v)$ is unique. This
feature grants free groups their relatively simple structure as well as
decidability of their various algorithmic problems.

The group $\mathsf{SL}(2,\mathbb{Z})$ is not far from being a free group, and
a similar approach to the above automata construction can also be applied to
$\mathsf{SL}(2,\mathbb{Z})$. We refer readers to [Potapov and Semukhin
(2017a)] for a detailed account of the method for $\mathsf{SL}(2,\mathbb{Z})$.

### Semigroup Membership in extensions of $\mathsf{SL}(2,\mathbb{Z})$

Note that one can naturally generalize the definition of Semigroup Membership
to the case where the ambient group $G$ is a _semigroup_ instead of a group. A
natural follow-up question to $\mathsf{SL}(2,\mathbb{Z})$ is whether Semigroup
Membership remains decidable when $G$ is the semigroup $\mathbb{Z}^{2\times
2}$ of $2\times 2$ integer matrices. Compared to $\mathsf{SL}(2,\mathbb{Z})$,
the semigroup $\mathbb{Z}^{2\times 2}$ contains matrices with determinant $0$
and $\pm d,d\geq 1$, which add an extra layer of difficulty. Nevertheless,
several important partial results have been obtained via extensions of the
solution for $\mathsf{SL}(2,\mathbb{Z})$:

######  Theorem 3.5.

Semigroup Membership is decidable in:

  1. (i)

[Potapov and Semukhin (2017a)] the set of $2\times 2$ integer matrices with
non-zero determinants.

  2. (ii)

[Potapov and Semukhin (2017b)] the set of $2\times 2$ integer matrices with
determinants $0,-1$ and $1$.

Decidability of Semigroup Membership remains an open problem for the set of
_all_ $2\times 2$ integer matrices.

Another interesting extension of $\mathsf{SL}(2,\mathbb{Z})$ is the group
$\mathsf{GL}(2,\mathbb{Q})$ of $2\times 2$ invertible matrices with _rational_
entries. All algorithmic problems listed in Figure 1 remain open for the group
$\mathsf{GL}(2,\mathbb{Q})$, with very limited partial results currently known
[Diekert et al. (2020), Cadilhac et al. (2020)].

###  3.2 Dimension three

One of the most outstanding open problems in computational group theory is the
decidability of Group Membership in $\mathsf{SL}(3,\mathbb{Z})$. In fact, the
decidability status of all algorithmic problems listed in Figure 1 remains
open for $\mathsf{SL}(3,\mathbb{Z})$. This is notably due to a lack of
understanding for the structure of subgroups in $\mathsf{SL}(3,\mathbb{Z})$.
Currently, the closest undecidability result is Semigroup Membership in the
set $\mathbb{Z}^{3\times 3}$ of $3\times 3$ integer matrices, by [Paterson
(1970)]:

######  Theorem 3.6 (Mortality Problem [Paterson (1970)]).

The following problem is undecidable: given a finite set $\mathcal{G}$ of
$3\times 3$ integer matrices, decide whether the zero matrix $0^{3\times 3}$
is in the semigroup $\langle\mathcal{G}\rangle$.

Although the decidability of algorithmic problems in
$\mathsf{SL}(3,\mathbb{Z})$ seems out of reach for the moment, positive
results have been obtained for several important subgroups of
$\mathsf{SL}(3,\mathbb{Z})$.

### The Heisenberg group $\operatorname{H}_{3}(\mathbb{Z})$

We consider the _integer Heisenberg group_ $\operatorname{H}_{3}(\mathbb{Z})$,
which is the group of $3\times 3$ upper-triangular integer matrices with ones
on the diagonal.

$\operatorname{H}_{3}(\mathbb{Z})\coloneqq\left\\{\begin{pmatrix}1&*&*\\\
0&1&*\\\ 0&0&1\\\ \end{pmatrix},\text{ where $*$ are entries in
$\mathbb{Z}$}\right\\},$

The Heisenberg groups play an important role in many branches of mathematics,
physics and computer science. They first arose in the description of one-
dimensional quantum mechanical systems [Neumann (1931), Weyl (1950)], and have
now become an important mathematical object connecting areas like
representation theory, Fourier analysis and quantum algorithms [Howe (1980),
Kirillov (2004), Krovi and Rötteler (2008)]. From a computational point of
view, the Heisenberg group received much attention in the past ten years
because it is one of the simplest non-commutative matrix groups.

######  Theorem 3.7.

In the Heisenberg group $\operatorname{H}_{3}(\mathbb{Z})$:

  1. (i)

[Colcombet et al. (2019)] Semigroup Membership is decidable.

  2. (ii)

[Ko et al. (2018)] The Identity Problem is decidable in PTIME.

  3. (iii)

[Dong (2022)] The Group Problem is decidable in PTIME.

  4. (iv)

[Dong (2023d)] Semigroup Intersection is decidable in PTIME.

It follows from Theorem 3.7(i) that Group Membership is also decidable in
$\operatorname{H}_{3}(\mathbb{Z})$. However we are not aware of any complexity
analysis on this problem. The main idea for proving Theorem 3.7(i) is to use
the _Baker-Campbell-Hausdorff formula_ [Baker (1905), Campbell (1897),
Hausdorff (1906)] from Lie algebra, as well as to incorporate Semigroup
Membership in a Parikh automaton. The main ideas behind Theorem 3.7(ii)-(iv)
are reductions to word combinatorics problems. Note that the decidability of
Rational Subset Membership in $\operatorname{H}_{3}(\mathbb{Z})$ remains an
intricate open problem.

### The special affine group $\mathsf{SA}(2,\mathbb{Z})$

Compared to $\operatorname{H}_{3}(\mathbb{Z})$, a larger subgroup of
$\mathsf{SL}(3,\mathbb{Z})$ is the _special affine group_
$\mathsf{SA}(2,\mathbb{Z})$. The group $\mathsf{SA}(2,\mathbb{Z})$ consists of
affine transformations of $\mathbb{Z}^{2}$ that preserve orientation, and can
be considered as an intermediate group between $\mathsf{SL}(2,\mathbb{Z})$ and
$\mathsf{SL}(3,\mathbb{Z})$. Written as matrices, elements of
$\mathsf{SA}(2,\mathbb{Z})$ are $3\times 3$ integer matrices of the following
form.

$\mathsf{SA}(2,\mathbb{Z})\coloneqq\left\\{M=\begin{pmatrix}*&*&*\\\ *&*&*\\\
0&0&1\\\ \end{pmatrix}\;\middle|\;\det(M)=1\text{, where $*$ are entries in
$\mathbb{Z}$}\right\\}.$

Like $\mathsf{SL}(2,\mathbb{Z})$, the special affine group is important in the
context of many fundamental problems, such as Lie groups [Wolf (1963)],
polyhedral geometry [Mundici (2014)], dynamical systems [Cabrer and Mundici
(2017)], and computer vision [Giefer et al. (2020)]. Apart from the intrinsic
interest to study $\mathsf{SA}(2,\mathbb{Z})$, we also point out that the
Special Affine group has tight connections to various reachability problems in
automata theory. Some of the central questions in automated verification
include reachability problems in _Affine Vector Addition Systems_ and _Affine
Vector Addition Systems with states (Affine VASS)_ over the integers [Raskin
et al. (2021)]. The study of these reachability problems in dimension two
necessitates the understanding of subsemigroups of
$\mathsf{SA}(2,\mathbb{Z})$.

Every element in $\mathsf{SA}(2,\mathbb{Z})$ can be written as a pair
$(A,\boldsymbol{a})$, where
$A\in\mathsf{SL}(2,\mathbb{Z}),\boldsymbol{a}\in\mathbb{Z}^{2}$. This pair
represents the element $\begin{pmatrix}A&\boldsymbol{a}\\\ 0&1\\\
\end{pmatrix}$. Multiplication in $\mathsf{SA}(2,\mathbb{Z})$ is then given by

$(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(AB,A\boldsymbol{b}+\boldsymbol{a}).$

Naturally, $\mathsf{SA}(2,\mathbb{Z})$ has a subgroup
$\\{(A,\boldsymbol{0})\mid A\in\mathsf{SL}(2,\mathbb{Z})\\}$ isomorphic to
$\mathsf{SL}(2,\mathbb{Z})$. In the language of group theory, this means that
$\mathsf{SA}(2,\mathbb{Z})$ is a _semidirect product_ of the groups
$\mathsf{SL}(2,\mathbb{Z})$ and $\mathbb{Z}^{2}$. This structure is crucial to
the resolution of several algorithmic problems in $\mathsf{SA}(2,\mathbb{Z})$.

######  Theorem 3.8.

In the group $\mathsf{SA}(2,\mathbb{Z})$:

  1. (i)

[Kapovich et al. (2005), Delgado Rodríguez (2017)] Group Membership is
decidable.

  2. (ii)

[Dong (2023b)] The Identity Problem and the Group Problem are decidable and
NP-complete.

The decidability of Semigroup Membership and Semigroup Intersection in
$\mathsf{SA}(2,\mathbb{Z})$ remains open. See [Dong (2023b)] for a discussion
of current obstacles to solving these problems. Theorem 3.8(i) comes from the
classic idea that $\mathsf{SA}(2,\mathbb{Z})$ can be realized as a _graph of
groups_. Graph of groups is a central object in the area of geometric group
theory, and Group Membership has been solved for a large class of graph of
groups using generalizations of Stallings foldings [Kapovich et al. (2005)].
However, such methods generally fail for semigroup problems, and the proof of
Theorem 3.8(ii) employs an algebraic approach instead of an automata-based
approach.

###  3.3 Dimension four

While the algorithmic problems of Figure 1 are decidable in
$\mathsf{SL}(2,\mathbb{Z})$ and open in $\mathsf{SL}(3,\mathbb{Z})$, they all
become undecidable for $\mathsf{SL}(4,\mathbb{Z})$. Note that
$\mathsf{SL}(4,\mathbb{Z})$ naturally contains as a subgroup the direct
product $\mathsf{SL}(2,\mathbb{Z})\times\mathsf{SL}(2,\mathbb{Z})$, and that
$\mathsf{SL}(2,\mathbb{Z})$ contains the free subgroup $F_{2}$. Therefore
$\mathsf{SL}(4,\mathbb{Z})$ contains the subgroup $F_{2}\times F_{2}$, which
constitutes the key to proving all undecidability results in
$\mathsf{SL}(4,\mathbb{Z})$. If a problem is undecidable in $F_{2}\times
F_{2}$, then it must also be undecidable in $\mathsf{SL}(4,\mathbb{Z})$.

######  Theorem 3.9.

In the groups $F_{2}\times F_{2}$ and $\mathsf{SL}(4,\mathbb{Z})$:

  1. (i)

[Mikhailova (1966)] Group Membership is undecidable.

  2. (ii)

[Bell and Potapov (2010)] The Identity Problem is undecidable.

As a result of Theorem 3.9, all algorithmic problems listed in Figure 1 are
undecidable in $F_{2}\times F_{2}$ and in $\mathsf{SL}(4,\mathbb{Z})$.
Mikhailova’s idea of proving Theorem 3.9(i) is an embedding of the _Word
Problem_ , which is one of the three fundamental problems of computational
group theory.

######  Theorem 3.10 (The Word Problem [Novikov (1955)]).

The following problem is undecidable: given an alphabet $\Sigma$ as well as
elements $v_{1},\ldots,v_{n},w$ in the free group $F(\Sigma)$, decide whether
$w$ is in the normal subgroup $\langle\langle
v_{1},\ldots,v_{n}\rangle\rangle$ generated by $v_{1},\ldots,v_{n}$. In other
words, it is undecidable whether a word $w\in\left(\Sigma^{\pm}\right)^{*}$ is
equal to the neutral element in the quotient $F(\Sigma)/\langle\langle
v_{1},\ldots,v_{n}\rangle\rangle$.

The subgroup $\langle\langle v_{1},\ldots,v_{n}\rangle\rangle$ is defined as
the smallest _normal_ subgroup containing the elements $v_{1},\ldots,v_{n}$.
It is in general different from $\langle v_{1},\ldots,v_{n}\rangle_{grp}$.
This constitutes the difference between the Word Problem and Group Membership.
For this reason, Group Membership is sometimes referred to in literature as
the _Generalized Word Problem_. Mikhailova showed that one can embed an
instance of the Word Problem into the Group Membership problem in $F_{2}\times
F_{2}$, thus proving its undecidability.

Bell and Potapov’s idea of proving Theorem 3.9(ii) is to embed a variation of
the famous _Post Correspondence Problem_.

######  Theorem 3.11 (Post Correspondence Problem [Post (1946)]).

The following problem is undecidable: given a set of word pairs
$S=\\{(v_{1},w_{1}),\ldots,(v_{K},w_{K})\\}$ in
$\\{a,b\\}^{*}\times\\{a,b\\}^{*}$, decide whether there exist $p\geq 1$ and a
sequence of indices $i_{1},\ldots,i_{p}\in\\{1,\ldots,K\\}$ such that
$v_{i_{1}}v_{i_{2}}\cdots v_{i_{p}}=w_{i_{1}}w_{i_{2}}\cdots w_{i_{p}}$.

The Post Correspondence Problem is one of the first known undecidability
results in algorithmic theory, and it remains a staple tool for proving
undecidability of various combinatorial problems. Bell and Potapov showed that
one can embed an instance of the Post Correspondence Problem into the Identity
Problem in $F_{2}\times F_{2}$, thus proving its undecidability.

######  Remark 3.12.

The Post Correspondence Problem can be considered as a special case of
Semigroup Intersection in the semigroup $\\{a,b\\}^{*}\times\\{a,b\\}^{*}$.
Indeed, the Post Correspondence Problem can be reformulated as deciding
whether the semigroup
$\langle(v_{1},w_{1}),\ldots,(v_{K},w_{K})\rangle\subseteq\\{a,b\\}^{*}\times\\{a,b\\}^{*}$
intersects the semigroup of diagonals $\langle(a,a),(b,b)\rangle$. Therefore,
if a group $G$ contains $\\{a,b\\}^{*}\times\\{a,b\\}^{*}$ as a subsemigroup,
then $G$ has undecidable Semigroup Intersection. Since the group
$F_{2}=F(\\{a,b\\})$ naturally contains the subsemigroup $\\{a,b\\}^{*}$, we
immediately obtain undecidability of Semigroup Intersection in $F_{2}\times
F_{2}$. Bell and Potapov’s main contribution for Theorem 3.9(ii) is the
strengthening of the undecidability result from Semigroup Intersection to the
Identity Problem.

It is worth pointing out that the same method cannot be applied to the group
$\mathsf{SL}(3,\mathbb{Z})$. Indeed, it has been shown in [Ko et al. (2018),
Theorem 11] that $\mathsf{SL}(3,\mathbb{Z})$ does not contain any subsemigroup
isomorphic to $\\{a,b\\}^{*}\times\\{a,b\\}^{*}$. This added an extra layer of
mystery to the decidability status of problems in $\mathsf{SL}(3,\mathbb{Z})$.

##  4 Groups with additional structure

In Section 3 we showed that most algorithmic problems that are undecidable for
general matrix groups become decidable when restricted to low dimensions. In
this section, instead of the restriction on dimension, we consider
restrictions on the _structure_ of the matrix group. An iconic result in this
direction comes from Babai, Beals, Cai, Ivanyos and Luks [Babai et al.
(1996)], who showed the NP-completeness of Semigroup Membership and PTIME
decidability of Group Membership in _commutative_ matrix groups. From the
introduction (Section 1), we also know that the problems in Figure 1 all have
classic interpretations in the commutative group $\mathbb{Z}^{d}$. In this
section we consider various relaxations of the commutativity requirement.

Recall from Subsection 3.3 that all problems in Figure 1 become undecidable
when the group $G$ contains the direct product $F_{2}\times F_{2}$ of two free
groups. Most natural classes of groups are stable under direct product (for
example, the direct product of two commutative groups is still commutative).
This motivates us to consider classes of groups that do not contain $F_{2}$ as
subgroup, as these are the only natural candidates for positive decidability
results.

By the following celebrated result of Tits, a matrix group that does not
contain the subgroup $F_{2}$ must be _virtually solvable_ , meaning it
contains a _solvable_ subgroup of finite index.

######  Theorem 4.1 (Tits alternative [Tits (1972)]).

Fix any $n\in\mathbb{N}$ and let $\mathbb{K}$ be any field. Recall that
$\mathsf{GL}(n,\mathbb{K})$ denotes the group of $n\times n$ invertible
matrices with entries in $\mathbb{K}$. For every finitely generated subgroup
$H$ of $\mathsf{GL}(n,\mathbb{K})$, exactly one of the following is true:

  1. (i)

$H$ contains $F_{2}$ as a subgroup.

  2. (ii)

$H$ contains a solvable subgroup of finite index.

We therefore concentrate our study on the class of solvable groups. Its exact
definition is given as follows.

######  Definition 4.2 (Solvable groups).

Given a group $G$ and its subgroup $H$, define the commutator $[G,H]$ to be
the group generated by the elements $\\{ghg^{-1}h^{-1}\mid g\in G,h\in H\\}$.
The _derived series_ of a group $G$ is the inductively defined descending
sequence of subgroups

$G=G^{(0)}\geq G^{(1)}\geq G^{(2)}\geq\cdots,$

in which $G^{(k)}=[G^{(k-1)},G^{(k-1)}]$. A group $G$ is called _solvable_ if
its derived series terminates with $G^{(d)}$ being the trivial group for some
finite $d$. In this case, the smallest such $d$ is called the _derived length_
of $G$. For example, an abelian group is solvable of derived length one.

We refer interested readers to [Druţu and Kapovich (2018), Chapter 13] for a
comprehensive introduction of solvable groups. It is well known that all
subgroups, quotients and direct products of solvable groups are solvable
[Druţu and Kapovich (2018), Proposition 13.91].

######  Example 4.3.

Denote by $\mathsf{T}(n,\mathbb{Q})$ the group of $n\times n$ invertible upper
triangular matrices with rational entries:

$\mathsf{T}(n,\mathbb{Q})\coloneqq\left\\{\begin{pmatrix}a_{1}&*&\cdots&*&*\\\
0&a_{2}&\cdots&*&*\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&a_{n-1}&*\\\ 0&0&\cdots&0&a_{n}\\\ \end{pmatrix},\text{ where
$a_{i}$ and $*$ are entries in $\mathbb{Q}$ },a_{1}a_{2}\cdots a_{n}\neq
0\right\\}.$

Then the group $\mathsf{T}(n,\mathbb{Q})$ is solvable.

Unfortunately, without additional constraints, algorithmic problems in
solvable groups remain highly intractable. For example, [Kharlampovich (1981)]
famously constructed a solvable group of derived length three with undecidable
Word Problem111To be precise, this means that the undecidability result in
Theorem 3.10 still holds when $\Sigma,v_{1},\ldots,v_{n}$ are fixed so that
the quotient $F(\Sigma)/\langle\langle v_{1},\ldots,v_{n}\rangle\rangle$ is a
solvable group of derived length three.. Other problems such as Semigroup
Membership and Semigroup Intersection are also undecidable in general solvable
groups (see Subsections 4.1 and 4.2). Therefore, in order to obtain
decidability results, we want to consider solvable groups with additional
constraints. In what follows, we consider two important special classes of
solvable groups: _nilpotent groups_ and _metabelian groups_.

###  4.1 Nilpotent groups

In this subsection we consider nilpotent groups, which are usually considered
as an immediate generalization of abelian groups.

######  Definition 4.4 (Nilpotent groups).

The _lower central series_ of a group $G$ is the inductively defined
descending sequence of subgroups

$G=G_{0}\geq G_{1}\geq G_{2}\geq\cdots,$

in which $G_{k}=[G,G_{k-1}]$. A group $G$ is called _nilpotent_ if its lower
central series terminates with $G_{d}$ being the trivial group for some finite
$d$. In this case, the smallest such $d$ is called the _nilpotency class_ of
$G$.

In particular, abelian groups are nilpotent of class one. One can easily show
$G_{k}\geq G^{(k)}$ by induction on $k$, therefore nilpotent groups are also
solvable (but the converse is not true). It is well known that all subgroups,
quotients and direct products of nilpotent groups are nilpotent [Druţu and
Kapovich (2018), Lemma 13.56, Theorem 13.57].

### The unitriangular matrix groups $\mathsf{UT}(n,\mathbb{Q})$

One of the most important examples of nilpotent groups is the group of
unitriangular matrices:

######  Definition 4.5 (Unitriangular matrix groups).

Denote by $\mathsf{UT}(n,\mathbb{Q})$ the group of $n\times n$ upper
triangular rational matrices with ones on the diagonal:

$\mathsf{UT}(n,\mathbb{Q})\coloneqq\left\\{\begin{pmatrix}1&*&\cdots&*&*\\\
0&1&\cdots&*&*\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&1&*\\\
0&0&\cdots&0&1\\\ \end{pmatrix},\text{ where $*$ are entries in $\mathbb{Q}$
}\right\\}.$

Then $\mathsf{UT}(n,\mathbb{Q})$ is a nilpotent group of class $n-1$ [Druţu
and Kapovich (2018), Examples 13.36]. Similarly, one can define the groups
$\mathsf{UT}(n,\mathbb{Z})$ by changing the entries from rationals to
integers.

The group $\mathsf{UT}(n,\mathbb{Z})$ (and hence $\mathsf{UT}(n,\mathbb{Q})$)
play an important role in the study of finitely generated nilpotent groups by
the following fact.

######  Theorem 4.6 ([Grunewald and Segal (1980)]).

Every finitely generated nilpotent group is isomorphic to a finite extension
of a subgroup of $\mathsf{UT}(n,\mathbb{Z})$ for some $n\in\mathbb{N}$.

We have already encountered the group
$\operatorname{H}_{3}(\mathbb{Z})=\mathsf{UT}(3,\mathbb{Z})$ in Subsection
3.2. Therefore the results in this subsection can be seen as generalizations
of Theorem 3.7.

######  Theorem 4.7.

In subgroups of $\mathsf{UT}(n,\mathbb{Q})$, we have the following results.

  1. (i)

[Mal’cev (1953)] Group Membership is decidable in
$\mathsf{UT}(n,\mathbb{Q}),n\in\mathbb{N}$.

  2. (ii)

[Roman’kov (2022)] There exists a large enough $k\in\mathbb{N}$, such that
Semigroup Membership is undecidable in the direct product
$\mathsf{UT}(3,\mathbb{Z})^{k}$.

  3. (iii)

[Dong (2023d)] Let $G$ be a class-2 nilpotent subgroup of
$\mathsf{UT}(n,\mathbb{Q})$ for some $n$. Then Semigroup Intersection is PTIME
decidable in $G$.

  4. (iv)

[Dong (2022)] Fix $d\leq 10$. Let $G$ be a class-$d$ nilpotent subgroup of
$\mathsf{UT}(n,\mathbb{Q})$ for some $n$. Then the Identity Problem and the
Group Problem are PTIME decidable in $G$.

For example, for any $k\in\mathbb{N}$, the direct product
$\mathsf{UT}(3,\mathbb{Z})^{k}$ is a class-two nilpotent subgroups of
$\mathsf{UT}(3k,\mathbb{Q})$. Therefore Theorem 4.9(iii) shows that
$\mathsf{UT}(3,\mathbb{Z})^{k}$ admits decidable (PTIME) Semigroup
Intersection. However, for large enough $k$, it admits undecidable Semigroup
Membership (Theorem 4.7(ii)).

It is worth pointing out that Theorem 4.7(i) follows from a more general
result of Mal’cev on finitely generated nilpotent groups222While
$\mathsf{UT}(n,\mathbb{Q})$ is not finitely generated, for Group Membership we
are always working in finitely generated subgroups of
$\mathsf{UT}(n,\mathbb{Q})$. (see Theorem 4.9(i)). Theorem 4.7(ii) is proven
through an embedding of the _Hilbert’s tenth problem_ , whose undecidability
follows from a celebrated result of Matiyasevich:

######  Theorem 4.8 (Hilbert’s tenth problem [Matiyasevich (1970)]).

The following problem is undecidable: given as input a polynomial
$f\in\mathbb{Z}[X_{1},\ldots,X_{n}]$, decide whether there exist integers
$z_{1},\ldots,z_{n}$ such that $f(z_{1},\ldots,z_{n})=0$.

On the other hand, Theorem 4.7(iii) and (iv) are proven using techniques from
Lie algebra and convex geometry. In fact, [Dong (2022)] proposed a conjecture
(depending on the nilpotency class $d$), subject to which Theorem 4.7(iv)
still holds for $d>10$. The conjecture is only verified up to $d=10$ using
computer algebra software.

### Arbitrary nilpotent groups

The close connection between $\mathsf{UT}(n,\mathbb{Q})$ and nilpotent groups
allows one to generalize the decidability results in Theorem 4.7 to arbitrary
finitely generated nilpotent groups.

######  Theorem 4.9.

In finitely generated nilpotent groups333As a convention in computational
group theory, a finitely generated nilpotent group is usually represented by
its _finite presentation_ , meaning it is written as a quotient
$F(\Sigma)/\langle\langle v_{1},\ldots,v_{n}\rangle\rangle$ for some alphabet
$\Sigma$ and elements $v_{1},\ldots,v_{n}\in\left(\Sigma^{\pm}\right)^{*}$,
similar to the setup of the Word Problem. Every finitely generated nilpotent
group admits a finite presentation [Druţu and Kapovich (2018), Proposition
13.84]., we have the following results.

  1. (i)

[Mal’cev (1953)] Group Membership is decidable in all finitely generated
nilpotent groups.

  2. (ii)

[Roman’kov (2022)] There exists a class-2 nilpotent group where Semigroup
Membership is undecidable.

  3. (iii)

[Dong (2023d)] Semigroup Intersection is decidable in all finitely generated
class-2 nilpotent groups.

  4. (iv)

[Dong (2022)] For $d\leq 10$, the Identity Problem and the Group Problem are
decidable in all finitely generated class-$d$ nilpotent groups.

The decidability of the Identity Problem, the Group Problem and Semigroup
Intersection in nilpotent groups of higher nilpotency classes remains open.

######  Remark 4.10.

By the generalized Tits alternative [Okniński and Salwa (1995)], a
subsemigroup of $\mathsf{GL}(n,\mathbb{K})$ either contains a finite-index
nilpotent subsemigroup444A semigroup is called nilpotent if the group it
generates is nilpotent. or it contains a subsemigroup isomorphic to the set of
non-empty words $\\{a,b\\}^{*}\setminus\\{\epsilon\\}$. Similar to Remark
3.12, Semigroup Intersection in the direct product
$\big{(}\\{a,b\\}^{*}\setminus\\{\epsilon\\}\big{)}\times\big{(}\\{a,b\\}^{*}\setminus\\{\epsilon\\}\big{)}$
is undecidable due to the Post Correspondence Problem. Therefore, nilpotent
groups are the largest “natural” class of matrix groups (i.e. a class that is
closed under direct products) where decidability of Semigroup Intersection
remains possible.

###  4.2 Metabelian groups

The class of metabelian groups is another generalization of abelian groups.

######  Definition 4.11 (Metabelian groups).

A group $G$ is called _metabelian_ if it is solvable of derived length at most
two. Equivalently, $G$ is metabelian if and only if it contains an abelian
normal subgroup $A$ such that the quotient $G/A$ is also abelian.

All subgroups, quotients and direct products of metabelian groups are
metabelian [Druţu and Kapovich (2018), Proposition 13.91].

######  Example 4.12.

Let $\mathsf{T}(2,\mathbb{K})$ denote the group of $2\times 2$ invertible
upper-triangular matrices over any non-trivial field $\mathbb{K}$:

$\mathsf{T}(2,\mathbb{K})\coloneqq\left\\{\begin{pmatrix}x&z\\\ 0&y\\\
\end{pmatrix}\;\middle|\;x,y\in\mathbb{K}\setminus\\{0\\},z\in\mathbb{K}\right\\}.$

Then $\mathsf{T}(2,\mathbb{K})$ is metabelian but not nilpotent.

### Example: the wreath product $\mathbb{Z}\wr\mathbb{Z}$

An important example of metabelian groups is the _wreath product_
$\mathbb{Z}\wr\mathbb{Z}$. The wreath product is a fundamental construction in
group and semigroup theory, and it also plays an important role in the
algebraic theory of automata. The Krohn–Rhodes theorem [Krohn and Rhodes
(1965)] states that every finite semigroup (and correspondingly, every finite
automaton) can be decomposed into elementary components using wreath products.

Following the work of [Magnus (1939)], it became clear that solving
algorithmic problems in arbitrary metabelian groups usually boils down to
solving them in wreath products of abelian groups [Baumslag (1973), Baumslag
et al. (1994)]. Therefore, studying the group $\mathbb{Z}\wr\mathbb{Z}$ is
usually the first step towards understanding general metabelian groups.

The wreath product $\mathbb{Z}\wr\mathbb{Z}$ is most easily defined as a
matrix group over the Laurent polynomial ring $\mathbb{Z}[X,X^{-1}]$:

$\displaystyle\mathbb{Z}\wr\mathbb{Z}=\left\\{\begin{pmatrix}X^{b}&y\\\
0&1\end{pmatrix}\;\middle|\;y\in\mathbb{Z}[X,X^{-1}],b\in\mathbb{Z}\right\\}.$
(3)

To see that $\mathbb{Z}\wr\mathbb{Z}$ is indeed metabelian, take its abelian
normal subgroup

$A\coloneqq\left\\{\begin{pmatrix}1&y\\\
0&1\end{pmatrix}\;\middle|\;y\in\mathbb{Z}[X,X^{-1}]\right\\}\cong\mathbb{Z}[X,X^{-1}],$

then the quotient $(\mathbb{Z}\wr\mathbb{Z})/A\cong\mathbb{Z}$ is also
abelian.

The group $\mathbb{Z}\wr\mathbb{Z}$ admits an interesting interpretation as an
infinite-state machine. Each element of $\mathbb{Z}\wr\mathbb{Z}$ can be seen
as a configuration of a “Turing machine”. The machine is composed of a bi-
infinite band with cells indexed by $\mathbb{Z}$, along with a _head_
positioned at one of its cells. Each cell contains an integer. The element
$\begin{pmatrix}X^{b}&\sum_{i=p}^{q}a_{i}X^{i}\\\ 0&1\end{pmatrix}$
corresponds to a configuration where the cells contain the integers
$\cdots,0,a_{p},a_{p+1},\ldots,a_{q},0,\cdots$, with $a_{i}$ being on the
$i$-th cell. The head of the machine is placed on the $b$-th cell. See Figure
4 for an illustration.

$\begin{pmatrix}X^{b}&\cdots+a_{-1}X^{-1}+a_{0}+a_{1}X+\cdots\\\
0&1\end{pmatrix}\quad\Longleftrightarrow$$a_{0}$$a_{-1}$$a_{-2}$$\cdots$$a_{1}$$a_{2}$$\cdots$
Figure 4: Intepretation of an element in $\mathbb{Z}\wr\mathbb{Z}$ as a
“Turing machine”. The upward arrow $\uparrow$ marks the $0$-th cell, and the
downward arrow $\downarrow$ marks the position of the head. In this example,
$\downarrow$ marks the cell at position 2, meaning $b=2$.
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}2}$$\begin{pmatrix}X^{1}&1+2X+2X^{2}\\\
0&1\end{pmatrix}\quad\;\;\times$$\times$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}$$\quad\;\;\begin{pmatrix}X^{2}&3+3X+3X^{2}\\\
0&1\end{pmatrix}\;\;=\;$$=$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}$${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}5}$${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}5}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}3}$$\begin{pmatrix}X^{3}&1+5X+5X^{2}+3X^{3}\\\
0&1\end{pmatrix}$ Figure 5: Example of multiplying two elements in
$\mathbb{Z}\wr\mathbb{Z}$ using the matrix representation and using the
machine representation.

Multiplication in $\mathbb{Z}\wr\mathbb{Z}$ also admits a simple
interpretation using this machine representation. To multiple two elements
under the machine representation, it suffices to align the $\downarrow$ arrow
of first element and the $\uparrow$ arrow of second element, then add up the
integers in corresponding cells. For the arrows, we keep the position of
$\uparrow$ in the first element and the position of $\downarrow$ in the second
element. See Figure 5 for an illustration.

Using the machine representation, every element in $\mathbb{Z}\wr\mathbb{Z}$
can be seen as an instruction on the machine by its effect of right-
multiplication. For example, the element $\begin{pmatrix}X&0\\\
0&1\end{pmatrix}$ or $0$$0$ corresponds to the instruction “move the head one
cell to the right”, which is the effect of (right)-multiplying $0$$0$ to a
configuration. Similarly, the element $\begin{pmatrix}1&1\\\ 0&1\end{pmatrix}$
or $1$ corresponds to the instruction “in the cell marked by the head,
increase the number by one”. Hence, Semigroup Membership in
$\mathbb{Z}\wr\mathbb{Z}$ can be reformulated as the problem: given a
configuration $T$ and a set of instructions $\mathcal{G}$, can one reach $T$
using a sequence of instructions from $\mathcal{G}$? Similarly, the Identity
Problem can be reformulated as: given a set of instructions $\mathcal{G}$, can
one reach the initial configuration using a (non-empty) sequence of
instructions from $\mathcal{G}$? For $\mathbb{Z}\wr\mathbb{Z}$, we have the
following results.

######  Theorem 4.13.

In the group $\mathbb{Z}\wr\mathbb{Z}$:

  1. (i)

[Lohrey et al. (2015)] Semigroup Membership is undecidable.

  2. (ii)

[Romanovskii (1974)] Group Membership in decidable.

  3. (iii)

[Dong (2023a)] The Identity Problem and the Group Problem are decidable.

Given the machine-like structure of $\mathbb{Z}\wr\mathbb{Z}$, the
undecidability result in Theorem 4.13(i) may not come as a surprise. Indeed,
[Lohrey et al. (2015)] showed that Semigroup Membership in
$\mathbb{Z}\wr\mathbb{Z}$ can simulate the halting problem in _2-counter
machines_ (also known as _Minsky machines_), which is equivalent to the
halting problem in arbitrary Turing machines [Minsky (1967)]. As for Theorem
4.13(ii), it follows from a more general result of Romanovskii on metabelian
groups (see Theorem 4.15(ii)). The most unexpected result seems to be the
decidability of the Identity Problem in Theorem 4.13(iii). This shows that by
restricting the target to the neutral element in Semigroup Membership, the
problem becomes much more tractable (the same phenomenon can be observed in
Theorem 4.9). The proof of Theorem 4.13(iii) uses a combination of graph
theory techniques and deep tools from algebraic geometry.

###### Remark 4.14

The decidability of Semigroup Intersection in $\mathbb{Z}\wr\mathbb{Z}$
remains an open problem at the moment. It can be shown that
$\mathbb{Z}\wr\mathbb{Z}$ does not contain $\\{a,b\\}^{*}\times\\{a,b\\}^{*}$
as a subsemigroup. This excludes the possibility of proving undecidability by
directly embedding the Post Correspondence Problem. However,
$\mathbb{Z}\wr\mathbb{Z}$ contains $\\{a,b\\}^{*}$ as a subsemigroup [Baumslag
and Roitberg (1982)]. Therefore as in Remark 3.12, Semigroup Intersection is
undecidable in the direct product
$(\mathbb{Z}\wr\mathbb{Z})\times(\mathbb{Z}\wr\mathbb{Z})$.

### Arbitrary metabelian groups and beyond

We now consider arbitrary finitely generated metabelian groups.

######  Theorem 4.15.

In finitely generated metabelian groups555As a convention in computational
group theory, a finitely generated metabelian group is usually represented by
a _finite $\mathscr{A}^{2}$-presentation_. Let $\Sigma$ be an alphabet and
$F(\Sigma)$ be the free group over $\Sigma$. The quotient $M(\Sigma)\coloneqq
F(\Sigma)/[[F(\Sigma),F(\Sigma)],[F(\Sigma),F(\Sigma)]]$ is metabelian, and is
called the _free metabelian group_ over $\Sigma$. A finite
$\mathscr{A}^{2}$-presentation of a metabelian group $G$ is the writing of $G$
as a quotient $M(\Sigma)/\langle\langle v_{1},\ldots,v_{n}\rangle\rangle$ for
some alphabet $\Sigma$ as well as elements $v_{1},\ldots,v_{n}\in M(\Sigma)$.
Here, $\langle\langle v_{1},\ldots,v_{n}\rangle\rangle$ denotes the normal
subgroup of $M(\Sigma)$ generated by $v_{1},\ldots,v_{n}$. Every finitely
generated metabelian group admits a finite $\mathscr{A}^{2}$-presentation
[Hall (1954), Corollary 1] [Baumslag et al. (1994), p.629]., we have the
following results.

  1. (i)

[Lohrey et al. (2015)] There exists a finitely generated metabelian group,
namely $\mathbb{Z}\wr\mathbb{Z}$, where Semigroup Membership is undecidable.

  2. (ii)

[Romanovskii (1974)] Group Membership is decidable in all finitely generated
metabelian groups.

  3. (iii)

[Dong (2023c)] The Identity Problem and the Group Problem are decidable in all
finitely generated metabelian groups.

  4. (iv)

(See Remark 4.14) There exists a finitely generated metabelian group, namely
$(\mathbb{Z}\wr\mathbb{Z})\times(\mathbb{Z}\wr\mathbb{Z})$, where Semigroup
Intersection is undecidable.

In particular, Theorem 4.15(iii) generalizes Theorem 4.13(iii), while Theorem
4.13(ii) is in fact a corollary of Theorem 4.15(ii).

Beyond nilpotent groups and metabelian groups, it would be interesting to
consider algorithmic problems in larger classes of solvable groups. A natural
candidate is the class of _polycyclic groups_ [Druţu and Kapovich (2018),
Chapter 13, p.463], which generalizes finitely generated nilpotent groups. By
a classic result of [Kopytov (1968)], polycyclic groups admit decidable Group
Membership. However, they are not yet well-studied in the context of semigroup
algorithmic problems. Another interesting class to consider is the so-called
_center-by-metabelian groups_ [Groves (1978)], which are a relatively
tractable subclass of solvable groups of derived length three.

##  5 Other algorithmic problems for groups and semigroups

To end this survey we mention some other interesting algorithmic problems in
infinite groups and matrix groups. These problems are less directly related to
semigroup theory, but have nevertheless tight connections with many other
areas in the theory of computing. Let $G$ be a group. The following list is
non-exhaustive.

  1. (i)

(Knapsack Problem [Myasnikov et al. (2015), König et al. (2016)]) Given as
input the elements $A_{1},\ldots,A_{K},T\in G$, decide whether there exist
$n_{1},\ldots,n_{K}\in\mathbb{N}$ such that $A_{1}^{n_{1}}\cdots
A_{K}^{n_{K}}=T$.

  2. (ii)

(Freeness Problem [Cassaigne et al. (1999), Cassaigne and Nicolas (2012)])
Given as input the elements $A_{1},\ldots,A_{K}\in G$, decide whether there
exist two different sequences $(i_{1},\ldots,i_{p})$ and
$(j_{1},\ldots,j_{q})$ such that $A_{i_{1}}\cdots A_{i_{p}}=A_{j_{1}}\cdots
A_{j_{q}}$.

  3. (iii)

(Subgroup Intersection [Howson (1954), Baumslag et al. (2010)]) Given two
finite sets $\mathcal{G},\mathcal{H}\subseteq G$, decide whether
$\langle\mathcal{G}\rangle_{grp}\cap\langle\mathcal{H}\rangle_{grp}$ is the
trivial group.

  4. (iv)

(Coset Intersection [Babai (2010), Macdonald et al. (2019)]) Given two finite
sets $\mathcal{G},\mathcal{H}\subseteq G$, as well as elements $g,h\in G$,
decide whether $g\cdot\langle\mathcal{G}\rangle_{grp}\cap
h\cdot\langle\mathcal{H}\rangle_{grp}$ is empty.

  5. (v)

(Vector Reachability [Bell and Potapov (2008), Potapov and Semukhin (2019)])
Given $K$ square matrices $A_{1},\ldots,A_{K}$ of dimension $d$, as well as
two vectors $v,w$ of dimension $d$, decide whether there exists $T\in\langle
A_{1},\ldots,A_{K}\rangle$ such that $Tv=w$. In particular, if one only
considers invertible matrices, then Vector Reachability can be reformulated as
a generalization of Coset Intersection. Let $T_{0}$ be an arbitrary matrix
such that $T_{0}v=w$, and denote by $H$ the matrix group $\\{A\mid Aw=w\\}$.
Then Vector Reachability is equivalent to deciding whether the semigroup
$\langle A_{1},\ldots,A_{K}\rangle$ has non-empty intersection with the coset
$H\cdot T_{0}$.

  6. (vi)

(Skolem Problem [Skolem (1933), Ouaknine and Worrell (2015)]) Given a square
matrix $A$ of dimension $d$, as well as two vectors $v,w$ of dimension $d$,
decide whether there exists $n\in\mathbb{N}$ such that $v^{\top}A^{n}w=0$.

  7. (vii)

(Positivity Problem [Soittola (1975), Ouaknine and Worrell (2014)]) Given a
square matrix $A$ of dimension $d$, as well as two vectors $v,w$ of dimension
$d$, decide whether there exists $n\in\mathbb{N}$ such that
$v^{\top}A^{n}w\geq 0$.

## References

  * [1]
  * Adyan (1955) Sergei I. Adyan. 1955.  Algorithmic unsolvability of problems of recognition of certain properties of groups. In Dokl. Akad. Nauk SSSR (N.S.), Vol. 103. 533–535.
  * Babai (2010) László Babai. 2010.  Coset intersection in moderately exponential time.  Chicago J. Theoret. Comp. Sci 88 (2010), 122–123.
  * Babai et al. (1996) László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. 1996.  Multiplicative equations over commuting matrices. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. 498–507.
  * Baker (1905) Henry Frederick Baker. 1905.  Alternants and continuous groups.  Proceedings of the London Mathematical Society 2, 1 (1905), 24–47.
  * Baumslag (1973) Gilbert Baumslag. 1973.  Subgroups of finitely presented metabelian groups.  Journal of the Australian Mathematical Society 16, 1 (1973), 98–110.
  * Baumslag et al. (1994) Gilbert Baumslag, Frank B. Cannonito, and Derek J.S. Robinson. 1994.  The algorithmic theory of finitely generated metabelian groups.  Trans. Amer. Math. Soc. 344, 2 (1994), 629–648.
  * Baumslag et al. (2010) Gilbert Baumslag, Charles F. Miller III, and Gretchen Ostheimer. 2010.  Subgroups of free metabelian groups.  Groups, Geometry, and Dynamics 4, 4 (2010), 657–679.
  * Baumslag and Roitberg (1982) G. Baumslag and Y. Roitberg. 1982.  Groups with free 2-generator subsemigroups. In Semigroup forum, Vol. 25. Springer, 135–143.
  * Beals and Babai (1993) Robert Beals and László Babai. 1993.  Las Vegas algorithms for matrix groups. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science. IEEE, 427–436.
  * Bell and Potapov (2008) Paul Bell and Igor Potapov. 2008.  Reachability problems in quaternion matrix and rotation semigroups.  Information and Computation 206, 11 (2008), 1353–1361.
  * Bell et al. (2017) Paul C. Bell, Mika Hirvensalo, and Igor Potapov. 2017.  The Identity Problem for Matrix Semigroups in $\operatorname{SL}_{2}(\mathbb{Z})$ is NP-complete. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 187–206.
  * Bell et al. (2023) Paul C. Bell, Mika Hirvensalo, and Igor Potapov. 2023.  Private Communication. (2023).
  * Bell and Potapov (2010) Paul C. Bell and Igor Potapov. 2010.  On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups.  International Journal of Foundations of Computer Science 21, 06 (2010), 963–978.
  * Benois (1969) Michèle Benois. 1969.  Parties rationnelles du groupe libre.  CR Acad. Sci. Paris, Sér. A 269 (1969), 1188–1190.
  * Blondel et al. (2005) Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, and Natacha Portier. 2005.  Decidable and undecidable problems about quantum automata.  SIAM J. Comput. 34, 6 (2005), 1464–1473.
  * Bruinier et al. (2008) Jan Hendrik Bruinier, Gerard van der Geer, Günter Harder, and Don Zagier. 2008.  Elliptic modular forms and their applications.  The 1-2-3 of modular forms: Lectures at a summer school in Nordfjordeid, Norway (2008), 1–103.
  * Cabrer and Mundici (2017) Leonardo Manuel Cabrer and Daniele Mundici. 2017.  Classifying orbits of the affine group over the integers.  Ergodic Theory and Dynamical Systems 37, 2 (2017), 440–453.
  * Cadilhac et al. (2020) Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche. 2020.  Rational Subsets of Baumslag-Solitar Groups. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 (LIPIcs), Vol. 168. 116:1–116:16.
  * Campbell (1897) John Edward Campbell. 1897.  On a law of combination of operators (second paper).  Proceedings of the London Mathematical Society 1, 1 (1897), 14–32.
  * Cassaigne et al. (1999) Julien Cassaigne, Tero Harju, and Juhani Karhumäki. 1999.  On the undecidability of freeness of matrix semigroups.  International Journal of Algebra and Computation 9, 03n04 (1999), 295–305.
  * Cassaigne and Nicolas (2012) Julien Cassaigne and François Nicolas. 2012.  On the decidability of semigroup freeness.  RAIRO-Theoretical Informatics and Applications 46, 3 (2012), 355–399.
  * Chistikov and Haase (2016) Dmitry Chistikov and Christoph Haase. 2016.  The taming of the semi-linear set. In International Colloquium on Automata, Languages, and Programming, Vol. 55. Schloss Dagstuhl.
  * Choffrut and Karhumäki (2005) Christian Choffrut and Juhani Karhumäki. 2005.  Some decision problems on integer matrices.  RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications 39, 1 (2005), 125–131.
  * Colcombet et al. (2019) Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, and James Worrell. 2019.  On Reachability Problems for Low-Dimensional Matrix Semigroups. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (LIPIcs), Vol. 132. 44:1–44:15.
  * Delgado Rodríguez (2017) Jordi Delgado Rodríguez. 2017.  Extensions of free groups: algebraic, geometric, and algorithmic aspects.  Ph.D. Dissertation. Universitat Politècnica de Catalunya.
  * Derksen et al. (2005) Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. 2005.  Quantum automata and algebraic groups.  Journal of Symbolic Computation 39, 3-4 (2005), 357–371.
  * Diekert et al. (2020) Volker Diekert, Igor Potapov, and Pavel Semukhin. 2020.  Decidability of membership problems for flat rational subsets of GL(2, Q) and singular matrices. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation. 122–129.
  * Dong (2022) Ruiwen Dong. 2022.  The Identity Problem in nilpotent groups of bounded class.  arXiv preprint arXiv:2208.02164 (2022).
  * Dong (2023a) Ruiwen Dong. 2023a.  The Identity Problem in $\mathbb{Z}\wr\mathbb{Z}$ Is Decidable. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 (LIPIcs), Vol. 261. 124:1–124:20.
  * Dong (2023b) Ruiwen Dong. 2023b.  The Identity Problem in the special affine group of $\mathbb{Z}^{2}$. In 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 1–13.
  * Dong (2023c) Ruiwen Dong. 2023c.  Semigroup algorithmic problems in metabelian groups.  arXiv preprint arXiv:2304.12893 (2023).
  * Dong (2023d) Ruiwen Dong. 2023d.  Semigroup Intersection Problems in the Heisenberg Groups. In 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023 (LIPIcs), Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 25:1–25:18.
  * Druţu and Kapovich (2018) Cornelia Druţu and Michael Kapovich. 2018.  Geometric group theory. Vol. 63.  American Mathematical Soc.
  * Giefer et al. (2020) Lino Antoni Giefer, Joachim Clemens, and Kerstin Schill. 2020.  Extended object tracking on the affine group Aff(2). In 2020 IEEE 23rd International Conference on Information Fusion (FUSION). IEEE, 1–8.
  * Groves (1978) John Richard James Groves. 1978.  Finitely presented centre-by-metabelian groups.  Journal of the London Mathematical Society 2, 1 (1978), 65–69.
  * Grunewald and Segal (1980) Fritz Grunewald and Daniel Segal. 1980.  Some general algorithms. II: Nilpotent groups.  Annals of Mathematics 112, 3 (1980), 585–617.
  * Hall (1954) P. Hall. 1954.  Finiteness Conditions for Soluble Groups.  Proceedings of the London Mathematical Society s3-4, 1 (01 1954), 419–436.
  * Hausdorff (1906) Felix Hausdorff. 1906.  Die symbolische Exponentialformel in der Gruppentheorie.  Berichte über die Verhandlungen der Königlich-Sächsischen Gesellschaft der Wissenschaften zu Leipzig, Mathematisch-Physische Klasse 58 (1906), 19–48.
  * Howe (1980) Roger Howe. 1980.  On the role of the Heisenberg group in harmonic analysis.  Bulletin (New Series) of the American Mathematical Society 3, 2 (1980), 821–843.
  * Howson (1954) A. G. Howson. 1954.  On the Intersection of Finitely Generated Free Groups.  Journal of the London Mathematical Society s1-29, 4 (10 1954), 428–434.
  * Hrushovski et al. (2018) Ehud Hrushovski, Joël Ouaknine, Amaury Pouly, and James Worrell. 2018\.  Polynomial invariants for affine programs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. 530–539.
  * Kapovich and Myasnikov (2002) Ilya Kapovich and Alexei Myasnikov. 2002.  Stallings Foldings and Subgroups of Free Groups.  Journal of Algebra 248, 2 (2002), 608–668.
  * Kapovich et al. (2005) Ilya Kapovich, Richard Weidmann, and Alexei Myasnikov. 2005.  Foldings, graphs of groups and the membership problem.  International Journal of Algebra and Computation 15, 01 (2005), 95–128.
  * Kharlampovich (1981) Ol’ga Georgievna Kharlampovich. 1981.  A finitely presented solvable group with unsolvable word problem.  Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya 45, 4 (1981), 852–873.
  * Kirillov (2004) Aleksandr Aleksandrovich Kirillov. 2004.  Lectures on the orbit method. Vol. 64.  American Mathematical Soc.
  * Ko et al. (2018) Sang-Ki Ko, Reino Niskanen, and Igor Potapov. 2018.  On the identity problem for the Special Linear Group and the Heisenberg Group. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 (LIPIcs), Vol. 107. 132:1–132:15.
  * König et al. (2016) Daniel König, Markus Lohrey, and Georg Zetzsche. 2016.  Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups.  Algebra and Computer Science 677 (2016), 138–153.
  * Kopytov (1968) V. M. Kopytov. 1968.  Solvability of the problem of occurrence in finitely generated soluble groups of matrices over the field of algebraic numbers.  Algebra and Logic 7, 6 (1968), 388–393.
  * Krohn and Rhodes (1965) Kenneth Krohn and John Rhodes. 1965.  Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines.  Trans. Amer. Math. Soc. 116 (1965), 450–464.
  * Krovi and Rötteler (2008) Hari Krovi and Martin Rötteler. 2008.  An efficient quantum algorithm for the hidden subgroup problem over Weyl-Heisenberg groups.  In Mathematical Methods in Computer Science. Springer, 70–88.
  * Lohrey (2013) Markus Lohrey. 2013.  The rational subset membership problem for groups: a survey. In Groups St Andrews, Vol. 422. Cambridge University Press, 368–389.
  * Lohrey (2023) Markus Lohrey. 2023.  Subgroup membership in GL(2,Z).  Theory of Computing Systems (2023), 1–26.
  * Lohrey et al. (2015) Markus Lohrey, Benjamin Steinberg, and Georg Zetzsche. 2015.  Rational subsets and submonoids of wreath products.  Information and Computation 243 (2015), 191–204.
  * Macdonald et al. (2019) Jeremy Macdonald, Alexei Miasnikov, and Denis Ovchinnikov. 2019.  Low-complexity computations for nilpotent subgroup problems.  International Journal of Algebra and Computation 29, 04 (2019), 639–661.
  * Magnus (1939) Wilhelm Magnus. 1939.  On a theorem for Marshall Hall.  Annals of Mathematics (1939), 764–768.
  * Mal’cev (1953) A. I. Mal’cev. 1953.  Nilpotent semigroups. In Ivanov. Gos Ped. Inst. Ucen Zap. Fiz.-Mat. Nauki, Vol. 4. 107–111.
  * Markov (1947) A. Markov. 1947.  On certain insoluble problems concerning matrices.  Doklady Akad. Nauk SSSR 57, 6 (1947), 539–542.
  * Matiyasevich (1970) Yuri Vladimirovich Matiyasevich. 1970.  The Diophantineness of enumerable sets.  Doklady Akademii Nauk SSSR 191, 2 (1970), 279–282.
  * Mikhailova (1966) K. A. Mikhailova. 1966.  The occurrence problem for direct products of groups.  Matematicheskii Sbornik 112, 2 (1966), 241–251.
  * Minsky (1967) Marvin Lee Minsky. 1967.  Computation: Finite and Infinite Machines.  Prentice-Hall Englewood Cliffs.
  * Mundici (2014) Daniele Mundici. 2014.  Invariant Measure Under the Affine Group Over $\mathbb{Z}$.  Combinatorics, Probability and Computing 23, 2 (2014), 248–268.
  * Myasnikov et al. (2015) Alexei Myasnikov, Andrey Nikolaev, and Alexander Ushakov. 2015.  Knapsack problems in groups.  Math. Comp. 84, 292 (2015), 987–1016.
  * Neumann (1931) J. von Neumann. 1931.  Die Eindeutigkeit der Schrödingerschen Operatoren.  Math. Ann. 104 (1931), 570–578.
  * Newman (1962) Morris Newman. 1962.  The structure of some subgroups of the modular group.  Illinois Journal of Mathematics 6, 3 (1962), 480–487.
  * Novikov (1955) Petr Sergeevich Novikov. 1955.  On the algorithmic unsolvability of the word problem in group theory.  Trudy Matematicheskogo Instituta imeni VA Steklova 44 (1955), 3–143.
  * Okniński and Salwa (1995) J. Okniński and A. Salwa. 1995.  Generalised Tits alternative for linear semigroups.  Journal of Pure and Applied Algebra 103, 2 (1995), 211–220.
  * Ouaknine and Worrell (2014) Joël Ouaknine and James Worrell. 2014.  Positivity problems for low-order linear recurrence sequences. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 366–379.
  * Ouaknine and Worrell (2015) Joël Ouaknine and James Worrell. 2015.  On linear recurrence sequences and loop termination.  ACM Siglog News 2, 2 (2015), 4–13.
  * Paterson (1970) Michael S. Paterson. 1970.  Unsolvability in 3 $\times$ 3 matrices.  Studies in Applied Mathematics 49, 1 (1970), 105–107.
  * Polterovich and Rudnick (2004) Leonid Polterovich and Zeev Rudnick. 2004.  Stable mixing for cat maps and quasi-morphisms of the modular group.  Ergodic Theory and Dynamical Systems 24, 2 (2004), 609–619.
  * Post (1946) Emil L. Post. 1946.  A variant of a recursively unsolvable problem.  Bull. Amer. Math. Soc. 52, 4 (1946), 264 – 268.
  * Potapov and Semukhin (2017a) Igor Potapov and Pavel Semukhin. 2017a.  Decidability of the membership problem for 2 $\times$ 2 integer matrices. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 170–186.
  * Potapov and Semukhin (2017b) Igor Potapov and Pavel Semukhin. 2017b.  Membership Problem in GL(2, Z) Extended by Singular Matrices. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (LIPIcs), Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 44:1–44:13.
  * Potapov and Semukhin (2019) Igor Potapov and Pavel Semukhin. 2019.  Vector and scalar reachability problems in $\operatorname{SL}_{2}(\mathbb{Z})$.  J. Comput. System Sci. 100 (2019), 30–43.
  * Raskin et al. (2021) Mikhail Raskin, Filip Mazowiecki, Christoph Haase, and Michael Blondin. 2021.  Affine extensions of integer vector addition systems with states.  Logical Methods in Computer Science 17 (2021).
  * Roman’kov (2022) Vitaly Roman’kov. 2022.  Undecidability of the submonoid membership problem for a sufficiently large finite direct power of the Heisenberg group.  arXiv preprint arXiv:2209.14786 (2022).
  * Romanovskii (1974) N. S. Romanovskii. 1974.  Some algorithmic problems for solvable groups.  Algebra and Logic 13, 1 (1974), 13–16.
  * Rüping (2010) Henrik Rüping. 2010.  The free group ${F}_{2}$ has index 12 in $\operatorname{SL}(2,\mathbb{Z}$).  MathOverflow. (2010).  https://mathoverflow.net/q/43740 (version: 2010-10-27). Username: HenrikRüping.
  * Skolem (1933) T. Skolem. 1933.  Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf Diophantische Gleichungen.  Acad. Oslo, Mat. Naturv. Klasse 6 (1933).
  * Soittola (1975) Matti Soittola. 1975.  On DOL Synthesis Problem. In Automata, Languages, Development. 313–321.
  * Tits (1972) Jacques Tits. 1972.  Free subgroups in linear groups.  Journal of Algebra 20, 2 (1972), 250–270.
  * Weyl (1950) Hermann Weyl. 1950.  The theory of groups and quantum mechanics.  Courier Corporation.
  * Wolf (1963) Joseph A. Wolf. 1963.  The affine group of a Lie group. In Proc. Amer. Math. Soc., Vol. 14. 352–353.