$X\subseteq\\{0,1\\}^{\omega}$, $f(X)$ is infinite.

(2) For every $f\in{\sf tot}M_{k,1}$ and for every finite set $H\subseteq
A^{\omega}$ such that $\,|H|>|{\rm domC}(f)|:$

$|f(H)|\,>\,|H|/|{\rm domC}(f)|$.

Proof. (1) Since $P={\rm domC}(f)$ is a finite maximal prefix code, we have:
$\,PA^{\omega}=A^{\omega}$. Hence, $X\cap PA^{\omega}=X$ is infinite.
Therefore (since $P$ is finite), there exists $p\in P$ such that
$X\,\cap\,p\,A^{\omega}$ is infinite, hence
$\,X\,\cap\,p\,A^{\omega}\,=\,p\,S$, where $S$ is an infinite subset of
$A^{\omega}$. Then $f(X)$ contains the infinite set $\,f(pS)=f(p)\ S$.

(2) Let $P={\rm domC}(f)$; this is a finite maximal prefix code, so
$\,P\,A^{\omega}=A^{\omega}$. There exists $p\in P$ such that $\,|H\cap
p\,A^{\omega}|\geq|H|/|P|$. Indeed, otherwise we would have $\,|H\cap
p\,A^{\omega}|<|H|/|P|\,$ for all $p\in P$; this would imply $\,(|H|=)\ |H\cap
P\,A^{\omega}|$ $\,\leq\,$ $\sum_{p\in P}|H\cap p\,A^{\omega}|$ $\,<\,$
$\sum_{p\in P}|H|/|P|$ $=$ $|P|\,(|H|/|P|)=|H|$; this would imply $\,|H|<|H|$.

For $p\in P$ such that $\,|H\cap p\,A^{\omega}|\geq|H|/|P|$, let

$H\cap p\,A^{\omega}\,=\,$ $p\ \\{s_{i}\ :\ i=1,\ \ldots\ ,\ |H|/|P|,\
|H|/|P|+1,\ \ldots\ \\}$,

where all $s_{i}\,$ $(\in A^{\omega})$ are different. Then $f(H)$ has the
subset

$f(p)\ \\{s_{i}\ :\ $ $i=1,\ \ldots\ ,\ |H|/|P|,\ |H|/|P|+1,\ \ldots\ \\}$,

so $\ |f(H)|>|H|/|P|$. $\Box$

###### Lemma 8.3

Let $g$ be any non-torsion element of $\,{\sf tot}M_{k,1}\,$ (i.e.,
$\\{g^{i}:i\in\omega\\}$ is infinite). Then for all $N>0$ there exists $u\in
A^{\omega}$ such that $|\\{g^{i}(u):i\geq 0\\}|>N$.

Proof. By contraposition we assume that there exists $N>0$ such that for all
$u\in A^{\omega}:$ $\ |\\{g^{i}(u):i\geq 0\\}|\leq N$. Since
$\,|\\{g^{i}(u):i\geq 0\\}|\,$ is finite, there exist $n,m\,$ (depending on
$u$) such that $g^{n}(u)=g^{n+m}(u)$, and $\,0\leq n<n\\!+\\!m\leq N$. Hence,
letting $M=N!$ we have for all $u$: $\ g^{M}(u)=g^{2M}(u)$. So, $g$ is a
torsion element. $\Box$

###### Lemma 8.4

If $S$ is a subsemigroup of $\,{\sf tot}M_{k,1}$ that contains a non-torsion
element, then $S$ has no left-zero.

Proof. Let $g\in S$ be a non-torsion element. Let us assume, for a
contradiction, that $S$ has a left-zero $z\,$ (i.e., $z\,s(.)=z(.)\,$ for all
$s\in S$). Then $\,z\,g^{i}(.)=z(.)\,$ for all $i\geq 0$. Let $P={\rm
domC}(z)$, and let $\,N>2\,|P|$. By Lemma 8.3, there exists $u\in A^{\omega}$,
such that $\,|\\{g^{i}(u):i\geq 0\\}|>N$. By Lemma 8.2,
$\,|z(\\{g^{i}(u):i\geq 0\\})|>N/|P|$; and $N$ can be chosen so that
$N/|P|\geq 2$. On the other hand, $\,zg^{i}(.)=z(.)$, so $\
|z(\\{g^{i}(u):i\geq 0\\})|=|\\{z(u)\\}|=1$. This leads to the false statement
$1\geq 2$. $\Box$

As a consequence, ${\sf tot}M_{k,1}$ itself has no left-zero (and hence no
zero). However, some subsemigroups have left-zeros.

Proof of Theorem 8.1:

The monoids ${\sf plep}M_{h,1}$ and $M_{h,1}$ contain a zero (namely the empty
map), and non-torsion elements (e.g., the element represented by the right-
ideal morphism $(\varepsilon\to 0)$).

Assume, for a contradiction, that $M_{h,1}$ (or ${\sf plep}M_{h,1}$) is
embeddable in ${\sf tot}M_{k,1}$. An embedding preserves non-torsion elements,
and the zero in the image submonoid. So the embedded copy of $M_{h,1}$ (or
${\sf plep}M_{h,1}$) in ${\sf tot}M_{k,1}$ is a subsemigroup with a left zero
and a non-torsion element. But this contradicts Lemma 8.4. $\Box$

Theorem 8.1 for $k\geq 3$ and $h=2$ can also be derived in an interesting way
from Theorem 8.1 for $k=2$. First, a Lemma and a Proposition that are of
independent interest are proved:

###### Lemma 8.5

.

For any finite maximal prefix code $C\subseteq\\{0,1\\}^{*}$ such that
$|C|\geq 2$ we have: $\\{0,1\\}^{\omega}\,=\,C^{\omega}$.

Proof. Obviously, $C^{\omega}\subseteq\\{0,1\\}^{\omega}$. Conversely, let us
show that any $z=(z_{i}:i\in\omega)\,$ (with $z_{i}\in$ $\\{0,1\\}$) is
factored in a unique way over $C$. Let $\ell={\rm maxlen}(C)$. Since $C$ is
maximal, $z$ has a unique prefix $c_{1}\in C$, of length $|c_{1}|=l_{1}$ with
$1\leq l_{1}\leq\ell$; so $\,z=c_{1}z_{l_{1}}\,\ldots\,$. Suppose now, by
induction, that a prefix of length $\,\geq n$ of $z$ has been factored over
$C$; i.e., $\,z=c_{1}\,\ldots\,c_{n}\,z_{l_{n}}\,\ldots\,$, where
$c_{1},\,\ldots\,,c_{n}\in C$ with $|c_{1}\,\ldots\,c_{n}|=l_{n}\geq n$. Then
$\,z_{l_{n}}\,\ldots\,z_{l_{n}+\ell}$ has a prefix in $C$; let us denote this
element of $C$ by $c_{n+1}$, with $|c_{1}\,\ldots\,c_{n}c_{n+1}|=$ $l_{n+1}$.
Then $\,z=c_{1}\,\ldots\,c_{n}c_{n+1}\,z_{l_{n+1}}\,\ldots\,$.

Moreover, every finite prefix of $z$ can be factored in at most one way over
$C$, since $C$ is a prefix code. $\Box$

However, $C^{*}\neq\\{0,1\\}^{*}\,$ unless $C=\\{0,1\\}$.

###### Proposition 8.6

For every $k\geq 3$, $\ M_{k,1}$ is embeddable into $M_{2,1}$, and $\,{\sf
tot}M_{k,1}$ is embeddable into $\,{\sf tot}M_{2,1}$.

Proof. This is proved in the same way as $G_{k,1}$ is embedded into $G_{2,1}$,
using Higman’s coding method. Let $A=$ $\\{0,1,\,\ldots\,,k\\!-\\!1\\}$, let
$C\subseteq\\{0,1\\}^{*}$ be any maximal prefix code of cardinality $|C|=k$,
and let $\,\eta:\,i\in A$ $\longmapsto$ $\eta(i)\in C\,$ be any bijection. For
any $x=x_{1}\,\ldots\,x_{n}\in A^{*}$ with $x_{i}\in$ $A$, consider the coding
$\eta(x)=$ $\eta(x_{1})\,\ldots\,\eta(x_{n})$ $\in
C^{*}\subseteq\\{0,1\\}^{*}$; then $\eta:A^{*}\to\\{0,1\\}^{*}$ is an
injective monoid morphism. For $x=x_{1}\,\ldots\,x_{n}\,\ldots\ \in
A^{\,\omega}$ with $x_{i}\in A$ we define $\eta(x)=$
$\eta(x_{1})\,\ldots\,\eta(x_{n})$ $\,\ldots\ $ $\in C^{\omega}$; since $C$ is
a maximal prefix code of $\\{0,1\\}^{*}$ we have
$\,C^{\omega}=\\{0,1\\}^{\omega}\,$ (by Lemma 8.5).

For any $f\in{\sf tot}M_{k,1}$ let $P={\rm domC}(f)$. This is a finite prefix
code of $A^{*}$, which is maximal if $f\in{\sf tot}M_{k,1}$. Then $\eta(P)$ is
a finite prefix code of $\\{0,1\\}^{*}$, which is maximal if $P$ is maximal.
We encode $f$ by $f^{\eta}\in$ ${\sf tot}M_{2,1}$, defined by

$f^{\eta}(\eta(x))=\eta(f(x))$

for every $x\in A^{*}\cup A^{\,\omega}$. Equivalently, for every $z\in
C^{*}\cup C^{\omega}$, $\ f^{\eta}(z)=\eta\circ f\circ\eta^{-1}(z)$; recall
that $\,\eta:A^{*}\cup A^{\omega}\to C^{*}\cup C^{\omega}\,$ is total and
injective.

Then $f^{\eta}\in M_{2,1}$ (and $f^{\eta}\in{\sf tot}M_{2,1}$ if $f\in{\sf
tot}M_{k,1}$), with ${\sf domC}(f^{\eta})=\eta(P)$. And $f\mapsto f^{\eta}$ is
a monoid morphism $\,M_{k,1}\to M_{2,1}\,$ and $\,{\sf tot}M_{k,1}\to{\sf
tot}M_{2,1}$, since $\,(gf)^{\eta}=\eta gf\eta^{-1}$ $=$ $\eta g\eta^{-1}\eta
f\eta^{-1}=g^{\eta}f^{\eta}$. And $f\mapsto f^{\eta}$ is injective since
$\eta$ and $\eta^{-1}$ are injective $\Box$

Proof of Theorem 8.1 for $k\geq 3$ and $h=2$, derived from Theorem 8.1 for
$k=2$:

Assume for a contradiction that $M_{2,1}$ is embeddable in ${\sf tot}M_{k,1}$.
By Prop. 8.6, ${\sf tot}M_{k,1}$ is embeddable into ${\sf tot}M_{2,1}$. Now,
$M_{2,1}\hookrightarrow{\sf tot}M_{k,1}$ $\hookrightarrow{\sf tot}M_{2,1}$, so
$M_{2,1}\hookrightarrow$ ${\sf tot}M_{2,1}$. This contradicts the Theorem for
$k=2$. $\Box$

##  9 Completion operations for $M_{2,1}$, $\,{\sf pfl}M_{2,1}$, $\,{\cal
RM}^{\sf fin}$, and $\,{\sf pfl}{\cal RM}^{\sf fin}$

The goal of a completion operation of a partial function $f$ is to find a
total function $\overline{f}$, such that $f$ can be recovered from
$\overline{f}$ and ${\rm Dom}(f)$. A completion operation
$\,\overline{(.)}:f\to\overline{f}\,$ may be a function (i.e., only one
$\overline{f}$ is found for each $f$); we call this a deterministic
completion. A completion operation could also be a relation (if $f$ is
completed in several ways); we call this a nondeterministic completion.

Theorem 8.1 is a non-completability result. This section gives several forms
of completability.

We work with the monoids of right-ideal morphisms ${\cal RM}^{\sf fin}$ and
${\sf pfl}{\cal RM}^{\sf fin}$; the corresponding results for $M_{2,1}$ and
${\sf pfl}M_{2,1}$ then hold too. Below, for any $h\geq 2$, $\,{\cal
RM}_{h}^{\sf fin}$ denotes the monoid ${\cal RM}^{\sf fin}$ of right-ideal
morphisms $A^{*}\to A^{*}$ for an alphabet $A$ of size $|A|=h$.

The following concept is used in all of our completion constructions.

###### Definition 9.1

(complementary prefix code). For a prefix code $P\subseteq A^{*}$, a
complementary prefix code of $P$ is a prefix code $Q\subseteq A^{*}$ such that
(1) $\,P\cup Q\,$ is a maximal prefix code, and (2) $\,PA^{*}\cap
QA^{*}=\varnothing$.

Every finite prefix code has finite complementary prefix codes. See [3, Def.
5.2], [8, Def. 3.29, Lemma 3.30], and also [14, Prop. 5.2].

###  9.1 Deterministic completion

###### Definition 9.2

A deterministic completion operation of $\,{\cal RM}_{h}^{\sf fin}\,$ in
$\,{\sf tot}{\cal RM}_{k}^{\sf fin}\,$ (and similarly of $M_{h,1}$ in ${\sf
tot}M_{k,1}$) is a total function

$\overline{(.)}:\,f\in{\cal RM}_{h}^{\sf fin}$ $\,\longmapsto\,$
$\overline{f}\in{\sf tot}{\cal RM}_{k}^{\sf fin}$,

together with a function

$\varrho:$ $\\{\,\overline{f}:f\in{\cal RM}_{h}^{\sf fin}\\}\,\subseteq$ ${\sf
tot}{\cal RM}_{k}^{\sf fin}$ $\ \longmapsto\ {\cal RM}_{h}^{\sf fin}$,

such that for all $f\in{\cal RM}_{h}^{\sf fin}$:

$f\,\subseteq\,\varrho(\,\overline{f}\,)$.

In other words, for all $x\in$ ${\rm Dom}(f)$:
$f(x)=\big{[}\varrho(\,\overline{f}\,)\big{]}(x)$.

A completion is called homomorphic iff for all $\,f_{2},f_{1}\in{\cal
RM}_{h}^{\sf fin}$: $\overline{f_{2}\cdot
f_{1}}(.)\,=\,\overline{f}_{2}\cdot\overline{f}_{1}(.)$. By Theorem 8.1, there
exists no injective homomorphic completion of $M_{h,1}$.

We give two examples of deterministic completions.

1\. A classical completion operation for ${\sf pfl}{\cal RM}_{2}^{\sf fin}$
and ${\cal RM}_{2}^{\sf fin}$

For $f\in{\sf pfl}{\cal RM}_{2}^{\sf fin}$ with ${\rm domC}(f)$ $\subseteq$
$\\{0,1\\}^{m}\,$ and $\,{\rm imC}(f)\subseteq$ $\\{0,1\\}^{n}$, we can define
a completion $\tilde{f}\in$ ${\sf tfl}{\cal RM}_{2}^{\sf fin}$ as follows:

${\rm domC}(\tilde{f})\,=\,\\{0,1\\}^{m}$, ${\rm imC}(\tilde{f})\,=\,{\rm
imC}(f)\cup\\{0^{n}\\}$ $\,\subseteq\,\\{0,1\\}^{n}$,

and for all $x\in\\{0,1\\}^{m}:$

$\tilde{f}(x)=f(x)$ if $x\in{\rm domC}(f)$,

$\tilde{f}(x)=0^{n}$ if $x\in$ $\\{0,1\\}^{m}\smallsetminus{\rm domC}(f)$.

More generally, for $f\in{\cal RM}^{\sf fin}$ we can define a completion
$\tilde{f}\in$ ${\sf tot}{\cal RM}^{\sf fin}$ as follows:

${\rm domC}(\tilde{f})\,=\,{\rm domC}(f)\,\cup\,Q$,

where $Q$ is a finite complementary prefix code of ${\rm domC}(f)$ in $A^{*}$.
For all $x\in P\cup Q$,

$\tilde{f}(x)=f(x)$ if $x\in{\rm domC}(f)=P$,

$\tilde{f}(x)=0$ if $x\in Q$.

Hence, $f\subseteq\tilde{f}$; so for the function $\varrho$ we can just pick
the identity function, i.e., $\varrho(\tilde{f})=\tilde{f}$. Then we have:
$\,f=\tilde{f}\ $ iff $\ f$ is total (i.e., ${\rm domC}(f)$ is a maximal
prefix code); hence $\tilde{\tilde{f}}=\tilde{f}$.

The completion operation $\widetilde{(.)}$ is not injective. In particular,
$\,\tilde{f}_{1}$ $=$ $\tilde{f}_{2}\,$ if the following two conditions hold:
(1) $\,f_{1}\subseteq f_{2}$; (2) if $f_{1}(x)$ is undefined then $f_{2}(x)$
is undefined or $f_{2}(x)\in 0A^{*}$.

The operation $\widetilde{(.)}$ is not homomorphic. For example, if $f=(1\to
0)$ and $g=(0\to 1)$ with $A=\\{0,1\\}$, then $gf(.)=(1\to 1)$, so
$\,\widetilde{gf}(.)$ $=$ ${\mathbb{1}}_{\\{0,1\\}}$. And $\tilde{f}$ has the
table $\\{(1,0),(0,0)\\}$ and $\tilde{g}$ has the table $\\{(0,1),(1,0)\\}$,
so $\tilde{g}\,\tilde{f}(.)$ has the table $\\{(0,1),(1,1)\\}$. Hence
$\,\widetilde{gf}(.)$ $\neq$ $\tilde{g}\,\tilde{f}(.)$.

Before describing another completion we give a preliminary construction. For
any prefix code $P\subseteq\\{0,1\\}^{*}$, $\ {\sf spref}(P)\,$ denotes the
set of strict prefixes of the elements of $P$ (i.e., the prefixes not in $P$).

###### Lemma 9.3

(expanding a maximal prefix code to a larger alphabet).

Let $\\{0,1,2\\}$ be a 3-letter alphabet. If $P$ is a finite prefix code in
$\\{0,1\\}^{*}$ then

$P\,\cup\,({\sf spref}(P))\,2\,$

is a finite prefix code in $\\{0,1,2\\}^{*}$, which is maximal in
$\\{0,1,2\\}^{*}\,$ iff $\,P$ is maximal in $\\{0,1\\}^{*}$.

Proof. See [3, Lemma 9.1] and [13, Lemma 1.5].) $\Box$

2\. An injective non-homomorphic completion of ${\cal RM}_{2}^{\sf fin}$ or of
$M_{2,1}$

Every element $f\in{\cal RM}_{2}^{\sf fin}$ (or of $M_{2,1}$) is completed to
an element $\overline{f}\in$ ${\sf tot}{\cal RM}_{2}^{\sf fin}$ (or in ${\sf
tot}M_{2,1}$) as follows. We first choose a finite complementary prefix code
$\,Q\subseteq\\{0,1\\}^{*}$ of $\,{\rm domC}(f)$. Then $\,P=$ ${\rm
domC}(f)\,\cup\,Q$, ($\subseteq$ $\\{0,1\\}^{*}$) is a finite maximal prefix
code of $\\{0,1\\}^{*}$, and $\ P\,\cup\,({\sf spref}(P))\,\bot\,$ is a finite
maximal prefix code of $\\{0,1,\bot\\}^{*}$ (by Lemma 9.3). Now $\overline{f}$
is the right-ideal morphism of $\\{0,1,\bot\\}^{*}$ defined as follows:

${\rm domC}(\overline{f})\,=\,{\rm domC}(f)\,\cup\,Q$ $\,\cup\,$ $\big{(}{\sf
spref}({\rm domC}(f)\,\cup\,Q)\big{)}\cdot\bot\,$;

$\overline{f}(x)\,=\,f(x)$ if $x\in{\rm domC}(f)$;

$\overline{f}(x)\,=\,\bot$ if $x\in Q$ $\,\cup\,$ $\big{(}{\sf spref}({\rm
domC}(f)\,\cup\,Q)\big{)}\cdot\bot\,$.

The function $f\in{\cal RM}_{2}^{\sf fin}$ $\longmapsto$ $\overline{f}$ $\in$
${\sf tot}{\cal RM}_{3}^{\sf fin}\,$ is total and injective; it is not a
monoid morphism, since $M_{2,1}$ is not embeddable into ${\sf tot}M_{3,1}\,$
(by Theorem 8.1). Taking $\varrho$ to be the identity function, we obtain a
completion $\,\overline{(.)}:$ ${\cal RM}_{2}^{\sf fin}\to{\sf tot}{\cal
RM}_{3}^{\sf fin}\,$ (and $M_{2,1}\to{\sf tot}M_{3,1}$).

By encoding the elements of ${\sf tot}{\cal RM}_{3}^{\sf fin}$ as in Prop.
8.6, $\,{\sf tot}{\cal RM}_{3}^{\sf fin}$ is embedded into ${\sf tot}{\cal
RM}_{2}^{\sf fin}$. This yields a (non-homomorphic) completion of ${\cal
RM}_{2}^{\sf fin}$ in ${\sf tot}{\cal RM}_{2}^{\sf fin}$. Taking $\varrho$ to
be the inverse of the embedding function $\,{\sf tot}{\cal RM}_{3}^{\sf
fin}\to{\sf tot}{\cal RM}_{2}^{\sf fin}$, we obtain a completion
$\,\overline{(.)}:{\cal RM}_{2}^{\sf fin}\to$ ${\sf tot}{\cal RM}_{2}^{\sf
fin}$.

Although deterministic completions are simple and fairly natural, they have
some drawbacks: They cannot be made homomorphic (if they are injective). It is
difficult to compute $\overline{f}$ or $\tilde{f}\,$ if $f$ is given by a
sequence of generators (in $\Gamma$ or in $\Gamma\cup\tau$); even when $f$ is
given by a table, it is difficult to find $\overline{f}$ or $\tilde{f}\,$
because we do not have an efficient method for finding a complementary prefix
code.

###  9.2 Inverse homomorphic completion

We construct a general completion operation that has (inverse) homomorphic
properties, and that provides an efficient computation of $\overline{f}\,$ as
a word of generators, if $f$ is given by a word of generators. Here we will
work with $M_{h,1}$, not with ${\cal RM}_{h}^{\sf fin}$.

###### Definition 9.4

(completion defined by an inverse homomorphism).

(1) An inverse homomorphic completion of $M_{h,1}$ in ${\sf tot}M_{k,1}$ is a
surjective semigroup homomorphism

$\varrho:\ {\rm Dom}(\varrho)\,\subseteq\,$ ${\sf tot}M_{k,1}\
\twoheadrightarrow\ M_{h,1}={\rm Im}(\varrho)$.

The inverse homomorphic completion of ${\sf plep}M_{2,1}$ in ${\sf
tlep}M_{2,1}$ is defined is the same way as for $M_{2,1}$ in ${\sf
tot}M_{2,1}$.

(2) A completion of $f\in M_{2,1}$ (or ${\sf plep}M_{2,1}$) is the choice of
any element in $\varrho^{-1}(f)$.

The homomorphism $\varrho$ is an inverse completion; one could also call it a
“completion removal operation”, or an “un-completion”. The completion of $f$
is nondeterministic (being a choice within $\varrho^{-1}(f)$, whereas the
inverse completion $\varrho(f)$ is deterministic.

Remark: A more general inverse homomorphic completion of $M_{h,1}$ in ${\sf
tot}M_{k,1}\,$ can be defined by a semigroup homomorphism (not necessarily
surjective) $\varrho:\,$ ${\rm Dom}(\varrho)\ (\,\subseteq\,{\sf tot}M_{k,1})\
\to\ M_{h,1}$, such that for every $f\in M_{h,1}$ there exists $s\in{\rm
Dom}(\varrho)$ satisfying $f\,\subseteq\,\varrho(s)$.

###### Theorem 9.5

(inverse homomorphic completion).

(1) The monoid $M_{2,1}$ is a homomorphic image of a submonoid of $\,{\sf
tot}M_{2,1}$. More precisely,

$f\,\in\,F_{0}\,=\,$ ${\sf Fix}_{{\sf
tot}M_{2,1}}\\!(0\\!\cdot\\!\\{0,1\\}^{\omega})$ $\ \ (\,\subseteq\,{\sf
tot}M_{2,1})$

$\stackrel{{\scriptstyle\rho}}{{\twoheadrightarrow}}$ $f\ \cap\
1\,\\{0,1\\}^{\omega}\\!\times\\!1\,\\{0,1\\}^{\omega}$

$\in\ $ $\big{\\{}\,(f$ $\,\cap\,$
$1\,\\{0,1\\}^{\omega}\\!\times\\!1\,\\{0,1\\}^{\omega})$ $\,\in
M_{2,1}\,:\,f\in F_{0}\big{\\}}$

$\stackrel{{\scriptstyle\iota}}{{\to}}$ $M_{2,1}\,$,

where

${\sf Fix}_{{\sf tot}M_{2,1}}\\!(0\\!\cdot\\!\\{0,1\\}^{\omega})$ $\,=\,$
$\\{f\in{\sf tot}M_{2,1}:\,$ $(\forall
z\in\\{0,1\\}^{\omega})\,[\,f(0z)=0z\,]\,\\}$ (fixator);

$\rho$ is a surjective monoid homomorphism;

$\iota$ is a monoid isomorphism;

$\,\varrho=\iota\circ\rho:\,F_{0}\twoheadrightarrow M_{2,1}\,$ is a surjective
monoid homomorphism.

The restriction of $\varrho$ to $\,\varrho^{-1}({\sf tot}M_{2,1})\,$ is
injective, i.e., elements of ${\sf tot}M_{2,1}$ have a unique completion.

(2) The monoid ${\sf plep}M_{2,1}$ is a homomorphic image of a submonoid of
$\,{\sf tlep}M_{2,1}$. More precisely,

$f\,\in\,S_{0}\,=\,$ ${\sf Stab}_{{\sf
tlep}M_{2,1}}\\!(0\\!\cdot\\!\\{0,1\\}^{\omega})$ $\ \ (\,\subseteq\,{\sf
tlep}M_{2,1})$

$\stackrel{{\scriptstyle\rho}}{{\twoheadrightarrow}}$ $\big{\\{}\,(f$
$\,\cap\,$ $1\,\\{0,1\\}^{\omega}\\!\times\\!1\,\\{0,1\\}^{\omega})$
$\,\in{\sf plep}M_{2,1}\,:\,f\in S_{0}\big{\\}}$

$\stackrel{{\scriptstyle\iota}}{{\to}}$ ${\sf plep}M_{2,1}\,$,

where

${\sf Stab}_{{\sf tlep}M_{2,1}}\\!(0\\!\cdot\\!\\{0,1\\}^{\omega})$ $\,=\,$
$\\{f\in{\sf tlep}M_{2,1}:\,$ $(\forall z\in\\{0,1\\}^{\omega})\,[\,f(0z)\in
0\,\\{0,1\\}^{\omega}\,]\,\\}$ (stabilizer);

$\iota$ and $\varrho\,$ are as in (1)

(3) The same results hold for ${\cal RM}^{\sf fin}$ (instead of $M_{2,1}$),
and ${\sf pfl}{\cal RM}^{\sf fin}$ (instead of ${\sf plep}M_{2,1}$).

Proof. In (1) the proof works in the same way for ${\cal RM}^{\sf fin}$ and
${\sf tot}{\cal RM}^{\sf fin}$ as for $M_{2,1}$ and ${\sf tot}M_{2,1}$. And in
(2) the proof works in the same way for ${\sf pfl}{\cal RM}^{\sf fin}$ and
${\sf tfl}{\cal RM}^{\sf fin}$ as for ${\sf plep}M_{2,1}$ and ${\sf
tlep}M_{2,1}$. We only give the proof for $M_{2,1}$ and ${\sf plep}M_{2,1}$.
For ${\cal RM}^{\sf fin}$, $\\{0,1\\}^{\omega}$ is replaced by
$\\{0,1\\}^{*}$.

(1) A function $f\in{\sf tot}M_{2,1}$ belongs to the fixator $F_{0}$ iff $\,f$
has a table of the form

$\left[\begin{array}[]{ccccccc}0&1x_{1}&\ldots&1x_{k}&1x^{\prime}_{1}&\
\ldots&1x^{\prime}_{h}\\\ 0&1y_{1}&\ldots&1y_{k}&0y^{\prime}_{1}&\
\ldots&0y^{\prime}_{h}\end{array}\right]\,,$

where $\ {\rm domC}(f)=\\{0\\}\,\cup\,1P\,\cup\,1P^{\prime}$, and where
$P=\\{x_{1},\,\ldots\,,x_{k}\\}$,
$P^{\prime}=\\{x^{\prime}_{1},\,\ldots\,,x^{\prime}_{h}\\}\,$ are any finite
prefix codes such that
$P\,\\{0,1\\}^{*}\,\cap\,P^{\prime}\,\\{0,1\\}^{*}=\varnothing$. Moreover,
$\,\\{y_{1},\,\ldots\,,y_{k}\\}\,$ is any set of size $\,\leq|P|$, and
$\,\\{y^{\prime}_{1},\,\ldots\,,y^{\prime}_{h}\\}\,$ is any set of size
$\,\leq|P^{\prime}|$. Since $f$ is total, ${\rm domC}(f)$ is a maximal finite
prefix code; hence, $P\cup P^{\prime}$ is a maximal finite prefix code, so
$P^{\prime}$ is a complementary finite prefix code of $P$.

The function $\,f^{\rho}\,=\,(f$ $\,\cap\,$
$1\,\\{0,1\\}^{\omega}\\!\times\\!1\,\\{0,1\\}^{\omega})\,\in\,M_{2,1}$ is
such that $f^{\rho}$ is undefined if the input, or the output, is in
$\,0\,\\{0,1\\}^{\omega}$. Thus the table of $f^{\rho}\,$ is

$f^{\rho}\ =\ \left[\begin{array}[]{ccc}1x_{1}&\ldots&1x_{k}\\\
1y_{1}&\ldots&1y_{k}\end{array}\right].$

The image set of $\rho$ is the set of all elements of $M_{2,1}$ that have a
table of the above form for $f^{\rho}\ $ (since $P$ can be any finite prefix
code),

The function

$\iota:\ \left[\begin{array}[]{ccc}1x_{1}&\ldots&1x_{k}\\\
1y_{1}&\ldots&1y_{k}\end{array}\right]\ \ \longmapsto\ \
\left[\begin{array}[]{ccc}x_{1}&\ldots&x_{k}\\\
y_{1}&\ldots&y_{k}\end{array}\right]$

is an isomorphism from $\rho(F_{0})$ onto $M_{2,1}$. It is surjective because
$\\{(x_{1},y_{1}),$ $\,\ldots\,,$ $(x_{k},y_{k})\\}$ can be the table of any
element of $M_{2,1}$. (Remark: The function $\rho$ could also be defined on
all of ${\sf tot}M_{2,1}$, but then it would not be a homomorphism, since
${\sf tot}M_{2,1}$ is congruence-simple.)

Let us prove that the restriction of $\varrho$ to $\,\varrho^{-1}({\sf
tot}M_{2,1})\,$ is injective: If
$\varphi=\\{(x_{1},y_{1}),\,\ldots\,,(x_{k},y_{k})\\}$ is the table of an
element of ${\sf tot}M_{2,1}$ then $P=\\{x_{1},\,\ldots\,,y_{k}\\}$ is a
maximal prefix code, and $P^{\prime}=\varnothing$. Hence
$\varrho^{-1}(\varphi)$ consists of just the element given by the table
$\,\\{(0,0),(1x_{1},1y_{1}),\,\ldots\,,(1x_{k},1y_{k})\\}$.

We still need to prove the following.

Claim: $\rho:\,f\in F_{0}\longmapsto f^{\rho}$ $\in\rho(F_{0})$ is a semigroup
homomorphism.

Proof of Claim: For $g,f\in F_{0}$ and $x\in\\{0,1\\}^{\omega}$ there are
several cases. We use parentheses $(.)$ for application of functions, and we
use brackets $[.]$ for grouping in the composition of functions.

$\circ$ $x,\,f(x)\in 1\,\\{0,1\\}^{\omega}:$

Then $\,g^{\rho}(f^{\rho}(x))=g^{\rho}(f(x))=g(f(x))$. Since $gf$ is total,
$g(f(x))$ belongs either to $1\,\\{0,1\\}^{\omega}$ or to
$0\,\\{0,1\\}^{\omega}$.

If $\,g(f(x))\in 1\,\\{0,1\\}^{\omega}$ then $g(f(x))=[gf]^{\rho}(x)$. Hence
$g^{\rho}(f^{\rho}(x))=[gf]^{\rho}(x)$.

If $\,g(f(x))\in 0\,\\{0,1\\}^{\omega}$ then $[gf]^{\rho}(x)$ is undefined.
Moreover, $g^{\rho}(f^{\rho}(x))$ $=$ $g(f(x))\in 0\,\\{0,1\\}^{\omega}$,
i.e., the image of $f(x)$ under $g$ is in $0\,\\{0,1\\}^{\omega}$; therefore,
$g^{\rho}(f^{\rho}(x))$ is undefined. So
$g^{\rho}(f^{\rho}(x))=[gf]^{\rho}(x)$, both being undefined.

$\circ$ $x\in 1\,\\{0,1\\}^{\omega}$ and $f(x)=0z\in$ $0\,\\{0,1\\}^{\omega}:$

Then $f^{\rho}(x)$ is undefined, hence $\,g^{\rho}(f^{\rho}(x))$ is undefined.
And $[gf]^{\rho}(x)\in\\{gf(x)\\}\cap 1\,\\{0,1\\}^{\omega}$, where
$gf(x)=g(0z)\in 0\,\\{0,1\\}^{\omega}\,$ (since $g\in F_{0}$); hence
$[gf]^{\rho}(x)\in\\{gf(x)\\}\cap 1\,\\{0,1\\}^{\omega}$ $=$ $\varnothing$, so
$[gf]^{\rho}(x)$ is also undefined.

$\circ$ $x=0z\in 0\,\\{0,1\\}^{\omega}:$

Then $f^{\rho}(x)$ is undefined, hence $\,g^{\rho}(f^{\rho}(x))$ is undefined.
Since $g,f\in F_{0}$, $gf(0z)=0z$. Now $[gf]^{\rho}(x)\in\\{gf(0z)\\}\cap
1\,\\{0,1\\}^{\omega}$ $=$ $\\{0z\\}\cap 1\,\\{0,1\\}^{\omega}$ $=$
$\varnothing$, so $[gf]^{\rho}(x)$ is also undefined.

This proves the Claim and part (1) of the Theorem.

The same proof works for ${\cal RM}^{\sf fin}$ and ${\sf tot}{\cal RM}^{\sf
fin}$, by replacing $\\{0,1\\}^{\omega}$ by $\\{0,1\\}^{*}$.

(2) The proof is similar to the proof of (1), but now we have to be careful
about lengths.

A function $f\in{\sf tlep}M_{2,1}$ belongs to the stabilizer $S_{0}\,$ iff
$\,f$ has a table of the form

$\left[\begin{array}[]{ccccccccc}0u_{1}&\ldots&0u_{r}&1x_{1}&\ldots&1x_{k}&1x^{\prime}_{1}&\
\ldots&1x^{\prime}_{h}\\\
0v_{1}&\ldots&0v_{r}&1y_{1}&\ldots&1y_{k}&0y^{\prime}_{1}&\
\ldots&0y^{\prime}_{h}\end{array}\right]\,,$

where $\,{\rm domC}(f)=0U\,\cup\,1P\,\cup\,1P^{\prime}$, and where
$U=\\{u_{1},\,\ldots\,,u_{r}\\}$, $P=\\{x_{1},\,\ldots\,,x_{k}\\}$,
$P^{\prime}=\\{x^{\prime}_{1},\,\ldots\,,x^{\prime}_{k}\\}\,$ are finite
prefix codes such that
$P\,\\{0,1\\}^{*}\,\cap\,P^{\prime}\,\\{0,1\\}^{*}=\varnothing$. Moreover,
$\\{y_{1},\,\ldots\,,y_{k}\\}$ is a set of size $\,\leq|P|$,
$\\{y^{\prime}_{1},\,\ldots\,,y^{\prime}_{h}\\}$ is a set of size
$\,\leq|P^{\prime}|$, and $\\{v_{1},\,\ldots\,,v_{r}\\}$ is a set of size
$\,\leq|U|$. Since $f$ is total, ${\rm domC}(f)$ is a maximal finite prefix
code; hence, $U$ and $P\cup P^{\prime}$ are each a maximal finite prefix code,
so $P^{\prime}$ is a complementary finite prefix code of $P$. Since $f$ is
tlep, we have the additional properties that for all $i$ (in the appropriate
ranges),

$|v_{i}|-|u_{i}|$ $\,=\,$ $|y_{i}|-|x_{i}|$ $\,=\,$
$|y_{i}^{\prime}|-|x_{i}^{\prime}|$ $\,=\,$ $\delta(f)$.

The remainder of the proof is the same as for (1).

The same proof works for ${\sf pfl}{\cal RM}^{\sf fin}$ and ${\sf tfl}{\cal
RM}^{\sf fin}$, by replacing $\\{0,1\\}^{\omega}$ by $\\{0,1\\}^{*}$. $\Box$

Remark. The reason why the fixator is not used in (2) is that we want
$\overline{f}$ to be length-equality preserving (lep). As a result, in (2),
the restriction of $\varrho$ to $\,\varrho^{-1}({\sf tlep}M_{2,1})\,$ is not
injective.

Inverse-homomorphic nondeterministic completion algorithm:

For a finite prefix code $P\subseteq A^{*}$ we define the size of $P\,$ by $\
\|P\|=\,\sum_{x\in P}|x|$, where $|x|$ is the length of $x$.

For a right-ideal morphism $g\in{\cal RM}^{\sf fin}$ given by a table
$\,\\{(x_{i},y_{i}):1\leq i\leq k\\}$, the size of the table is defined by
$\|g\|=\,\sum_{i=1}^{k}|x_{i}y_{i}|$.

By [8, Def. 3.29, Lemma 3.30] and [14, Prop. 5.2], every finite prefix code
$P\subseteq A^{*}$ has a complementary prefix code $Q\subseteq A^{*}$ such
that $\,{\rm maxlen}(P)={\rm maxlen}(Q)$. If $P\subseteq A^{m}$ then
$\,A^{m}\smallsetminus P\,$ is a complementary prefix code of $P$.

In Prop. 9.6, $\varrho$ is as in Theorem 9.5.

###### Proposition 9.6

.

(1) ${\cal RM}^{\sf fin}$ and ${\sf tot}{\cal RM}^{\sf fin}:$

The following nondeterministic algorithm, on input $g\in M_{2,1}$ (given by
the table of a right-ideal morphism in ${\cal RM}^{\sf fin}$ that represents
$g$), outputs an element $\,\overline{g}\in$ ${\sf tot}M_{2,1}\,$ (given by
the table of a right-ideal morphism in ${\sf tot}{\cal RM}^{\sf fin}$), such
that $\,\varrho(\,\overline{g}\,)=g$.

(2) ${\sf pfl}{\cal RM}^{\sf fin}$ and ${\sf tfl}{\cal RM}^{\sf fin}:$

A variant of this nondeterministic algorithm, on input $g\in$ ${\sf
plep}M_{2,1}$ (given by the table of a right-ideal morphism in ${\sf pfl}{\cal
RM}^{\sf fin}$), outputs an element $\,\overline{g}\in$ ${\sf tlep}M_{2,1}$
(given by the table of a right-ideal morphism in ${\sf tfl}{\cal RM}^{\sf
fin}$), such that $\,\varrho(\,\overline{g}\,)=g$. The algorithm can find such
a $\,\overline{g}\,$ in time $O(\|g\|)$.

Algorithm:

For any function $g\in{\cal RM}^{\sf fin}$ with table

$g\,=\,\left[\begin{array}[]{ccc}x_{1}&\ldots&x_{k}\\\
y_{1}&\ldots&y_{k}\end{array}\right]$

where $\,{\rm domC}(g)=P=\\{x_{1},\,\ldots\,,x_{k}\\}$ is a finite prefix
code, a completion can be obtained by choosing

$\overline{g}\ =\
\left[\begin{array}[]{ccccccc}0&1x_{1}&\ldots&1x_{k}&1x^{\prime}_{1}&\
\ldots&1x^{\prime}_{h}\\\ 0&1y_{1}&\ldots&1y_{k}&0y^{\prime}_{1}&\
\ldots&0y^{\prime}_{h}\end{array}\right]\,,$

where $\,P^{\prime}=\\{x^{\prime}_{1},\,\ldots\,,x^{\prime}_{h}\\}\,$ is an
arbitrary complementary finite prefix code of $P$, and
$\,g^{\prime}=\\{(x^{\prime}_{1},y^{\prime}_{1}),$ $\,\ldots\,,$
$(x^{\prime}_{h},y^{\prime}_{h})\\}\,$ is an arbitrary element of ${\cal
RM}^{\sf fin}$ with domain code $P^{\prime}$. (If $g$ is total, i.e. $P$ is
maximal, then $P^{\prime}=\varnothing$, so $g^{\prime}$ is the empty function
$\theta$.)

If $g\in{\sf plep}M_{2,1}$, represented by a right-ideal morphism in ${\sf
pfl}{\cal RM}^{\sf fin}$, then $P=\\{x_{1},\,\ldots\,,x_{k}\\}$
$\subseteq\\{0,1\\}^{m}$, and $\\{y_{1},\,\ldots\,,y_{k}\\}\in\\{0,1\\}^{n}$,
with $n=m+\delta(g)$. We chose

$\overline{g}\ =\
\left[\begin{array}[]{ccccccccc}0u_{1}&\ldots&0u_{r}&1x_{1}&\ldots&1x_{k}&1x^{\prime}_{1}&\
\ldots&1x^{\prime}_{h}\\\
0v_{1}&\ldots&0v_{r}&1y_{1}&\ldots&1y_{k}&0y^{\prime}_{1}&\
\ldots&0y^{\prime}_{h}\end{array}\right]\,,$

where $U=\\{0,1\\}^{m}$ (no choice). We arbitrarily choose a set
$\,\\{v_{1},\,\ldots\,,v_{r}\\}$ $\subseteq$ $\\{0,1\\}^{n}$, and we choose
the pairing arbitrarily so that
$\,\\{(u_{1},v_{1}),\,\ldots\,,(u_{r},v_{r})\\}$ $\in{\sf tfl}{\cal RM}^{\sf
fin}$. We let $P^{\prime}=\\{0,1\\}^{m}\smallsetminus P\,$ (no choice), we
arbitrarily choose a set $\\{y^{\prime}_{1},\,\ldots\,,y^{\prime}_{h}\\}$
$\subseteq$ $\\{0,1\\}^{n}$, and we choose the pairing
$\,g^{\prime}=\\{(x^{\prime}_{i},y^{\prime}_{i}):i=1,\ldots,h\\}$ in ${\sf
pfl}{\cal RM}^{\sf fin}$. The resulting table for $\overline{g}$ gives a
right-ideal morphism in ${\sf tfl}{\cal RM}^{\sf fin}$, with fixed input
length $m\\!+\\!1$ and fixed output length $n\\!+\\!1$.

In the case of ${\sf pfl}M_{2,1}$, if $g$ is given by a table with ${\rm
domC}(g)\subseteq\\{0,1\\}^{m}$, then the complementary prefix code of ${\rm
domC}(g)$ is easily found.

The choices in the construction of $\,\overline{g}$ from $g$ are of course
nondeterministic, but the inverse process $\,\varrho:\overline{g}\mapsto g\,$
is a function, and a homomorphism $F_{0}\twoheadrightarrow M_{2,1}$,
respectively $S_{0}\twoheadrightarrow{\sf tfl}M_{2,1}$. $\Box$

Remark. In part (1) of the algorithm we do not know whether the time
complexity is polynomial in $\|g\|$ because we do not know an efficient
algorithm for finding a finite complementary prefix code of a finite prefix
code.

Besides the above nondeterministic completion procedure, there are many other
ones; there are many monoid homomorphisms from submonoids of ${\sf
tot}M_{2,1}$ onto $M_{2,1}$, respectively submonoids of ${\sf pfl}M_{2,1}$
onto ${\sf tfl}M_{2,1}$.

The above algorithm does not run in polynomial time (except in the pfl case).
In the next two subsections we give algorithms that run in log-space, but use
a different form of input than the above algorithm: $g$ will either be given
by a generator word over $\Gamma$ or $\Gamma\cup\tau$, or (in the pfl case) by
an acyclic circuit.

###  9.3 Generator-based completion

Generator-based completion for $M_{2,1}$

Let $\,\varrho:F_{0}\twoheadrightarrow M_{2,1}$, with $F_{0}\leq$ ${\sf
tot}M_{2,1}$, be as in Theorem 9.5. Let $\Gamma_{\rm\\!M}$ be any finite set
such that $\Gamma_{\rm\\!M}\cup\tau$ generates $M_{2,1}$; similarly, let
$\Gamma_{\rm\\!tot}$ be any finite set such that $\Gamma_{\rm\\!tot}\cup\tau$
generates ${\sf tot}M_{2,1}$.

For each generator $\gamma$ in the finite set $\Gamma_{\rm\\!M}\,$ we choose a
word $\overline{\gamma}\in$ $(\Gamma_{\rm\\!tot}\cup\tau)^{*}$ such that
$E_{\overline{\gamma}}$ $\in$ $\varrho^{-1}(\gamma)\subseteq F_{0}$.

For a transposition $\tau_{i,j}\in\tau$ with $1\leq i<j$ we choose
$\overline{\tau}_{i,j}$ as follows: For all $x\in\\{0,1\\}^{\geq j}$,

$\overline{\tau}_{i,j}(0x)\,=\,0x$,

$\overline{\tau}_{i,j}(1x)\,=\,\tau_{i+1,j+1}(1x)$,

so $\,{\rm domC}(\overline{\tau}_{i,j})=\\{0,1\\}^{j+1}$ $=$ ${\rm
imC}(\overline{\tau}_{i,j})$. Then
$\,\overline{\tau}_{i,j}\in\varrho^{-1}(\tau_{i,j})$ $\subseteq F_{0}$, so
$\overline{\tau}_{i,j}$ is indeed a completion of $\tau_{i,j}$ according to
Theorem 9.5(1). To represent $\overline{\tau}_{i,j}$ be a word in
$(\Gamma_{\rm\\!tot}\cup\tau)^{*}$ we use the following formula: For every
string $bx\in\\{0,1\\}^{j+1}$ with $b\in\\{0,1\\}$,

$\overline{\tau}_{i,j}(bx)\ =\ $ $\big{(}(b^{\prime})^{j+1}\ \ {\sf
and}_{j+1}\ \ bx\big{)}$ $\ \ {\sf or}_{j+1}\ \ $ $\big{(}b^{j+1}\ \ {\sf
and}_{j+1}\ \ \tau_{i+1,j+1}(bx)\big{)}\,$,

where $b^{\prime}={\sf not}(b)$, $z^{n}$ denotes the concatenation of $n$
copies of $z$, ${\sf and}_{n}$ (or ${\sf or}_{n}$) is the bitwise and
(respectively or) of two bitstrings of length $n$.

Based on this formula, one can easily build an acyclic boolean circuit for
$\overline{\tau}_{i,j}$, and this circuit then yields a word in
$(\Gamma_{\rm\\!tot}\cup\tau)^{*}\,$ (by Theorem 3.8(1)). Thus for
$\tau_{i,j}$ we can construct a word for $\overline{\tau}_{i,j}$ in space
$O(\log j)$.

This proves the following:

###### Corollary 9.7

For any $\,w=w_{n}\,\ldots\,w_{1}$ $\in(\Gamma_{\rm\\!M}\cup\tau)^{*}$ with
$w_{i}\in\Gamma_{\rm\\!M}\cup\tau$ (for $i=1,\ldots,n$), let
$\,E_{w}=w_{n}\circ\ldots\circ w_{1}(.)$ $\,\in\,$ $M_{k,1}$ be the function
generated. By completing each generator and concatenating we obtain $\,W\,=\,$
$\overline{w}_{n}\,\ldots\,\overline{w}_{1}$ $\in$
$(\Gamma_{\rm\\!tot}\cup\tau)^{*}$, which generates the total function
$\,E_{W}\,=\,$ $\overline{w}_{n}\circ\ldots\circ\overline{w}_{1}(.)$ $\,\in\,$
$F_{0}\,\subseteq{\sf tot}M_{k,1}$.

Then $\,E_{W}\,$ is a completion of $\,E_{w}\,$, i.e., $\varrho(E_{W})=E_{w}$.

The word $W$ can be computed from $w$ in log-space. $\Box$

In other words, a completion of a function $f\in M_{k,1}$, given by a sequence
of generators, can be efficiently obtained by completing the generators and
composing them. The same approach works for ${\cal RM}^{\sf fin}$.

Generator-based completion for ${\sf pfl}{\cal RM}^{\sf fin}$

For ${\sf pfl}{\cal RM}^{\sf fin}$ we obtain more results, based on the
generating sets $\Gamma_{\rm\\!pfl}\cup\tau$, respectively
$\Gamma_{\rm\\!tfl}\cup\tau$, with $\Gamma_{\rm\\!pfl}$ and
$\Gamma_{\rm\\!tfl}$ finite.

For the finitely many generators $\gamma\in\Gamma_{\rm\\!pfl}$ we choose
$\overline{\gamma}\in\varrho^{-1}(\gamma)\subseteq S_{0}$ nondeterministically
as in Prop. 9.6. For a position transposition $\tau_{i,j}\in\tau$ with $1\leq
i<j$ we choose

$\overline{\tau}_{i,j}=\tau_{i+1,j+1}$.

For this choice, $\,\tau_{i+1,j+1}(0z)\in$ $0\\{0,1\\}^{*}\,$ for all
$z\in\\{0,1\\}^{\geq j+1}$ and for all $z\in$ $\\{0,1\\}^{\omega}$; so
$\tau_{i+1,j+1}$ $\in$ $S_{0}$ ($\,\subseteq$ ${\sf tfl}{\cal RM}^{\sf fin}$),
and $\,\varrho(\,\tau_{i+1,j+1}\,)$ $=$ $\tau_{i,j}$.

Remarks: (1) Many completions of $\tau_{i,j}$ are possible, but the above one
has the advantage of being itself in $\tau$. (2) Note that
$\,\tau_{i+1,j+1}\,\not\in\,F_{0}$, so the above completion of $\tau_{i,j}$
only works for ${\sf plep}M_{2,1}$, not for $M_{2,1}$.

###### Proposition 9.8

(completion in terms of generators).

For every $w\in(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ there exists a word
$\,\overline{w}\in(\Gamma_{\sf\\!tfl}\cup\tau)^{*}$ such that

(1) $E_{\overline{w}}\,\in\,S_{0}\,$ $(\,\subseteq$ ${\sf tfl}{\cal RM}^{\sf
fin})$ is a completion of $E_{w}$, and $\overline{w}$ can be found from $w$ by
a deterministic algorithm that runs in linear time and log-space.

(2) $\,|w|_{\Gamma_{\sf\\!pfl}\cup\tau}$ $\,\leq\,$
$|\overline{w}|_{\Gamma_{\sf\\!tfl}\cup\tau}$ $\,\leq\,$
$c\,|w|_{\Gamma_{\sf\\!pfl}\cup\tau}\,$, for some constant $c\geq 1$;

$\,{\rm maxindex}_{\tau}(w)$ $\,\leq\,$ ${\rm
maxindex}_{\tau}(\overline{w})\,\leq\,{\rm maxindex}_{\tau}(w)+1\,$;

$\,\ell_{\rm in}(\overline{w})\,=\,\ell_{\rm in}(w)+1$, and $\ell_{\rm
out}(\overline{w})+1\,=\,\ell_{\rm out}(w)+1$; hence,

$\,|w|\leq|\overline{w}|\leq c\,|w|\,$, for some constant $c\geq 1$.

(3) $\,\overline{w}\in(\Gamma_{\sf\\!tfl}\cup\tau)^{*}$ can be chosen so that
in addition to the above,

$\,{\sf depth}(\overline{w})\,\leq\,$ $c\,+\,\max\\{{\sf
depth}(w),\,\log_{2}|w|_{\Gamma_{\sf\\!pfl}}\\}\,$, for some constant $c\geq
1$.

Proof. (1) This is proved in the same way as Corollary 9.7, except that a
simpler form for $\overline{\tau}_{i,j}$ is now used. The construction of
$\overline{w}$ implies that it can be computed from $w$ in linear times and
log-space (if every transposition $\tau_{i,j}$ is encoded in the form
$0^{i}1^{j}$ over the alphabet $\\{0,1\\}\cup\Gamma_{\sf\\!pfl}$, assuming
$\,\\{0,1\\}^{*}\cap\Gamma_{\sf\\!pfl}=\varnothing$).

(2) The claims about $|\overline{w}|_{\Gamma_{\sf\\!tfl}\cup\tau}$ and ${\rm
maxindex}_{\tau}(\overline{w})$ follow immediately from the construction of
$\overline{w}$.

The claims about $\ell_{\rm in}(\overline{w})$ and $\ell_{\rm
out}(\overline{w})$ follow from the definition. Let $x\in$ $\\{0,1\\}^{m}$. By
induction on $i$ $\in$ $\\{1,\ldots,k\\}$, one proves that
$\,\overline{w}_{i}\circ\ldots\circ\overline{w}_{1}(1x)$ is defined iff
$w_{i}\circ\ldots\circ w_{1}(x)$ ($\in\\{0,1\\}^{n}$) is defined. And for
$x\not\in{\rm Dom}(w_{i}\circ\ldots\circ w_{1})$,
$\,\overline{w}_{i}\circ\ldots\circ\overline{w}_{1}(1x)\in 0\\{0,1\\}^{n}$.
Moreover, $\,\overline{w}_{i}\circ\ldots\circ\overline{w}_{1}(0\\{0,1\\}^{m})$
$\subseteq$ $0\\{0,1\\}^{n}$. Hence, $\ell_{\rm in}(\overline{w})=\ell_{\rm
in}(w)+1$ and $\ell_{\rm out}(\overline{w})=\ell_{\rm out}(w)+1$.

(3) The claim about ${\sf depth}(\overline{w})$ follows from Prop. 9.9(2)
below, and and the definition of depth in terms of circuits (Def. 3.12).
$\Box$

###  9.4 Circuit-based completion

We now construct circuit completions that do not use generators nor Theorems
3.8 and 3.11 (about the conversion between words and circuits or partial
circuits). By a circuit we always mean an acyclic circuit.

###### Proposition 9.9

(boolean circuit for the completion).

Let $\varrho$ be as in Theorem 9.5. Suppose that $f\in{\sf pfl}{\cal RM}^{\sf
fin}$ has a partial circuit $C_{\\!f}$ with input-length $m$, output-length
$n$, and size $s$. Then we have:

(1) $f$ has a completion $\overline{f}\,\in\,$
$\varrho^{-1}(f)\,\subseteq\,{\sf tfl}{\cal RM}^{\sf fin}\,$ that has a
boolean circuit with input-length $m\\!+\\!1$, output-length $n\\!+\\!1$, and
size $\,\leq c\,s\,$ (for some constant $c\geq 1$).

(2) If, in addition, $C_{\\!f}$ has depth $d$, then $f$ has a completion
$\,\overline{f}\,\in\,\varrho^{-1}(f)\,$ that has a boolean circuit with depth
$\,\leq\,O(1)$ $\,+\,$ $\max\\{d,\ \lceil\log_{2}s\rceil$ $+$
$2\,\lceil\log_{2}(n\\!+\\!1)\rceil\\}\,$, input-length $m\\!+\\!1$, output-
length $n\\!+\\!1$, and size $\,O(s)$.

The boolean circuit for $\overline{f}$ can be computed from $C_{\\!f}$ in log-
space.

(3) Under the assumptions of (2), the classical completion $\,\tilde{f}\in{\sf
tfl}{\cal RM}^{\sf fin}\,$ (defined in Subsection 9.1) has a boolean circuit
with $\,{\rm depth}$ $\,\leq\,O(1)$ $+$ $\max\\{d,\ $
$\lceil\log_{2}s\rceil+2\,\lceil\log_{2}(n\\!+\\!1)\rceil\\}\,$, input-length
$m$, output-length $n$, and size $\,\leq O(s)$.

The boolean circuit for $\tilde{f}$ can be computed from the partial circuit
$C_{\\!f}$ in log-space.

Proof. (1) This follows from Prop. 9.8(2) (about the word-lengths of $f=E_{w}$
and $\overline{f}=E_{\overline{w}}$), combined with Theorems 3.8 and 3.11
(about the connection between word-length and circuit-size). (1) also follows
from the construction in part (2) below.

(2) We pick the completion

$\overline{f}\ =\
\left[\begin{array}[]{ccccccccc}0u^{(1)}&\ldots&0u^{(r)}&1x^{(1)}&\ldots&1x^{(k)}&1z^{(1)}&\ldots&1z^{(h)}\\\
0^{n+1}&\ldots&0^{n+1}&1y^{(1)}&\ldots&1y^{(k)}&0^{n+1}&\ldots&0^{n+1}\end{array}\right]\,,$

with $\varrho(\overline{f})=f$. Here
$U=\\{u^{(1)},\,\ldots\,,u^{(r)}\\}=\\{0,1\\}^{m}$, with $\,r=2^{m}$; $\ {\rm
domC}(f)=P=\\{x^{(1)},\,\ldots\,,x^{(k)}\\}$ $\subseteq\\{0,1\\}^{m}$, and
$\,y^{(i)}=f(x^{(i)})\in\\{0,1\\}^{n}\,$ for $i\in[1,k]$; $\
P^{\prime}=\\{z^{(1)},\,\ldots\,,z^{(h)}\\}=$ $\\{0,1\\}^{m}\smallsetminus
P\,$ (complementary prefix code), with $h=2^{m}-k$. In other words, for all
inputs $x_{0}\,x$ with $x_{0}\in\\{0,1\\}$ and $x\in\\{0,1\\}^{m}:$

$\overline{f}(x_{0}x)\,=\,1\,f(x)$ if $x_{0}=1$ and $x\in P$;

$\overline{f}(x_{0}x)\,=\,0^{n+1}$ if $x_{0}=0$ or
$x\in\\{0,1\\}^{m}\smallsetminus P$.

Claim: Suppose $f$ has a partial circuit $C_{\\!f}$ with input-length $m$,
output-length $n$, size $s$, and depth $d$. Then there is a boolean circuit
$C_{G}$ with the following properties:

$\circ$ The input-output function of $C_{\\!G}$ is $G:\
x\in\\{0,1\\}^{m}\,\longmapsto\,G(x)\in\\{0,1\\}^{n+1}\,$, where

$G(x)\,=\,1\,f(x)$ if $x\in P$,

$G(x)\,=\,0^{n+1}$ if $x\in\\{0,1\\}^{m}\smallsetminus P$.

So, $\,G(x)\,=\,\overline{f}(1x)\ $ for all $x\in\\{0,1\\}^{m}$.

$\circ$ The boolean circuit $C_{\\!G}$ has size $\,\leq c_{0}\,s$, and depth
$\,\leq c_{1}+\max\\{d,\ $ $\lceil\log_{2}s\rceil+\lceil\log_{2}n\rceil\\}$
(for some constants $c_{0},c_{1}\geq 1$).

Proof of the Claim: We modify the partial circuit $C_{\\!f}$ by completing
every partial gate $g$ as follows. To $g$ we add a new output wire that
outputs $0$ if the gate-output is undefined on the given gate-input; and for
that gate-input, the already existing output wires of the gate $g$ now receive
the value 0. If on the given gate-input of $g$, the gate-output is defined,
the newly added output wire outputs 1. This modified gate, which is total, is
the completion of the partial gate $g$.

The newly added output wires do not feed into any existing gates, but into a
binary tree of and-gates, of size $\,\leq s$ and depth $\,\leq
1+\lceil\log_{2}s\rceil$. Let $y_{0}$ be the single output bit of this tree of
and-gates. Let $\overline{y}$ be output, other than $y_{0}$, of the completed
circuit; so $\overline{y}$ has length $n$.

Next, $n$ copies of $y_{0}$ are produced by a binary tree of $\,\leq n\,$ fork
gates (of depth $1+\lceil\log_{2}n\rceil$).

The output $\overline{y}$ is combined (using and-gates) with the $n$ copies of
$y_{0}$. In other words, this yields the bitstring $\ y_{0}^{\ n}\ {\sf
and}_{n}\ \overline{y}\,$, where $\,{\sf and}_{n}\,$ is the bitwise and of two
bitstrings of length $n$. We also output $y_{0}$ itself. The output of
$C_{\\!G}$ is thus $y_{0}\,(y_{0}^{\ n}\ {\sf and}_{n}\ \overline{y})$, which
is $\,1\,f(x)\,$ if $x\in P$, and $\,0^{n+1}\,$ if $\,x\in$
$\\{0,1\\}^{m}\smallsetminus P$. This completes the construction of
$C_{\\!G}$.

The claim about circuit size is straightforward.

The depth of $C_{\\!G}$ is
$\,\leq\max\\{d,\,2+\lceil\log_{2}s\rceil+\lceil\log_{2}n\rceil\\}$, since the
and-tree, followed by the fork-tree, can be put in parallel with the completed
circuit for $G$, except for a delay of one gate (this is why there is “$2+$”
in $\,2+2\,\lceil\log_{2}s\rceil+\lceil\log_{2}n\rceil\,$ instead of the
previous “$1+$”). [End, proof of Claim.]

The definition of $\,\overline{f}:\\{0,1\\}^{m+1}\to\\{0,1\\}^{n+1}$ can be
formulated as follows. For all inputs $x_{0}\,x$ with $x_{0}\in\\{0,1\\}$ and
$x\in\\{0,1\\}^{m}$,

$\overline{f}(x_{0}\,x)\ =\ $ $x_{0}^{\ n+1}\ \ {\sf and}_{n+1}\ \ G(x)$,

where $x_{0}^{\ n+1}\in\\{0^{n+1},1^{n+1}\\}\,$ is the concatenation of
$n\\!+\\!1$ copies of the bit $x_{0}$.

Let us now describe a log-space algorithm that constructs a boolean circuit
$C_{\\!\overline{f}}$ for $\overline{f}$, based on the partial circuit
$C_{\\!f}$. First, the boolean circuit $C_{\\!G}$ is constructed as the proof
of the Claim; on input $x$, $C_{\\!G}$ outputs $\overline{f}(1x)$. Second,
$n\\!+\\!1$ copies of $x_{0}$ are made, by using a binary tree of fork gates,
of depth $1+\lceil\log_{2}(n\\!+\\!1)\rceil$. This can be done in log-space.
Finally, we use the formula $\ \overline{f}(x_{0}x)\,=\,x_{0}^{\ n+1}\ {\sf
and}_{n+1}\ G(x)$; for this, a row of $n\\!+\\!1$ and-gates combines $x_{0}^{\
n+1}$ bitwise with the output of $C_{\\!G}$.

The size of $C_{\\!\overline{f}}$ is $O(s)$, and the depth is $\,\leq\,3$ $+$
$\max\\{d,\ 2+\lceil\log_{2}s\rceil+\lceil\log_{2}n\rceil$ $+$
$\lceil\log_{2}(n\\!+\\!1)\rceil\\}$.

(3) The boolean circuit $C_{\\!\overline{f}}$ can be modified to a boolean
circuit that it computes $\tilde{f}$, as follows. On input
$x\in\\{0,1\\}^{m}$, the circuit prepends $1$, and computes
$\overline{f}(1x)$. If the result is $1\,f(x)$ the circuit outputs $f(x)$; if
the output is in $\,0\\{0,1\\}^{*}$, the circuit outputs $0^{n}$. $\Box$

##  10 Representation of a function in $M_{2,1}$ or ${\cal RM}^{\sf fin}$ by a
union of partial circuits with disjoint domains

###  10.1 Preliminaries

Recall the definitions of $\ell_{\rm in}(C)$, $\ell_{\rm out}(C)\,$ (Def.
3.1), circuit size (Def. 3.2), $\ell_{\rm in}(w)$, $\ell_{\rm out}(w)\,$ (Def.
3.3), and various word-lengths and maxlen($\cal F$) (Def. 3.5).

###### Proposition 10.1

.

(1) For any partial acyclic circuit $C:$

$\ell_{\rm in}(C),\ \ell_{\rm out}(C)\ \leq\ |C|$.

(2) Let $\Gamma_{\rm\\!RM}$ be a finite set such that
$\Gamma_{\rm\\!RM}\cup\tau$ generates ${\cal RM}^{\sf fin}$. For every word
$w\in$ $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ let $\ |w|\,=\,$
$|w|_{\Gamma_{\rm\\!RM}\cup\tau}\,+\,{\rm maxindex}_{\tau}(w)\,$. Then we
have:

$\ell_{\rm in}(w)\ \leq\ c\,|w|_{\Gamma_{\rm\\!RM}}$ $\,+\,$ ${\rm
maxindex}_{\tau}(w)$ $\leq\ c\,|w|$,

$\ell_{\rm out}(w)\ \leq\ 2\,c\,|w|_{\Gamma_{\rm\\!RM}}$ $\,+\,$ ${\rm
maxindex}_{\tau}(w)$ $\leq\ 2\,c\,|w|$,

where $c={\rm maxlen}(\Gamma_{\rm\\!RM})$.

Proof. (1) The inequality is immediate from the definition of circuit size
(Def. 3.2).

(2) Let $\,\ell=$ $c\,|w|_{\Gamma_{\rm\\!RM}}+{\rm maxindex}_{\tau}(w)$. For
the first inequality it suffices to show that $E_{w}(x)$ is defined for every
$x\in\\{0,1\\}^{\geq\ell}$ such that $x\,\\{0,1\\}^{\omega}$ $\subseteq$ ${\rm
Dom}(E_{w})\,\\{0,1\\}^{\omega}$.

When $w$ is applied to $x$, the generators in $\tau$ do not cause any change
in length, and can only have an effect within length $\,\leq{\rm
maxindex}_{\tau}(w)$; indeed, the generators of $w$ in $\Gamma_{\rm\\!RM}$
cannot cause a decrease of more than $\,c\,|w|_{\Gamma_{\rm\\!RM}}$, so the
string that results at any moment has length $\,\geq{\rm maxindex}_{\tau}(w)$.
And the $|w|_{\Gamma_{\rm\\!RM}}$ generators in $\Gamma_{\rm\\!RM}$ cause a
length-increase of at most $c\cdot|w|_{\Gamma_{\rm\\!RM}}$.

Hence, if $|x|\geq\ell$ then $x$ is not too short for any of the generators to
be applied (if $x\\{0,1\\}^{\omega}\in{\rm Dom}(E_{w})$). Hence $m\leq\ell$.
And in the output of the action of $w$ on $x\in\\{0,1\\}^{\ell}$ is a most
$c\cdot|w|_{\Gamma_{\rm\\!RM}}$ longer than $x$. $\Box$

###### Definition 10.2

(common input-length and common output-length).

Let $\Gamma_{\sf\\!pfl}$ be a finite set such that
$\Gamma_{\sf\\!pfl}\cup\tau$ generates ${\sf pfl}{\cal RM}^{\sf fin}$.

(1) For a set of words $\,\\{u_{1},\,\ldots\,,u_{k}\\}$ $\subseteq$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$, the common input-length is

$\ell_{\rm in}(u_{1},\,\ldots\,,u_{k})$ $\ =\ $ $\max\\{\ell_{\rm
in}(u_{1}),\,\ldots\,,\ell_{\rm in}(u_{k})\\}\,$,

where $\ell_{\rm in}(u_{i})$ is as in Def. 3.3.

(2) If $\,\delta(E_{u_{i}})\,$ is the same for all $i\in[1,k]$, then the
common output-length of $\,\\{u_{1},\,\ldots\,,u_{k}\\}$ is

$\ell_{\rm in}(u_{1},\,\ldots\,,u_{k})\,+\,\delta(E_{u_{i}})\,$,

which is the same for all $i$.

If $\delta(E_{u_{i}})$ is not the same for all $i\in[1,k]$ then
$\,\\{u_{1},\,\ldots\,,u_{k}\\}$ has no common output-length.

###### Lemma 10.3

Under the conditions of Def. 10.2, the common input-length $m$ and the common
output-length $n$ satisfy

$m,\ n\ \leq\ $ $\max\big{\\{}\,{\rm maxlen}(\Gamma_{\sf\\!pfl})$
$\\!\cdot\\!$ $|u_{i}|_{\Gamma_{\sf\\!pfl}}$ $\,+\,$ ${\rm
maxindex}_{\tau}(u_{i})\,:\,1\leq i\leq k\,\big{\\}}$.

Proof. This is proved in a similar way as Prop. 10.1. $\Box$

Depth of words in ${\cal RM}^{\sf fin}$ and $M_{2,1}$

We saw that words in $(\Gamma_{\sf\\!tfl}\cup\tau)^{*}$ or
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ are closely related to boolean circuits,
respectively partial circuits. Words in $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$,
where $\Gamma_{\rm\\!RM}$ is finite set such that $\Gamma_{\rm\\!RM}\cup\tau$
generates ${\cal RM}^{\sf fin}$ (and hence $M_{2,1}$) are a generalization of
partial circuits. However, the previous definition of depth of an element of
$(\Gamma_{\sf\\!tfl}\cup\tau)^{*}$ or $(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ are
based on circuits that are directly obtained from words of generators. This
approach does not directly apply to $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ since a
generator in $\Gamma_{\rm\\!RM}$ need not have a fixed input-length and a
fixed output-length, so no circuit digraph with fixed in- and out-degrees can
be formed.

Nevertheless, Def. 10.4 gives the depth of a word $w\in$
$(\Gamma_{\rm\\!RM}\cup\tau)^{*}\,$ for a given input $x\in\\{0,1\\}^{*}\,$.
Let $w=w_{k}\,\ldots\,w_{1}$ with $w_{i}\in\Gamma_{\rm\\!RM}\cup\tau$ (for
$1\leq i\leq k$). For a fixed input $x\in\\{0,1\\}^{*}\,$ of length
$\,|x|\geq\ell_{\rm in}(w)=m$, each $w_{i}(.)$ has a fixed input-length, and a
fixed output-length. So for a given $w\in$ $(\Gamma_{\rm\\!RM}\cup\tau)^{*}\,$
and $x\in\\{0,1\\}^{\geq m}$, there is a partial circuit $C_{w,x}$ such that
$C_{w,x}(x)=E_{w}(x)\,$ (as constructed for partial circuits in Theorem 3.11).
If $E_{w}(x)$ is undefined then $C_{w,x}$ and its depth are undefined.

###### Definition 10.4

(depth of a word in ${\cal RM}^{\sf fin}$).

Let $\Gamma_{\rm\\!RM}$ be a finite set such that $\Gamma_{\rm\\!RM}\cup\tau$
generates ${\cal RM}^{\sf fin}$ and hence $M_{2,1}$. Let $\,w\in$
$(\Gamma_{\rm\\!RM}\cup\tau)^{*}$, and let $\,\ell_{\rm in}(w)=m\,$ be the
input-length of $w$ (Def. 3.3). For any $x\in{\rm
Dom}(E_{w})\cap\\{0,1\\}^{m}$, let $\,C_{w,x}\,$ be the partial circuit just
constructed for $w$ on input $x$. Then the depth of $w$ is defined by

${\sf depth}(w)\,=\,$ $\max\big{\\{}{\sf depth}(C_{w,x})\,:\,$ $x\in{\rm
Dom}(E_{w})\cap\\{0,1\\}^{m}\big{\\}}$.

If $E_{w}=\theta\,$ (the empty function) then ${\sf depth}(w)$ is not defined.

###  10.2 Unambiguous union

###### Definition 10.5

(unambiguous union).

(1) Sets: For an indexed family of sets $\,(D_{i}:i\in I)\,$ the unambiguous
union, denoted by $!$$\bigcup_{i\in I}D_{i}\,$, is the set of elements that
belong to exactly one of the sets $D_{i}:$

$!$$\bigcup_{i\in I}D_{i}$ $\ =\ $ $\\{d\in\bigcup_{i\in
I}D_{i}\,:\,(\exists!\,j\in I)[\,d\in D_{j}\,]\,\\}$.

In particular, if $\,D_{i}\cap D_{j}=\varnothing\,$ for all $i,j\in I$ with
$i\neq j$, then $!$$\bigcup_{i\in I}D_{i}\,=\,\bigcup_{i\in I}D_{i}$.

(2) Functions: Consider a family of functions $\,(f_{i}:i\in I)$, where
$f_{i}=(X,r_{i},X)\,$ (see Def. 2.1); so all $f_{i}$ have the same source and
target set $X$. The unambiguous union of that family of functions is denoted
by

$!$$\bigcup_{i\in I}f_{i}$

and defined to be $\,(X,r,X)$ where $r$ is the restriction of the relation
$\,\bigcup_{i\in I}r_{i}\,$ to the unambiguous union $\,!$$\bigcup_{i\in
I}{\rm Dom}(r_{i})$.

In particular, if all the functions $f_{i}$ have two-by-two disjoint domains,
then $\,!$$\bigcup_{i\in I}f_{i}$ $\,=\,$ $\bigcup_{i\in I}f_{i}$.

The empty set is a neutral element for unambiguous union: If
$D_{j_{0}}=\varnothing$ then $!$$\bigcup_{i\in I}D_{i}$ $\,=\,$
$!$$\bigcup_{i\in I\smallsetminus\\{j_{0}\\}}D_{i}$.

For unambiguous union the order of the sets or functions in a family does not
matter, i.e., the unambiguous union operation satisfies generalized
commutativity.

Associativity, and relation between unambiguous union and symmetric
difference:

For any two sets $D_{1},D_{2}:$ $\ D_{1}$$\,!$$\cup\,$$D_{2}$ $=$
$D_{1}\\!\\!\vartriangle\\!\\!D_{2}$ (symmetric difference). The symmetric
difference is associative. Since $\vartriangle$ and $\,!$$\cup$ are the same
when applied to two sets, the unambiguous union, as a binary operation, is
associative.

The symmetric difference of a finite family of sets $(D_{1},\,\ldots\,,D_{N})$
satisfies

$\Delta$${}_{i=1}^{{}^{N}}D_{i}$ $\ =\ $
$\\{x\in\bigcup_{i=1}^{{}^{N}}D_{i}\,:\,x$ occurs in $D_{i}$ for an odd number
of indices $i\\}$

$=\,$ $(\ldots((D_{1}\vartriangle D_{2})\vartriangle D_{3})\vartriangle$
$\ldots$ $\vartriangle D_{n-1})\vartriangle D_{n}$.

However, for unambiguous union the situation is different. As a variable-arity
operation,

$!$$\bigcup_{i\in I}D_{i}$ $\ =\ \\{x\in\bigcup_{i=1}^{{}^{N}}D_{i}\,:\,x$
occurs in $D_{i}$ for exactly one index $i\\}$.

This is usually different from $\
(\ldots((D_{1}\,!$$\cup\,D_{2})\,!$$\cup\,D_{3})\,!$$\cup\,$ $\ldots$
$\,!$$\cup\,D_{n-1})\,!$$\cup\,D_{n}\,$, since the latter is the same as the
symmetric difference. So, non-binary unambiguous union (of a family) is not
associative.

For an infinite family the unambiguous union $!$$\bigcup_{i\in I}D_{i}$ is
well-defined but the symmetric difference is not defined. [End, Remark.]

###### Proposition 10.6

.

(1) For any family $(f_{1},\ldots,f_{k})$ with $f_{i}\in M_{2,1}$ (or
$\in{\cal RM}^{\sf fin}$) for all $i\in[1,k]$:

$!$$\bigcup_{i=1}^{k}f_{i}\ \in\,M_{2,1}$ (respectively $\,\in{\cal RM}^{\sf
fin}$).

(2) Consider any $f_{i}\in$ ${\rm plep}M_{2,1}\smallsetminus\\{\theta\\}$ (or
$\in$ ${\sf pfl}{\cal RM}^{\sf fin}\smallsetminus\\{\theta\\}$), for
$i\in[1,n]$.

If $\,\delta(f_{i})$ is the same for every $i$, then

$\ !$$\bigcup_{i=1}^{k}f_{i}$ $\in\ {\sf plep}M_{2,1}$ (respectively $\,\in$
${\sf pfl}{\cal RM}^{\sf fin}$).

Proof. (1) follows straightforwardly from the definition of unambiguous union.
(2) follows easily from the definitions of $\,!$$\cup$, $\,\delta(.)$, $\,{\sf
plep}M_{2,1}$, and ${\sf pfl}{\cal RM}^{\sf fin}$. $\Box$

The input-output length difference function $\delta(.)\,$ (see Def. 7.5 for
total functions, and Prop. 7.8 for partial functions) can be generalized to
$\,{\cal RM}^{\sf fin}$, $\,M_{2,1}$, and $G_{2,1}$:

###### Definition 10.7

(general input-output length difference $\delta_{M}(.)$).

For $f\in{\cal RM}^{\sf fin}\,$ we define

$\delta_{M}(f)$ $\,=\,$ $\\{\,|f(x)|-|x|\,:\ x\in{\rm domC}(f)\\}$.

Then $\,\delta_{M}$ is a total function from ${\cal RM}^{\sf fin}$ onto ${\cal
P}_{\rm fin}({\mathbb{Z}})\,$ (the set of all finite subsets of
${\mathbb{Z}}$).

For $f\in{\sf pfl}{\cal RM}^{\sf fin}$), we have:
$\delta_{M}(f)=\\{\delta(f)\\}$. In particular, for the empty function
$\theta$ we have $\,\delta_{M}(\theta)=\varnothing$; so $\delta_{M}(\theta)$
is defined, while $\delta(\theta)$ is undefined.

###### Proposition 10.8

.

(1) If $\,g,f\in{\cal RM}^{\sf fin}$ satisfy $\,g\equiv_{\rm fin}f$, then $\
\delta_{M}(g)=\delta_{M}(f)$. Hence $\delta_{M}$ is well-defined on $M_{2,1}$.

(2) For all $g,f\in M_{2,1}$:

$\delta_{M}(g\circ f)\ \subseteq\ \delta_{M}(g)+\delta_{M}(f)$

where $+$ denotes elementwise addition in $\,{\cal P}_{\rm
fin}({\mathbb{Z}})$.

(3) Let $\Gamma$ be a finite set such that $\Gamma\cup\tau$ generates ${\cal
RM}^{\sf fin}$. Then for every word $\,w\in$ $(\Gamma\cup\tau)^{*}$,

$\delta_{M}(E_{w})\ \subseteq\ $ $[-c_{{}_{(-)}}\,|w|_{\Gamma},\
c^{{}^{(+)}}\,|w|_{\Gamma}]\,$,

where $\,c^{{}^{(+)}}\,=\,$ $\max\\{\,j:\,j\geq
0,\,j\in\delta_{M}(\gamma),\,\gamma\in\Gamma\\}$, and $\,c_{{}_{(-)}}\,=\,$
$\max\\{\,|j|:\,j\leq 0,\,j\in\delta_{M}(\gamma),\,\gamma\in\Gamma\\}$.

Proof. Both (1) and (2) are straightforward. Elementwise addition of
$X,Y\in{\cal P}_{\rm fin}({\mathbb{Z}})$ is defined by $\ X+Y=\\{x+y:x\in
X,y\in Y\\}$; hence, if $X=\varnothing$ or $Y=\varnothing$ then
$X+Y=\varnothing$.

(3) This follows from (2), using the fact that
$\,\delta_{M}(\tau_{i,j})=\\{0\\}\,$ for all $\tau_{i,j}\in\tau$. $\Box$

The inclusion “$\subseteq$” in (2) can be strict, e.g. if $g\circ f=\theta$,
but $g\neq\theta\neq f$. So the function $\delta_{M}(.)$ is not a semigroup
homomorphism.

The invariance of $\delta(.)$ under $\,\equiv_{\rm fin}\,$ (Prop. 10.8(1)),
and the fact that $f$ is a right-ideal morphism, imply that

$\delta_{M}(f)$ $\,=\,$ $\\{|f(x)|-|x|:x\in{\rm domC}(f)\\}$

$=\,$ $\\{|f(x)|-|x|:x\in{\rm Dom}(f)\\}\,$.

This is a finite set (although ${\rm Dom}(f)$ is infinite), and part (3) gives
bounds on that set.

Since the monoids $M_{2,1}$, $\,{\rm tot}M_{2,1}$, and ${\rm plep}M_{2,1}$ are
congruence-simple (see Subsection 7.1), $\delta_{M}(.)$ is not a semigroup
morphism on these monoids.

Theorem 10.9 will use the functions ${\sf C}(.)$ and ${\sf W}(.)$ from
Theorems 3.8 and 3.11. Let $\Gamma_{\rm\\!RM}$ be a finite generating set of
${\cal RM}^{\sf fin}$ (and hence $M_{2,1}$), and let $\Gamma_{\sf\\!pfl}$ be a
finite set such that $\,\Gamma_{\sf\\!pfl}\cup\tau\,$ generates ${\sf
pfl}{\cal RM}^{\sf fin}$ (and hence ${\sf plep}M_{2,1}$).

###### Theorem 10.9

(I. From an unambiguous union of partial circuits to a
$(\Gamma_{\rm\\!RM}\cup\tau)$-word).

(1) Unambiguous union of partial circuits with the same $\delta$-value

An unambiguous union of acyclic partial circuits with the same $\delta$-value
is equivalent an acyclic partial circuit, or equivalently, to a word in
$\,(\Gamma_{\rm\\!pfl}\cup\tau)^{*}$. In detail:

Let $\,\\{u_{1},\,\ldots\,,u_{k}\\}$ $\subseteq$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}\,$ be such that for all $i\neq j$ in
$[1,k]:$

$\delta(E_{u_{i}})=\delta(E_{u_{j}})$ and ${\rm Dom}(E_{u_{i}})$ $\cap$ ${\rm
Dom}(E_{u_{j}})=\varnothing$.

Let $m$ and $n$ be the common input-length, respectively output-length, of
$\,(E_{u_{1}},\,\ldots\,,E_{u_{k}})$.

Then there exists a partial circuit $C$, and hence a word $\,w={\sf W}(C)\in$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}\,$ with $E_{w}=E_{C}$, such that:

$\,\bullet$ $!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$ $\ =\ $
$\bigcup_{i=1}^{k}E_{u_{i}}$ $\,=\,E_{C}\,\in\,{\sf pfl}{\cal RM}^{\sf fin}$.

$\,\bullet$ $|C|$ $\,\leq\,$
$O\big{(}mk+nk+\sum_{i=1}^{k}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\big{)}$.

$\,\bullet$ $\ell_{\rm im}(C)=m\,$, $\ell_{\rm out}(C)=n$.

$\,\bullet$ ${\sf depth}(C)$ $\,\leq\,$ $O\big{(}\log k+\log n+\log m$ $\,+\,$
$\max\\{\max\\{{\sf depth}(u_{i}),$
$\,\log_{2}|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau}\\}\,:\,i\in[1,k]\\}\big{)}$.

$\,\bullet$ There is a deterministic algorithm that computes $\,C\,$ on input
$\,(u_{1},\,\ldots\,,u_{k})$, in log-space

(in terms of the input-length $\,\sum_{i=1}^{k}|u_{i}|$, where any
$\tau_{i,j}\in\tau$ is given the length $j$).

(2) Unambiguous union of partial circuits with different $\delta$-values

An unambiguous union of partial circuits with different $\delta$-values is
equivalent to a word in $\,(\Gamma_{\rm\\!RM}\cup\tau)^{*}$. In detail:

Let
$\,\\{u_{1},\,\ldots\,,u_{k}\\}\subseteq(\Gamma_{\sf\\!pfl}\cup\tau)^{*}\,$ be
such that for all $i\neq j$ in $[1,k]$:

$\delta(E_{u_{i}})\neq\delta(E_{u_{j}})$ (hence $\,{\rm
Dom}(E_{u_{i}})\,\cap\,{\rm Dom}(E_{u_{j}})=\varnothing$).

Let $m$ be the common input-length of $\,(E_{u_{1}},\,\ldots\,,E_{u_{k}})$,
let $\,n_{i}=m+\delta(E_{u_{i}})\,$ (for $i\in[1,k]$), and let $\ n_{\rm
max}=\max\\{n_{i}:i\in[1,k]\\}$.

Then there exists a word $\,w\in(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ such that

$\,\bullet$ $!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$ $\ =\ $
$\bigcup_{i=1}^{k}E_{u_{i}}$ $\,=\,E_{w}\,\in\,{\cal RM}^{\sf fin}$.

$\,\bullet$ $|w|_{\Gamma_{\rm\\!RM}\cup\tau}$ $\,\leq\,$
$\,O\big{(}\sum_{i=1}^{k}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\big{)}\,$.

$\,\bullet$ $\ell_{\rm in}(w)=m$.

$\,\bullet$ ${\sf depth}(w)$ $\,\leq\,$ $O(1)\,+\,\max\big{\\{}\max\\{{\sf
depth}(u_{i}),\,$
$\lceil\log_{2}|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau}\rceil\\}$
$\,:\,i\in[1,k]\big{\\}}$

$\,\bullet$ There is a deterministic algorithm that computes $\,w\,$ on input
$\,(u_{1},\,\ldots\,,u_{k})$, in log-space

(in terms of the input-length $\,\sum_{i=1}^{k}|u_{i}|$, where any
$\tau_{i,j}\in\tau$ is given the length $j$).

Proof. (1) By Prop. 10.6(2), $\ !$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$
$\,\in\,$ ${\sf pfl}{\cal RM}^{\sf fin}$, so there exists $w\in$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ such that $\,E_{w}=$ $\
!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$. We will construct a partial
circuit for $w$; then Theorem 3.11 immediately yields $w$ as a word over
$\Gamma_{\sf\\!pfl}\cup\tau$. The partial circuit to be constructed has an
input-output function $\,x\in\\{0,1\\}^{m}$ $\,\longmapsto\,$
$E_{w}(x)\in\\{0,1\\}^{n}$, where $m$ is the common input-length of
$\,(E_{u_{i}}:i\in[1,k])$, and $n$ is the common output-length.

The partial circuit is constructed so as to have four levels.

Level 1: The input is $x\in\\{0,1\\}^{m}$. The output is $x^{k}\,$ (i.e., $k$
copies of $x$). It is produced by $\,m$ binary trees, each of depth
$\,\lceil\log_{2}k\rceil$, and each consisting of $\,k\\!-\\!1\,$ fork-gates.
It is straightforward to construct the boolean circuit of level 1 in space
$O(\log(km))$.

Level 2: A preliminary remark: If we would apply
$\,(E_{u_{1}},\,E_{u_{2}},\,\ldots\,,E_{u_{k}})\,$ to $\,(x,\,\ldots\,,x)$
$\,(=x^{k})$, the result would be the concatenation
$\,E_{u_{1}}(x)\,E_{u_{2}}(x)\,\ldots\,E_{u_{k}}(x)$, which is undefined for
all $x\,$ (by disjointness of the domains). So instead, we first use the
completion $\overline{E}_{u_{i}}$ of each $E_{u_{i}}$.

Level 2 takes input $x^{k}$, and consists of the $k$ circuits
$\,\overline{C}_{u_{1}},\,\ldots\,,\overline{C}_{u_{k}}$ in parallel, where
$\overline{C}_{u_{i}}$ is a circuit for the completion of ${\sf C}(u_{i})\,$
(constructed in Prop. 9.9). Each $\overline{C}_{u_{i}}$ takes one copy of $1x$
as input (so, for this, a 1 is prepended to each of the $k$ copies of $x$,
i.e., $(1x)^{k}$ is produced). Each $\overline{C}_{u_{i}}$ has the same
output-length, namely $n\\!+\\!1$. Recall that $\,\overline{E}_{u_{i}}(1x)$
$=$ $1\,E_{u_{i}}(x)\,$ if $\,E_{u_{i}}(x)\,$ is defined, and $\,=0^{n+1}\,$
otherwise. The output of level 2 is the concatenation $\
\overline{E}_{u_{1}}(1x)$ $\,\ldots\,$ $\overline{E}_{u_{k}}(1x)\,$ of length
$\,k\,(n\\!+\\!1)$. So, the boolean circuit for level 2 has input-output
function

$x^{k}\longmapsto$ $\,\overline{E}_{u_{1}}(1x)\ \overline{E}_{u_{2}}(1x)$ $\
\ldots\ $ $\overline{E}_{u_{k-1}}(1x)\ \overline{E}_{u_{k}}(1x)\,$.

The size of the boolean circuit for level 2 is

$\leq\ k\,+\,\sum_{i=1}^{k}|\overline{u}_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}$ $\
<\ c\,\sum_{i=1}^{k}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\,$,

for some constant $c>1$. The $+k$ is for producing the $k$ 1s for $(1x)^{k}$,
and the size of the boolean circuit $\overline{C}_{u_{i}}$ is
$\,O(|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau})$, by Prop. 9.9.

The depth of this boolean circuit is

$\,\leq\,$ $O(1)\,+\,$ $\max\\{{\sf depth}(u_{i}),\,$
$\log_{2}|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau}+2\,\log_{2}(n\\!+\\!1)\,:\,$
$i\in[1,k]\\}$,

by Prop. 9.9. And $\overline{C}_{u_{i}}$ and $\overline{u}_{i}$ can be
computed from $u_{i}$ in log-space, by Prop. 9.9 and Theorem 3.8(1).

Level 3: This level has input $\ \overline{E}_{u_{1}}(1x)$ $\,\ldots\,$
$\overline{E}_{u_{k}}(1x)$, and its output is the completion of
!$\cup(E_{u_{1}},$ $\,\ldots$ $\,,$ $E_{u_{k}})(x)$. Equivalently, the output
is $\,\overline{E}_{u_{j}}(1x)$, where $j\in[1,k]$ is the unique index for
which $\,E_{u_{j}}(x)\,$ is defined; otherwise the output is $\,0^{n+1}$, if
$\,E_{u_{i}}(x)\,$ is undefined for all $i\in[1,k]$.

To obtain this output, we form the bitwise or of the $k$ bitstrings
$\,\overline{E}_{u_{i}}(1x)$, for $i\in[1,k]$. Let $y_{j}^{(i)}$ be the $j$th
output bit of $\overline{E}_{u_{i}}(1x)$, for $j\in[0,n]$, $\,i\in[1,k]$
(using the fact that all $\,E_{u_{i}}(x)\,$ are $\,0^{n+1}$, except perhaps
one). Then the $j$th output bit is

$y_{j}=\ $OR${}_{i=1}^{k}\,y_{j}^{(i)}$ for every $j\in[0,n]$.

Thus, level 3 consists of $n\\!+\\!1$ or-trees, each of size $k\\!-\\!1$ and
depth $\lceil\log_{2}k\rceil$. The $j$th or-tree (for $j\in[0,n]$) has $k$
input bits and one output bit, namely $y_{j}$. The total output of level 3 is
the concatenation $\,y_{0}y_{1}\,\ldots\,y_{n}$.

The boolean circuit for level 3 has size $(n\\!+\\!1)\,(k\\!-\\!1)$ and depth
$\lceil\log_{2}k\rceil$.

Levels 1, 2, and 3 together form an acyclic boolean (total) circuit.

Level 4: This level turns $\,y_{0}y_{1}\,\ldots\,y_{n}$, which is the output
of completion $\,!$$\cup(E_{u_{1}},\,\ldots\,,$ $E_{u_{k}})(x)$, into the
final partial output $\,!$$\cup(E_{u_{1}},\,\ldots\,,$ $E_{u_{k}})(x)\,)\,$.
This is equal to $\,y_{1}\,\ldots\,y_{n}\,$ if $y_{0}=1$, and is undefined if
$y_{0}=0$.

We build a partial circuit for level 4 as follows. We use the partial one-bit
gate $h_{0}$ such that $h_{0}(1)=1$, and $h_{0}(0)$ is undefined. First, a
partial $h_{0}$-gate is connected to the leftmost wire (that carries the bit
$y_{0}$). Second, $n$ copies of the output-wire of the $h_{0}$-gate are made
(by a binary tree of depth $\lceil\log_{2}n\rceil$, made of $n\\!-\\!1$ fork-
gates); then we form

$(h_{0}(y_{0}))^{n}\ {\sf and}_{n}\ y_{1}\,\ldots\,y_{n}$

(the bitwise and of two bitstrings of length $n$). Thus the result is
undefined if $y_{0}=0$; and it is $\,y_{1}\,\ldots\,y_{j}\,\ldots\,y_{n}\,$ if
$y_{0}=1$.

The size the partial circuit of level 4 is $\,n\\!-\\!1+n$, and the depth is
$\lceil\log_{2}n\rceil+1$. [End, Level 4]

This completes the construction of a partial circuit for
$\,!$$\cup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$. As mentioned at the beginning of
the proof, an equivalent word $w={\sf
W}(C)\in(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ can now be obtained by Theorem 3.11.

By adding up the sizes and the depths of the four levels we obtain that the
total size of the partial circuit is

$\leq\,$
$O\big{(}mk+nk+\sum_{i=1}^{k}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\big{)}$;

and the depth is

$\leq\,O\big{(}\log k+\log n+\log m+\,$ $\max\\{\max\\{{\sf depth}(u_{i}),$
$\,\log_{2}|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau}\\}\,:\,i\in[1,k]\\}\big{)}$.

Complexity of computing $w$: For levels 1, 3, and 4, the log-space
computability is straightforward. For level 2, Prop. 9.9 yields log-space
computability of $\overline{u_{i}}$.

(2) Since $\,!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})\in$ ${\cal RM}^{\sf
fin}$, by Prop. 10.6(1), there exists a word
$w\in(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ such that $\,E_{w}=$
$\,!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$. We construct the word $w$ in
four levels similar to the ones in part (1). Let $m$ be the common input-
length of $(E_{u_{i}}:i=1,\ldots,k)$. There is no common output-length.

We first construct a (slightly generalized) partial circuit for
$\,!$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})$, and then a word in
$(\Gamma_{\rm\\!RM}\cup\tau)^{*}$.

Level 1: The input is $x\in\\{0,1\\}^{m}$, the output is $x^{k}\,$ (i.e., $k$
copies of $x$), and a boolean circuit for this is built as in part (1).

Level 2: The input is $x^{k}$. Level 2 consists of the $k$ boolean circuits
$\,\overline{C}_{u_{1}},\,\ldots\,,\overline{C}_{u_{k}}$ in parallel, just as
in part (1), except that now $\overline{C}_{u_{i}}$ has output-length
$n_{i}+1$, which is different for every $i\in[1,k]$. The output of level 2 is
the concatenation $\,\overline{E}_{u_{1}}(1x)\ \ldots\
\overline{E}_{u_{k}}(1x)$, of length $\,k+\,\sum_{i=1}^{k}n_{i}$. By the same
reasoning as in part (1) we find that the size of the boolean circuit
$C^{(2)}$ of level 2 is

$|C^{(2)}|\,\leq\,$
$k\,+\,\sum_{i=1}^{k}|\overline{u}_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}$
$\,<\,O\big{(}\sum_{i=1}^{k}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\big{)}\,$,

and the depth of level 2 is

${\sf depth}(C^{(2)})\,\leq\,$ $O(1)\,+\,$ $\max\\{{\sf depth}(u_{i}),\,$
$\log_{2}|u_{i}|_{\Gamma_{\sf\\!tfl}\cup\tau}+2\,\log_{2}(n_{i}+1)\,:\,$
$i\in[1,k]\\}$,

Level 3: This level has input $\,\overline{E}_{u_{1}}(1x)\ \ldots\
\overline{E}_{u_{k}}(1x)$, of length $\,k+\,\sum_{i=1}^{k}n_{i}\,$. Its output
is $\,\overline{E}_{u_{j}}(1x)\,$ $(\,=1\,E_{u_{j}}(x))$, where $j\in[1,k]$ is
the unique index for which $\,E_{u_{j}}(x)\,$ is defined; otherwise the output
is $0\,$ (if $\,E_{u_{i}}(x)\,$ is undefined for all $i\in[1,k]$).

As in level 3 of part (1), let $y_{0}$ be the or of the leading bits of the
$k$ strings $\overline{E}_{u_{i}}(1x)\,$ (for $i\in[1,k]$). Hence,
$\,y_{0}=1\,$ if $\ !$$\bigcup(E_{u_{1}},\,\ldots\,,E_{u_{k}})(x)\,$ is
defined, and $y_{0}=0$ otherwise. As in level 3 of (1), we can use an or-tree
(of size $k\\!-\\!1$ and depth $\lceil\log_{2}k\rceil$) to compute $y_{0}$.

Since the strings $\overline{E}_{u_{i}}(1x)\,$ (for $i\in[1,k]$) all have
different lengths, the output cannot be obtained by an or-trees as in level 3
of part (1). Instead, we first apply the transformation $\xi_{i}$ to each
$\overline{E}_{u_{i}}(1x)$, so the output of level 3 is $y_{0}\
\xi_{1}(\overline{C}_{u_{1}}(1x))$ $\ \ldots\ $
$\xi_{k}(\overline{C}_{u_{k}}(1x))$. Each $\,\xi_{i}(.)$ (for $i\in[1,k]$) is
the right-ideal morphism defined by

$\xi_{i}:\ z_{0}\,y\in\\{0,1\\}\,\\{0,1\\}^{n_{i}}$ $\,\longmapsto\,$
$\xi_{i}(z_{0}y)\in\\{\varepsilon\\}\cup\\{0,1\\}^{n_{i}}\,$, where

$\xi_{i}(0y)=\varepsilon\,$, and

$\xi_{i}(1y)=1y\,$;

so $\,{\rm domC}(\xi_{i})=\\{0,1\\}^{n_{i}+1}$. To express $\xi_{i}$ by a word
in $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ we introduce the right-ideal morphism

$\zeta:\ z_{0}z_{1}\in\\{0,1\\}^{2}\,\longmapsto\,\zeta(z_{0}z_{1})$ $\,\in\,$
$\\{\varepsilon\\}\cup\\{0,1\\}\,$, where

$\zeta(0z_{1})=\varepsilon\,$, and

$\zeta(1z_{1})=z_{1}\,$;

so $\,{\rm domC}(\zeta)=\\{0,1\\}^{2}$.

We can either include $\zeta$ into the generating set $\Gamma_{\rm\\!RM}$, or
express it by a fixed word in $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$.

Now for all $\,y=y_{1}\,\ldots\,y_{j}\,\ldots\ y_{n_{i}}$, with $y_{j}\in$
$\\{0,1\\}\,$ for $j\in[1,n_{i}]$, we have

$\xi_{i}(z_{0}\,y_{1}\,\ldots\,y_{j}\,\ldots\,y_{n_{i}})$ $\,=\,$
$\zeta(z_{0}y_{1})\ \ldots\ \zeta(z_{0}y_{j})\ \ldots\ \zeta(z_{0}y_{n_{i}})$.

Indeed, if $z_{0}=0$ this expression becomes $\varepsilon$, and if $z_{0}=1$
the expression becomes $y$.

Thus, $\xi_{i}(z_{0}\,y_{1}\,\ldots\,y_{n_{i}})$ can be computed by a tree of
fork-gates (of size $n_{i}-1$ and depth $\lceil\log_{2}n_{i}\rceil$), that
makes $n_{i}$ copies of $z_{0}$; this tree can be converted into a
$(\Gamma_{\sf\\!tfl}\cup\tau)$-word of size $O(n_{i})$. The $n_{i}$ copies of
$z_{0}$ are then combined with $y_{1}\,\ldots\,y_{j}\,\ldots\,y_{n_{i}}$ in a
row of $n_{i}$ instances of $\zeta(.)$. This yields a word for $\xi_{i}$ over
$\\{\zeta,\,{\sf fork}\\}$ of size $O(n_{i})$.

Hence the output $\,y_{0}\ \xi_{1}(\overline{C}_{u_{1}}(1x))$ $\ \ldots\ $
$\xi_{k}(\overline{C}_{u_{k}}(1x))\,$ of level 3 can be computed by a word
$w^{(3)}$ $\in(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ of size

$|w^{(3)}|_{\Gamma_{\rm\\!RM}\cup\tau}$ $\,\leq\,$ $k-1$ $+$
$\sum_{i=1}^{k}O(n_{i})$ $\ \leq\ O(\sum_{i=1}^{k}n_{i})$,

where, $k\\!-\\!1$ is for computing $y_{0}$, and $O(n_{i})$ is for $\xi_{i}$.
And the depth is

${\sf depth}(w^{(3)})\,\leq\,$ $\lceil\log_{2}k\rceil$ $+$
$\max\\{\lceil\log_{2}n_{i}\rceil:i\in[1,k]\\}$ $\,+\,$ $O(1)$.

Level 4: This level has input $0$ if $\,E_{u_{i}}(x)\,$ is undefined for all
$i\in[1,k]$; or it is $\,\overline{E}_{u_{j}}(1x)$ $(=1\,E_{u_{j}}(x))$, where
$j\in[1,k]$ is the unique index for which $\,E_{u_{j}}(x)\,$ is defined. The
circuit for level 4 consists of the single right-ideal morphism $e$, defined
by ${\rm domC}(e)=$ $\\{1\\}$, $\,{\rm imC}(e)=\\{\varepsilon\\}$, and

$e(1)=\varepsilon\,$

with $e(0)$ undefined.

Then the output of level 4 is either $\,E_{u_{j}}(x)$, if $y_{0}=1$ and $j$ is
as given for the input of level 4; or the output is undefined (if $y_{0}=0$).

Hence the size and depth of level 4 are constants.

The total size of the word $w$ of part (2) is $\ \leq\,$
$O\big{(}\sum_{i=1}^{k}(|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}+n_{i})\big{)}$.

The total depth of $w$ is

${\sf depth}(w)\,\leq\,$ $O(1)\,+\,\max\big{\\{}\max\\{{\sf depth}(u_{i}),\,$
$\lceil\log_{2}|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\rceil$ $+$
$2\,\lceil\log_{2}(n_{i}+1)\rceil\\}\ :\ i\in[1,k]\big{\\}}$.

Finally, since $\,n_{i}\leq$ $c\,|u_{i}|_{\Gamma_{\sf\\!pfl}\cup\tau}\,$ by
Prop. 10.1, the term involving $n_{i}$ can be removed from the formulas for
size and depth.

All the levels are easily computed in log-space. For levels 1 and 2, this is
similar to part (1); level 3 has a very simple structure, and level 4 has just
one gate. $\Box$

###### Definition 10.10

($\,\\{\cdot,\,!$$\cup\\}$-expressions, their length, depth and evaluation).

Let $\Gamma$ be one of the finite sets $\Gamma_{\rm\\!RM}$,
$\Gamma_{\sf\\!pfl}$, or $\Gamma_{\sf\\!tfl}$, seen above.

(1) A $\,\\{\cdot,!$$\cup\\}$-expression over $\Gamma\cup\tau$ is defined
recursively as follows.

$\ \bullet$ (Words) Any word $w\in(\Gamma\cup\tau)^{*}$ is a
$\\{\cdot,!$$\cup\\}$-expression.

$\ \bullet$ (Concatenation) If $\,W_{1}$ and $\,W_{2}$ are
$\\{\cdot,!$$\cup\\}$-expressions, then so is $\,W_{2}\cdot W_{1}\ $ (also
denoted

by $\,W_{2}\,W_{1}$).

$\ \bullet$ (Unambiguous union) If $(W_{k},\,\ldots\,,W_{1})$ is a sequence of
$\\{\cdot,!$$\cup\\}$-expressions with $k\geq 2$, then

$\,!$$\cup\,(W_{k},\,\ldots\,,W_{1})$ is a $\\{\cdot,!$$\cup\\}$-expression.

The length $\,|W|_{\Gamma\cup\tau}$ and the depth of a
$\\{\cdot,!$$\cup\\}$-expression $W$ are defined recursively:

$\ \bullet$ For any word $w\in(\Gamma\cup\tau)^{*}$, the length
$\,|w|_{\Gamma\cup\tau}$ and $\,{\sf depth}(w)$ are as in Definitions 3.5 and
3.12.

$\ \bullet$ If $W_{1}$ and $W_{2}$ are $\\{\cdot,!$$\cup\\}$-expressions, then

$|W_{2}\cdot W_{1}|_{\Gamma\cup\tau}$ $\,=\,$
$|W_{1}|_{\Gamma\cup\tau}\,+\,|W_{2}|_{\Gamma\cup\tau}\,$,

${\sf depth}(W_{2}\cdot W_{1})\,=\,$ ${\sf depth}(W_{2})+{\sf
depth}(W_{1})\,$.

$\ \bullet$ If $(W_{k},\,\ldots\,,W_{1})$ is a sequence of
$\\{\cdot,!$$\cup\\}$-expressions with $k\geq 2$, then

$|!$$\cup\,(W_{k},\,\ldots\,,W_{1})|_{\Gamma\cup\tau}$ $\,=\,$
$\sum_{i=1}^{k}|W_{i}|_{\Gamma\cup\tau}\,$,

${\sf depth}(!$$\cup\,(W_{k},\,\ldots\,,W_{1}))$ $\,=\,$ $\max\\{{\sf
depth}(W_{i}):i\in[1,k]\\}\,$.

(2) The evaluation function $E_{W}$ of a $\\{\cdot,!$$\cup\\}$-expression $W$
is defined recursively:

$\ \bullet$ A word $w\in(\Gamma\cup\tau)^{*}$ has an evaluation function
$\,E_{w}\in M_{2,1}$ (or $\in{\cal RM}^{\sf fin}$), obtained by composing

the generators from right to left, as they appear in $w$.

$\ \bullet$ The concatenation $\,W_{2}\cdot W_{1}\,$ of
$\\{\cdot,!$$\cup\\}$-expressions has the evaluation function
$\,E_{W_{2}}\circ E_{W_{1}}(.)\,$

(composition of functions).

$\ \bullet$ The unambiguous union $\,!$$\cup\,(W_{k},\,\ldots\,,W_{1})$ of
$\,\\{\cdot,!$$\cup\\}$-expressions has the evaluation function

$\,!$$\cup\,(E_{W_{k}},\,\ldots\,,E_{W_{1}})$ (unambiguous union of
functions).

###### Lemma 10.11

(distributivity of composition over union with disjoint domains).

(1) Let $f,g,\alpha,\beta$ be functions $X\to X$ for some set $X$, such that
$\ {\rm Dom}(\alpha)\,\cap\,{\rm Dom}(\beta)=\varnothing$. Then

(1.a) ${\rm Dom}(\alpha\circ f(.))$ $\,\cap\,$ ${\rm Dom}(\beta\circ f(.))$
$=$ $\varnothing$,

(1.b) ${\rm Dom}(f\circ\alpha(.))$ $\,\cap\,$ ${\rm Dom}(g\circ\beta(.))$ $=$
$\varnothing$.

(2) Let $(f_{i}:i\in I)$ and $(g_{j}:j\in J)$ be families of functions on $X$
with $\,{\rm Dom}(f_{i_{1}})\cap{\rm Dom}(f_{i_{2}})$ $=$ $\varnothing\,$ for
all $i_{1}\neq i_{2}$ in $I$, and $\,{\rm Dom}(g_{j_{1}})\cap{\rm
Dom}(g_{j_{2}})$ $=$ $\varnothing\,$ for all $j_{1}\neq j_{2}$ in $J$. Then:

(2.a) For all $i_{1},i_{2},j_{1},j_{2}$ such that $\,(j_{1},i_{1})$ $\neq$
$(j_{2},i_{2}):$ ${\rm Dom}(g_{j_{1}}\circ f_{i_{1}})$ $\cap$ ${\rm
Dom}(g_{j_{2}}\circ f_{i_{2}})$ $=$ $\varnothing$.

(2.b) (Distributivity:) ($!$$\bigcup_{j\in J}g_{j}$) $\circ$
($!$$\bigcup_{i\in I}f_{i}$) $\ =\ $ $!$$\bigcup_{(i,j)\in I\times
J}\,g_{j}\circ f_{i}$.

Proof. (1.a) For any function $X\stackrel{{\scriptstyle F}}{{\to}}X$, $\ {\rm
Dom}(F)=F^{-1}(X)$. Hence, $\,{\rm Dom}(\alpha\circ f(.))$ $\,\cap\,$ ${\rm
Dom}(\beta\circ f(.))$ $\,=\,$ $f^{-1}\alpha^{-1}(X)$ $\,\cap\,$
$f^{-1}\beta^{-1}(X)$ $\,=\,$ $f^{-1}\big{(}\alpha^{-1}(X)$ $\,\cap\,$
$\beta^{-1}(X)\big{)}$ $\,=\,$ $f^{-1}(\varnothing)=\varnothing$.

(1.b) We have $\,{\rm Dom}(f\circ\alpha(.))$ $\subseteq{\rm Dom}(\alpha)$;
indeed, if $f(\alpha(x))$ is defined, then $\alpha(x)$ is defined too. Hence,
$\,{\rm Dom}(f\circ\alpha(.))$ $\,\cap\,$ ${\rm Dom}(g\circ\beta(.))$
$\,\subseteq\,$ ${\rm Dom}(\alpha)\,\cap\,{\rm Dom}(\beta)=\varnothing$.

(2) If $i_{1}\neq i_{2}$ then (1.b) implies $\,{\rm Dom}(g_{j_{1}}\circ
f_{i_{1}})$ $\cap$ ${\rm Dom}(g_{j_{2}}\circ f_{i_{2}})$ $=$ $\varnothing\,$
for all $j_{1},j_{2}$ (including if $j_{1}=j_{2}$). If $i_{1}=i_{2}$ and
$j_{1}\neq j_{2}$ then (1.a) implies $\,{\rm Dom}(g_{j_{1}}\circ f_{i_{1}})$
$\cap$ ${\rm Dom}(g_{j_{2}}\circ f_{i_{1}})$ $=$ $\varnothing$.

By disjointness of the domains, the distributivity of composition over
unambiguous union now follows from the distributivity of composition over
union. $\Box$

###### Proposition 10.12

(partial circuits for the composition of unambiguous unions).

Consider two finite sets

$\\{(u^{(1)},\,d_{u}^{(1)}),\ \ldots\ ,(u^{(h)},\,d_{u}^{(h)})\\}$, $\
\\{(v^{(1)},\,d_{v}^{(1)}),\ \ldots\ ,(v^{(k)},\,d_{v}^{(k)})\\}$ $\
\subseteq\ (\Gamma_{\sf\\!pfl}\cup\tau)^{*}\times{\mathbb{Z}}$

satisfying the following assumptions:

for all $i\in[1,h]:$ if $E_{u^{(i)}}\neq\theta$ then
$\,d_{u}^{(i)}=\delta(u^{(i)})$;

for all $j\in[1,k]:$ if $E_{v^{(j)}}\neq\theta$ then
$\,d_{v}^{(j)}=\delta(v^{(j)})$;

for all $i_{1}\neq i_{2}$ in $[1,h]:$ $\ {\rm Dom}(E_{u_{i_{1}}})\cap{\rm
Dom}(E_{u_{i_{2}}})=\varnothing$;

for all $j_{1}\neq j_{2}$ in $[1,k]:$ $\ {\rm Dom}(E_{v_{j_{1}}})\cap{\rm
Dom}(E_{v_{j_{2}}})=\varnothing$.

Let $m$ be the common input-length of $\
\\{v_{j}u_{i}\,:\,i\in[1,h],\,j\in[1,k]\\}$;

let $n_{b}\,=\,$
$m+\max\\{d_{u}^{(i)}+d_{v}^{(j)}:\,i\in[1,h],\,j\in[1,k]\\}$;

let $n_{a}\,=\,$
$m+\min\\{d_{u}^{(i)}+d_{v}^{(j)}:\,i\in[1,h],\,j\in[1,k]\\}$.

We restrict every $E_{v_{j}u_{i}}(.)\,$ to $\\{0,1\\}^{\geq m}\ $ (for
$\,i\in[1,h],\,j\in[1,k]$). Then we have:

(1) (Decomposition according to $\delta$-values).

For every $r\in[n_{a},n_{b}]$ there exists $\,w^{(r)}\in$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ such that

(1.1) $E_{w^{(r)}}\ =\ $ $!$$\bigcup$ $\big{(}E_{v_{j}}\circ
E_{u_{i}}(.)\,:\,(i,j)\in[1,h]\times[1,k],$ $\
\delta(E_{v_{j}u_{i}})=r\\!-\\!m\big{)}$;

moreover, by Def. 10.10, this is the evaluation function of the expression

$!$$\bigcup\big{(}v_{j}u_{i}\,:\,$ $(i,j)\in[1,h]\times[1,k],\
\delta(E_{v_{j}u_{i}})=r\\!-\\!m\big{)}$;

(1.2) $E_{w^{(r)}}\in$ ${\sf pfl}{\cal RM}^{\sf fin}$;

(1.3) if $E_{w^{(r)}}\neq\theta\,$ then $E_{w^{(r)}}$ satisfies:

${\rm imC}(E_{w^{(r)}})\subseteq\\{0,1\\}^{r}$, ${\rm
domC}(E_{w^{(r)}})\subseteq\\{0,1\\}^{m}$, so

$\delta(E_{w^{(r)}})=r\\!-\\!m$;

(1.4) $|w^{(r)}|_{\Gamma_{\sf pfl}\cup\tau}$ $\ \leq\ $
$O\big{(}|I|\,|J|\,m\,n$ $\,+\,$ $\sum(\,|v_{j}u_{i}|_{\Gamma_{\sf
pfl}\cup\tau}\,:\,$ $(i,j)\in[1,h]\times[1,k],\
\delta(E_{v_{j}u_{i}})=r\\!-\\!m)\,\big{)}$;

(1.5) ${\rm maxindex}_{\tau}(w)$ $\,\leq\,$ $O\big{(}\max(\,\\{|I|\,|J|\,m,\
|I|\,|J|\,n\\}$

$\cup$ $\\{{\rm maxindex}_{\tau}(v_{j}u_{i})\,:\,(i,j)\in[1,h]\times[1,k],$ $\
\delta(E_{v_{j}u_{i}})=r\\!-\\!m\\})\,\big{)}.$

(1.6) ${\sf depth}(w^{(r)})$ $\,\leq\,$ $O\big{(}\log_{2}(hk)$ $\,+\,$

$\max\\{{\sf depth}(v_{j})+{\sf depth}(u_{i})$ $+$
$\log_{2}|v_{j}u_{i}|_{\Gamma_{\sf pfl}}\,:\,$ $i\in[1,h],\,j\in[1,k],\
\delta(E_{v_{j}u_{i}})=r\\!-\\!m\\}\big{)}$;

(1.7) $w^{(r)}$ and $\,m\\!-\\!r\,$ can be computed from
$\,\\{u_{1},\,\ldots\,,u_{h}\\}$, $\\{v_{1},\,\ldots\,,v_{k}\\}$

in log-space.

(2) (Recombination into an unambiguous union).

(2.1) ${\rm Dom}(E_{w^{(r)}})$ $\cap$ ${\rm Dom}(E_{w^{(s)}})=\varnothing$ for
all $r\neq s$ in $[n_{a},n_{b}]$.

(2.2) $!$$\bigcup\big{(}E_{w^{(r)}}:r\in[n_{a},n_{b}]\big{)}\ $ $(\in
M_{2,1})\,$ is the evaluation function of the expression

$!$$\bigcup(v_{j}u_{i}\,:\,$ $(i,j)\in[1,h]\times[1,k])$ $\ =\ $
($!$$\bigcup_{j=1}^{k}v_{j}\big{)}$ $\cdot$
($!$$\bigcup_{i=1}^{h}u_{i}\big{)}$;

and $\delta_{M}$ of this function is $\ \\{r\\!-\\!m\,:\,r\in[n_{a},n_{b}],\
E_{w^{(r)}}\neq\theta\\}$.

The set $\ \\{(w^{(r)},\,r\\!-\\!m):r\in[n_{a},n_{b}]\\}\,$ can be computed
from $\,\\{u_{1},\,\ldots\,,u_{h}\\},\,\\{v_{1},\,\ldots\,,v_{k}\\}$

in log-space.

Moreover, a word $w\in(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ for the disjoint union
of functions in (2.2) can be found in log-space, by Theorem 10.9(2).)

Proof. (1.1), (1.2) and (1.3) follow from Theorem 10.9(1), since for
$E_{w^{(r)}}$ we only consider words $v_{j}u_{i}$ with the same $\delta$-value
(namely $r\\!-\\!m$). (1.4) follows from the fact that for $x\in{\rm
Dom}(E_{w^{(r)}})$ we have $|E_{w^{(r)}}(x)|-|x|=r$, while for $x\in{\rm
Dom}(E_{w^{(s)}}$ we have $|E_{w^{(s)}}(x)|-|x|=s\neq r$. (1.5), (1.6), (1.7),
and (1.8) follow from Theorem 10.9(1), applied to the unambiguous union
$!$$\bigcup\big{(}v_{j}u_{i}\,:\,(i,j)\in[1,h]\times[1,k],$
$\,m+\delta(E_{v_{j}u_{i}})=r\big{)}$. (2) follows immediately from the
properties of the functions $E_{w^{(r)}}$ proved in (1). $\Box$

So far we have proved the following: (1) The unambiguous union of a finite
family of functions in $M_{2,1}$ (or in ${\cal RM}^{\sf fin}$) is in $M_{2,1}$
(respectively in ${\cal RM}^{\sf fin}$), by Prop. 10.6. (2) The unambiguous
union of a finite family of functions in ${\rm plep}M_{2,1}$ (or ${\sf
pfl}{\cal RM}^{\sf fin}$) with the same $\delta$-value is in ${\rm
plep}M_{2,1}$ (respectively ${\sf pfl}{\cal RM}^{\sf fin}$), and a circuit for
it can be constructed (Theorem 10.9). If the functions have different
$\delta$-values then their unambiguous union is just in $M_{2,1}$ (or in
${\cal RM}^{\sf fin}$), and a word in $(\Gamma_{\rm\\!RM}\cup\tau)^{*}$ can be
constructed by Theorem 10.9. (3) The composition of two finite unambiguous
unions of functions in $M_{2,1}$ (or in ${\cal RM}^{\sf fin}$) is a function
in $M_{2,1}$ (respectively in ${\cal RM}^{\sf fin}$); a finite set of ${\rm
plep}M_{2,1}$ (or ${\sf pfl}{\cal RM}^{\sf fin}$) circuits for it can be
constructed, one for each $\delta$-value (Prop. 10.12).

###  10.3 Decomposition into an unambiguous union of partial circuits

The next Theorem shows that, conversely, any “generalized circuit” $w\in$
$(\Gamma\cup\tau)^{*}\,$ (where $\Gamma$ is finite and $\Gamma\cup\tau$
generates ${\cal RM}^{\sf fin}$, hence $M_{2,1}$) can be decomposed into an
equivalent unambiguous union of partial circuits, one for each number in
$\delta_{\\!M}(w)$.

The proof of the Theorem uses the following finite generating set of
$M_{2,1}\,$ (see [6, Section 3]):

$a_{0}=\left(\begin{array}[]{l|l}0&1\\\ 1&0\end{array}\right)$,
$a_{1}=\left(\begin{array}[]{r|r|r}00&01&1\\\ 00&1&01\end{array}\right)$,
$a_{2}=\left(\begin{array}[]{r|r|r}0&10&11\\\ 10&0&11\end{array}\right)$,
$\tau_{1,2}=$ $\left(\begin{array}[]{r|r|r|r}00&01&10&11\\\
00&10&01&11\end{array}\right)$,

$a_{3}=(\varepsilon\to 0)$, $a_{4}=(0\to\varepsilon)$, $a_{5}=(0\to 00)$,
$a_{6}=(00\to 0)$, $a_{7}=\left(\begin{array}[]{l|l}0&1\\\
0&0\end{array}\right)$, and
$a_{8}=\left(\begin{array}[]{r|r}0&1\\\ 0&01\end{array}\right)$ .

Let $\Gamma_{\\!M}$ $=$ $\\{a_{i}:i\in[0,8]\\}$; then $\Gamma_{\\!M}\cup\tau$
generates $M_{2,1}$. Since we will use a generating set of the form
$\Gamma\cup\tau$, the generator $\tau_{1,2}$ above will be considered to be
only in $\tau$, and not in $\Gamma_{\\!M}$.

The elements of $\Gamma_{\\!M}$ are pfl (plep with fixed input-length) except
for $a_{1}$, $a_{2}$, and $a_{8}$. The non-pfl generators can be written as
unambiguous unions of pfl functions as follows:

$a_{1}=\left(\begin{array}[]{r|r|r}00&01&1\\\ 00&1&01\end{array}\right)$ $\ =\
$ $!$$\bigcup$$\,\big{\\{}(01\to 1),\ (00\to 00),$ $\ (1\to 01)\big{\\}}$ $\
=\ $ $!$$\bigcup$$\,\\{a_{1,-1},\ a_{1,0},\ a_{1,1}\\}$ ;

the $a_{1,k}\,$ (for $k\in\\{-1,0,1\\}=\delta_{M}(a_{1})\,$) have 2-by-2
disjoint domains;

$a_{2}=$ $\left(\begin{array}[]{r|r|r}0&10&11\\\ 10&0&11\end{array}\right)$ $\
=\ $ $!$$\bigcup$$\,\big{\\{}\\!(10\to 0),\ (11\to 11),\ (0\to 10)\big{\\}}$
$\ =\ $ $!$$\bigcup$$\,\\{a_{2,-1},\ a_{2,0},\ a_{2,1}\\}\,$;

the $a_{2,k}\,$ (for $k\in\\{-1,0,1\\}=\delta_{M}(a_{2})\,$) have 2-by-2
disjoint domains.

$a_{8}=\left(\begin{array}[]{r|r}0&1\\\ 0&01\end{array}\right)$ $\,=\,$
$!$$\bigcup\,\\{(0\to 0),\ (1\to 01)\\}$ $\,=\,$ $!$$\bigcup\,\\{a_{8,0},\
a_{8,1}\\}\,$;

moreover, the $a_{8,k}\,$ (for $k\in\\{0,1\\}=\delta_{M}(a_{8})\,$) have
disjoint domains;

From $\Gamma_{\\!M}$ we thus obtain the set

$\Gamma_{\\!M,\,{\sf pfl}}$ $=$ $\\{a_{0},\,a_{1,-1},\,a_{1,0},\,a_{1,1},\,$
$a_{2,-1},\,a_{2,0},\,a_{2,1},\,$
$a_{3},\,a_{4},\,a_{5},\,a_{6},\,a_{7},\,a_{8,0},\,a_{8,1}\\}\,$.

So, $\Gamma_{\\!M,\,{\sf pfl}}\subseteq$ ${\sf pfl}{\cal RM}^{\sf fin}$; and
$\Gamma_{\\!M,\,{\sf pfl}}$ consists of the pfl elements of $\Gamma_{\\!M}$,
together with the eight newly introduced pfl fragments of the non-plep
elements of $\Gamma_{\\!M}$.

The monoid generated by $\Gamma_{\\!M,\,{\sf pfl}}\cup\tau$ in ${\cal RM}^{\sf
fin}$ is a submonoid of ${\sf pfl}{\cal RM}^{\sf fin}$ that, under the map of
the congruence $\equiv_{\rm fin}$, maps onto ${\rm plep}M_{2,1}$. If we want
to generate all of ${\sf pfl}{\cal RM}^{\sf fin}$ we can add the gates
$\,\\{{\sf and},{\sf or},{\sf fork}\\}\,$ to $\Gamma_{\\!M,\,{\sf pfl}}\,$
(the gate $\,{\sf not}\,$ is already included).

In Theorem 10.13(2), $\,{\sf fLog\,unif\,AC}_{2}$ denotes the parallel
complexity class ${\sf AC}_{2}$ with log-space uniformity.

###### Theorem 10.13

(II. Decomposing functions in ${\cal RM}^{\sf fin}$ or $M_{2,1}$ into an

unambiguous union of partial circuits).

(1) Function form of the Theorem:

For any $f\in M_{2,1}$, let $\,m={\rm maxlen}\big{(}{\rm domC}(f)\big{)}$. And
let $\,n_{a}={\rm minlen}\big{(}f(\\{0,1\\}^{m})\big{)}\,$ and $\,n_{b}$ $=$
${\rm maxlen}\big{(}f(\\{0,1\\}^{m})\big{)}$. Then there exist functions
$\,f^{(n_{a})},\,\ldots\,,f^{(n_{b})}$ $\in$ ${\rm plep}M_{2,1}$ such that:

$\,\bullet$ $f\,=$ $\ \bigcup_{i=n_{a}}^{\ \ n_{b}}f^{(i)}$ $\ =\ $
$!$$\bigcup_{i=n_{a}}^{\ \ n_{b}}f^{(i)}$.

$\,\bullet$ For all $i\neq j:$ ${\rm Dom}(f^{(i)})\cap{\rm
Dom}(f^{(j)})=\varnothing$.

$\,\bullet$ For all $i\in[n_{a},n_{b}]$: $\ f^{(i)}$ is the restriction of $f$
such that

${\rm domC}(f^{(i)})$ $\,=\,$ $\\{0,1\\}^{m}\,\cap\,f^{-1}(\\{0,1\\}^{i})$;
hence

$f^{(i)}(\\{0,1\\}^{m})\,=\,{\rm im}C(f^{(i)})$ $\ \subseteq\ $
$\\{0,1\\}^{i}$,

$\delta(f^{(i)})=i\\!-\\!m$ if $f^{(i)}\neq\theta$.

(2) Circuit form of the Theorem:

Let $\,\Gamma_{\\!M}=\\{a_{i}:i\in[0,8]\\}$ and $\,\Gamma_{\\!M,{\sf pfl}}$
$\subseteq\Gamma_{\sf\\!pfl}\,$ be as described before the Theorem.

For any $\,w\in(\Gamma_{\\!M}\cup\tau)^{*}$, let $\,m=\ell_{\rm in}(w)$. Then
there exist $\,n_{b}\geq n_{a}\geq 0$, and there exist partial circuits
$\,W^{(n_{a})},$ $\,\ldots\,,$ $W^{(n_{b})}$ $\,\in\,$
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}\,$ such that the following holds:

(2.1) Decomposition of $w$ into partial circuits:

$\,\bullet$ $E_{w}\,=\ \bigcup_{i=n_{a}}^{\ n_{b}}E_{W^{(i)}}$ $\ =\ $
$!$$\bigcup_{i=n_{a}}^{\ n_{b}}E_{W^{(i)}}$; so $E_{w}$ is the evaluation
function of  $!$$\bigcup_{i=n_{a}}^{\ n_{b}}\\!W^{(i)}$.

$\,\bullet$ For all $i\neq j:$ ${\rm Dom}(E_{W^{(i)}})\,\cap\,{\rm
Dom}(E_{W^{(j)}})=\varnothing$.

$\,\bullet$ $\,m\,\leq\,$ ${\rm
maxlen}(\Gamma_{\\!M})\cdot|w|_{\Gamma_{\\!M}}$ $\,+\,$ ${\rm
maxindex}_{\tau}(w)\,$;

$n_{a}\,\leq\,n_{b}\,\leq\,$ $2\ {\rm
maxlen}(\Gamma_{\\!M})\cdot|w|_{\Gamma_{\\!M}\cup\tau}$ $\,+\,$ ${\rm
maxindex}_{\tau}(w)$.

(2.2) For all $i\in[n_{a},n_{b}]:$

$\,\bullet$ $E_{W^{(i)}}$ is the restriction of $E_{w}$ such that

${\rm domC}(E_{W^{(i)}})$ $\,=\,$ $\,\\{0,1\\}^{m}\,\cap\,E_{w}^{\
-1}(\\{0,1\\}^{i})\ \subseteq\ \\{0,1\\}^{m}$.

Hence $E_{W^{(i)}}$ (but not the word $W^{(i)}$) is uniquely determined by
$E_{w}$;

$E_{W^{(i)}}(\\{0,1\\}^{m})\,=\,{\rm im}C(E_{W^{(i)}})$ $\ \subseteq\ $
$\\{0,1\\}^{i}$,

$\delta(E_{W^{(i)}})=i\\!-\\!m$ if $E_{W^{(i)}}\neq\theta$.

$\,\bullet$ $|W^{(i)}|_{\Gamma_{\\!M,\,{\sf pfl}}\cup\tau}$ $\,\leq\,$ ${\rm
maxlen}(\Gamma_{\\!M})\,|w|_{\Gamma_{\\!M}\cup\tau}$ $\,+\,$ ${\rm
maxindex}_{\tau}(w)\,$;

${\rm maxindex}_{\tau}(W^{(i)})\,\leq\,{\rm maxindex}_{\tau}(w)$.

$\,\bullet$ ${\sf depth}(w)$ $\,=\,$ $\max\\{{\sf
depth}(W^{(i)}):i\in[n_{a},n_{b}]\\}$ (where ${\sf depth}(w)$ was defined in
Def. 10.4).

$\,\bullet$ On input $w$, the sequence
$\,(W^{(n_{a})},\,\ldots\,,W^{(n_{b})})\,$ can be computed in $\,{\sf
fLog\,unif\,AC}_{2}$

(where the length of the input $w$ is taken to be $\ {\rm
maxlen}(\Gamma_{\\!M})\ |w|_{\Gamma_{\\!M}}$ $+$ ${\rm maxindex}_{\tau}(w)$).

(3) The results of (2) also hold with $M_{2,1}$ replaced by $\,{\cal RM}^{\sf
fin}$, and $\,{\rm plep}M_{2,1}$ replaced by $\,{\sf pfl}{\cal RM}^{\sf fin}$.

Proof. (1) We represent $f\in M_{2,1}$ by a maximally extended right-ideal
morphism in ${\cal RM}^{\sf fin}$, that we also call $f$. Let $m={\rm
maxlen}({\rm domC}(f))$; we assume $m\geq 1$ (otherwise we choose $m=1$). Let
$n_{b}={\rm maxlen}(f(\\{0,1\\}^{m}))$, and let $n_{a}={\rm
minlen}(f(\\{0,1\\}^{m}))$.

For every $i\in[n_{a},n_{b}]$, let $f^{(i)}$ be the restriction of $f$ with
$\,{\rm domC}(f^{(i)})$ $\,=\,$ $\\{0,1\\}^{m}$ $\cap$
$f^{-1}(\\{0,1\\}^{i})$. Then $f^{(i)}\in{\rm plep}M_{2,1}$, and the other
properties in part (1) of the Theorem are easily verified.

Note that some of the functions $f^{(i)}$ could be the empty function
$\theta$.

(2) Let $\,\Gamma_{\\!M}$ and $\Gamma_{\\!M,\,{\sf pfl}}(\subseteq$
$\Gamma_{\sf\\!pfl})$ be as above. For any $w\in(\Gamma_{\\!M}\cup\tau)^{*}$,
there exists $m\geq 1$ such that by Prop. 10.1:

$m\,\leq\,$ ${\rm maxlen}(\Gamma_{\\!M})\cdot|w|_{\Gamma_{\\!M}}$ $\,+\,$
${\rm maxindex}_{\tau}(w)$,

${\rm domC}(E_{w})$ is $\equiv_{\rm fin}$-equivalent to a subset of
$\\{0,1\\}^{m}$, and

$E_{w}(\\{0,1\\}^{m})\subseteq\\{0,1\\}^{\leq n}$ for some $n\geq 1$ with

$n\,\leq\,$ $2\ {\rm maxlen}(\Gamma_{\\!M})\cdot|w|_{\Gamma_{\\!M}}$ $\,+\,$
${\rm maxindex}_{\tau}(w)$.

We represent $E_{w}$ by a right-ideal morphism restricted to
$\,\\{0,1\\}^{\geq m}$, i.e., ${\rm domC}(E_{w})\subseteq\\{0,1\\}^{m}$. In
${\rm Dom}(E_{w})\subseteq\\{0,1\\}^{\geq m}\,$ we have: $\,E_{w}\equiv_{\rm
fin}\,w_{\ell}\circ\,\ldots\,\circ w_{1}(.)$, where
$w=w_{\ell}\,\ldots\,w_{1}$ with $w_{t}\in\Gamma_{\\!M}\cup\tau$ for all
$t\in[1,\ell]$. So, when $w_{\ell}\circ\ldots\circ w_{1}(x)$ is calculated for
$|x|\geq m$, the functions $w_{t}$ are composed and they are defined without
any need of a further restriction of right-ideal morphisms (see also [2, Cor.
3.7], [7, Thm. 4.5], [12, Prop. 6.5], [14, Def. 2.4]).

Among the generators that appear in $\\{w_{\ell},\,\ldots\,,w_{1}\\}$, some
are in ${\rm plep}M_{2,1}$, namely those in $\\{a_{0},$ $a_{3},$ $a_{4},$
$a_{5},$ $a_{6},$ $a_{7}\\}$ $\cup$ $\tau$. For the other generators, namely
those in $\\{a_{1},a_{2},a_{8}\\}$, we use the decompositions into unambiguous
unions with disjoint domains: $\,a_{1}=$
$!$$\cup\\{a_{1,-1},\,a_{1,0},\,a_{1,1}\\}$ $\,(=a_{1}^{!})$, $\,a_{2}=$
$!$$\cup\\{a_{2,-1},\,a_{2,0},\,a_{2,1}\\}$ $\,(=a_{2}^{!})$, and $\,a_{8}=$
$!$$\cup\\{a_{8,0},\,a_{8,1}\\}$ $\,(=a_{8}^{!})$. For
$w_{t}\in\\{a_{1},a_{2},a_{8}\\}$, we denote the relevant decomposition of
$w_{t}$ into an unambiguous union by $w_{t}^{!}$; for $w_{t}\in{\rm
plep}M_{2,1}$ we have $\,w_{t}^{!}=w_{t}$.

Main idea of the proof: In the composition $\,E_{w}=w_{\ell}\circ\ldots\circ
w_{1}(.)\,$ we will replace each $w_{t}$ by $w_{t}^{!}$, for all
$t\in[1,\ell]$. Then, by using distributivity of composition over union in
$\,w_{\ell}^{!}\circ\ldots\circ w_{1}^{!}(.)\,$ (Lemma 10.11) , we obtain an
expression for $E_{w}$ in the form of an unambiguous union of pfl-functions
with disjoint domains. If, moreover, we collect together the terms of equal
$\delta$-value we obtain $\,E_{w}\,=\
!$$\cup(E_{W^{(n_{a})}},\,\ldots\,,E_{W^{(n_{b})}})$, where for every
$i\in[n_{a},n_{b}]$: either $E_{W^{(i)}}=\theta\,$ or
$\delta(E_{W^{(i)}})=i\\!-\\!m$.

The claimed properties of the words $W^{(i)}$ in the Theorem do not depend on
the order in which the distributivity steps are carried out in
$\,w_{\ell}^{!}\circ\ldots\circ w_{1}^{!}(.)$. However, the complexity of the
algorithm for finding the words $W^{(i)}$ depends on this order.

We implement this idea in two algorithms.

In the first algorithm, called the sequential algorithm, the generators and
distributivity are applied from right to left (starting with $w_{1}^{!}$, then
$w_{2}^{!}\,w_{1}^{!}$, then $w_{3}^{!}\,w_{2}^{!}\,w_{1}^{!}$, etc.). At each
step, Theorem 10.9 and Prop. 10.12 are used in order to collect the terms with
the same $\delta$-value. This algorithm runs in polynomial time (but it is not
an NC-algorithm).

In the second algorithm, called the parallel algorithm, a binary tree of
pairwise compositions is used. So we compute the sequence

$\ldots\ ,\ \ \ldots\ ,$ $\ \ (w_{2h}^{!}\circ w_{2h-1}^{!}),\ \ \ldots\ ,\ $
$(w_{4}^{!}\circ w_{3}^{!})$, $(w_{2}^{!}\circ w_{1}^{!})\,$;

then we again compose the results in pairs, and again in pairs, etc. In each
step, distributivity and Prop. 10.12 are applied. There are
$\lceil\log_{2}\ell\rceil$ parallel steps. This can be carried out as a
parallel algorithm, since all the pairs used in the same step can be composed
independently at the same time. We will see that this is an ${\sf
AC}_{2}$-algorithm.

We next describe the two algorithms in detail. In the algorithms, “$:=$”
denotes assignment, “$=$” is equality, and in a loop “for $k\in[a,b]:\ldots$”
the variable $\,k$ ranges over the integers in $[a,b]$ in increasing order.

Sequential algorithm:

/* Input: $w=w_{\ell}\,\ldots\,w_{1}\,$ (with $w_{t}\in$
$\Gamma_{\\!M}\cup\tau$ for $t\in[1,\ell]$);

* Output: $\\{(W^{(i)},\,i\\!-\\!m):i\in[n_{a},\,n_{b}]\\}$ $\,\subseteq\,$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\times{\mathbb{Z}}$, satisfying the conditions of the Theorem. */

$m\,:=\,$ ${\rm maxlen}(\Gamma_{\\!M})\cdot|w|_{\Gamma_{\\!M}\cup\tau}$
$\,+\,$ ${\rm maxindex}_{\tau}(w)\,$; /* will not change */

$n_{b}:=m$; $n_{a}:=m$; $W^{(n_{a})}:=\varepsilon$; /* initialization, will
change */

for $\,t\in[1,\,\ell]:$

/* Loop assertion: At the beginning of the loop (i.e., at value $t\\!-\\!1$),
numbers $n_{b}\geq n_{a}\geq 0$, and words

* $\,W^{(n_{a})},\,\ldots\,,W^{(n_{b})}\in$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\,$ have been found such that for all $i,j\in[n_{a},n_{b}]:$

* $E_{w_{t-1}\,\ldots\,w_{1}}$ $=$ $!$$\bigcup_{r=n_{a}}^{\ n_{b}}E_{W^{(r)}}\,$,

* ${\rm Dom}(E_{W^{(i)}})\,\cap\,{\rm Dom}(E_{W^{(j)}})$ $=$ $\varnothing\,$ if $i\neq j\,$,

* $E_{W^{(i)}}$ is pfl with $\,{\rm domC}(E_{W^{(i)}})\subseteq\\{0,1\\}^{m}$ and $E_{W^{(i)}}(\\{0,1\\}^{m})\subseteq\\{0,1\\}^{i}$. */

/* Case 1: $w_{t}$ is pfl */

if $w_{t}\in$ $\\{a_{0},a_{3},a_{4},a_{5},a_{6},a_{7}\\}\cup\tau\,$ then$:$

for $i\in[n_{a},\,n_{b}]:$ $W^{(i+\delta(w_{t}))}_{{}_{\rm\\!new}}$ $:=$
$\,w_{t}\cdot W^{(i)}\,$;

$n_{b}:=n_{b}+\delta(w_{t})\,$; $n_{a}:=n_{a}+\delta(w_{t})$;

for $j\in[n_{a},\,n_{b}]:$ $W^{(j)}:=W^{(j)}_{{}_{\rm\\!new}}\,$;

/* Case 2: $w_{t}$ is not plep; so, $w_{t}\in\\{a_{1},a_{2},a_{8}\\}$. Note
that $\delta(a_{i,k})=k$ if $\,i\in\\{1,2,8\\}$, $\,k\in\\{-1,0,1\\}$ */

if $w_{t}=a_{1}$ /* Case 2.$a_{1}$: */

then:

for $j\,\in\,[n_{a}\\!-\\!1,\ n_{b}\\!+\\!1]:$

Let $W^{(j)}_{{}_{\rm\\!new}}\in$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\,$
be the word constructed in Theorem 10.9 for

$!$$\bigcup$ $\big{\\{}a_{1,k}\cdot W^{(i)}\ :\ i\in[n_{a},\,n_{b}]\,$ and
$\,k\in\\{-1,0,1\\}\,$ such that $\,i+\delta(a_{1,k})=j\big{\\}}\,$;

$n_{b}:=n_{b}\\!+\\!1$; $n_{a}:=n_{a}\\!-\\!1$;

for $j\in[n_{a},\,n_{b}]:$ $W^{(j)}:=W^{(j)}_{{}_{\rm\\!new}}\,$;

if $w_{t}=a_{2}$ /* Case 2.$a_{2}$: */

then:

for $j\,\in\,[n_{a}\\!-\\!1,\ n_{b}\\!+\\!1]:$

Let $W^{(j)}_{{}_{\rm\\!new}}\in$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\,$
be the word constructed in Theorem 10.9 for

$!$$\bigcup$ $\big{\\{}a_{2,k}\cdot W^{(i)}\ :\ i\in[n_{a},\,n_{b}],$ and
$\,k\in\\{-1,0,1\\}\,$ such that $\,i+\delta(a_{2,k})=j\big{\\}}$;

$n_{b}:=n_{b}\\!+\\!1$; $n_{a}:=n_{a}\\!-\\!1$;

for $j\in[n_{a},\,n_{b}]:$ $W^{(j)}:=W^{(j)}_{{}_{\rm\\!new}}\,$;

if $w_{t}=a_{8}$ /* Case 2.$a_{8}$: */

then:

for $j\,\in\,[n_{a},\ n_{b}\\!+\\!1]:$

Let $W^{(j)}_{{}_{\rm\\!new}}\in$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\,$
be the word constructed in Theorem 10.9 for

$!$$\bigcup$ $\big{\\{}a_{8,k}\cdot W^{(i)}\ :\ i\in[n_{a},\,n_{b}]\,$ and
$\,k\in\\{0,1\\}\,$ such that $\,i+\delta(a_{8,k})=j\big{\\}}\,$;

$n_{b}:=n_{b}\\!+\\!1$; /* $n_{a}$ is not changed */

for $j\in[n_{a},\,n_{b}]:$ $W^{(j)}:=W^{(j)}_{{}_{\rm\\!new}}\,$;

/* End of the “for $t$” loop; all the generators in $w$ have been applied. */

output $\,\\{(W^{(i)},\,i\\!-\\!m)\,:\,i\in[n_{a},n_{b}]\\}$.

[End, Sequential algorithm.]

Correctness of the Sequential Algorithm follows from the following claim.

Claim. If the loop assertion holds at the beginning of an execution of the
for-loop then it holds at the end of the loop for the new $n_{a}$, $n_{b}$,
and $(W^{(n_{a})},\,\ldots\,,W^{(n_{b})})$.

Proof of Claim. In case 1, $W^{(i)}$ and $w_{t}$ are pfl; moreover, ${\rm
domC}(E_{W^{(i)}})$ $\subseteq$ $\\{0,1\\}^{m}$ and $\
E_{W^{(i)}}(\\{0,1\\}^{m})$ $\subseteq$ $\\{0,1\\}^{i}$. Therefore the new
$W^{(i+\delta(w_{t}))}$ is also pfl, and $\,E_{W^{(i)}}(\\{0,1\\}^{m})$
$\subseteq$ $\\{0,1\\}^{i+\delta(w_{t})}$.

In case 2, $\,W^{(i)}$ and each fragment $w_{t,k}$ are pfl, and $W^{(i)}$
satisfies $\,{\rm domC}(E_{W^{(i)}})\subseteq\\{0,1\\}^{m}\,$ and
$E_{W^{(i)}}(\\{0,1\\}^{m})\subseteq\\{0,1\\}^{i}$. Therefore, $W^{(i)}\cdot
w_{t,k}\,$ is pfl; and the construction of $W^{(j)}_{{}_{\rm\\!new}}$ makes it
pfl (with input-length $m$ and output-length $j$).

In both cases 1 and 2, at the end of the loop we have $\,{\rm
Dom}(E_{W^{(i_{1})}})\cap{\rm Dom}(E_{W^{(i_{2})}})$ $=$ $\varnothing\,$ (if
$i_{1}\neq i_{2}$); this follows from Lemma 10.11.

At the end of the loop with value $t$, $\ E_{w_{t}w_{t-1}\,\ldots\,w_{1}}$
$\,=\,$ $!$$\bigcup_{s=n_{a}}^{\ n_{b}}E_{W^{(s)}}$. This holds because the
relation is true at the beginning of the loop (for $w_{t-1}\,\ldots\,w_{1}$).
Moreover, in case 1, $w_{t}$ is applied in the next loop, so the relation then
holds for $\,w_{t}w_{t-1}\,\ldots\,w_{1}$. In case 2, the fragments of
$w_{t}^{!}$ are applied (and the disjoint union of the fragments is equal to
$w_{t}$); the operation “$W^{(j)}_{\rm\\!new}:=\ldots$” permutes the functions
and sorts them according to output-length, but this does not change the
disjoint union (which is commutative). [This proves the Claim.]

For the length we have $\,|W^{(i)}|\leq$ ${\rm
maxlen}(\Gamma_{\\!M})\,|w|_{\Gamma_{\\!M}}$ $+$ ${\rm maxindex}_{\tau}(w)$,
since in every execution of the loop, $|W^{(i)}|$ grows by at most by length
$c\,$ ($\,=\,$ ${\rm maxlen}(\Gamma_{\\!M})$), or increases to some length
$\,\leq{\rm maxindex}_{\tau}(w)$.

The computation of final expressions $(W^{(n_{a})},\,\ldots\,,W^{(n_{b})})$
for $w$ takes polynomial time. Indeed, the loop is iterated $\,\leq\ell\,$
($=|w|_{\Gamma_{\\!M}\cup\tau}$) times. Moreover, each execution of the body
of the loop takes polynomial time: For case 1, it is straightforward that the
execution takes linear time. In case 2, the set

$W^{(j)}_{{}_{\rm new}}$ $\,=\,$ $\\{a_{r,k}\cdot W^{(i)}\ :$ $\
i\in[n_{a},\,n_{b}],\ k\in\\{-1,0,1\\}\,$ (or $\in\\{0,1\\}$), such that
$j=i+\delta(a_{r,k})\\}\,$

has 3 elements (if $a_{r}=a_{1}$ or $a_{r}=a_{2}$), or 2 elements (if
$a_{r}=a_{8}$); e.g. for $a_{1}$, $\,\delta(a_{1,k})$ ranges over
$\\{-1,0,1\\}$, and $i$ is determined by $\delta(a_{1,k})\,$ (since
$i=j-\delta(a_{1,k})$); so

$W^{(j)}_{{}_{\rm new}}$ $\,=\,$ $\\{a_{1,-1}\cdot W^{(j+1)},$ $a_{1,0}\cdot
W^{(j)},$ $a_{1,1}\cdot W^{(j-1)}\\}$.

In the formation of the set $W^{(j)}_{{}_{\rm new}}$, no new copy of any
existing $W^{(i)}$ is made; the exiting $W^{(i)}s$ are simply either left
unchanged, or rearranged and concatenated with one letter $a_{r,k}$. Thus,
$W^{(j)}_{{}_{\rm new}}$ is constructed in linear time.

The next algorithm is an ${\sf AC}_{2}$ algorithm, with parallel for-loops. In
“parallelfor $i\in[a,b]$ … ”, the $\,b\\!-\\!a\\!+\\!1\,$ iterations of the
body of the loop are independent and are executed simultaneously. See again
the earlier descriptions of the sequential algorithm and the parallel
algorithm.

Parallel algorithm

/* Input: $w=w_{\ell}\,\ldots\,w_{1}\,$ (with $w_{t}\in$
$\Gamma_{\\!M}\cup\tau$ for $t\in[1,\ell]$);

* Output: $\\{(W^{(j)},\,j\\!-\\!m):j\in[n_{a},\,n_{b}]\\}$ $\ \subseteq\ $ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\times{\mathbb{Z}}$, satisfying the conditions of the Theorem. */

parallelfor $t\in[1,\ell]:$ $x_{t}:=w_{t}^{!}\,$;

$D=\lceil\log_{2}\ell\rceil\,$;

if $\ell$ is not a power of 2 then:

parallelfor $t\in[\ell\\!+\\!1,\,2^{D}]:$ $x_{t}:={\mathbb{1}}\,$;

/* attach a prefix of $\,2^{D}\\!-\\!\ell\,$ copies of ${\mathbb{1}}$ to $x$,
acting as the identity function in compositions */

$\ell:=2^{D}\,;$ /* Now, $\,\ell=|x|=2^{D}$ */

parallelfor $t\in[1,\ell]:$

$n_{a,t}:=m+\min(\delta_{M}(x_{t}))\,$;

$n_{b,t}:=m+\max(\delta_{M}(x_{t}))\,$;

for $d\in[0,D\\!-\\!1]:$

/* Loop assertion:

* For all $i\in[1,\,2^{D-d}]:$ Assume that $x_{i}$ has been decomposed into an unambiguous union

* $\,x_{i}=$ $!$$\bigcup$ $\big{(}x_{i}^{(j)}:j\in[n_{a,i},n_{b,i}]\big{)}$, with $x_{i}^{(j)}$ $\in$ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\,$, and $\,{\rm imC}(E_{x_{i}^{(j)}})\subseteq\\{0,1\\}^{j}$.

* Assume that $x_{i}$ is represented by a set $\\{(x_{i}^{(j)},\ d_{i}^{(j)}):j\in[n_{a,i},n_{b,i}]\\}$ $\ \subseteq\ $ $(\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\times{\mathbb{Z}}$,

* with $d_{i}^{(j)}=j\\!-\\!m$; and $d_{i}^{(j)}=\delta(E_{x_{i}^{(j)}})\,$ if $\,E_{x_{i}^{(j)}}\neq\theta$. */

parallelfor $h\in[1,\,2^{D-d-1}]:$

$N_{a,h}:=m+\min\\{d_{2h}^{(j)}+d_{2h-1}^{(j^{\prime})}:$
$j\in[n_{a,2h},\,n_{b,2h}]$, $j^{\prime}\in[n_{a,2h-1},\,n_{b,2h-1}]\\}\,$;

$N_{b,h}:=m+\max\\{d_{2h}^{(j)}+d_{2h-1}^{(j^{\prime})}:$
$j\in[n_{a,2h},\,n_{b,2h}]$, $j^{\prime}\in[n_{a,2h-1},\,n_{b,2h-1}]\\}\,$;

Let $\,X_{h}=$ $\\{(X_{h}^{(j)},\,D_{h}^{(j)}):j\in[N_{a,h},\,N_{b,h}]\\}$ $\
\subseteq\ (\Gamma_{\\!M,\,{\sf pfl}}\cup\tau)^{*}\times{\mathbb{Z}}\,$

be the set constructed in Prop. 10.12 for

$x_{2h}\circ x_{2h-1}$ $\,=\,$
$\\{(x_{2h}^{(j)},\,d_{2h}^{(j)}):j\in[n_{a,2h},\,n_{b,2h}]\\}$ $\circ$
$\\{(x_{2h-1}^{(j)},\,d_{2h-1}^{(j)}):j\in[n_{a,2h-1},\,n_{b,2h-1}]\\}\,$;

parallelfor $h\in[1,\,2^{D-d-1}]:$

$n_{a,h}:=N_{a,h}\,$; $n_{b,h}:=N_{b,h}\,$;

parallelfor $j\in[n_{a,h},n_{b,h}]:$

$(x_{h}^{(j)},\,d_{h}^{(j)}):=(X_{h}^{(j)},\,D_{h}^{(j)})\,$; /* i.e.,
$x_{h}:=X_{h}$ */

output $x_{1}$ /* $\,=\,$
$\\{(x_{1}^{(j)},\,d_{1}^{(j)}):j\in[n_{a,1},n_{b,1}]\\}$ */ .

[End, Parallel algorithm.]

The parallel algorithm and the sequential algorithm produce the same output.
Indeed, the two algorithms differ only by the grouping of subexpressions, and
composition is associative and distributes over union.

The parallel algorithm uses $D=\lceil\log_{2}\ell\rceil$ sequential steps,
where $\ell=|w|_{\Gamma_{\\!M}\cup\tau}$. In step $\,d\in[0,D\\!-\\!1]\,$
there are $2^{D-d-1}$ simultaneous compositions of the form $\,x_{2h}\circ
x_{2h-1}\,$ (in “parallelfor $h\in[1,2^{D-d-1}]$”); each such composition is
computed in log-space (by Prop. 10.12). Since log-space is contained in ${\sf
AC}_{1}$, each parallel step $d$ is in ${\sf AC}_{1}$. Thus the parallel
algorithm is in ${\sf AC}_{2}$.

(3) The proof for ${\cal RM}^{\sf fin}$ is similar to the proof for $M_{2,1}$,
using a generating set of the form $\Gamma\cup\tau$, where $\Gamma$ is finite.
Just as in the proof of (2), each generator $\gamma\in$ $\Gamma$
$\smallsetminus$ ${\sf pfl}{\cal RM}^{\sf fin}$ can be decomposed as into an
unambiguous union of elements of ${\sf pfl}{\cal RM}^{\sf fin}$ with disjoint
domains. From there on the reasoning is the same as in (2). $\Box$

Comments on Theorem 10.13

1\. Theorem 10.13(2) and the function-emptiness problem:

A subtle aspect of Theorem 10.13(2)(3) is that it produces a correct output in
polynomial time (in fact in complexity ${\sf AC}_{2}$) regardless of whether
$E_{w}=\theta$, which is coNP-complete Prop. 11.1(1).

2\. Equivalent forms of the input-length, and of the depth of a word in ${\cal
RM}^{\sf fin}$

Based on the unambiguous union decomposition of the elements of ${\cal
RM}^{\sf fin}$ we obtain the following characterization of input-length and
depth.

###### Proposition 10.14

(input-length and depth for ${\cal RM}^{\sf fin}$ and union of partial
circuits).

Let $\ell_{\rm in}(.)$ be the input-length function (Def. 3.3 and Lemma 3.4),
and let $\,{\sf depth}(.)$ be the depth function (Def. 10.4). Then for any
$w\in$ $(\Gamma\cup\tau)^{*}$ and its decomposition $\,!$$\bigcup_{i=n_{a}}^{\
\ n_{b}}W^{(i)}\,$, given in Theorem 10.13(2), we have:

$\ell_{\rm in}(w)\ =\ \ell_{\rm in}(W^{(i)})$, for every
$\,i\in[n_{a},n_{b}]$;

${\sf depth}(w)\ =\ $ $\max\\{\,{\sf
depth}(W^{(i)})\,:\,i\in\delta_{M}(w)\\}$.

For an element $w\in(\Gamma\cup\tau)^{*}$ with $\,E_{w}\in$ ${\cal RM}^{\sf
fin}\smallsetminus{\sf pfl}{\cal RM}^{\sf fin}$, there is more than one
output-length; the output-lengths for the set $\,\\{\ell_{\rm in}(w)+d\,:\,$
$d\in\delta_{M}(w)\\}$.

Proof. The property of $\ell_{\rm in}(w)$ is given in the first item of
Theorem 10.13(2.2). The depth property is proved in the third item of Theorem
10.13(2.2). $\Box$

##  11 Appendix: The function emptiness problem, and computing $\delta(.)$ in
${\sf pfl}{\cal RM}^{\sf fin}$

We consider the following three problems about ${\sf pfl}{\cal RM}^{\sf fin}$
with generating set $\Gamma_{\sf\\!pfl}$ $\cup$ $\tau$, with
$\Gamma_{\sf\\!pfl}$ finite. The function emptiness problem also applies to
${\cal RM}^{\sf fin}$ with generating set $\Gamma_{\sf\\!fin}\cup\tau$, with
$\Gamma_{\sf\\!fin}$ finite.

(1) The function emptiness problem is the following decision problem.

Input: $w\in(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$, or
$\,w\in(\Gamma_{\sf\\!fin}\cup\tau)^{*}$.

Question: Is $\,E_{w}=\theta$ (the empty function, as an element of ${\rm
pfl}{\cal RM}^{\sf fin}$, respectively of ${\cal RM}^{\sf fin}$)?

In ${\sf pfl}{\cal RM}^{\sf fin}$, this is equivalent to the question: Is
$\,\delta(w)\,$ defined?

In ${\cal RM}^{\sf fin}$ it is equivalent to the question: Is
$\,\delta_{\\!M}(w)=\varnothing\,$?

(2) The computation problem for $\delta$ in the non-empty case is the
following premiss problem.

Input: $w\in(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$.

Premiss: $E_{w}\neq\theta$.

Output: $\delta(E_{w})\ $ (a number in ${\mathbb{Z}}$, written in sign-
magnitude binary notation).

(3) The computation problem for $\delta$ is the following input-output
problem.

Input: $w\in(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$.

Output: $\delta(E_{w})\ $ (a number in ${\mathbb{Z}}$, written in sign-
magnitude binary notation).

The coNP-completeness of function emptiness problem for $M_{2,1}$ over
$\Gamma\cup\tau$ was already proved in [8, Prop. 6.2]. In Prop. 11.1(1) this
is now proved for ${\cal RM}^{\sf fin}$ and ${\sf pfl}{\cal RM}^{\sf fin}$.

###### Proposition 11.1

(complexity of $\delta(.))$.

(1) The function emptiness problem for ${\sf pfl}{\cal RM}^{\sf fin}$, or for
${\cal RM}^{\sf fin}$, is coNP-complete (with respect to log-space many-one
reduction).

(2) The premiss problem for computing $\delta(.)$ in ${\sf pfl}{\cal RM}^{\sf
fin}$ belongs deterministic log-space. (However, checking the premiss is the
negation of the function emptiness problem, hence it is NP-complete.)

(3) The computation problem for $\delta(.)$ in ${\sf pfl}{\cal RM}^{\sf fin}$
is coNP-hard.

Proof. (1) The function emptiness problem is in coNP. Indeed for any $w$ in
$(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ or $(\Gamma_{\sf\\!fin}\cup\tau)^{*}$ we
have: $E_{w}=\theta$ iff $(\forall x\in\\{0,1\\}^{m})[E_{w}(x)$ is undefined].
Here we can choose $m$ to be $\,m=$ ${\rm
maxlen}(\Gamma_{\sf\\!pfl})\,|w|_{\Gamma_{\sf\\!pfl}\cup\tau}$ $+$ ${\rm
maxindex}_{\tau}(w)\,$; hence $m$ is easily computed. And for a given $w$ and
$x$, it can be checked in polynomial time (in terms of $|w|+|x|$) whether
$E_{w}(x)$ is undefined.

To show coNP-hardness we first consider the following problem: The input is an
acyclic circuit $C$ with a single output wire and $m$ input wires, for any
$m\in{\mathbb{N}}$; and the question is whether for all inputs in
$\\{0,1\\}^{m}$ the output of $C$ is 0. Let us call this problem NonSat; it is
the negation of the satisfiabilty problem for acyclic circuits, and it is
well-known to be coNP-complete (see e.g. [24, 25]).

Next, NonSat is reduced to the function emptiness problem. Given a circuit
$C$, we find ${\sf W}(C)\in$ $(\Gamma_{\sf\\!tfl}\cup\tau)^{*}$ such that
$E_{{\sf W}(C)}$ is the input-output function of $C$; by Theorem 3.8, ${\sf
W}(C)$ can be computed in log-space. Thus $C$ has output 0 on all inputs in
$\\{0,1\\}^{m}\,$ iff $\,[{\sf W}(C)](x)=0\,$ for all $x\in\\{0,1\\}^{m}$.
Next, we define $\zeta\in$ ${\rm pfl}{\cal RM}^{\sf fin}$ as follows: $\
\zeta(1z)=1z$, and $\,\zeta(0z)\,$ is undefined (for all $z\in\\{0,1\\}^{*}$).
Let $w_{0}\in$ $(\Gamma_{\sf\\!pfl}\cup\tau)^{*}$ be such that
$\,E_{w_{0}}=\zeta$. Then $C$ is a yes-case of NonSat iff $\,E_{w_{0}\,{\sf
W}(C)}=\theta$.

(2) Let $\,w=w_{k}\,\ldots\,w_{1}$ with $w_{t}\in\Gamma_{\sf\\!pfl}\cup\tau$
for $t\in[1,k]$. By Prop. 7.8(3), $\delta(w)=$ $\sum_{t=1}^{k}\delta(w_{t})\,$
if $E_{w}\neq\theta$. And for $\gamma\in$ $\Gamma_{\sf\\!pfl}\cup\tau$,
$\,\delta(\gamma)$ is bounded by constants from above and from below, since
$\Gamma_{\sf\\!pfl}$ is finite, and $\delta(\tau_{i,j})=0$ for all
$\tau_{i,j}\in\tau$. We now use the well-known and easy fact that the sum of
$k$ bounded integers can be computed in space $O(\log k)$.

(3) This follows immediately from (1) and (2). $\Box$

Remark: We have for all $w\in$ $(\Gamma_{\sf\\!fin}\cup\tau)^{*}$:
$\,E_{w}=\theta\,$ in ${\cal RM}^{\sf fin}$ iff $E_{w}=\theta\,$ in $M_{2,1}$.
Indeed, $E_{w}=\theta$ iff ${\rm domC}(E_{w})=\varnothing$, and this holds
whether $E_{w}$ is taken in ${\cal RM}^{\sf fin}$ or in $M_{2,1}$. Hence the
above Proposition also applies to $M_{2,1}$ and ${\sf plep}M_{2,1}$.

## References

  * [1] J. Berstel, D. Perrin, Theory of Codes, Academic Press (1985).
  * [2] J.C. Birget, “The groups of Richard Thompson and complexity”, International J. of Algebra and Computation 14 (Nos. 5 & 6) (Dec. 2004) 569-626. http://arXiv.org/abs/math.GR/0204292 (Apr. 2002)
  * [3] J.C. Birget, “Circuits, coNP-completeness, and the groups of Richard Thompson”, International J. of Algebra and Computation 16(1) (Feb. 2006) 35-90.
  * [4] J.C. Birget, “Factorizations of the Thompson-Higman groups, and circuit complexity”, International J. of Algebra and Computation 18.2 (March 2008) 285-320.
  * [5] J.C. Birget, “One-way permutations, computational asymmetry and distortion”, J. of Algebra 320(11) (Dec. 2008) 4030-4062. https://arXiv.org/pdf/0704.1569.pdf
  * [6] J.C. Birget, “Monoid generalizations of the Richard Thompson groups”, J. of Pure and Applied Algebra 213(2) (Feb. 2009) 264-278.
  * [7] J.C. Birget, “Monoid generalizations of the Richard Thompson groups”, http://arXiv.org/abs/0704.0189 Version 3 (corrected version of [6]).
  * [8] J.C. Birget, “The $\cal R$\- and $\cal L$-orders of the Thompson-Higman monoid $M_{k,1}$ and their complexity”, International J. of Algebra and Computation 20.4 (June 2010) 489-524.
http://arXiv.org/abs/0812.4434 (Dec 2008).

  * [9] J.C. Birget, “Monoids that map onto the Thompson-Higman groups”, Semigroup Forum 83.1 (Aug. 2011) 33-51. http://arXiv.org/abs/1009.0502
  * [10] J.C. Birget, “Polynomial-time right-ideal morphisms and congruences”, International J. of Algebra and Computation 28.05 (Aug. 2018) 791-835. (doi.org/10.1142/S0218196718500364)
http://arXiv.org/abs/1511.02056

  * [11] J.C. Birget, “The word problem of the Brin-Thompson groups is coNP-complete”, J. Algebra 553 (1 July 2020) 268-318. (doi.org/10.1016/j.jalgebra.2020.02.013)
  * [12] J.C. Birget, “A monoid version of the Brin-Higman-Thompson groups”, arXiv.org (27 June 2020).
  * [13] J.C. Birget, “New embeddings between the Higman-Thompson groups”, Communications in Algebra 48(8) (2020) 3429-3438. (doi.org/10.1080/00927872.2020.1739290)
  * [14] J.C. Birget, “Evaluation problems for the Thompson group and the Brin-Thompson group, and their relation to the word problem”, arXiv:2111.08646 (Nov 2021)
  * [15] Matthew G. Brin, Personal communication on monoid generalizations of the Thompson group $V$ (Jan.-Mar. 2021).
  * [16] Matthew G. Brin, Lecture at the Logic Seminar, Mathematics Department, Cornell University (Fall 2021).
  * [17] Matt Brin’s answer to “Who was Richard Thompson?” (10 July 2022)
https://hsm.stackexchange.com/questions/14594/who-was-richard-thompson

  * [18] J. W. Cannon, W. J. Floyd, W. R. Parry, “Introductory notes on Richard Thompson’s groups”,
L’Enseignement Mathématique 42 (1996) 215-256.

  * [19] P. Clote, E. Kranakis, Boolean functions and computation models, Springer (2002).
  * [20] Bill de Witt, Luke Elliott, “Finite presentability of Brin-Higman-Thompson monoids via free Jónsson-Tarski algebras”, https://arXiv.org/abs/2303.16044
  * [21] G. Higman, “Finitely presented infinite simple groups”, Notes on Pure Mathematics 8, The Australian National University, Canberra (1974).
  * [22] J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley (1979).
  * [23] H.J. Hoover, M.M. Klawe, N.J. Pippenger, “Bounding fan-out in logical networks”, J. of the ACM 31(1) (1984) 13-18.
  * [24] Ch. Papadimitriou, Computational Complexity, Addison-Wesley (1994).
  * [25] J.E. Savage, Models of computation, Addison-Wesley (1998).
  * [26] Richard J. Thompson, Manuscript (mid 1960s).
  * [27] R. McKenzie, R. J. Thompson, “An elementary construction of unsolvable word problems in group theory”, in Word Problems, (W. W. Boone, F. B. Cannonito, R. C. Lyndon, editors), North-Holland (1973) pp. 457-478.
  * [28] Richard J. Thompson, Lecture, Palo Alto, 10 Jan. 2004 (notes by M. Brin).
  * [29] Richard J. Thompson, Lecture, Luminy, 2 June 2008 (notes by M. Brin).
  * [30] I. Wegener, The complexity of boolean functions, Teubner and Wiley (1987).

<EMAIL_ADDRESS>