# Linear equations and recursively enumerable sets

Juha Honkala
Department of Mathematics and Statistics
University of Turku
FI-20014 Turku, Finland
<EMAIL_ADDRESS>
###### Abstract

We study connections between linear equations over various semigroups and
recursively enumerable sets of positive integers. We give variants of the
universal Diophantine representation of recursively enumerable sets of
positive integers established by Matiyasevich. These variants use linear
equations with one unkwown instead of polynomial equations with several
unknowns. As a corollary we get undecidability results for linear equations
over morphism semigoups and over matrix semigroups.

Keywords: Recursively enumerable set, linear equation, free monoid morphism,
upper triangular matrix, Diophantine representation of recursively enumerable
sets

##  1 Introduction

In this paper we study connections between linear equations over semigroups
and recursively enumerable sets of positive integers. Matiyasevich has proved
that recursively enumerable sets of positive integers have a universal
Diophantine representation. To state this result more precisely, fix an
enumeration ${\mathcal{R}}_{1},{\mathcal{R}}_{2},{\mathcal{R}}_{3},\ldots$ of
the recursively enumerable sets of positive integers. Matiyasevich has shown
that there is a polynomial $p(x_{1},\ldots,x_{t})$ with integer coefficients
such that for all positive integers $s$ and $n$, we have

$s\in{\mathcal{R}}_{n}$

if and only if there exist positive integers $n_{3},\ldots,n_{t}$ such that

$p(n,s,n_{3},\ldots,n_{t})=0.$

For the proof and more information of this deep result see [6].

In this paper we study linear equations over various semigroups. Let $S$ be a
semigroup. We study equations of the form $ax=bx$ and equations of the form
$ax=by$. Here $a$ and $b$ are elements of $S$ and $x$ and $y$ are unknowns. If
$S$ has a zero, these equations have trivial solutions. In this paper we will
only consider nonannihilating solutions of these equations. By definition,
$c\in S$ is a nonannihilating solution of $ax=bx$ if $ac=bc\neq 0$.

We will prove two variants of the universal Diophantine representation of
recursively enumerable sets of positive integers. These variants use linear
equations with one unknown instead of polynomial equations with several
unknowns.

The first variant uses linear equations over a semigroup generated by two
upper triangular free monoid morphisms. The second variant uses linear
equations over a matrix semigroup generated by two upper triangular matrices
having nonnegative integer entries. The matrices in the second variant are the
matrices of the morphisms in the first variant.

More precisely, we will construct two upper triangular morphisms $g_{1}$ and
$g_{2}$ such that the monoid ${\mathcal{H}}$ generated by $g_{1}$ and $g_{2}$
has the following property:

> For all positive integers $s$ and $n$ we have
>
> $s\in{\mathcal{R}}_{n}$
>
> if and only if there is a morphism $h\in{\mathcal{H}}$ such that
>
> $f_{n,s}h=g_{n,s}h\neq o$

where $f_{n,s}=g_{2}^{2}g_{1}^{n}g_{2}g_{1}^{s}g_{2}$,
$g_{n,s}=g_{2}^{3}g_{1}^{n}g_{2}g_{1}^{s}g_{2}$ and $o$ is the morphism
erasing all letters.

As a corollary we see that there are two upper triangular matrices $M_{1}$ and
$M_{2}$ having nonnegative integer entries such that the multiplicative monoid
${\mathcal{M}}$ generated by $M_{1}$ and $M_{2}$ has the following property:

> For all positive integers $s$ and $n$ we have
>
> $s\in{\mathcal{R}}_{n}$
>
> if and only if there is a matrix $N\in{\mathcal{M}}$ such that
>
> $K_{n,s}N=M_{n,s}N\neq O$

where $K_{n,s}=M_{2}^{2}M_{1}^{n}M_{2}M_{1}^{s}M_{2}$ and
$M_{n,s}=M_{2}^{3}M_{1}^{n}M_{2}M_{1}^{s}M_{2}$.

These results imply undecidability results for linear equations over these
semigroups.

We now outline the contents of the paper. In Section 2 we recall basic
definitions and fix our notation. In Section 3 we show how the values of
polynomials can be computed by a pair of upper triangular free monoid
morphisms. In Section 4 we use the universal Diophantine representation of
recursively enumerable sets of positive integers to construct two upper
triangular morphisms $g_{1}$ and $g_{2}$. Then we use the monoid
${\mathcal{H}}$ generated by $g_{1}$ and $g_{2}$ to give our first variant of
the universal Diophantine representation of recursively enumerable sets of
positive integers. In Section 5 we construct two upper triangular matrices
$M_{1}$ and $M_{2}$ having nonnegative integer entries such that the
multiplicative monoid ${\mathcal{M}}$ generated by $M_{1}$ and $M_{2}$ can be
used to give our second variant.

We will assume that the reader is familiar with the basics of language theory
(see [1, 7, 8, 11]) and recursively enumerable sets (see [6, 9, 10, 12]).
These references should be consulted for all unexplained notation and
terminology. For various undecidability results concerning matrix semigroups
see e.g. [2, 3, 4, 5].

##  2 Definitions

As usual, ${\mathbb{N}}$, ${\mathbb{Z}}$ and ${\mathbb{Z}}_{+}$ are the sets
of nonnegative integers, all integers and positive integers, respectively. In
particular, $0\in{\mathbb{N}}$ but $0\not\in{\mathbb{Z}}_{+}$.

A semigroup $S$ is a set equipped with an associative binary operation,
usually called the product. The product of $a,b\in S$ is denoted by $ab$. If a
semigroup $S$ contains an element $1$ such that $s1=1s=s$ for all $s\in S$, we
say that $1$ is an identity element of $S$ and we say that $S$ is a monoid. A
semigroup $S$ has at most one identity element.

If a semigroup $S$ with at least two elements contains an element $0$ such
that $0s=s0=0$ for all $s\in S$, we say that $0$ is a zero element of $S$. A
semigroup $S$ has at most one zero.

If $m$ and $n$ are positive integers, ${\mathbb{N}}^{m\times n}$ is the set of
$m\times n$ matrices having nonnegative integer entries and
$\operatorname{Tri}(n,{\mathbb{N}})$ is the subset of ${\mathbb{N}}^{n\times
n}$ consisting of upper triangular matrices.
$\operatorname{Tri}(n,{\mathbb{N}})$ is a multiplicative monoid which has a
zero.

The free monoid generated by a finite nonempty set $Z$ is $Z^{*}$ consisting
of (finite) words over the alphabet $Z$. The identity element of $Z^{*}$ is
the empty word $\varepsilon$. The length of a word $w$ is denoted by $|w|$ and
the number of occurrences of a letter $x$ in a word $w$ is denoted by
$|w|_{x}$.

In what follows, we usually apply mappings on the right. If $f:A\to B$ is a
mapping from a set $A$ to a set $B$, the image of $a\in A$ under $f$ is
written $af$. If $f:A\to B$ and $g:B\to C$ are mappings, the product $fg$ of
$f$ and $g$ is the mapping from $A$ to $C$ defined by $a(fg)=(af)g$ for every
$a\in A$. In the literature concerning free monoid morphisms, it is more
common to apply mappings on the left, but the constructions given below are
more natural if we apply mappings on the right. However, when we have a
mapping $f:{\mathbb{N}}^{k}\to{\mathbb{N}}$ where $k>1$ is an integer, we will
write the image of $(n_{1},\ldots,n_{k})$ under $f$ as
$f(n_{1},\ldots,n_{k})$.

If $S$ and $T$ are monoids, a mapping $f:S\to T$ is a (monoid) morphism if
$(ab)f=(af)(bf)$ for all $a,b\in S$ and $1_{S}f=1_{T}$, where $1_{S}$ and
$1_{T}$ are the identity elements of $S$ and $T$, respectively. The set of all
morphisms from $S$ to $T$ is denoted by $\operatorname{Hom}(S,T)$. If $S=T$,
we will use the notation $\operatorname{Hom}(S)$.

Assume that $Z=\\{z_{1},\ldots,z_{k}\\}$ is an ordered alphabet with
$z_{1}<z_{2}<\cdots<z_{k}$. For $i=1,\ldots,k$, let ${\bf
e}_{i}=(0,\ldots,0,1,0,\ldots,0)$ be the vector whose only nonzero entry is a
$1$ in the $i$th position. Let $\psi:Z^{*}\to{\mathbb{N}}^{k}$ be the monoid
morphism mapping $z_{i}$ to ${\bf e}_{i}$ for $i=1,\ldots,k$. If $w\in Z^{*}$,
then $w\psi$ is often called the Parikh vector of $w$. The $i$th entry of
$w\psi$ equals the number of occurrences of the letter $z_{i}$ in $w$.

Assume $g\in\operatorname{Hom}(Z^{*})$. Then the matrix $M_{g}$ of $g$ is the
$k\times k$ matrix, whose rows are $z_{1}g\psi,\ldots,z_{k}g\psi$. If $w\in
Z^{*}$, we have $w\psi M_{g}=wg\psi$.

Define the mapping $\Psi:\operatorname{Hom}(Z^{*})\to{\mathbb{N}}^{k\times k}$
by $g\Psi=M_{g}$. It is well known that $\Psi$ is a monoid morphism.

The morphism $g$ is upper triangular if its matrix is upper triangular. The
subset of $\operatorname{Hom}(Z^{*})$ consisting of upper triangular morphisms
is denoted by $\operatorname{Tri}(Z^{*})$.

Let $X$ and $Y$ be alphabets which do not have a common letter and let
$Z=X\cup Y$. Let $f\in\operatorname{Hom}(X^{*})$ and
$g\in\operatorname{Hom}(Y^{*})$. The direct sum of $f$ and $g$ is the morphism
$f\oplus g\in\operatorname{Hom}(Z^{*})$ defined by

$z(f\oplus g)=\left\\{\begin{array}[]{rrr}zf&\mbox{ if }&z\in X\\\ zg&\mbox{
if }&z\in Y\end{array}\right..$

##  3 M-triples and how to use them to compute values of polynomials

In this section we define and study M-triples, which are a technical tool used
in later sections to compute values of polynomials.

Let $A$ be an ordered alphabet. A partition $(A_{1},\ldots,A_{s})$ of $A$ is
compatible with the order of $A$ if all letters of $A_{i}$ precede all letters
of $A_{i+1}$ in the order of $A$ for $i=1,\ldots,s-1$.

###### Definition 1

Let $t$ be a positive integer. Let $A$ be an ordered alphabet and let
$(A_{1},\ldots,A_{t+1})$ be a partition of $A$ compatible with the order of
$A$. Let $g_{1},g_{2}\in\operatorname{Tri}(A^{*})$. Then $(A,g_{1},g_{2})$ is
an M-triple of dimension $t$ if the following conditions hold:

  1. (i)

$A_{i}g_{1}\subseteq A_{i}^{*}$ for $i=1,\ldots,t+1$,

  2. (ii)

$A_{i}g_{2}\subseteq A_{i+1}^{*}$ for $i=1,\ldots,t$,

  3. (iii)

$ag_{2}^{2}=\varepsilon$ for every $a\in A$,

  4. (iv)

$A_{t+1}=\\{e\\}$, where $e$ is the last letter of $A$,

  5. (iv)

$eg_{1}=eg_{2}=\varepsilon$.

The partition $(A_{1},\ldots,A_{t+1})$ is called the underlying partition of
$(A,g_{1},g_{2})$ and $A_{i}$ is called the subalphabet of level $i$ of $A$
for $i=1,\ldots,{t+1}$.

The following definition defines mappings computable by an $M$-triple.

###### Definition 2

Let $t$ be a positive integer and let
$f:{\mathbb{Z}}_{+}^{t}\to{\mathbb{Z}}_{+}$ be a mapping. We say that $f$ is
computable by an M-triple $G=(A,g_{1},g_{2})$ of dimension $t$ if there is a
word $w\in A_{1}^{*}$ such that for all positive integers $n_{1},\ldots,n_{t}$
we have

$wg_{1}^{n_{1}}g_{2}g_{1}^{n_{2}}g_{2}\cdots
g_{1}^{n_{t}}g_{2}=e^{f(n_{1},\ldots,n_{t})},$ (1)

where $e$ is the last letter of $A$.

Assume that $f$ is computable by an M-triple $(A,g_{1},g_{2})$. Assume that
(1) holds for $w\in A_{1}^{*}$. Consider the word
$wg_{1}^{n_{1}}g_{2}g_{1}^{n_{2}}g_{2}\cdots g_{1}^{n_{t}}g_{2}$. By condition
(i) of Definition 1, $g_{1}$ maps each word over $A_{1}$ to a word over
$A_{1}$. Hence, the leftmost iteration of $g_{1}$ is done over the subalphabet
$A_{1}$. The word $wg_{1}^{n_{1}}$ belongs to $A_{1}^{*}$. The leftmost
application of $g_{2}$ maps this word to a word over $A_{2}$. The next
iteration of $g_{1}$ is done over the subalphabet $A_{2}$. Every new
application of $g_{2}$ increases the level of the subalphabet by one. Finally,
the last $g_{2}$ gives a word over the one-letter alphabet $A_{t+1}=\\{e\\}$.
Observe that the letter $e$ does not appear until this final application of
$g_{2}$.

We next define the direct sum of two M-triples. Intuitively, the direct sum of
M-triples $F$ and $G$ is obtained by taking the disjoint union of $F$ and $G$
and merging the last letters of the underlying alphabets.

Assume that $F=(A,f_{1},f_{2})$ and $G=(B,g_{1},g_{2})$ are M-triples of
dimension $t$. Assume that $A\cap B=\emptyset$. Let the underlying partitions
of $A$ and $B$ be $(A_{1},\ldots,A_{t+1})$ and $(B_{1},\ldots,B_{t+1})$,
respectively. Let $A_{t+1}=\\{e_{1}\\}$ and $B_{t+1}=\\{e_{2}\\}$. To define
the direct sum of $F$ and $G$, take a new letter $e$. Let
$C=C_{1}\cup\cdots\cup C_{t+1}$, where $C_{i}=A_{i}\cup B_{i}$ is the
subalphabet of level $i$ of $C$ for $i=1,\ldots,t$ and $C_{t+1}=\\{e\\}$ is
the subalphabet of level $t+1$ of $C$. The letters of $C$ are ordered so that
all letters of a subalphabet of level $i$ precede all letters of the
subalphabet of level $i+1$ for $i=1,\ldots,t$. Furthermore, all letters of
$A_{i}$ precede all letters of $B_{i}$ for $i=1,\ldots,t$.

The morphism $h_{1}\in\operatorname{Tri}(C^{*})$ is defined by

$ch_{1}=\left\\{\begin{array}[]{lll}cf_{1}&\mbox{ if }&c\in A\mbox{ and }c\neq
e_{1}\\\ cg_{1}&\mbox{ if }&c\in B\mbox{ and }c\neq e_{2}\\\
\varepsilon&\mbox{ if }&c=e\end{array}\right..$

To define $h_{2}$ we first define a morphism $k:(A\cup B)^{*}\to C^{*}$ which
maps the last letters $e_{1}$ and $e_{2}$ of $A$ and $B$ to $e$ and maps all
other letters of $A\cup B$ as the identity mapping. Then
$h_{2}\in\operatorname{Tri}(C^{*})$ is defined by

$ch_{2}=\left\\{\begin{array}[]{lll}cf_{2}k&\mbox{ if }&c\in A\mbox{ and
}c\neq e_{1}\\\ cg_{2}k&\mbox{ if }&c\in B\mbox{ and }c\neq e_{2}\\\
\varepsilon&\mbox{ if }&c=e\end{array}\right..$

Then the direct sum $F\oplus G$ of $F$ and $G$ is the M-triple
$(C,h_{1},h_{2})$. It is not difficult to check that all conditions of
Definition 1 are satisfied.

We show next that ${\mathbb{N}}$-linear combinations of mappings computable by
M-triples of the same dimension are also computable by M-triples.

###### Proposition 1

Let $t$ be a positive integer. Let $F=(A,f_{1},f_{2})$ and $G=(B,g_{1},g_{2})$
be M-triples of dimension $t$. Assume that $A\cap B=\emptyset$. Let
$p:{\mathbb{Z}}_{+}^{t}\to{\mathbb{Z}}_{+}$ and
$q:{\mathbb{Z}}_{+}^{t}\to{\mathbb{Z}}_{+}$ be mappings such that $p$ is
computable by $F$ and $q$ is computable by $G$. Assume
${\alpha},{\beta}\in{\mathbb{Z}}_{+}$. Then $\alpha p+\beta q$ is computable
by $F\oplus G$.

Proof. Let $A_{1}$ and $B_{1}$ be the subalphabets of level 1 of $A$ and $B$,
respectively. Let $e_{1}$ be the last letter of $A$ and let $e_{2}$ be the
last letter of $B$. By assumption, there exist words $u\in A_{1}^{*}$ and
$v\in B_{1}^{*}$ such that

$uf_{1}^{n_{1}}f_{2}f_{1}^{n_{2}}f_{2}\cdots
f_{1}^{n_{t}}f_{2}=e_{1}^{p(n_{1},\ldots,n_{t})}$

and

$vg_{1}^{n_{1}}g_{2}g_{1}^{n_{2}}g_{2}\cdots
g_{1}^{n_{t}}g_{2}=e_{2}^{q(n_{1},\ldots,n_{t})}$

for all positive integers $n_{1},\ldots,n_{t}$. Let $F\oplus
G=(C,h_{1},h_{2})$ and let $e$ be the last letter of $C$. Then

$uh_{1}^{n_{1}}h_{2}h_{1}^{n_{2}}h_{2}\cdots
h_{1}^{n_{t}}h_{2}=e^{p(n_{1},\ldots,n_{t})}$

and

$vh_{1}^{n_{1}}h_{2}h_{1}^{n_{2}}h_{2}\cdots
h_{1}^{n_{t}}h_{2}=e^{q(n_{1},\ldots,n_{t})}$

for all positive integers $n_{1},\ldots,n_{t}$.

Let $w=u^{\alpha}v^{\beta}$. Then

$\displaystyle wh_{1}^{n_{1}}h_{2}h_{1}^{n_{2}}h_{2}\cdots h_{1}^{n_{t}}h_{2}$
$\displaystyle=$ $\displaystyle(uh_{1}^{n_{1}}h_{2}h_{1}^{n_{2}}h_{2}\cdots
h_{1}^{n_{t}}h_{2})^{\alpha}\ (vh_{1}^{n_{1}}h_{2}h_{1}^{n_{2}}h_{2}\cdots
h_{1}^{n_{t}}h_{2})^{\beta}$ $\displaystyle=$ $\displaystyle e^{\alpha
p(n_{1},\ldots,n_{t})}e^{\beta q(n_{1},\ldots,n_{t})}=e^{\alpha
p(n_{1},\ldots,n_{t})+\beta q(n_{1},\ldots,n_{t})}$

for all positive integers $n_{1},\ldots,n_{t}$.

Hence $\alpha p+\beta q$ is computable by $F\oplus G$. $\Box$

The following lemma is the starting point in showing that polynomials over
nonnegative integers are computable by M-tuples.

###### Lemma 2

Let $k$ be a positive integer. Let

$N=\left(\begin{array}[]{rr}1&1\\\ 0&1\end{array}\right)$

and let $N_{k}$ be the Kronecker product of $k$ copies of $N$. Let $Z$ be an
ordered alphabet having $2^{k}$ letters and let
$h\in\operatorname{Hom}(Z^{*})$ be a morphism such that $h\Psi=N_{k}$. Let $a$
be the first letter of $Z$ and let $b$ be the last letter of $Z$. Then
$h\in\operatorname{Tri}(Z^{*})$ and

$|ah^{n}|_{b}=n^{k}$

for every positive integer $n$.

Proof. Since $h\Psi$ is upper triangular, $h\in\operatorname{Tri}(Z^{*})$. For
every positive integer $n$, the number of occurrences of $b$ in $ah^{n}$
equals the last entry in the first row of $h^{n}\Psi$. For every positive
integer $n$, we have

$h^{n}\Psi=(h\Psi)^{n}=(N\otimes\cdots\otimes N)^{n}=N^{n}\otimes\cdots\otimes
N^{n}$ $=\left(\begin{array}[]{rr}1&1\\\
0&1\end{array}\right)^{n}\otimes\cdots\otimes\left(\begin{array}[]{rr}1&1\\\
0&1\end{array}\right)^{n}=\left(\begin{array}[]{rr}1&n\\\
0&1\end{array}\right)\otimes\cdots\otimes\left(\begin{array}[]{rr}1&n\\\
0&1\end{array}\right).$

The last entry of the first row of this matrix equals $n^{k}$. $\Box$

The next step is to show that any monomial with coefficient 1 is computable by
an M-triple.

###### Lemma 3

Let $t$ be a positive integer and let $\alpha_{1},\ldots,\alpha_{t}$ be
nonnegative integers. Let

$p(x_{1},\ldots,x_{t})=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots
x_{t}^{\alpha_{t}}.$

Then we can effectively construct an M-triple $G=(A,g_{1},g_{2})$ of dimension
$t$ such that $p(x_{1},\ldots,x_{t})$ is computable by $G$.

Proof. Let $i\in\\{1,\ldots,t\\}$. Assume first that $\alpha_{i}>0$. By Lemma
2 there exist an ordered alphabet $A_{i}$ and a morphism
$h_{i}\in\operatorname{Tri}(A_{i}^{*})$ such that

$|a_{i}h_{i}^{n}|_{b_{i}}=n^{\alpha_{i}}$ (2)

for every positive integer $n$ where $a_{i}$ is the first letter of $A_{i}$
and $b_{i}$ is the last letter of $A_{i}$. Furthermore, we have $a_{i}\neq
b_{i}$. Assume then that $\alpha_{i}=0$. Then it is easy to see that there
exist an ordered alphabet $A_{i}=\\{a_{i},b_{i}\\}$ with $a_{i}<b_{i}$ and a
morphism $h_{i}\in\operatorname{Tri}(A_{i}^{*})$ such that (2) holds for every
positive integer $n$. Without loss of generality assume that $A_{i}\cap
A_{j}=\emptyset$ if $i\neq j$.

Next, choose a new letter $e$ and let $A_{t+1}=\\{e\\}$. Define
$h_{t+1}\in\operatorname{Tri}(A_{t+1}^{*})$ by $eh_{t+1}=\varepsilon$.

Let $A=A_{1}\cup\cdots\cup A_{t+1}$. Order the letters of $A$ so that all
letters in $A_{i}$ precede all letters in $A_{i+1}$ for $i=1,\ldots,t$. Inside
$A_{i}$ use the order already chosen for $A_{i}$. Let

$g_{1}=h_{1}\oplus\cdots\oplus h_{t+1}.$

Then $g_{1}\in\operatorname{Hom}(A^{*})$. Since

$g_{1}\Psi=h_{1}\Psi\oplus\cdots\oplus h_{t+1}\Psi,$

we have $g_{1}\in\operatorname{Tri}(A^{*})$.

Define $g_{2}\in\operatorname{Hom}(A^{*})$ as follows. Let
$b_{i}g_{2}=a_{i+1}$ for $i=1,\ldots,t-1$ and let $b_{t}g_{2}=e$. Let
$ag_{2}=\varepsilon$ if $a\not\in\\{b_{1},\ldots,b_{t}\\}$. Then
$g_{2}\in\operatorname{Tri}(A^{*})$.

Hence

$A_{i}g_{1}\subseteq A_{i}^{*}\hskip 8.53581pt\mbox{for }\hskip
8.53581pti=1,\ldots,t+1$

and

$A_{i}g_{2}\subseteq A_{i+1}^{*}\hskip 8.53581pt\mbox{for }\hskip
8.53581pti=1,\ldots,t.$

To check condition (iii) in Definition 1 assume that $a\in A$. If
$a\not\in\\{b_{1},\ldots,b_{t}\\}$, we have $ag_{2}=\varepsilon$. If $a=b_{i}$
for some $i\in\\{1,\ldots,t-1\\}$, then $ag_{2}^{2}=a_{i+1}g_{2}=\varepsilon$.
Finally, $b_{t}g_{2}^{2}=eg_{2}=\varepsilon$. Hence condition (iii) holds. It
follows that $(A,g_{1},g_{2})$ is an M-triple of dimension $t$.

It remains to show that $p(x_{1},\ldots,x_{t})$ is computable by $G$. Equation
(2) implies that for every positive integer $n$ we have

$a_{i}g_{1}^{n}g_{2}=a_{i+1}^{n^{\alpha_{i}}}$

for $i=1,\ldots,t-1$ and

$a_{t}g_{1}^{n}g_{2}=e^{n^{\alpha_{t}}}.$

Hence

$\displaystyle a_{1}g_{1}^{n_{1}}g_{2}g_{1}^{n_{2}}g_{2}\cdots
g_{1}^{n_{t}}g_{2}$ $\displaystyle=$ $\displaystyle\
a_{2}^{n_{1}^{\alpha_{1}}}g_{1}^{n_{2}}g_{2}\cdots g_{1}^{n_{t}}g_{2}$
$\displaystyle=$ $\displaystyle\
a_{3}^{n_{1}^{\alpha_{1}}n_{2}^{\alpha_{2}}}g_{1}^{n_{3}}g_{2}\cdots
g_{1}^{n_{t}}g_{2}$ $\displaystyle=$ $\displaystyle\ \cdots$ $\displaystyle=$
$\displaystyle\ e^{n_{1}^{\alpha_{1}}n_{2}^{\alpha_{2}}\cdots
n_{t}^{\alpha_{t}}}=e^{p(n_{1},\ldots,n_{t})}$

for all positive integers $n_{1},\ldots,n_{t}$. Hence $p(x_{1},\ldots,x_{t})$
is computable by $G$. $\Box$

Now we can show that any polynomial over nonnegative integers is computable by
an M-triple.

###### Proposition 4

Let $p(x_{1},\ldots,x_{t})$ be a polynomial having nonnegative integer
coefficients. Then we can effectively compute an M-triple $G$ of dimension $t$
such that $p(x_{1},\ldots,x_{t})$ is computable by $G$.

Proof. The claim follows by Proposition 1 and Lemma 3. $\Box$

##  4 Linear equations over a morphism monoid and recursively enumerable sets

In this section we first construct two upper triangular morphisms $g_{1}$ and
$g_{2}$ over an ordered alphabet $Z$. Then we study linear equations over the
monoid ${\mathcal{H}}$ generated by $g_{1}$ and $g_{2}$. In particular, we
study the connections between such linear equations and the recursively
enumerable subsets of ${\mathbb{Z}}_{+}$.

For the remainder of this paper, fix an enumeration

${\mathcal{R}}_{1},\ {\mathcal{R}}_{2},\ {\mathcal{R}}_{3},\ \ldots$

of the recursively enumerable subsets of ${\mathbb{Z}}_{+}$.

The following deep theorem is due to Matiyasevich.

###### Theorem 5

There is a positive integer $t$ and polynomials $p(x_{1},\ldots,x_{t})$ and
$q(x_{1},\ldots,x_{t})$ with nonnegative integer coefficients such that for
all positive integers $s$ and $n$ we have

$s\in{\mathcal{R}}_{n}$

if and only if there exist positive integers $n_{3},\ldots,n_{t}$ such that

$p(n,s,n_{3},\ldots,n_{t})=q(n,s,n_{3},\ldots,n_{t}).$

Furthermore, we can compute such polynomials $p(x_{1},\ldots,x_{t})$ and
$q(x_{1},\ldots,x_{t})$.

For the proof of Theorem 5 see the monograph [6].

In what follows $p(x_{1},\ldots,x_{t})$ and $q(x_{1},\ldots,x_{t})$ will be as
in Theorem 5. Since the coefficients of these two polynomials are nonnegative
integers, we have $p(n_{1},\ldots,n_{t})>0$ and $q(n_{1},\ldots,n_{t})>0$ for
all positive integers $n_{1},\ldots,n_{t}$.

Let $C(x_{1},\ldots,x_{t+1})$ be a polynomial with nonnegative integer
coefficients such that $C$ defines an injective mapping from
${\mathbb{Z}}_{+}^{t+1}$ to ${\mathbb{Z}}_{+}$. It is easy to compute such a
polynomial using the Cantor pairing polynomial.

Let

$p_{1}(x_{1},\ldots,x_{t})=C(x_{1},\ldots,x_{t},p(x_{1},\ldots,x_{t}))$

and

$q_{1}(x_{1},\ldots,x_{t})=C(x_{1},\ldots,x_{t},q(x_{1},\ldots,x_{t})).$

By Proposition 4 we can effectively compute M-triples
$F_{1}=(A,f_{11},f_{12})$ and $F_{2}=(B,f_{21},f_{22})$ of dimension $t$ such
that $p_{1}$ is computable by $F_{1}$ and $q_{1}$ is computable by $F_{2}$.
Without loss of generality assume that $A\cap B=\emptyset$. Let the underlying
partition of $A$ be $(A_{1},\ldots,A_{t+1})$ and let the underlying partition
of $B$ be $(B_{1},\ldots,B_{t+1})$.

Let $G=(\overline{D},f_{1},f_{2})$ be the direct sum of $F_{1}$ and $F_{2}$.
Let $(\overline{D}_{1},\ldots,\overline{D}_{t+1})$ be the underlying partition
of $\overline{D}$ and let $\overline{D}_{t+1}=\\{e\\}$.

Then we have

$A_{i}f_{1}\subseteq A_{i}^{*},\hskip 8.53581ptB_{i}f_{1}\subseteq B_{i}^{*}$
(3)

for $i=1,\ldots,t$, and

$A_{i}f_{2}\subseteq A_{i+1}^{*},\hskip 8.53581ptB_{i}f_{2}\subseteq
B_{i+1}^{*},\hskip 8.53581ptA_{t}f_{2}\subseteq e^{*},\hskip
8.53581ptB_{t}f_{2}\subseteq e^{*}$ (4)

for $i=1,\ldots,t-1$. Furthermore, $ef_{1}=ef_{2}=\varepsilon$ and
$df_{2}^{2}=\varepsilon$ for all $d\in\overline{D}$.

Since $p_{1}$ is computable by $F_{1}$ and $q_{1}$ is computable by $F_{2}$,
there are words $u\in A_{1}^{*}$ and $v\in B_{1}^{*}$ such that

$uf_{1}^{n_{1}}f_{2}f_{1}^{n_{2}}f_{2}\cdots
f_{1}^{n_{t}}f_{2}=e^{p_{1}(n_{1},\ldots,n_{t})}$ (5)

and

$vf_{1}^{n_{1}}f_{2}f_{1}^{n_{2}}f_{2}\cdots
f_{1}^{n_{t}}f_{2}=e^{q_{1}(n_{1},\ldots,n_{t})}$ (6)

for all positive integers $n_{1},\ldots,n_{t}$.

Next, let $C=\\{c_{0},c_{1},c_{2},c_{3}\\}$ be a new alphabet ordered by
$c_{0}<c_{1}<c_{2}<c_{3}$. Let $D=C\cup\overline{D}$ be an ordered alphabet
such that all letters of $C$ precede all letters of $\overline{D}$. Define
$g_{1}\in\operatorname{Hom}(D^{*})$ by

$c_{0}g_{1}=c_{1}g_{1}=\varepsilon,\ c_{2}g_{1}=uf_{1},\ c_{3}g_{1}=vf_{1}$

and

$dg_{1}=df_{1}\mbox{ for all }d\in\overline{D}.$

Define $g_{2}\in\operatorname{Hom}(D^{*})$ by

$c_{0}g_{2}=c_{1},\ c_{1}g_{2}=c_{2},\ c_{2}g_{2}=c_{3}g_{2}=c_{3}$

and

$dg_{2}=df_{2}\mbox{ for all }d\in\overline{D}.$

Then $g_{1},g_{2}\in\operatorname{Tri}(D^{*})$.

By (3) and (4) we have

$A_{i}g_{1}\subseteq A_{i}^{*},\hskip 8.53581ptB_{i}g_{1}\subseteq B_{i}^{*}$
(7)

for $i=1,\ldots,t$, and

$A_{i}g_{2}\subseteq A_{i+1}^{*},\hskip 8.53581ptB_{i}g_{2}\subseteq
B_{i+1}^{*},\hskip 8.53581ptA_{t}g_{2}\subseteq e^{*},\hskip
8.53581ptB_{t}g_{2}\subseteq e^{*}$ (8)

for $i=1,\ldots,t-1$. Furthermore, $eg_{1}=eg_{2}=\varepsilon$ and
$dg_{2}^{2}=\varepsilon$ for all $d\in\overline{D}$.

We have used M-triples to construct $D$, $g_{1}$ and $g_{2}$, but it should be
observed that $(D,g_{1},g_{2})$ is not an M-triple. (For example,
$c_{2}g_{2}^{2}=c_{3}\neq\varepsilon$.)

Let ${\mathcal{H}}$ be the monoid generated by $g_{1}$ and $g_{2}$.

Define the morphism $o\in\operatorname{Tri}(D^{*})$ by $o(d)=\varepsilon$ for
all $d\in D$. Since $g_{1}g_{2}^{2}=o$, the morphism $o$ belongs to
${\mathcal{H}}$. It is the zero of ${\mathcal{H}}$.

Before discussing connections between linear equations over ${\mathcal{H}}$
and recursively enumerable subsets of ${\mathbb{Z}}_{+}$ we prove two lemmas.

For positive integers $\alpha,n_{1},\ldots,n_{\alpha}$, denote

$\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=g_{1}^{n_{1}}g_{2}g_{1}^{n_{2}}g_{2}\cdots
g_{1}^{n_{\alpha}}g_{2}.$

In particular, $\operatorname{Prod}(n_{1})=g_{1}^{n_{1}}g_{2}$ and

$\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=\operatorname{Prod}(n_{1})\operatorname{Prod}(n_{2})\cdots\operatorname{Prod}(n_{\alpha}).$

###### Lemma 6

Let $\alpha,n_{1},\ldots,n_{\alpha}$ be positive integers and let $j$ be a
nonnegative integer.

(i) If $\alpha<t$, then

$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}\in
A_{\alpha+1}^{*}$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}\in
B_{\alpha+1}^{*}.$

(ii) If $\alpha=t$, then

$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=e^{p_{1}(n_{1},\ldots,n_{\alpha})}$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=e^{q_{1}(n_{1},\ldots,n_{\alpha})}.$

(iii) If $\alpha=t$ and $j\geq 1$, then

$g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}=o\hskip
8.53581pt\mbox{ and }\hskip
8.53581ptg_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}=o.$

(iv) If $\alpha\leq t$, then

$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})\neq\varepsilon$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})\neq\varepsilon.$

Proof. By the definition of $g_{2}$, we have

$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=u\operatorname{Prod}(n_{1},\ldots,n_{\alpha})$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})=v\operatorname{Prod}(n_{1},\ldots,n_{\alpha}),$

where $u\in A_{1}^{*}$ and $v\in B_{1}^{*}$. Hence (i) follows by (7) and (8),
and (ii) follows by (5) and (6).

Since $Dg_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{t})\subseteq e^{*}$ and
$eg_{1}=\varepsilon$, we have
$g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}=o$ if
$\alpha=t$ and $j\geq 1$. Hence also
$g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})g_{1}^{j}=o$ if
$\alpha=t$ and $j\geq 1$.

Finally, the first claim of (iv) follows by (ii) if $\alpha=t$ because
$p_{1}(n_{1},\ldots,n_{t})>0$. If $\alpha<t$, we have
$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})(g_{1}g_{2})^{t-\alpha}\neq\varepsilon$.
Hence
$c_{0}g_{2}^{2}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})\neq\varepsilon$.
It is seen similarly that
$c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{\alpha})\neq\varepsilon$.
$\Box$

###### Lemma 7

If $h_{1},h_{2}\in{\mathcal{H}}$, then $g_{1}h_{1}g_{2}^{2}h_{2}=o$.

Proof. If $d\in D$, then $dg_{1}\in{\overline{D}}^{*}$. This implies that
$dg_{1}h_{1}\in{\overline{D}}^{*}$. Hence $dg_{1}h_{1}g_{2}^{2}=\varepsilon$.
This proves the claim. $\Box$

Now we are ready to prove the main lemma of this section.

###### Lemma 8

If $n$ and $s$ are positive integers, the following three conditions are
equivalent:

  1. (i)

there exist positive integers $n_{3},\ldots,n_{t}$ such that

$p(n,s,n_{3},\ldots,n_{t})=q(n,s,n_{3},\ldots,n_{t}),$ (9)

  2. (ii)

there exists a morphism $h$ in ${\mathcal{H}}$ such that

$g_{2}^{2}\operatorname{Prod}(n,s)h=g_{2}^{3}\operatorname{Prod}(n,s)h\neq o,$
(10)

  3. (iii)

there exist morphisms $h_{1}$ and $h_{2}$ in ${\mathcal{H}}$ such that

$g_{2}^{2}\operatorname{Prod}(n,s)h_{1}=g_{2}^{3}\operatorname{Prod}(n,s)h_{2}\neq
o\ .$ (11)

Proof. We show first that (i) implies (ii).

Assume that (i) holds. Let $n,s,n_{3},\ldots,n_{t}$ be positive integers such
that (9) holds. Then we have

$p_{1}(n,s,n_{3},\ldots,n_{t})=q_{1}(n,s,n_{3},\ldots,n_{t}).$ (12)

We claim that

$g_{2}^{2}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})=g_{2}^{3}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t}).$
(13)

To see this we have to show that

$dg_{2}^{2}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})=dg_{2}^{3}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})$
(14)

for all $d\in D$.

Assume first that $d=c_{0}$. By Lemma 6 (ii), we have

$c_{0}g_{2}^{2}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})=e^{p_{1}(n,s,n_{3},\ldots,n_{t})}$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})=e^{q_{1}(n,s,n_{3},\ldots,n_{t})}.$

Hence (12) implies (14) for $d=c_{0}$.

Assume then that $d\in D$ and $d\neq c_{0}$. Then $dg_{2}^{2}=dg_{2}^{3}$.
This follows from the definition of $g_{2}$ if $d\in\\{c_{1},c_{2},c_{3}\\}$.
If $d\in\overline{D}$, this follows from $dg_{2}^{2}=\varepsilon$. The
equation $dg_{2}^{2}=dg_{2}^{3}$ for $d\neq c_{0}$ implies that (14) holds for
$d\neq c_{0}$. Hence (14) holds for all $d\in D$. This proves (13).

Furthermore, by Lemma 6 (iv), we have
$g_{2}^{2}\operatorname{Prod}(n,s,n_{3},\ldots,n_{t})\neq o$. Hence, (10)
holds for $h=\operatorname{Prod}(n_{3},\ldots,n_{t})$. This concludes the
proof that (i) implies (ii).

Trivially, (ii) implies (iii).

Finally, assume that (iii) holds. Let $h_{1},h_{2}\in{\mathcal{H}}$ be
morphisms such that (11) holds.

Since $g_{2}^{2}\operatorname{Prod}(n,s)h_{1}\neq o$, Lemma 7 implies that
there exist positive integers $\alpha,m_{1},\ldots,m_{\alpha}$ and a
nonnegative integer $\gamma$ such that

$\operatorname{Prod}(n,s)h_{1}=\operatorname{Prod}(m_{1},\ldots,m_{\alpha})g_{1}^{\gamma},$

where $m_{1}=n$ and $m_{2}=s$. Similarly, there exist positive integers
$\beta,n_{1},\ldots,n_{\beta}$ and a nonnegative integer $\delta$ such that

$\operatorname{Prod}(n,s)h_{2}=\operatorname{Prod}(n_{1},\ldots,n_{\beta})g_{1}^{\delta},$

where $n_{1}=n$ and $n_{2}=s$.

Lemma 6 (iii) implies that $\alpha\leq t$ and $\beta\leq t$. Lemma 6 (i) and
(ii) imply that

$c_{0}g_{2}^{2}\operatorname{Prod}(n,s)h_{1}\in A_{\alpha+1}^{*}$

if $\alpha<t$ and

$c_{0}g_{2}^{2}\operatorname{Prod}(n,s)h_{1}\in e^{*}$

if $\alpha=t$. Similarly,

$c_{0}g_{2}^{3}\operatorname{Prod}(n,s)h_{2}\in B_{\beta+1}^{*}$

if $\beta<t$ and

$c_{0}g_{2}^{3}\operatorname{Prod}(n,s)h_{2}\in e^{*}$

if $\beta=t$. By Lemma 6 (iv), the word
$c_{0}g_{2}^{2}\operatorname{Prod}(n,s)h_{1}$ is nonempty if $\alpha<t$ and
the word $c_{0}g_{2}^{3}\operatorname{Prod}(n,s)h_{2}$ is nonempty if
$\beta<t$. Since no two of the sets
$A_{1},\ldots,A_{t},B_{1},\ldots,B_{t},\\{e\\}$ have a common letter, it
follows that $\alpha=\beta=t$. Since
$g_{2}^{2}\operatorname{Prod}(n,s)h_{1}\neq o$ and
$g_{2}^{3}\operatorname{Prod}(n,s)h_{2}\neq o$, Lemma 6 (iii) implies that
$\gamma=\delta=0$.

Next, by Lemma 6 (ii),

$c_{0}g_{2}^{2}\operatorname{Prod}(n,s)h_{1}=c_{0}g_{2}^{2}\operatorname{Prod}(m_{1},\ldots,m_{t})=e^{p_{1}(m_{1},\ldots,m_{t})}$

and

$c_{0}g_{2}^{3}\operatorname{Prod}(n,s)h_{2}=c_{0}g_{2}^{3}\operatorname{Prod}(n_{1},\ldots,n_{t})=e^{q_{1}(n_{1},\ldots,n_{t})}.$

Hence

$p_{1}(m_{1},\ldots,m_{t})=q_{1}(n_{1},\ldots,n_{t}).$

Therefore

$C(m_{1},\ldots,m_{t},p(m_{1},\ldots,m_{t}))=C(n_{1},\ldots,n_{t},q(n_{1},\ldots,n_{t})).$

Since $C$ is injective on ${\mathbb{Z}}_{+}^{t+1}$, we see that

$m_{1}=n_{1},\ \ldots,\ m_{t}=n_{t},\
p(m_{1},\ldots,m_{t})=q(n_{1},\ldots,n_{t}).$

Finally, because $m_{1}=n$ and $m_{2}=s$, we see that (9) holds. This
concludes the proof that (iii) implies (i). $\Box$

Now we are ready for a variant of Theorem 5 which uses linear equations over
${\mathcal{H}}$ instead of polynomial equations over integers.

Since ${\mathcal{H}}$ has a zero, we will consider only such solutions $h$
(resp. $h_{1},h_{2}$) of $ax=bx$ (resp. $ax=by$) which satisfy the condition
$ah\neq o$ (resp. $ah_{1}\neq o$). We will call these solutions
nonannihilating.

For positive integers $n$ and $s$ denote

$f_{n,s}=g_{2}^{2}\operatorname{Prod}(n,s)$

and

$g_{n,s}=g_{2}^{3}\operatorname{Prod}(n,s).$

###### Theorem 9

Let $g_{1}$ and $g_{2}$ be the upper triangular morphisms constructed above
and let ${\mathcal{H}}$ be the monoid generated by $g_{1}$ and $g_{2}$. For
all positive integers $s$ and $n$ we have

$s\in{\mathcal{R}}_{n}$

if and only if there exists $h\in{\mathcal{H}}$ such that

$f_{n,s}h=g_{n,s}h\neq o.$

Proof. Let $n$ and $s$ be positive integers. By Theorem 5 we have
$s\in{\mathcal{R}}_{n}$ if and only if there are positive integers
$n_{3},\ldots,n_{t}$ such that (9) holds. Now the claim follows by Lemma 8.
$\Box$

Instead of nonannihilating solutions of $f_{n,s}x=g_{n,s}x$ we may consider
nonannihilating solutions of $f_{n,s}x=g_{n,s}y$.

###### Theorem 10

Let $g_{1}$ and $g_{2}$ be the upper triangular morphisms constructed above
and let ${\mathcal{H}}$ be the monoid generated by $g_{1}$ and $g_{2}$. For
all positive integers $s$ and $n$ we have

$s\in{\mathcal{R}}_{n}$

if and only if there exist $h_{1},h_{2}\in{\mathcal{H}}$ such that

$f_{n,s}h_{1}=g_{n,s}h_{2}\neq o.$

Proof. The claim follows by Theorem 5 and Lemma 8. $\Box$

Since the membership problem is undecidable for recursively enumerable sets
(see [9, 10, 12]), Theorems 9 and 10 imply the following result.

###### Theorem 11

Let ${\mathcal{H}}$ be as in Theorem 9. The following problems are
undecidable:

(i) Given $a,b\in{\mathcal{H}}$, decide whether the equation

$ax=bx$

has a nonannihilating solution in ${\mathcal{H}}$.

(ii) Given $a,b\in{\mathcal{H}}$, decide whether the equation

$ax=by$

has a nonannihilating solution in ${\mathcal{H}}$.

In fact, a stronger result holds. Assume that $n$ is an integer such that
${\mathcal{R}}_{n}$ is not recursive. Then there is no algorithm to decide
whether for a given integer $s$ the equation $f_{n,s}x=g_{n,s}x$ (or
$f_{n,s}x=g_{n,s}y$) has a nonannihilating solution in ${\mathcal{H}}$.

##  5 Linear equations over a matrix monoid and recursively enumerable sets

In this section we present a variant of Theorem 5 which uses linear equations
over a monoid generated by two upper triangular matrices. We also present
undecidability results for linear equations over matrix monoids. We will get
the results of this section as easy consequences of the constructions in the
previous section.

We continue with the notations of the previous section. In particular,
$p(x_{1},\ldots,x_{t})$ and $q(x_{1},\ldots,x_{t})$ will be the polynomials of
Theorem 5, $g_{1}$ and $g_{2}$ will be the morphisms over the alphabet $D$
constructed in Section 4 and ${\mathcal{H}}$ will be the monoid generated by
$g_{1}$ and $g_{2}$.

Let $k$ be the number of letters in $D$. Let
$\Psi:\operatorname{Hom}(D^{*})\to{\mathbb{N}}^{k\times k}$ be the mapping
which maps every $h\in\operatorname{Hom}(D^{*})$ to the matrix of $h$. Let
$M_{i}=g_{i}\Psi$ be the matrix of $g_{i}$ for $i=1,2$. Let ${\mathcal{M}}$ be
the multiplicative submonoid of $\operatorname{Tri}(k,{\mathbb{N}})$ generated
by $M_{1}$ and $M_{2}$.

For positive integers $\alpha$ and $n_{1},\ldots,n_{\alpha}$, denote

$\operatorname{prod}(n_{1},\ldots,n_{\alpha})=M_{1}^{n_{1}}M_{2}M_{1}^{n_{2}}M_{2}\cdots
M_{1}^{n_{\alpha}}M_{2}.$

Then we have

$\operatorname{Prod}(n_{1},\ldots,n_{\alpha})\Psi=\operatorname{prod}(n_{1},\ldots,n_{\alpha}).$

If $M\in{\mathcal{M}}$, there is a morphism $h\in{\mathcal{H}}$ such that
$h\Psi=M$. In fact, if $M=M_{i_{1}}M_{i_{2}}\cdots M_{i_{\alpha}}$, where
$i_{1},\ldots,i_{\alpha}\in\\{1,2\\}$, then $(g_{i_{1}}g_{i_{2}}\cdots
g_{i_{\alpha}})\Psi=M$.

###### Lemma 12

Let $n$ and $s$ be positive integers and let $E,F\in{\mathcal{M}}$. Assume
that

$M_{2}^{2}\operatorname{prod}(n,s)E=M_{2}^{3}\operatorname{prod}(n,s)F\neq O.$
(15)

Let $h_{1}\in{\mathcal{H}}$ be a morphism such that $h_{1}\Psi=E$ and let
$h_{2}\in{\mathcal{H}}$ be a morphism such that $h_{2}\Psi=F$. Then

$g_{2}^{2}\operatorname{Prod}(n,s)h_{1}=g_{2}^{3}\operatorname{Prod}(n,s)h_{2}\neq
o.$

Proof. Denote $y_{1}=g_{2}^{2}\operatorname{Prod}(n,s)h_{1}$ and
$y_{2}=g_{2}^{3}\operatorname{Prod}(n,s)h_{2}$. Since

$y_{1}\Psi=M_{2}^{2}\operatorname{prod}(n,s)E\hskip 8.53581pt\mbox{ and
}\hskip 8.53581pty_{2}\Psi=M_{2}^{3}\operatorname{prod}(n,s)F,$

(15) implies that

$y_{1}\Psi=y_{2}\Psi.$

Hence $c_{0}y_{1}\psi=c_{0}y_{2}\psi$. By Lemma 6, we have $c_{0}y_{1}\in
A_{i}^{*}$ for some $i\leq t$ or $c_{0}y_{1}\in e^{*}$. Similarly,
$c_{0}y_{2}\in B_{i}^{*}$ for some $i\leq t$ or $c_{0}y_{2}\in e^{*}$. Since
no two of the sets $A_{1},\ldots,A_{t},B_{1},\ldots,B_{t},\\{e\\}$ have a
common letter, it follows that $c_{0}y_{1}\in e^{*}$ and $c_{0}y_{2}\in
e^{*}$. Together with $c_{0}y_{1}\psi=c_{0}y_{2}\psi$, this implies that
$c_{0}y_{1}=c_{0}y_{2}$.

Assume next that $d\in\\{c_{1},c_{2},c_{3}\\}$. Since
$dg_{2}^{3}=c_{0}g_{2}^{3}$, we have $dy_{2}=c_{0}y_{2}\in e^{*}$. Hence the
equation $dy_{1}\psi=dy_{2}\psi$ again implies that $dy_{1}=dy_{2}$. Finally,
if $d\in\overline{D}$, then $dg_{2}^{2}=dg_{2}^{3}=\varepsilon$ and
$dy_{1}=dy_{2}$. It follows that $y_{1}=y_{2}$.

Finally, $y_{1}$ is not the zero of ${\mathcal{H}}$, since $y_{1}\Psi\neq O$.
$\Box$

###### Lemma 13

If $n$ and $s$ are positive integers, the following three conditions are
equivalent:

  1. (i)

there exist positive integers $n_{3},\ldots,n_{t}$ such that

$p(n,s,n_{3},\ldots,n_{t})=q(n,s,n_{3},\ldots,n_{t}),$ (16)

  2. (ii)

there exists a matrix $N$ in ${\mathcal{M}}$ such that

$M_{2}^{2}\operatorname{prod}(n,s)N=M_{2}^{3}\operatorname{prod}(n,s)N\neq O,$
(17)

  3. (iii)

there exist matrices $N_{1}$ and $N_{2}$ in ${\mathcal{M}}$ such that

$M_{2}^{2}\operatorname{prod}(n,s)N_{1}=M_{2}^{3}\operatorname{prod}(n,s)N_{2}\neq
O.$ (18)

Proof. First, assume that (i) holds. Then Lemma 8 implies that there is a
morphism $h\in{\mathcal{H}}$ such that

$g_{2}^{2}\operatorname{Prod}(n,s)h=g_{2}^{3}\operatorname{Prod}(n,s)h\neq o.$

Hence

$M_{2}^{2}\operatorname{prod}(n,s)(h\Psi)=M_{2}^{3}\operatorname{prod}(n,s)(h\Psi)\neq
O.$

This shows that (17) holds with $N=h\Psi$. Hence (ii) holds.

Trivially, (ii) implies (iii).

Finally, assume that (iii) holds. Let $N_{1},N_{2}\in{\mathcal{M}}$ be
matrices such that (18) holds. Let $h_{1},h_{2}\in{\mathcal{H}}$ be morphisms
such that $h_{1}\Psi=N_{1}$ and $h_{2}\Psi=N_{2}$. Now Lemma 12 implies that
(11) holds. Hence Lemma 8 implies that there exist positive integers
$n_{3},\ldots,n_{t}$ such that (16) holds. $\Box$

Now we are ready for a variant of Theorem 5 which uses linear equations over
${\mathcal{M}}$.

Since ${\mathcal{M}}$ has a zero, we will consider only such solutions $N$
(resp. $N_{1},N_{2}$) of $ax=bx$ (resp. $ax=by$) which satisfy the condition
$aN\neq O$ (resp. $aN_{1}\neq O$). We will again call these solutions
nonannihilating.

For positive integers $n$ and $s$ denote

$K_{n,s}=M_{2}^{2}\operatorname{prod}(n,s)$

and

$M_{n,s}=M_{2}^{3}\operatorname{prod}(n,s).$

###### Theorem 14

Let $M_{1}$ and $M_{2}$ be the upper triangular matrices constructed above and
let ${\mathcal{M}}$ be the multiplicative monoid generated by $M_{1}$ and
$M_{2}$. For all positive integers $s$ and $n$ we have

$s\in{\mathcal{R}}_{n}$

if and only if there exists $N\in{\mathcal{M}}$ such that

$K_{n,s}N=M_{n,s}N\neq O.$

Proof. Let $n$ and $s$ be positive integers. By Theorem 5 we have
$s\in{\mathcal{R}}_{n}$ if and only if there are positive integers
$n_{3},\ldots,n_{t}$ such that (16) holds. Now the claim follows by Lemma 13.
$\Box$

Instead of nonannihilating solutions of $K_{n,s}x=M_{n,s}x$ we may consider
nonannihilating solutions of $K_{n,s}x=M_{n,s}y$.

###### Theorem 15

Let $M_{1}$ and $M_{2}$ be the upper triangular matrices constructed above and
let ${\mathcal{M}}$ be the multiplicative monoid generated by $M_{1}$ and
$M_{2}$. For all positive integers $s$ and $n$ we have

$s\in{\mathcal{R}}_{n}$

if and only if there exist $N_{1},N_{2}\in{\mathcal{M}}$ such that

$K_{n,s}N_{1}=M_{n,s}N_{2}\neq O.$

Proof. The claim follows by Theorem 5 and Lemma 13. $\Box$

Theorems 14 and 15 imply the following result.

###### Theorem 16

Let ${\mathcal{M}}$ be as in Theorem 14. The following problems are
undecidable:

(i) Given $a,b\in{\mathcal{M}}$, decide whether the equation

$ax=bx$

has a nonannihilating solution in ${\mathcal{M}}$.

(ii) Given $a,b\in{\mathcal{M}}$, decide whether the equation

$ax=by$

has a nonannihilating solution in ${\mathcal{M}}$.

Again a stronger result holds. Assume that $n$ is an integer such that
${\mathcal{R}}_{n}$ is not recursive. Then there is no algorithm to decide
whether for a given integer $s$ the equation $K_{n,s}x=M_{n,s}x$ (or
$K_{n,s}x=M_{n,s}y$) has a nonannihilating solution in ${\mathcal{M}}$.

## References

  * [1] J.-P. Allouche and J. Shallit, Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, 2003.
  * [2] P. Bell, V. Halava, T. Harju, J. Karhumäki and I. Potapov, Matrix equations and Hilbert’s tenth problem, Internat. J. Algebra and Comput. 18 (2008) 1231–1241.
  * [3] J. Cassaigne and F. Nicolas, On the decidability of semigroup freeness, RAIRO \- Theoret. Inform. Appl. 46 (2012) 355–399.
  * [4] É. Charlier and J. Honkala, The freeness problem over matrix semigroups and bounded languages, Inform. Comput. 237 (2014) 243–256.
  * [5] J. Honkala, Products of matrices and recursively enumerable sets, J. Comput. System Sci. 81 (2015) 468–472.
  * [6] Y. Matiyasevich, Hilbert’s Tenth Problem, MIT Press, 1993.
  * [7] J.-É. Pin (Ed.), Handbook of Automata Theory, Vols. 1-2, EMS Press, 2021.
  * [8] M. Rigo, Formal Languages, Automata and Numeration Systems 1–2, John Wiley & Sons, 2014.
  * [9] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
  * [10] G. Rozenberg and A. Salomaa, Cornerstones of Undecidability, Prentice Hall, 1994.
  * [11] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Vols. 1-3, Springer, 1997.
  * [12] A. Salomaa, Computation and Automata, Cambridge University Press, 1985.


# Contrastive Transformer: Contrastive Learning Scheme with Transformer innate
Patches

Sander Riisøen Jyhne
Department of ICT
University of Agder
Grimstad, Norway
<EMAIL_ADDRESS>
Per-Arne Andersen
Department of ICT
University of Agder
Grimstad, Norway
<EMAIL_ADDRESS>
Morten Goodwin
Department of ICT
University of Agder
Grimstad, Norway
<EMAIL_ADDRESS>

###### Abstract

This paper presents Contrastive Transformer, a contrastive learning scheme
using the Transformer innate patches. Contrastive Transformer enables existing
contrastive learning techniques, often used for image classification, to
benefit dense downstream prediction tasks such as semantic segmentation. The
scheme performs supervised patch-level contrastive learning, selecting the
patches based on the ground truth mask, subsequently used for hard-negative
and hard-positive sampling. The scheme applies to all vision-transformer
architectures, is easy to implement, and introduces minimal additional memory
footprint. Additionally, the scheme removes the need for huge batch sizes, as
each patch is treated as an image.

We apply and test Contrastive Transformer for the case of aerial image
segmentation, known for low-resolution data, large class imbalance, and
similar semantic classes. We perform extensive experiments to show the
efficacy of the Contrastive Transformer scheme on the ISPRS Potsdam aerial
image segmentation dataset. Additionally, we show the generalizability of our
scheme by applying it to multiple inherently different Transformer
architectures. Ultimately, the results show a consistent increase in mean IoU
across all classes.

_Keywords_ Remote sensing $\cdot$ Contrastive Learning $\cdot$ Deep Learning

##  1 Introduction

Building segmentation in aerial images is a crucial task that has garnered
much attention due to its importance in various fields, such as urban
planning, disaster management, and environmental monitoring. Building
segmentation provides valuable information for urban planning, such as
population density estimation and urban development mapping. In the event of
natural disasters, building segmentation can aid in damage assessment and
relief efforts. Environmental monitoring also benefits from building
segmentation, as it allows for the analysis of land use and urbanization
patterns. Furthermore, accurate building segmentation is the first step
towards automating map creation performed by entities such as the Norwegian
Mapping Authority.

Building segmentation in aerial images is challenging due to the complex and
diverse nature of real-world building structures. Aerial images can contain
various types of buildings, such as skyscrapers, residential buildings, and
industrial buildings, which vary in shape, size, and texture. Factors such as
shadows, occlusions, and variations in lighting affect aerial images,
complicating the segmentation process. Furthermore, building structures in
aerial images can overlap or be partially obscured by other objects, making it
difficult to segment individual buildings accurately.

Previous research on building segmentation has primarily focused on
applications such as urban planning, disaster damage assessment, and change
detection. However, these applications often have different precision
requirements than map production, which creates a research gap when
considering the level of accuracy needed for segmentation masks. Also, models
must be able to effectively segment various types of buildings and
environments, including those in urban and rural settings.

In this study, we propose Contrastive Transformer, a supervised contrastive
learning scheme based on the transformer architecture. This model aims to
improve the accuracy of existing segmentation models by utilizing innate
patches in the Transformer architecture to perform both intra- and inter-image
contrastive learning using existing contrastive loss functions. Depending on
the patch and image size, each image can contain over 20,000 patches collected
from four stages. The collection of patches is guided by the ground truth
mask, which constrains the anchor and positive samples to patches with a
homogenous class distribution. Negative samples, on the other hand, can have a
heterogeneous class distribution as long as they do not contain the class from
the anchor and positive samples. To further enhance contrastive learning,
naive hard-sample mining is applied to select the best samples from the
patches.

As a summary of the above, this paper presents the following key contributions
to computer vision segmentation tasks:

  1. 1.

The paper proposes a supervised contrastive learning scheme called Contrastive
Transformer that utilizes innate patches in the Transformer architecture for
dense downstream prediction tasks such as semantic segmentation.

  2. 2.

The scheme performs supervised patch-level contrastive learning, selecting the
patches based on the ground truth mask, subsequently used for hard-negative
and hard-positive sampling.

  3. 3.

The scheme applies to all vision-transformer architectures is easy to
implement, and introduces minimal additional memory footprint.

  4. 4.

The proposed Contrastive Transformer removes the need for huge batch sizes, as
each patch is treated as an image.

  5. 5.

The paper tests the Contrastive Transformer on the ISPRS Potsdam aerial image
segmentation dataset, known for low-resolution data, large class imbalance,
and similar semantic classes.

  6. 6.

The scheme is shown to be effective in improving the accuracy of existing
segmentation models and increases mean IoU across all classes consistently.

  7. 7.

The proposed scheme has potential applications in dense prediction fields
where accurate semantic representations are crucial, such as map production.

This paper is structured as follows. Section 2 provides an overview of prior
work, highlighting gaps in the current literature that motivate our
contributions. In Section 3, we introduce our primary contribution, the
Contrastive Transformer learning scheme. We evaluate the proposed method and
compare it to previous state-of-the-art methods in aerial building
segmentation in Section 4. Finally, in Section 5, we summarize our findings
and discuss the implications of our work. We also explore potential future
directions for the Contrastive Transformer in Section 6.

##  2 Related Work

Advances in semantic segmentation often depend on developing more powerful
deep neural networks. Initially, these networks are variations of deep
convolutional neural networks, such as the U-Net model [14]. However, since
the release of [5], the Transformer architecture is the most prominent method
for large-scale semantic segmentation. The main issue with Transformers was
the scalability, as the self-attention mechanism has quadratic time and space
complexity [6]. In the preceding years, several works have reduced the
computational complexity while maintaining or increasing the accuracy. The
authors of [13] introduce a hierarchical transformer model using shifted
windows, effectively reducing self-attention computation. Other works, such as
[20], replace the attention-based module with a simple spatial pooling
operator performing basic token mixing. Furthermore, in [9], the authors
propose a more generalizable model that uses convolutions and self-attention
for vision tasks. Lastly, current state-of-the-art models for aerial image
segmentation is dominated by transformer-based architectures. The top 2
performing models on the ISPRS Potsdam Dataset [8] use the Swin Transformer
[13] as the backbone, a strong argument for advancing the performance of
transformers.

A different approach is creating optimization strategies that increase
accuracy without changing the network architecture, such as new loss
functions. Contrastive Transformer is a transformer-based approach that
utilizes the inherent patch representations from the backbone to perform
contrastive learning, improving the internal representations of the classes.
Contrastive learning is a technique that aims to reduce the distance between
the representations of the same class while increasing the distance between
representations of different classes. Contrastive learning uses a similarity
metric to evaluate two representations and then gives feedback to the network
based on the measure and class. The latest contrastive frameworks determine
similarity scores using the global representation of the data, often used in
image classification [3, 4, 15, 7]. A different approach is to use dense
representations for contrastive learning, where the representation of a group
of pixels of a specific class is used instead of the global representation of
the image. Using dense representations shows better performance for dense
prediction tasks such as object detection [11].

Existing literature on contrastive learning for semantic segmentation explores
several different approaches. The most common is to operate using a two-stage
training process, where the backbone is pre-trained using contrastive learning
and then finetuned for semantic segmentation. Both [21, 22] use generated
auxiliary labels in combination with the ground truth labels to perform
contrastive learning with substantial memory consumption. In contrast, our
work performs end-to-end training without requiring a two-stage process. Other
works, such as [18, 1], are also trained end-to-end. However, they use a
memory bank to store features during training, while our approach chooses
features on the fly. Furthermore, the active sampling in [1] uses class-
specific attention modules, whereas our approach uses ground truth labels to
choose the patches used for contrastive learning. In [11], the authors
introduce a contrastive learning framework for regional learning to assist
semantic segmentation with end-to-end learning and active sampling. Unlike our
approach, they sample key pixels using a class relationship graph, while hard
queries are sampled using the predicted confidence map.

##  3 Contrastive Transformer (CT)

Contrastive Transformer (CT) is a patch-based contrastive learning scheme that
exploits the innate patch-based architecture in vision transformers, resulting
in enhanced semantic representation of classes in a Transformer backbone.
Figure 1 presents a high-level overview of the CT approach. The procedure
involves processing an input image using the transformer backbone. A
contrastive loss is computed between positive and negative samples at each
backbone stage. This generates contrastive feedback at multiple abstraction
levels, allowing for learning from more robust data signals. The contrastive
loss is computed at both the initial and final encoding stages. In addition, a
normal segmentation loss is employed, which jointly optimizes the model. The
CT methodology is straightforward yet highly effective and can be applied to
all Transformer models. Furthermore, it can be paired with most image-based
contrastive learning methods, improving performance for dense prediction
tasks.

Figure 1: CT uses the innate patch representations from each encoder stage and
calculates the contrastive loss between positive and negative samples using
the ground truth mask.

Let $(X,Y)$ represent the training dataset, where $x\in X$ represents the
training images, and $y\in Y$ represents the pixel-level classes in the
dataset. A segmentation network $g$ is trained to learn the mapping
$g_{\theta}:X\rightarrow Y$, where $\theta$ represents the network’s
parameters. The segmentation network $g$ consists of two components, the
backbone $\phi$, which maps $\phi:X\rightarrow Z$, and the decoder $\omega$,
which maps $\omega:Z\rightarrow Y$. To perform patch-level contrastive
learning, we attach a projection head $\psi$ in parallel to the decoder
network on the $\phi$ mapping, where $\psi:Z\rightarrow F$ and $F$ is an
$n$-dimensional representation of $Z$. The projection head only incurs
additional computational costs during training and is removed during
inference.

CT collects all encoder stage patch representations during training and
couples them with the corresponding ground truth. For each encoder stage $s$,
we have feature patches $F_{s}$ and corresponding ground truth patches $G_{s}$
constructed with the same patch size as the feature patches. For each class
$c$ in $G$, we sample positive patches $P_{s}$ and negative patches $N_{s}$
from $F_{s}$. $P_{s}$ are sampled from $F_{s}$ where $G_{s}$ have a homogenous
class distribution of class $c$. Similarly, $N_{s}$ are sampled from $F_{s}$
where class $c$ is not in $G_{s}$. Figure 2 visualizes the sampling process
for positive and negative samples. The positive and negative samples are then
used in a contrastive loss function.

Figure 2: CT contrastive loss module takes the ground truth and constructs
patches the same size as the feature patches for the particular stage.
Furthermore, it uses the ground truth patches to create a mask that defines
the positive and negative patches. Positive patches contain a homogenous class
distribution of the target class. Negative patches can be heterogenous or
homogenous if they do not contain the target class. Finally, the selected
positive and negative patches are used in a contrastive loss function, pulling
the representation of positive patches closer and pushing the representation
of negative patches further away.

###  3.1 Sampling and Loss Functions

Sampling strategies and loss functions are two critical components of
contrastive learning. Firstly, we use a sampling strategy to filter positive
and negative samples for the contrastive loss function. Our experiments use a
naive sampling strategy that randomizes all patches in the batch for both
positive and negative samples. For negative contrastive learning, we calculate
the cosine similarity for a fixed number of the positive and negative pairs,
sort them in descending order, and take the top 50%. For positive contrastive
learning, we split the positive samples into two halves, compute the cosine
similarity, sort them in ascending order, and take the top 50%.

Once the sampling process is complete, we calculate the loss using a
contrastive loss function. Treating each patch as an image allows us to
utilize contrastive loss functions from the image classification literature,
giving us various options. Additionally, each image has many patches split
among multiple stages. Therefore we’re not required to use a large batch size
to collect a sufficient amount of samples for contrastive learning. We use the
InfoNCE [15] and a contrastive loss function in our experiments.

The contrastive loss function (CL) we use takes the positive and negative
samples, calculates the cosine similarity, and normalizes them to be in a
range between 0 and 1, where 0 is dissimilar, and 1 is similar. Then, using
the soft cross-entropy loss function with a smoothing set to 0.1, we calculate
the loss, where the target is 0 for samples from different classes and 1 for
samples from the same class.

##  4 Experiments

This section reveals that CT is able to improve mean IoU on the ISPRS Potsdam
Dataset using image-based contrastive loss functions. Our experimental
evaluation aims to answer these questions:

  * •

How well does a simple approach for transformer-based contrastive learning
compare to state-of-the-art segmentation models?

  * •

What conclusions can we draw about the ability to handle semantic classes
smaller than the smallest patch in the Transformer?

  * •

How does the learning scheme perform with different types of transformer
backbones?

###  4.1 Experimental Setup

We test the effectiveness of our proposed learning scheme on the International
Society for Photogrammetry, and Remote Sensing (ISPRS) Potsdam semantic
labeling dataset [8]. It contains 38 tiles, each of size 6000x6000. Similar to
previous research [10, 2, 12], we use 24 tiles for training and 14 tiles for
testing. We create image tiles of size 500x500 from the original tile and
resize them to 512 for training and testing purposes. We do not use the DSMs
in our experiments, mainly because we want to advance image-based research.

We evaluate CT using DCSwin [16], UnetFormer [17], and the PoolFormer [20]
backbone with the DCSwin [16] decoder. All experiments use a learning rate of
$8e-5$, batch size of $32$, and the AdamW optimizer. We clip both the
gradients and the contrastive loss to $1.0$ to stop the contrastive learning
from being the dominant optimization factor. All experiments use a joint loss
function of soft cross-entropy loss and dice loss. Each experiment is trained
using 50 epochs and averaged across 3 separate runs.

###  4.2 Results

We compare our results with baselines for all models, where the only
difference is the addition of the CT learning scheme. We evaluate CT with
InfoNCE and CL, two popular loss functions for image-based contrastive
learning. Table 1 presents the results for the experiments, displaying
consistent improvements compared to the baselines for at least one of the
contrastive loss functions for each model.

Table 1: Evaluation results on the ISPRS Potsdam dataset for all models. Values in the mIoU column display the average mIoU across all runs with the standard deviation behind in parentheses. The values in the class columns are the average IoU for the class across each run. The results show that CT achieves comparable or better results for all models. _Model_ | _Backbone_ | _Contrastive Loss_ | _mIoU $(\sigma)$_ | _Surface_ | _Building_ | _Vegetation_ | _Tree_ | _Car_ | _Clutter_ | _Source_
---|---|---|---|---|---|---|---|---|---|---
DCSwin (Baseline) | Swin | - | 0.7728 (0.0016) | 0.8284 | 0.8852 | 0.7309 | 0.7292 | 0.6906 | 0.3182 | [16]
DCSwin | Swin | CL | 0.7740 (0.0019) | 0.8303 | 0.8900 | 0.7284 | 0.7267 | 0.6945 | 0.3073 | Ours
DCSwin | Swin | InfoNCE | 0.7730 (0.0013) | 0.8263 | 0.8855 | 0.7257 | 0.7311 | 0.6924 | 0.3200 | Ours
UnetFormer (Baseline) | Swin | - | 0.7687 (0.0011) | 0.8293 | 0.8891 | 0.7218 | 0.7191 | 0.6842 | 0.3153 | [17]
UnetFormer | Swin | CL | 0.7674 (0.0017) | 0.8275 | 0.8874 | 0.7204 | 0.7145 | 0.6874 | 0.3181 | Ours
UnetFormer | Swin | InfoNCE | 0.7715 (0.0006) | 0.8300 | 0.8896 | 0.7266 | 0.7217 | 0.6896 | 0.3337 | Ours
DCPoolFormer (Baseline) | PoolFormer | - | 0.7559 (0.0021) | 0.8113 | 0.8694 | 0.7084 | 0.7053 | 0.6853 | 0.2752 | [16, 20]
DCPoolFormer | PoolFormer | CL | 0.7620 (0.0055) | 0.8155 | 0.8732 | 0.7068 | 0.7108 | 0.6887 | 0.2897 | Ours
DCPoolFormer | PoolFormer | InfoNCE | 0.7625 (0.0068) | 0.8126 | 0.8735 | 0.7076 | 0.7080 | 0.6855 | 0.2701 | Ours

Figure 3 presents the graph for max validation mIoU for the DCPoolFormer model
for each experiment. It visualizes the improvements in mIoU over the training
period, displaying the effectiveness of our approach.

Furthermore, it is worth noting the results for the car class. The approach
outperforms the baselines on the car class, despite the situation that the car
class does not fit into the smallest patch during training. CT is still able
to perform better than the baseline for this class, indicating that it is
sufficient for the class to be present in negative samples to create a better
semantic representation than the baseline.

Figure 3: The validation mIoU graph for DCPoolFormer clearly demonstrate the
performance improvement throughout the training time.

It is also worth mentioning that CT performs well with both the Swin
Transformer and PoolFormer backbone. However, it seems to pair better with the
PoolFormer backbone, which might indicate that the Swin Transformer is better
at representation learning than PoolFormer, but this needs further research.
Thereby we conclude:

  * •

CT performs well with the backbone and improves upon the baselines in all but
one experiment.

  * •

Even though instances of cars are too small to be used as a positive sample
during contrastive learning, the results indicate that it is sufficient to be
part of the negative samples to improve the representation of a class.

  * •

In our experiments, we have used two different transformer-based backbones,
and CT outperforms the baseline with both. However, the results indicate that
it pairs better with the PoolFormer backbone. Further research is necessary to
explore which types of Transformer-based backbones are best fit, and why.

##  5 Conclusion

In this work, we introduce Contrastive Transformer (CT), a novel patch-based
contrastive learning scheme for transformers. We show that CT improves
performance for segmentation transformers when trained end-to-end with an on-
the-fly naive sampling strategy. In particular, we want to highlight the
simplicity of CT and the large potential for future work it introduces. In our
experiments, we show consistent improvements in segmentation results for all
models on the ISPRS Potsdam dataset.

##  6 Future Work

The Contrastive Transformer is a novel mechanism that leverages the inherent
patch characteristics of vision-based transformers. The results demonstrate
the potential to improve the performance and robustness of transformers for
dense prediction tasks. The idea of using innate Transformer patches for
contrastive learning is simple yet novel and warrants further exploration.
This research highlights several avenues for future investigation:

  * •

Investigating the impact of patch size and number of patches used in
contrastive learning on CT’s performance for dense prediction tasks.

  * •

Exploring the use of various augmentation techniques on patches to improve the
quality of learned representations.

  * •

Developing new architectures that can better leverage the representations
learned by contrastive learning.

  * •

Studying the effects of different objective functions on the quality of
learned representations.

  * •

Investigating the use of unsupervised pre-training techniques to initialize
the model before fine-tuning it for specific dense prediction tasks.

  * •

Evaluating the generalization capability of learned representations across
different datasets and domains.

Another interesting avenue for study is sampling techniques in CT. Preliminary
studies indicate that attention could be useful for selecting the most
influential patches for each stage in a batch, with work from [19] serving as
a key accelerator. Another promising approach is to explore how patches
containing a heterogeneous class distribution of positive and negative classes
can be utilized. Hard samples are often present around the edges of two
different semantic classes, and including them in the learning scheme can have
a positive impact on the results.

## References

  * [1] I. Alonso, A. Sabater, D. Ferstl, L. Montesano, and A. C. Murillo.  Semi-Supervised Semantic Segmentation With Pixel-Level Contrastive Learning From a Class-Wise Memory Bank, 2021.
  * [2] N. Audebert, B. Le Saux, and S. Lefèvre.  Beyond RGB: Very high resolution urban remote sensing with multimodal deep networks.  ISPRS Journal of Photogrammetry and Remote Sensing, 140:20–32, 6 2018.
  * [3] T. Chen, S. Kornblith, M. Norouzi, and G. E. Hinton.  A Simple Framework for Contrastive Learning of Visual Representations.  ArXiv, 2020.
  * [4] S. D. Dao, E. Zhao, D. Phung, and J. Cai.  Multi-Label Image Classification with Contrastive Learning.  ArXiv, 2021.
  * [5] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby.  An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale.  In Proceedings of the 9th International Conference on Learning Representations (ICLR), pages 1–21, 10 2021.
  * [6] F. Duman Keles, P. Mahesakya Wijewardena, C. Hegde, S. Agrawal, and F. Orabona.  On The Computational Complexity of Self-Attention, 2 2023.
  * [7] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick.  Momentum Contrast for Unsupervised Visual Representation Learning, 2020\.
  * [8] isprs.org.  ISPRS Potsdam Dataset.
  * [9] K. Li, Y. Wang, J. Zhang, P. Gao, G. Song, Y. Liu, H. Li, and Y. Qiao.  UniFormer: Unifying Convolution and Self-attention for Visual Recognition.  ArXiv, 1 2022.
  * [10] Q. Liu, M. Kampffmeyer, R. Jenssen, and A. B. Salberg.  Dense dilated convolutions merging network for land cover classification.  IEEE Transactions on Geoscience and Remote Sensing, 58(9):6309–6320, 9 2020.
  * [11] S. Liu, S. Zhi, E. Johns, and A. J. Davison.  Bootstrapping Semantic Segmentation with Regional Contrast.  ArXiv, 4 2021.
  * [12] Y. Liu, B. Fan, L. Wang, J. Bai, S. Xiang, and C. Pan.  Semantic labeling in very high resolution images via a self-cascaded convolutional neural network.  ISPRS Journal of Photogrammetry and Remote Sensing, 145:78–95, 11 2018.
  * [13] Z. Liu, H. Hu, Y. Lin, Z. Yao, Z. Xie, Y. Wei, J. Ning, Y. Cao, Z. Zhang, L. Dong, F. Wei, and B. Guo.  Swin Transformer V2: Scaling Up Capacity and Resolution, 2022.
  * [14] O. Ronneberger, P. Fischer, and T. Brox.  U-net: Convolutional networks for biomedical image segmentation.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9351:234–241, 2015.
  * [15] A. van den Oord DeepMind, Y. Li DeepMind, and O. Vinyals DeepMind.  Representation Learning with Contrastive Predictive Coding.  ArXiv, 7 2018.
  * [16] L. Wang, R. Li, C. Duan, C. Zhang, X. Meng, and S. Fang.  A Novel Transformer Based Semantic Segmentation Scheme for Fine-Resolution Remote Sensing Images.  IEEE Geoscience and Remote Sensing Letters, 19, 2022.
  * [17] L. Wang, R. Li, C. Zhang, S. Fang, C. Duan, X. Meng, and P. M. Atkinson.  UNetFormer: A UNet-like transformer for efficient semantic segmentation of remote sensing urban scene imagery.  ISPRS Journal of Photogrammetry and Remote Sensing, 190:196–214, 8 2022.
  * [18] W. Wang, T. Zhou, F. Yu, J. Dai, E. Konukoglu, and L. Van Gool.  Exploring Cross-Image Pixel Contrast for Semantic Segmentation, 2021\.
  * [19] Z. Xia, X. Pan, S. Song, L. E. Li, and G. Huang.  Vision Transformer With Deformable Attention, 2022.
  * [20] W. Yu, M. Luo, P. Zhou, C. Si, Y. Zhou, X. Wang, J. Feng, and S. Yan.  MetaFormer Is Actually What You Need for Vision, 2022.
  * [21] F. Zhang, P. Torr, R. Ranftl, and S. R. Richter.  Looking Beyond Single Images for Contrastive Semantic Segmentation Learning.  Advances in Neural Information Processing Systems, 34:3285–3297, 12 2021.
  * [22] X. Zhao, R. Vemulapalli, P. A. Mansfield, B. Gong, B. Green, L. Shapira, and Y. Wu.  Contrastive Learning for Label Efficient Semantic Segmentation, 2021\.