missing  11institutetext: Université Paris Cité, CNRS, IRIF, F-75013, Paris,
France22institutetext: Direction générale de l’armement - Ingénierie des
projets, Paris, France 22email<EMAIL_ADDRESS>
# Pebble minimization: the last theorems

Gaëtan Douéneau-Tabot 1122

###### Abstract

Pebble transducers are nested two-way transducers which can drop marks (named
“pebbles”) on their input word. Such machines can compute functions whose
output size is polynomial in the size of their input. They can be seen as
simple recursive programs whose recursion height is bounded. A natural problem
is, given a pebble transducer, to compute an equivalent pebble transducer with
minimal recursion height. This problem is open since the introduction of the
model.

In this paper, we study two restrictions of pebble transducers, that cannot
see the marks (“blind pebble transducers” introduced by Nguyên et al.), or
that can only see the last mark dropped (“last pebble transducers” introduced
by Engelfriet et al.). For both models, we provide an effective algorithm for
minimizing the recursion height. The key property used in both cases is that a
function whose output size is linear (resp. quadratic, cubic, etc.) can always
be computed by a machine whose recursion height is $1$ (resp. $2$, $3$, etc.).
We finally show that this key property fails as soon as we consider machines
that can see more than one mark.

###### Keywords:

Pebble transducers Polyregular functions Blind pebble transducers Last pebble
transducers Factorization forests.

##  1 Introduction

Transducers are finite-state machines obtained by adding outputs to finite
automata. They are very useful in a lot of areas like coding, computer
arithmetic, language processing or program analysis, and more generally in
data stream processing. In this paper, we consider deterministic transducers
which compute functions from finite words to finite words. In particular, a
deterministic two-way transducer is a two-way automaton with outputs. This
model describes the class of regular functions, which is often considered as
one of the functional counterparts of regular languages. It has been
intensively studied for its properties such as closure under composition [5],
equivalence with logical transductions [12] or regular expressions [7],
decidable equivalence problem [14], etc.

####  1.0.1 Pebble transducers and polyregular functions.

Two-way transducers can only describe functions whose output size is at most
linear in the input size. A possible solution to overcome this limitation is
to consider nested two-way transducers. In particular, the model of $k$-pebble
transducer has been studied for a long time [13]. For $k=1$, a $1$-pebble
transducer is just a two-way transducer. For $k\geqslant 2$, a $k$-pebble
transducer is a two-way transducer that, when on any position $i$ of its input
word, can call a $(k{-}1)$-pebble transducer. The latter takes as input the
original input where position $i$ is marked by a “pebble”. The main two-way
transducer then outputs the concatenation of all the outputs produced along
its calls. The intuitive behavior of a $3$-pebble transducer is depicted in
fig. 1. It can be seen as recursive program whose recursion stack has height
$3$. The class of functions computed by pebble transducers is known as
polyregular functions. It has been intensively studied due to its properties
such as closure under composition [11], equivalence with logical
interpretations [4], etc.

Input word${\vdash}$${\dashv}$ Main machineInput
word${\vdash}$${\dashv}$Submachine called in
${\color[rgb]{0.70703125,0.55859375,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.70703125,0.55859375,0.6796875}\bullet}$$\begin{subarray}{c}\text{pebble}\end{subarray}$Input
word${\vdash}$${\dashv}$ Submachine called in
${\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\bullet}$
$\begin{subarray}{c}\text{pebble}\end{subarray}$$\begin{subarray}{c}\text{pebble}\end{subarray}$

Figure 1:  Behavior of a $3$-pebble transducer.

####  1.0.2 Optimization of pebble transducers.

Given a $k$-pebble transducer computing a function $f$, a very natural problem
is to compute the least possible $1\leqslant\ell\leqslant k$ such that $f$ can
be computed by an $\ell$-pebble transducer. Furthermore, we can be interested
in effectively building an $\ell$-pebble transducer for $f$. Both questions
are open, but they are meaningful in practice. Indeed, they ask whether we can
optimize the recursion height (i.e. the running time) of a program.

It is easy to observe that if $f$ is computed by a $k$-pebble transducer, then
$|f(u)|=\mathcal{O}(|u|^{k})$. It was first conjectured in the literature that
the minimal recursion height $\ell$ of $f$ (i.e. the least possible $\ell$
such that $f$ can be computed by an $\ell$-pebble transducer) was exactly the
least possible $\ell$ such that $|f(u)|=\mathcal{O}(|u|^{\ell})$. However,
Bojańczyk recently disproved this statement in [3, Theorem 6.3]: the function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{inner-
squaring}}}}{}{}:u_{1}\\#\cdots\\#u_{n}\mapsto(u_{1}\\#)^{n}\cdots(u_{n}\\#)^{n}$
can be computed by a $3$-pebble transducer and is such that
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{inner-
squaring}}}{}{}(u)|=\mathcal{O}(|u|^{2})$, but it cannot be computed by a
$2$-pebble transducer. Therefore, computing the minimal recursion height of
$f$ is believed to be hard, since this value not only depends on the output
size of $f$, but also on the word combinatorics of this output.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

####  1.0.3 Optimization of blind pebble transducers.

A subclass of pebble transducers, named blind pebble transducers, was recently
introduced in [16]. A blind $k$-pebble transducer is somehow a $k$-pebble
transducer, with the difference that the positions are no longer marked when
making recursive calls. The behavior of a blind $3$-pebble transducer is
depicted in fig. 2. The class of functions computed by blind pebble
transducers is strictly included in polyregular functions [10, 16]. The main
result of [16] shows that for blind pebble transducers, the minimal recursion
height for computing a function only depends on the growth of its output. More
precisely, if $f$ is computed by a blind $k$-pebble transducer, then the least
possible $1\leqslant\ell\leqslant k$ such that $f$ can be computed by an blind
$\ell$-pebble transducer is the least possible $\ell$ such that
$|f(u)|=\mathcal{O}(|u|^{\ell})$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Input word${\vdash}$${\dashv}$ Main machineInput
word${\vdash}$${\dashv}$Submachine called in
${\color[rgb]{0.70703125,0.55859375,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.70703125,0.55859375,0.6796875}\bullet}$Input
word${\vdash}$${\dashv}$ Submachine called in
${\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\bullet}$

Figure 2:  Behavior of a blind $3$-pebble transducer.

####  1.0.4 Contributions.

In this paper, we first give a new proof of the connection between minimal
recursion height and growth of the output for blind pebble transducers.
Furthermore, our proof provides an algorithm that, given a function computed
by a blind $k$-pebble transducer, builds a blind $\ell$-pebble transducer
which computes it, for the least possible $1\leqslant\ell\leqslant k$. This
effective result is not claimed in [16], and our proof techniques
significantly differ from theirs. Indeed, we make a heavy use of factorization
forests, which have already been used as a powerful tool in the study of
pebble transducers [2, 8, 10].

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Secondly, the main contribution of this paper is to show that the (effective)
connection between minimal recursion height and growth of the output also
holds for the class of last pebble transducers (introduced in [13]).
Intuitively, a last $k$-pebble transducer is a $k$-pebble transducer where a
called submachine can only see the position of its call, but not the full
stack of the former positions. The behavior of a last $3$-pebble transducer is
depicted in fig. 3. Observe that a blind $k$-pebble transducer is a restricted
version of a last $k$-pebble transducer. Formally, we show that if $f$ is
computed by a last $k$-pebble transducer, then the least possible $\ell$ such
that $f$ can be computed by a last $\ell$-pebble transducer is the least
possible $\ell$ such that $|f(u)|=\mathcal{O}(|u|^{\ell})$. Furthermore, our
proof gives an algorithm that effectively builds a last $\ell$-pebble
transducer computing $f$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Input word${\vdash}$${\dashv}$ Main machineInput
word${\vdash}$${\dashv}$Submachine called in
${\color[rgb]{0.70703125,0.55859375,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.70703125,0.55859375,0.6796875}\bullet}$$\begin{subarray}{c}\text{pebble}\end{subarray}$Input
word${\vdash}$${\dashv}$ Submachine called in
${\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\bullet}$
$\begin{subarray}{c}\text{pebble}\end{subarray}$

Figure 3:  Behavior of a last $3$-pebble transducer.

As a third theorem, we show that our result for last pebble transducers is
tight, in the sense that the connection between minimal recursion height and
growth of the output does not hold for more powerful models. More precisely,
we define the model of last-last $k$-pebble transducers, which extends last
$k$-pebble transducers by allowing them to see the two last positions of the
calls (and not only the last one). We show that for all $k\geqslant 1$, there
exists a function $f$ such that $|f(u)|=\mathcal{O}(|u|^{2})$ and that is
computed by a last-last $(2k{+}1)$-pebble transducer, but cannot be computed
by a last-last $2k$-pebble transducer. In this setting, minimizing the
recursion height seems to be out of reach.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

####  1.0.5 Outline.

We introduce two-way transducers in section 2. In section 3 we describe blind
pebble transducers and last pebble transducers. We also state our main results
that connect the minimal recursion height of a function to the growth of its
output. Their proof goes over sections 4, 5 and 6. In section 7, we finally
show that these results cannot be extended to two visible marks.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

##  2 Preliminaries on two-way transducers

Capital letters $A,B$ denote alphabets, i.e. a finite sets of letters. The
empty word is denoted by $\varepsilon$. If $u\in A^{*}$, let
$|u|\in\mathbb{N}$ be its length, and for $1\leqslant i\leqslant|u|$ let
$u[i]$ be its $i$-th letter. If $i\leqslant j$, we let $u[i{:}j]$ be
$u[i]u[i{+}1]\cdots u[j]$ (empty if $j<i$). If $a\in A$, let $|u|_{a}$ be the
number of letters $a$ occurring in $u$. We assume that the reader is familiar
with the basics of automata theory, in particular two-way automata and monoid
morphisms. The type of total (resp. partial, i.e. possibly undefined on some
inputs) functions is denoted $S\rightarrow T$ (resp. $S\rightharpoonup T$).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The machines described in this paper are always deterministic.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Definition 1

A two-way transducer $\mathscr{T}=(A,B,Q,q_{0},F,\delta,\lambda)$ consists of:

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

  * •

an input alphabet $A$ and an output alphabet $B$;

  * •

a finite set of states $Q$ with $q_{0}\in Q$ initial and $F\subseteq Q$ final;

  * •

a transition function
$\delta:Q\times(A\uplus\\{{{\vdash}},{{\dashv}}\\})\rightharpoonup
Q\times\\{\triangleleft,\triangleright\\}$;

  * •

an output function
$\lambda:Q\times(A\uplus\\{{{\vdash}},{{\dashv}}\\})\rightharpoonup B^{*}$
with same domain as $\delta$.

The semantics of a two-way transducer $\mathscr{T}$ is defined as follows.
When given as input a word $u\in A^{*}$, $\mathscr{T}$ disposes of a read-only
input tape containing ${{\vdash}}u{{\dashv}}$. The marks ${{\vdash}}$ and
${{\dashv}}$ are used to detect the borders of the tape, by convention we
denote them by positions $0$ and $|u|{+}1$ of $u$. Formally, a configuration
over ${{\vdash}}u{{\dashv}}$ is a tuple $(q,i)$ where $q\in Q$ is the current
state and $0\leqslant i\leqslant|u|{+}1$ is the position of the reading head.
The transition relation
$\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}$ is defined as
follows. Given a configuration $(q,i)$, let
$(q^{\prime},\star):=\delta(q,u[i])$. Then
$(q,i)\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q^{\prime},i^{\prime})$
whenever either $\star=\triangleleft$ and $i^{\prime}=i{-}1$ (move left), or
$\star=\triangleright$ and $i^{\prime}=i{+}1$ (move right), with $0\leqslant
i^{\prime}\leqslant|u|{+}1$. A run is a sequence of configurations
$(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{n},i_{n})$.
Accepting runs are those that begin in $(q_{0},0)$ and end in a configuration
of the form $(q,|u|{+}1)$ with $q\in F$ (and never visit such a configuration
before).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The partial function $f:A^{*}\rightharpoonup B^{*}$ computed by the two-way
transducer $\mathscr{T}$ is defined as follows: for $u\in A^{*}$, if there
exists an accepting run on ${{\vdash}}u{{\dashv}}$, then it is unique, and
$f(u)$ is defined as
$\lambda(q_{1},({\vdash}u{\dashv})[i_{1}])\cdots\lambda(q_{n},({\vdash}u{\dashv})[i_{n}])\in
B^{*}$. The class of functions computed by two-way transducers is called
regular functions.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Example 1

Let $\widetilde{u}$ be the mirror image of $u\in A^{*}$. Let $\\#\not\in A$ be
a fresh symbol. The function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{map-
reverse}}}}{}{}:u_{1}\\#\cdots\\#u_{n}\mapsto\widetilde{u_{1}}\\#\cdots\\#\widetilde{u_{n}}$
can be computed by a two-way transducer, that reads each factor $u_{j}$ from
right to left.

It is well-known that the domain of a regular function is always a regular
language (see e.g. [17]). From now on, we assume without losing generalities
that our two-way transducers only compute total functions (in other words,
they have exactly one accepting run on each ${\vdash}u{\dashv}$). Furthermore,
we assume that $\lambda(q,{\vdash})=\lambda(q,{\dashv})=\varepsilon$ for all
$q\in Q$ (we only lose generalities for the image of $\varepsilon$).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

In the rest of this section, $\mathscr{T}$ denotes a two-way transducer with
input alphabet $A$, output alphabet $B$ and output function $\lambda$. Now, we
define the crossing sequence in a position $1\leqslant i\leqslant|u|$ of input
${\vdash}u{\dashv}$. Intuitively, it regroups the states of the accepting run
which are visited in this position.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Definition 2

Let $u\in A^{*}$ and $1\leqslant i\leqslant|u|$ . Let
$(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{n},i_{n})$ be
the accepting run of $\mathscr{T}$ on ${\vdash}u{\dashv}$. The crossing
sequence of $\mathscr{T}$ in $i$, denoted
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{\textsf{{cross}}}}}}_{\mathscr{T}}^{u}{}{}(i)$,
is defined as the sequence $(q_{j})_{1\leqslant j\leqslant n\text{\small and
}i_{j}=i}$.

If $\mu:A^{*}\rightarrow\Mono$ is a monoid morphism, we say that any
$m,m^{\prime}\in\Mono$ and $a\in A$ define a $\mu$-context that we denote by
$m{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a\bm{\rrbracket}}m^{\prime}$.
It is well-known that the crossing sequence in a position of the input only
depends on the context of this position, for a well-chosen monoid, as claimed
in proposition 1 (see e.g. [7]).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Proposition 1

One can build a finite monoid $\mathbb{T}$ and a monoid morphism
$\mu:A^{*}\rightarrow\mathbb{T}$, called the transition morphism of
$\mathscr{T}$, such that for all $u\in A^{*}$ and $1\leqslant i\leqslant|u|$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{cross}}}}}_{\mathscr{T}}^{u}{}{}(i)$
only depends on $\mu(u[1{:}i{-}1]),u[i]$ and $\mu(u[i{+}1{:}|u|])$.
Thus we denote it
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{\textsf{{cross}}}}}}_{\mathscr{T}}{}{}(\mu(u[1{:}i{-}1]){\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}u[i]\bm{\rrbracket}}\mu(u[i{+}1{:}|u|])$.

Finally, let us define “the output produced below position $i$”.

###### Definition 3

Let $u\in A^{*}$ and $1\leqslant i\leqslant|u|$ and $q_{1}\cdots
q_{n}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{cross}}}}}_{\mathscr{T}}^{u}{}{}(i)$.
We define the production of $\mathscr{T}$ in $i$, denoted
$\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{\textsf{{prod}}}}}}_{\mathscr{T}}^{u}{}{}(i)$,
as $\lambda(q_{1},u[i])\cdots\lambda(q_{n},u[i])$.

By proposition 1, it also makes sense to define
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{\textsf{{prod}}}}}}_{\mathscr{T}}{}{}(m{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a\bm{\rrbracket}}m^{\prime})\in
B^{*}$ to be
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}}^{u}{}{}(i)$
whenever $m=\mu(u[1{:}i{-}1])$, $m^{\prime}=\mu(u[i{+}1{:}|u|])$ and $a=u[i]$.

##  3 Blind and last pebble transducers

Now, we are ready to define formally the models of blind pebble transducers
and last pebble transducers. Intuitively, they correspond to two-way
transducers which make a tree of recursive calls to other two-way transducers.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Definition 4 (Blind pebble transducer [16])

For $k\geqslant 1$, a blind $k$-pebble transducer with input alphabet $A$ and
output alphabet $B$ is:

  * •

if $k=1$, a two-way transducer with input alphabet $A$ and output $B$;

  * •

if $k\geqslant 2$, a tree
$\mathscr{T}\langle\mathscr{B}_{1},\cdots,\mathscr{B}_{p}\rangle$ where
$\mathscr{B}_{1},\dots,\mathscr{B}_{p}$ are blind $(k{-}1)$-pebble transducers
with input $A$ and output $B$; and $\mathscr{T}$ is a two-way transducer with
input $A$ and output alphabet $\\{\mathscr{B}_{1},\dots,\mathscr{B}_{p}\\}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The (total) function $f:A^{*}\rightarrow B^{*}$ computed by the blind
$k$-pebble transducer of definition 4 is built in a recursive fashion, as
follows:

  * •

for $k=1$, $f$ is the function computed by the two-way transducer;

  * •

for $k\geqslant 2$, let $u\in A^{*}$ and
$(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{n},i_{n})$ be
the accepting run of $\mathscr{T}=(A,B,Q,q_{0},F,\delta,\lambda)$ on
${\vdash}u{\dashv}$. For all $1\leqslant j\leqslant n$, let
$f_{j}:A^{*}\rightarrow B^{*}$ be the concatenation of the functions
recursively computed by the sequence
$\lambda(q_{j},({\vdash}u{\dashv})[i_{j}])\in\\{\mathscr{B}_{1},\dots,\mathscr{B}_{p}\\}^{*}$.
Then $f(u)\coloneqq f_{1}(u)\cdots f_{n}(u)$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The behavior of a blind $3$-pebble transducer is depicted in fig. 2.

###### Example 2

The function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\mathsf{unmarked-
square}}}}{}{}:A^{*}\rightarrow A^{*}\uplus\\{\\#\\},u\mapsto(u\\#)^{|u|}$ can
be computed by a blind $2$-pebble transducer. This machine has shape
$\mathscr{T}\langle\mathscr{T}^{\prime}\rangle$: $\mathscr{T}$ calls
$\mathscr{T}^{\prime}$ on each position $1\leqslant i\leqslant|u|$ of its
input $u$, and $\mathscr{T}^{\prime}$ outputs $u\\#$.

The class of functions computed by a blind $k$-pebble transducer for some
$k\geqslant 1$ is called polyblind functions [10]. They form a strict subclass
of polyregular functions [8, 10, 16] which is closed under composition [16,
Theorem 6.1].

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Now, let us define last pebble transducers. They corresponds to blind pebble
transducers enhanced with the ability to mark the current position of the
input when doing a recursive call. Formally, this position is underlined and
we define
$u\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\bullet}}i{}{}\coloneqq
u[1]\cdots u[i{-}1]\underline{u[i]}u[i{+}1]\cdots u[|u|]$ for $u\in A^{*}$ and
$1\leqslant i\leqslant|u|$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Definition 5 (Last pebble transducer [13])

For $k\geqslant 1$, a last $k$-pebble transducer with input alphabet $A$ and
output alphabet $B$ is:

  * •

if $k=1$, a two-way transducer with input alphabet $A\uplus\underline{A}$ and
output $B$;

  * •

if $k\geqslant 2$, a tree
$\mathscr{T}\langle\mathscr{L}_{1},\cdots,\mathscr{L}_{p}\rangle$ where
$\mathscr{L}_{1},\dots,\mathscr{L}_{p}$ are last $(k{-}1)$-pebble transducers
with input $A$ and output $B$; and $\mathscr{T}$ is a two-way transducer with
input $A\uplus\underline{A}$ and output alphabet
$\\{\mathscr{L}_{1},\dots,\mathscr{L}_{p}\\}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The (total) function $f:(A\uplus\underline{A})^{*}\rightarrow B^{*}$ computed
by the last $k$-pebble transducer of definition 5 is defined in a recursive
fashion, as follows:

  * •

for $k=1$, $f$ is the function computed by the two-way transducer;

  * •

for $k\geqslant 2$, let $u\in A^{*}$ and
$(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{n},i_{n})$ be
the accepting run of
$\mathscr{T}=(A\uplus\underline{A},B,Q,q_{0},F,\delta,\lambda)$ on
${\vdash}u{\dashv}$. For all $1\leqslant j\leqslant n$, let
$f_{j}:A^{*}\rightarrow B^{*}$ be the concatenation of the functions
recursively computed by
$\lambda(q_{j},({\vdash}u{\dashv})[i_{j}])\in\\{\mathscr{L}_{1},\dots,\mathscr{L}_{p}\\}^{*}$.
Let $\tau:(A\uplus\underline{A})^{*}\rightarrow A^{*}$ be the morphism which
erases the underlining (i.e. $\tau(\underline{a})=a$), then $f(u)\coloneqq
f_{1}(\tau(u){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{1}{}{})\cdots
f_{n}(\tau(u){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{n}{}{})$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The behavior of a last $3$-pebble transducer is depicted in fig. 3. Observe
that our definition builds a function of type
$(A\uplus\underline{A})^{*}\rightarrow B^{*}$, but at shall in fact consider
its restriction to $A^{*}$ (the marks are only used within the induction
step).

######  Example 3 ([1])

The function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\mathsf{square}}}}{}{}:u\mapsto(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}1{}{})\\#\cdots(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}|u|{}{})\\#$
can be computed by a last $2$-pebble transducer, which successively marks and
makes recursive calls in positions $1,2$, etc. However this function is not
polyblind [16].

We are ready to state our main result. Its proof goes over sections 4, 5 and
6.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Theorem 3.1 (Minimization of the recursion height)

Let $1\leqslant\ell\leqslant k$. Let $f:A^{*}\rightarrow B^{*}$ be computed by
a blind $k$-pebble transducer (resp. by a last $k$-pebble transducer). Then
$f$ can be computed by a blind $\ell$-pebble transducer (resp. by a last
$\ell$-pebble transducer) if and only if $|f(u)|=\mathcal{O}(|u|^{\ell})$.
This property is decidable and the construction is effective.

As an easy consequence, the class of functions computed by last pebble
transducers form a strict subclass of the polyregular functions (because
theorem 3.1 does not hold for the full model of pebble transducers [3, Theorem
6.3]) and therefore it is not closed under composition (because any
polyregular function can be obtained as a composition of regular functions and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\mathsf{square}}}{}{}$s
[1]).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Even if a (non-effective) theorem 3.1 was already known for blind pebble
transducers [16, Theorem 7.1], we shall first present our proof of this case.
Indeed, it is a new proof (relying on factorization forests) which is simpler
than the original one. Furthermore, understanding the techniques used is a key
step for understanding the proof for last pebble transducers presented
afterwards.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

##  4 Factorization forests

In this section, we introduce the key tool of factorization forests. Given a
monoid morphism $\mu:A^{*}\rightarrow\Mono$ and $u\in A^{*}$, a
$\mu$-factorization forest of $u$ is an unranked tree structure defined as
follows. We use the brackets $\langle\cdots\rangle$ to build a tree.

######  Definition 6 (Factorization forest [18])

Given a morphism $\mu:A^{*}\rightarrow\Mono$ and $u\in A^{*}$, we say that
$\mathcal{F}$ is a $\mu$-forest of $u$ if:

  * •

either $u=\varepsilon$ and $\mathcal{F}=\varepsilon$; or $u=\langle
a\rangle\in A$ and $\mathcal{F}=a$;

  * •

or $\mathcal{F}=\langle\mathcal{F}_{1},\cdots,\mathcal{F}_{n}\rangle$,
$u=u_{1}\cdots u_{n}$, for all $1\leqslant i\leqslant n$, $\mathcal{F}_{i}$ is
a $\mu$-forest of $u_{i}\in A^{+}$, and if $n\geqslant 3$ then
$\mu(u)=\mu(u_{1})=\dots=\mu(u_{n})$ is idempotent.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

We use the standard tree vocabulary of height, child, sibling, descendant and
ancestor (a node being itself one of its ancestors/descendants), etc. We
denote by
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Nodes}}}}^{\mathcal{F}}{}{}$
the set of nodes of $\mathcal{F}$. In order to simplify the statements, we
identify a node
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$
with the subtree rooted in this node. Thus
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$
can also be seen as the set of subtrees of $\mathcal{F}$, and
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$.
We say that a node is idempotent if it has at least $3$ children. We denote by
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Forests}}}}_{\mu}{}{}(u)$
(resp.
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Forests}}}}_{\mu}^{d}{}{}(u)$)
the set of $\mu$-forests of $u\in A^{*}$ (resp. $\mu$-forests of $u\in A^{*}$
of height at most $d$). We write
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Forests}}}}_{\mu}{}{}$
and
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Forests}}}}_{\mu}^{d}{}{}$
of all forests (of any word).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

A $\mu$-forest of $u\in A^{*}$ can also be seen as “the word $u$ with
brackets” in definition 6. Therefore
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}$
can be seen as a language over ${\widehat{A}}\coloneqq
A\uplus\\{\langle,\rangle\\}$. In this setting, it is well-known that
$\mu$-forests of bounded height can effectively be computed by a rational
function, i.e. a particular case of regular function that can be computed by a
non-deterministic one-way transducer (see e.g. [8]).

######  Theorem 4.1 (Simon [18, 6])

Given a morphism $\mu:A^{*}\to\Mono$ into a finite monoid $\Mono$, one can
effectively build a rational function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{forest}}}}_{\mu}{}{}:A^{*}\to({\widehat{A}})^{*}$
such that for all $u\in A^{*}$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}^{3|\Mono|}{}{}(u)$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Building $\mu$-forests of bounded height is especially useful for us, since it
enables to decompose any word in a somehow bounded way. This decomposition
will be guided by the following definitions, that have been introduced in [8,
10]. First, we define iterable nodes as the middle children of idempotent
nodes.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Definition 7

Let
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$.
Its iterable nodes, denoted
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Iter}}}}^{\mathcal{F}}{}{}$,
are:

  * •

if $\mathcal{F}=\langle a\rangle\in A$ or $\mathcal{F}=\varepsilon$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}\coloneqq\varnothing$;

  * •

otherwise if
$\mathcal{F}=\langle\mathcal{F}_{1},\cdots,\mathcal{F}_{n}\rangle$, then:

$\displaystyle{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}\coloneqq\\{\mathcal{F}_{i}:2\leqslant
i\leqslant n{-}1\\}\cup\bigcup_{1\leqslant i\leqslant
n}{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}_{i}}{}{}.$

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Now, we define the notion of skeleton of a node $\mathfrak{t}$, which contains
all the descendants of $\mathfrak{t}$ except those which are iterable.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Definition 8 (Skeleton, frontier)

Let
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$,
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$,
we define the skeleton of $\mathfrak{t}$, denoted
$\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Skel}}}}^{\mathcal{F}}{}{}(\mathfrak{t})$,
by:

  * •

if $\mathfrak{t}=\langle a\rangle\in A$ is a leaf, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathfrak{t})\coloneqq\\{\mathfrak{t}\\}$;

  * •

otherwise if
$\mathfrak{t}=\langle\mathcal{F}_{1},\cdots,\mathcal{F}_{n}\rangle$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathfrak{t})\coloneqq\\{\mathfrak{t}\\}\cup{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathcal{F}_{1})\cup{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathcal{F}_{n})$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

The frontier of $\mathfrak{t}$ is the set
$\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{Fr}}}}^{\mathcal{F}}{}{}(\mathfrak{t})\subseteq[1{:}|u|]$
containing the positions of $u$ which belong to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathfrak{t})$
(when seen as leaves of the $\mu$-forest $\mathcal{F}$ over $u$).

###### Example 4

Let $\Mono\coloneqq(\\{-1,1,0\\},\times)$ and $\mu:\Mono^{*}\rightarrow\Mono$
the product. A $\mu$-forest $\mathcal{F}$ of the word $(-1)(-1)0(-1)000000$ is
depicted in Figure 4. Double lines denote idempotent nodes. The set of blue
nodes is the skeleton of the topmost blue node.

$-1$$-1$$0$$-1$$0$$0$$0$$0$$0$$0$

Figure 4:
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}((-1)(-1)0(-1)000000)$
and a skeleton.

It is easy to observe that for
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}^{d}{}{}(u)$,
the size of a skeleton, or of a frontier, is bounded independently from
$\mathcal{F}$. Furthermore, the set of skeletons
$\\{{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Skel}}}^{\mathcal{F}}{}{}(\mathfrak{t}):\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}\cup\\{\mathcal{F}\\}\\}$
is a partition of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$
[8, Lemma 33]. As a consequence, the set of frontiers
$\\{{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}):\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}\cup\\{\mathcal{F}\\}\\}$
is a partition of $[1{:}|u|]$. Given a position $1\leqslant i\leqslant|u|$, we
can thus define the origin of $i$ in $\mathcal{F}$, denoted
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\operatorname{\textsf{origin}}}}^{\mathcal{F}}{}{}(i)$,
as the unique
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}\cup\\{\mathcal{F}\\}$
such that
$i\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}{}(\mathfrak{t})$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Definition 9 (Observation)

Let
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}$
and
$\mathfrak{t},\mathfrak{t}^{\prime}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$.
We say that
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$
observes
$\mathfrak{t}^{\prime}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}}{}{}$
if either $\mathfrak{t}^{\prime}$ is an ancestor of $\mathfrak{t}$, or
$\mathfrak{t}^{\prime}$ is the immediate right or left sibling of an ancestor
of $\mathfrak{t}$.

Nodes that observe $\bullet$$\bullet$ observes these nodes

Figure 5:  Nodes that observe $\bullet$ and that $\bullet$ observes

The intuition behind the notion of observation (which is _not_ symmetrical) is
depicted in fig. 5. Note that in a forest of bounded height, the number of
nodes that some $\mathfrak{t}$ observes is bounded. This will be a key
argument in the following. We say that $\mathfrak{t}$ and
$\mathfrak{t}^{\prime}$ are dependent if either $\mathfrak{t}$ observes
$\mathfrak{t}^{\prime}$ or the converse. Given $\mathcal{F}$, we can translate
these notions to the positions of $u$: we say that $i$ observes (resp. depends
on) $i^{\prime}$ if
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
observes (resp. depends on)
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i^{\prime})$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

##  5 Height minimization of blind pebble transducers

In this section, we show theorem 3.1 for blind pebble transducers. We say that
a two-way transducer $\mathscr{T}$ is a submachine of a blind pebble
transducer $\mathscr{B}$ if $\mathscr{T}$ labels a node in the tree
description of $\mathscr{B}$. If
$\mathscr{B}=\mathscr{T}\langle\mathscr{B}_{1},\dots,\mathscr{B}_{n}\rangle$,
we say that the submachine $\mathscr{T}$ is the head of $\mathscr{B}$. We let
the transition morphism of $\mathscr{B}$ be the cartesian product of all the
transition morphisms of all the submachines of $\mathscr{B}$. Observe that it
makes sense to consider the production of a submachine $\mathscr{T}$ in a
context defined using the transition morphism of $\mathscr{B}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###  5.1 Pumpability

We first give a sufficient condition, named pumpability, for a blind
$k$-pebble transducer to compute a function $f$ such that
$|f(u)|\neq\mathcal{O}(|u|^{k-1})$. The behavior of a pumpable blind
$2$-pebble transducer is depicted in fig. 6 over a well-chosen input: it has a
factor in which the head $\mathscr{T}_{1}$ calls a submachine
$\mathscr{T}_{2}$, and a factor in which $\mathscr{T}_{2}$ produces a non-
empty output. Furthermore both factors can be iterated without destroying the
runs of these machines (due to idempotents).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Definition 10

Let $\mathscr{B}$ be a blind $k$-pebble transducer whose transition morphism
is $\mu:A^{*}\rightarrow\mathbb{T}$. We say that the transducer $\mathscr{B}$
is pumpable if there exists:

  * •

submachines $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of $\mathscr{B}$, such
that $\mathscr{T}_{1}$ is the head of $\mathscr{B}$;

  * •

$m_{0},\dots,m_{k},{\ell}_{1},\dots,{\ell_{k}},r_{1},\dots,r_{k}\in\mu(A^{*})$;

  * •

$a_{1},\dots,a_{k}\in A$ such that for all $1\leqslant j\leqslant k$,
$e_{i}\coloneqq{\ell}_{j}\mu(a_{j})r_{j}$ is an idempotent;

  * •

a permutation $\sigma:[{1}{:}{k}]\rightarrow[{1}{:}{k}]$;

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

such that if $\mathcal{M}_{i}^{j}\coloneqq m_{i}e_{i+1}m_{i+1}\cdots
e_{j}m_{j}$ for all $0\leqslant i\leqslant j\leqslant k$, and if we define the
following context for all $1\leqslant j\leqslant k$:

$\displaystyle\mathcal{C}_{j}\coloneqq\mathcal{M}_{0}^{\sigma(j)-1}e_{\sigma(j)}\ell_{\sigma(j)}{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{\sigma(j)}\bm{\rrbracket}}r_{\sigma(j)}e_{\sigma(j)}\mathcal{M}_{\sigma(j)}^{k}$

then for all $1\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}{}{}(\mathcal{C}_{j})|_{\mathscr{T}_{j+1}}\neq
0$, and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}{}{}(\mathcal{C}_{k})\neq\varepsilon$.

$a_{1}$$a_{2}$${\vdash}$${\dashv}$$m_{0}$$e_{1}$$\ell_{1}$${\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{1}\bm{\rrbracket}}$$r_{1}$$e_{1}$$m_{1}$$e_{2}$$\ell_{2}$$\mu(a_{2})$$r_{2}$$e_{2}$$m_{2}$$a_{1}$$a_{2}$${\vdash}$${\dashv}$$m_{0}$$e_{1}$$\ell_{1}$$\mu(a_{1})$$r_{1}$$e_{1}$$m_{1}$$e_{2}$$\ell_{2}$${\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{2}\bm{\rrbracket}}$$r_{2}$$e_{2}$$m_{2}$

$\mathscr{T}_{1}$ head

$\mathscr{T}_{2}$

$\lambda\neq\varepsilon$Call $\mathscr{T}_{2}$

Figure 6:  Pumpability in a blind $2$-pebble transducer.

Lemma 1 follows by choosing inverse images in $A^{*}$ for the $m_{i}$,
$\ell_{i}$ and $r_{i}$.

###### Lemma 1

Let $f$ be computed by a pumpable blind $k$-pebble transducer. There exists
words $v_{0},\dots,v_{k},u_{1},\dots,u_{k}$ such that $|f(v_{0}u_{1}^{X}\cdots
u_{k}^{X}v_{k})|=\theta(X^{k})$.

Now, we use pumpability as a key ingredient for showing theorem 3.1, which
directly follows by induction from the more precise theorem 5.1.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Theorem 5.1 (Removing one layer)

Let $k\geqslant 2$ and $f:A^{*}\rightarrow B^{*}$ be computed by a blind
$k$-pebble transducer $\mathscr{B}$. The following are equivalent:

  1. 1.

$|f(u)|=\mathcal{O}(|u|^{k-1})$;

  2. 2.

$\mathscr{B}$ is not pumpable;

  3. 3.

$f$ can be computed by a blind $(k{-}1)$-pebble transducer.

Furthermore, this property is decidable and the construction is effective.

###### Proof

Item 3 $\Rightarrow$ item 1 is obvious. Item 1 $\Rightarrow$ item 2 is lemma
1. Furthermore, pumpability can be tested by an enumeration of $\mu(A^{*})$
and $A$. It remains to show item 2 $\Rightarrow$ item 3 (in an effective
fashion): this is the purpose of section 5.2.

###  5.2 Algorithm for removing a recursion layer

Let $k\geqslant 2$ and $\mathscr{U}$ be a last $k$-pebble transducer that is
not pumpable, and that computes $f:A^{*}\rightarrow B^{*}$. We build a blind
$(k{-}1)$-pebble transducer $\overline{\mathscr{U}}$ for $f$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Let $\mu:A^{*}\rightarrow\mathbb{T}$ be the transition morphism of
$\mathscr{U}$. We shall consider that, on input $u\in A^{*}$, the submachines
of $\overline{\mathscr{U}}$ can in fact use
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)\subseteq({\widehat{A}})^{*}$
as input. Indeed
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}$
is a rational function (by theorem 4.1), hence its information can be
recovered by using a lookaround. Informally, the lookaround feature enables a
two-way transducer to chose its transitions not only depending on its current
state and current letter $u[i]$ in position $1\leqslant i\leqslant|u|$, but
also on a regular property of the prefix $u[1{:}i{-}1]$ and the suffix
$u[i{+1}{:}|u|]$. It is well-known that given a two-way transducer
$\mathscr{T}$ with lookarounds, one can build an equivalent
$\mathscr{T}^{\prime}$ that does not have this feature (see e.g. [15, 12]).
Furthermore, even if the accepting runs of $\mathscr{T}$ and
$\mathscr{T}^{\prime}$ may differ, they produce the same outputs from the same
positions (this observation will be critical for last pebble transducers, in
order to ensure that the marked positions of the recursive calls will be
preserved).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Now, we describe the two-way transducers that are the submachines of
$\overline{\mathscr{U}}$. First, it has submachines
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{old-}}}\mathscr{T}}}}{}{}$
for $\mathscr{T}$ a submachine of $\mathscr{U}$, which are described in
algorithm 1. Intuitively,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}}}{}{}$
is just a copy of $\mathscr{T}$. It is clear that if $\mathscr{T}$ is a
submachine of $\mathscr{U}$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}}}{}{}(u)$
is the concatenation of the outputs produced by (the recursive calls of)
$\mathscr{T}$ along its accepting run on ${\vdash}u{\dashv}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

1

2Submachine
_$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{old-}}}\mathscr{T}}}}{}{}(u)$_

3

4 $\rho\coloneqq$ accepting run of $\mathscr{T}$ over ${\vdash}u{\dashv}$;
$\lambda\coloneqq$ output function of $\mathscr{T}$;

5 for  _$(q,i)\in\rho$_ do

6

7 if  _$\mathscr{T}$ is a leaf of $\mathscr{U}$_ then

8

9 Output $\lambda(q,({\vdash}u{\dashv})[i])$; /* $\mathscr{T}$ has output in
$B^{*}$; */

10

11 else

12

13 for  _$\mathscr{B}^{\prime}\in\lambda(q,({\vdash}u{\dashv})[i])$_ do

14

15 $\mathscr{T}^{\prime}\coloneqq$ head of $\mathscr{B}^{\prime}$;

16 Call
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}}}{}{}(u)$;
/* $\mathscr{T}$ makes recursive calls; */

17

18 end for

19

20 end if

21

22 end for

23

24

25

Algorithm 1 Submachines that behave as the original ones

$\overline{\mathscr{U}}$ also has submachines
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{accelerate-}}}\mathscr{T}}}}{}{}$
for $\mathscr{T}$ a submachine of $\mathscr{U}$, which are described in
algorithm 2. Intuitively,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
simulates $\mathscr{T}$ while trying to inline recursive calls in its own run.
More precisely, let $u\in A^{*}$ be the input and
$\mathcal{F}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$.
If $\mathscr{T}$ calls $\mathscr{B}^{\prime}$ in $1\leqslant i\leqslant|u|$
that belongs to the frontier of the root node $\mathcal{F}$ of $\mathcal{F}$,
then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
inlines the behavior of the head of $\mathscr{B}^{\prime}$. Otherwise it makes
a recursive call, except if $\mathscr{B}^{\prime}$ is a leaf of $\mathscr{U}$.
Hence if $\mathscr{T}$ is a submachine of $\mathscr{U}$ which is not a leaf,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}(u)$
is the concatenation of the outputs produced by the calls of $\mathscr{T}$
along its accepting run.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

1

2Submachine
_$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{accelerate-}}}\mathscr{T}}}}{}{}\leavevmode\nobreak\
(u)$_

3

4 /* $\mathscr{T}$ is not a leaf of $\mathscr{U}$ (i.e. it makes calls); */

5

6 $\rho\coloneqq$ accepting run of $\mathscr{T}$ over ${\vdash}u{\dashv}$;
$\mathcal{F}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$;
$\lambda\coloneqq\text{output of }\mathscr{T}$;

7 for  _$(q,i)\in\rho$_ do

8

9 for  _$\mathscr{B}^{\prime}\in\lambda(q,({\vdash}u{\dashv})[i])$_ do

10

11 $\mathscr{T}^{\prime}\coloneqq$ head of $\mathscr{B}^{\prime}$;

12 if
_$i\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$_
then

13

14 /* We can inline the call since
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})|$
is bounded; */

15

16 Inline the code of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}}}{}{}\leavevmode\nobreak\
(u)$;

17

18 else if  _$\mathscr{B}^{\prime}$ is a leaf of $\mathscr{U}$_ then

19

20 /* Then $\mathscr{B}^{\prime}=\mathscr{T}^{\prime}$ and we can inline the
call because the output of $\mathscr{T}^{\prime}$ on input $u$ is bounded; */

21

22 Inline the code of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}}}{}{}\leavevmode\nobreak\
(u)$;

23

24 else

25

26 /* It is not possible to inline the call to $\mathscr{B}^{\prime}$, so we
make a recursive call; */

27

28 Call
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}{\mathscr{T}^{\prime}}}}{}{}\leavevmode\nobreak\
(u)$;

29 end if

30

31 end for

32

33 end for

34

35

36

Algorithm 2 Submachines that try to simulate their recursive calls

Finally, the transducer $\overline{\mathscr{U}}$ is obtained by defining
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
to be its head, where $\mathscr{T}$ is the head of $\mathscr{U}$. Furthermore,
we remove the submachines
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}}}{}{}$
or
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
which are never called. Observe that $\overline{\mathscr{U}}$ indeed computes
the function $f$. Furthermore, we observe that $\overline{\mathscr{U}}$ has
recursion height (i.e. the number of nested Call instructions, plus $1$ for
the head) $k{-}1$, since each inlining of algorithms 2, 2 and 2 in algorithm 2
removes exactly one recursion layer of $\mathscr{U}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

It remains to justify that each
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
can be implemented by a two-way transducer (i.e. with lookarounds but a
bounded memory). We represent variable $i$ by the current position of the
transducer. Since it has access to $\mathcal{F}$, the lookaround can be used
to check whether
$i\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
or not (since the size of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
is bounded). It remains to explain how the inlinings are performed:

  * •

if
$i\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$,
the two-way transducer inlines
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}}}{}{}$
by executing the same moves and calls as $\mathscr{T}^{\prime}$ does. Once its
computation is ended, it has to go back to position $i$. This is indeed
possible since belonging to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
is a property that can be detected by using the lookaround, hence the machine
only needs to remember that $i$ was the $\ell$-th position of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
($\ell$ being bounded);

  * •

else if $\mathscr{B}^{\prime}=\mathscr{T}^{\prime}$ is a blind $1$-pebble
transducer, we produce the output of $\mathscr{T}^{\prime}$ without moving.
This is possible since for all
$i^{\prime}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}^{\prime}}^{u}{}{}(i^{\prime})=\varepsilon$
(hence the output of $\mathscr{T}^{\prime}$ on $u$ is bounded, and its value
can be determined without moving, just by using the lookaround). Indeed, if
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}^{\prime}}^{u}{}{}(i^{\prime})\neq\varepsilon$
for such an
$i^{\prime}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
when reaching algorithm 2 of algorithm 2, then the conditions of lemma 2 hold,
which yields a contradiction. This lemma is the key argument of this proof,
relying on the non-pumpability of $\mathscr{U}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Lemma 2 (Key lemma)

Let $u\in A^{*}$ and
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$.
Assume that there exists a sequence $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of
submachines of $\mathscr{U}$ and a sequence of positions $1\leqslant
i_{1},\dots,i_{k}\leqslant|u|$ such that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$;

  * •

for all $1\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$ and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}^{u}{}{}(i_{k})\neq\varepsilon$;

  * •

for all $1\leqslant j\leqslant k$,
$i_{j}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
(i.e.
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}$).

Then $\mathscr{B}$ is pumpable.

######  Proof (idea)

We first observe that pumpability follows as soon as the nodes
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
are two by two independent. We then show that this independence condition can
always be obtained, up to duplicating some iterable subtrees of $\mathcal{F}$
(and some factors of $u$), because the behavior of a submachine in a blind
pebble transducer does not depend on the positions of the above recursive
calls.

##  6 Height minimization of last pebble transducers

In this section, we show theorem 3.1 for last pebble transducers. The notions
of submachine, head and transition morphism for a last pebble transducer are
defined as in section 5. The transition morphism is now defined over
$(A\uplus\underline{A})^{*}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###  6.1 Pumpability

The sketch of the proof is similar to section 5. We first give an equivalent
of pumpability for last pebble transducers. The intuition behind this notion
is depicted in fig. 7. The formal definition is however more cumbersome, since
we need to keep track of the fact that the calling position is marked.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Definition 11

Let $\mathscr{L}$ be a last $k$-pebble transducer whose transition morphism is
$\mu:(A\cup\underline{A})^{*}\rightarrow\mathbb{T}$. We say that the
transducer $\mathscr{L}$ is pumpable if there exists:

  * •

submachines $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of $\mathscr{L}$, such
that $\mathscr{T}_{1}$ is the head of $\mathscr{L}$;

  * •

$m_{0},\dots,m_{k},{\ell}_{1},\dots,{\ell_{k}},r_{1},\dots,r_{k}\in\mu(A^{*})$;

  * •

$a_{1},\dots,a_{k}\in A$ such that for all $1\leqslant j\leqslant k$
$e_{j}\coloneqq{\ell}_{j}\mu(a_{j})r_{j}$ is idempotent;

  * •

a permutation $\sigma:[{1}{:}{k}]\rightarrow[{1}{:}{k}]$;

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

such that if we let $\mathcal{M}_{i}^{j}\coloneqq m_{i}e_{i+1}m_{i+1}\cdots
e_{j}m_{j}$ for all $0\leqslant i\leqslant j\leqslant k$, and if we define the
following context:

$\displaystyle\mathcal{C}_{1}\coloneqq\mathcal{M}_{0}^{\sigma(1)-1}e_{\sigma(1)}\ell_{\sigma(1)}{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{\sigma(1)}\bm{\rrbracket}}r_{1}e_{\sigma(1)}\mathcal{M}_{\sigma(1)}^{k}$

and for all $1\leqslant j\leqslant k{-}1$ the context:

$\displaystyle\mathcal{C}_{j+1}$
$\displaystyle\coloneqq\mathcal{M}_{0}^{\sigma(j)-1}e_{\sigma(j)}\ell_{\sigma(j)}\mu(\underline{a_{\sigma(j)}})r_{\sigma(j)}e_{\sigma(j)}\mathcal{M}_{\sigma(j)}^{\sigma(j+1)-1}$
$\displaystyle
e_{\sigma(j+1)}\ell_{\sigma(j+1)}{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{\sigma(j+1)}\bm{\rrbracket}}r_{\sigma(j+1)}e_{\sigma(j+1)}\mathcal{M}_{\sigma(j+1)}^{k}$
if $\sigma(j)<\sigma(j+1)$; $\displaystyle\mathcal{C}_{j+1}$
$\displaystyle\coloneqq\mathcal{M}_{0}^{\sigma(j)-1}e_{\sigma(j+1)}\ell_{\sigma(j+1)}{\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{\sigma(j+1)}\bm{\rrbracket}}r_{\sigma(j+1)}e_{\sigma(j+1)}$
$\displaystyle\mathcal{M}_{\sigma(j+1)}^{\sigma(j)-1}e_{\sigma(j)}\ell_{\sigma(j)}\mu(\underline{a_{\sigma(j)}})r_{\sigma(j)}e_{\sigma(j)}\mathcal{M}_{\sigma(j)}^{k}$
otherwise;

then for all $1\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}{}{}(\mathcal{C}_{j})|_{\mathscr{T}_{j+1}}\neq
0$, and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}{}{}(\mathcal{C}_{k})\neq\varepsilon$.

$a_{1}$$a_{2}$${\vdash}$${\dashv}$$m_{0}$$e_{1}$$\ell_{1}$${\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{1}\bm{\rrbracket}}$$r_{1}$$e_{1}$$m_{1}$$e_{2}$$\ell_{2}$$\mu(a_{2})$$r_{2}$$e_{2}$$m_{2}$$a_{1}$$a_{2}$${\vdash}$${\dashv}$$m_{0}$$e_{1}$$\ell_{1}$$\mu(\underline{a_{1}})$$r_{1}$$e_{1}$$m_{1}$$e_{2}$$\ell_{2}$${\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\bm{\llbracket}a_{2}\bm{\rrbracket}}$$r_{2}$$e_{2}$$m_{2}$

$\mathscr{T}_{1}$ head

$\mathscr{T}_{2}$

$\lambda\neq\varepsilon$Call $\mathscr{T}_{2}$

Figure 7:  Pumpability in a last $2$-pebble transducer.

We obtain lemma 3 by a proof which is similar to that of lemma 1.

###### Lemma 3

Let $f$ be computed by a pumpable last $k$-pebble transducer. There exists
words $v_{0},\dots,v_{k},u_{1},\dots,u_{k}$ such that $|f(v_{0}u_{1}^{X}\cdots
u_{k}^{X}v_{k})|=\theta(X^{k})$.

######  Theorem 6.1 (Removing one layer)

Let $k\geqslant 2$ and $f:A^{*}\rightarrow B^{*}$ be computed by a last
$k$-pebble transducer $\mathscr{L}$. The following are equivalent:

  1. 1.

$|f(u)|=\mathcal{O}(|u|^{k-1})$;

  2. 2.

$\mathscr{L}$ is not pumpable;

  3. 3.

$f$ can be computed by a last $(k{-}1)$-pebble transducer.

Furthermore, this property is decidable and the construction is effective.

###### Proof

Item 3 $\Rightarrow$ item 1 is obvious. Item 1 $\Rightarrow$ item 2 is lemma
3. Furthermore, pumpability can be tested by an enumeration of $\mu(A^{*})$
and $A$. It remains to show item 2 $\Rightarrow$ item 3 (in an effective
fashion): this is the purpose of section 6.2.

###  6.2 Algorithm for removing a recursion layer

Let $k\geqslant 2$ and $\mathscr{U}$ be a last $k$-pebble transducer that is
not pumpable, and that computes $f:A^{*}\rightarrow B^{*}$. We build a last
$(k{-}1)$-pebble transducer $\overline{\mathscr{U}}$ for $f$. Let
$\mu:(A\uplus\underline{A})^{*}\rightarrow\mathbb{T}$ be the transition
morphism of $\mathscr{U}$. As before (using a lookaround), the submachines of
$\overline{\mathscr{U}}$ will use
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$
as input instead of $u\in A^{*}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Now, we describe the submachines of $\overline{\mathscr{U}}$. It has
submachines
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}}{}{}$
for $\mathscr{T}$ a submachine of $\mathscr{U}$ and $\rho$ a run of
$\mathscr{T}$, which are described in algorithm 1. Intuitively, these machines
mimics the behavior of $\mathscr{T}$ along the run $\rho$ (which is not
necessarily accepting) of $\mathscr{T}$ over ${\vdash}v{\dashv}$ with
$v\in(A\uplus\underline{A})^{*}$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Since they are indexed by a run $\rho$, it may seem that we create an infinite
number of submachines, but it will not be the case. Indeed, a run $\rho$ will
be represented by its first configuration $(q_{1},i_{1})$ and last
configuration $(q_{n},i_{n})$. This information is sufficient to simulate
exactly the two-way moves of $\rho$, but there is still an unbounded
information: the positions $i_{1}$ and $i_{n}$. In fact, the input will be of
the form
$v=u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}$
and we shall guarantee that the $i_{1}$ and $i_{n}$ can be detected by the
lookaround if $i$ is marked. Hence the run $\rho$ will be represented in a
bounded way, independently from the input $v$, and so that its first and last
configurations can be detected by the lookaround of the submachine.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

By algorithm 1, it is clear that if $\mathscr{T}$ is a submachine of
$\mathscr{U}$, then for all $v\in(A\cup\underline{A})^{*}$ and $\rho$ run of
$\mathscr{T}$ on ${\vdash}v{\dashv}$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}\leavevmode\nobreak\
(v)$ is the concatenation of the outputs produced by (the recursive calls of)
$\mathscr{T}$ along $\rho$.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

We also define a submachine
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{normal-}}}\mathscr{T}{{\textsf{-along-}}}\rho{{\textsf{-pebble-}}}i}}}{}{}$
that is similar to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$,
except that it ignores the mark of its input and acts as if it was in position
$i$ (as above for $\rho$, $i$ will be encoded by a bounded information).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

1

2Submachine
_$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}}{}{}(v)$_

3

4 /* $v\in(A\uplus\underline{A})^{*}$; $\rho$ is a run of $\mathscr{T}$ over
${\vdash}v{\dashv}$; */

5

6 $\lambda\coloneqq$ output function of $\mathscr{T}$;

7 for  _$(q,i)\in\rho$_ do

8

9 if  _$\mathscr{T}$ is a leaf of $\mathscr{U}$_ then

10

11 Output $\lambda(q,({\vdash}v{\dashv})[i])$; /* $\mathscr{T}$ has output in
$B^{*}$; */

12

13 else

14

15 for  _$\mathscr{L}^{\prime}\in\lambda(q,({\vdash}v{\dashv})[i])$_ do

16

17 $\mathscr{T}^{\prime}\coloneqq$ head of $\mathscr{L}^{\prime}$;
$\rho^{\prime}\coloneqq$ accepting run of $\mathscr{T}^{\prime}$ on
${\vdash}\tau(v){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}{\dashv}$;

18 Call
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}}}{}{}(\tau(v){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$;
/* Recursive call; */

19

20 end for

21

22 end if

23

24 end for

25

26

27

28Submachine
_$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{normal-}}}\mathscr{T}{{\textsf{-along-}}}\rho{{\textsf{-pebble-}}}i}}}{}{}(v)$_

29

30 /* $v\in(A\uplus\underline{A})^{*}$; $\rho$ is a run of $\mathscr{T}$ over
${\vdash}\tau(v){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}{\dashv}$;
*/

31

32 Simulate
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}\leavevmode\nobreak\
(\tau(v){\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$;

33

34

Algorithm 3 Submachines that behave like the original ones

$\overline{\mathscr{U}}$ also has submachines
$\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}}{}{}$
for $\mathscr{T}$ a submachine of $\mathscr{U}$, which are described in
algorithm 4. Intuitively,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
simulates $\mathscr{T}$ along $\rho$ while trying to inline some recursive
calls. Whenever it is in position $i$ and needs to call recursively
$\mathscr{L}^{\prime}$ whose head is $\mathscr{T}^{\prime}$, it first slices
the accepting run $\rho^{\prime}$ of $\mathscr{T}^{\prime}$ on
${\vdash}u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}{\dashv}$,
with respect to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}{}(u)$
and $i$, as explained in definition 12 and depicted in fig. 8. Intuitively,
this operation splits $\rho^{\prime}$ into a bounded number of runs whose
positions either all observe $i$, or $i$ observes all of them, or none of
these cases occur (the positions are either $0$, $|u|{+}1$ or independent of
$i$).

######  Definition 12 (Slicing)

Let $u\in A^{*}$,
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$
and $1\leqslant i\leqslant|u|$. We let
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\uparrow
i}}{}{}$ (resp.
$\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}\downarrow
i}}{}{}$) be the set of positions that $i$ observes (resp. that observe $i$).
Let $\rho=(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{n},i_{n})$ be
a run of a two-way transducer $\mathscr{T}$ on
${\vdash}u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}{\dashv}$.
We build by induction a sequence $\ell_{1},\dots,\ell_{N+1}$ with
$\ell_{1}\coloneqq 1$ and:

  * •

if $\ell_{j}=n{+}1$ then $j\coloneqq N$ and the process ends;

  * •

else if
$i_{\ell_{j}}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$ (resp.
$i_{\ell_{j}}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$, resp.
$i_{\ell_{j}}\in[0{:}|u|{+}1]\smallsetminus({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}\cup{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{})$), then $\ell_{j+1}$ is the largest index such that for all
$\ell_{j}\leqslant\ell\leqslant\ell_{j+1}{-}1$,
$i_{\ell}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$ (resp.
$i_{\ell}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$, resp.
$i_{\ell}\in[0{:}|u|{+}1]\smallsetminus({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}\cup{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{})$).

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Finally the slicing of $\rho$ ,with respect to $\mathcal{F}$ and $i$, is the
sequence of runs $\rho_{1},\dots,\rho_{N}$ where
$\rho_{j}\coloneqq(q_{\ell_{j}},i_{\ell_{j}})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{\ell_{j}+1},i_{\ell_{j}+1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}(q_{\ell_{j+1}-1},i_{\ell_{j+1}-1})$.

${\vdash}$${\dashv}$$i$${\color[rgb]{0.70703125,0.55859375,0.6796875}\definecolor[named]{pgfstrokecolor}{rgb}{0.70703125,0.55859375,0.6796875}\begin{subarray}{c}\text{positions
that}\\\ \text{belong to
}{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}\end{subarray}}$${\color[rgb]{0.75,0.37890625,0.4140625}\definecolor[named]{pgfstrokecolor}{rgb}{0.75,0.37890625,0.4140625}\begin{subarray}{c}\text{positions
that}\\\ \text{belong to
}{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}\end{subarray}}$$\rho_{1}$$\rho_{2}$$\rho_{3}$$\rho_{4}$$\rho_{5}$$\rho_{6}$$\rho_{7}$$\rho_{8}$$\rho_{9}$$\rho_{10}$$\rho_{11}$$\rho_{12}$$\rho_{13}$$\rho_{14}$$\rho_{15}$$\rho_{16}$$\rho_{17}$
Figure 8:  Slicing of a run $\rho$ with respect to $i$ and $\mathcal{F}$.

Now, let $\rho^{\prime}_{1},\dots,\rho^{\prime}_{N}$ be slicing of the run
$\rho^{\prime}$ of $\mathscr{T}^{\prime}$ on the input
$u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}$.
For all $1\leqslant j\leqslant N$, there are mainly two cases. Either the
positions of $\rho^{\prime}_{j}$ all are in
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$ or
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}$. In this case,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
directly inlines
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}$
within its own run (i.e. without making a recursive call). Otherwise, it makes
a recursive call to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}$,
except if $\mathscr{L}^{\prime}$ is a leaf of $\mathscr{U}$ (thus
$\mathscr{L}^{\prime}=\mathscr{T}^{\prime}$).

1

2Submachine
_$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}}{}{}\leavevmode\nobreak\
(v)$_

3

4 /* $\mathscr{T}$ is not a leaf of $\mathscr{U}$ (i.e. it makes calls); */

5

6 /* $v\in(A\uplus\underline{A})^{*}$; $\rho$ is a run of $\mathscr{T}$ over
${\vdash}v{\dashv}$; */

7

8 $u\coloneqq\tau(v)$;
$\mathcal{F}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$;
$\lambda\coloneqq\text{output function of }\mathscr{T}$;

9 for  _$(q,i)\in\rho$_ do

10

11 for  _$\mathscr{L}^{\prime}\in\lambda(q,({\vdash}v{\dashv})[i])$_ do

12

13 $\mathscr{T}^{\prime}\coloneqq$ head of $\mathscr{L}^{\prime}$;
$\rho^{\prime}\coloneqq\text{accepting run of $\mathscr{T}^{\prime}$ over
${\vdash}u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}{\dashv}$}$;

14 $\rho^{\prime}_{1},\cdots,\rho^{\prime}_{N}\coloneqq$ slicing of
$\rho^{\prime}$ with respect to $\mathcal{F}$ and $i$;

15 for  _$j=1$ to $N$_ do

16

17 $(q_{1},i_{1})\mathchoice{\xrightarrow{}}{\xrightarrow{\smash{\lower
1.0pt\hbox{$\scriptstyle$}}}}{\xrightarrow{}}{\xrightarrow{}}\cdots(q_{n},i_{n})\coloneqq\rho^{\prime}_{j}$

18 if
_$i_{1},\dots,i_{n}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$_ then

19

20 /* We inline the call because $n$ is bounded; */

21

22 Inline the code of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}\leavevmode\nobreak\
(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$;

23 else if
_$i_{1},\dots,i_{n}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}$_ then

24

25 /* We can inline the call because the positions $i_{1},\dots,i_{n}$ are
‘‘below’’ $i$ in $\mathcal{F}$; */

26

27 Inline the code of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}\leavevmode\nobreak\
(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$;

28 else if  _$\mathscr{L}^{\prime}$ is a leaf of $\mathscr{U}$_ then

29

30 /* The output of $\mathscr{L}^{\prime}=\mathscr{T}^{\prime}$ along
$\rho^{\prime}_{j}$ is empty; */

31

32

33 else

34

35 /* It is not possible to inline the call to $\mathscr{L}^{\prime}$, so we
make a recursive call; */

36

37 Call
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}{\mathscr{T}^{\prime}}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}\leavevmode\nobreak\
(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$;

38 end if

39

40 end for

41

42 end for

43

44 end for

45

46

47

48

Algorithm 4 Submachines that try to simulate their recursive calls

Finally, $\overline{\mathscr{U}}$ is described as follows: on input $u\in
A^{*}$, its head is the submachine
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}\leavevmode\nobreak\
(u)$, where $\mathscr{T}$ is the head of $\mathscr{U}$ and $\rho$ is the
accepting run of $\mathscr{T}$ on ${\vdash}u{\dashv}$ (represented by the
bounded information that it is both initial and final). As before, we remove
the submachines which are never called in $\overline{\mathscr{U}}$. Observe
that we have created a machine with recursion height $k{-}1$ (because
algorithm 4 in algorithm 4 prevents from calling a $k$-th layer).

Let us justify that each
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
can indeed be implemented by a two-way transducer. First, let us observe that
since $\mathcal{F}$ has bounded height, the number $N$ of slices given in
algorithm 4 of algorithm 4 is bounded. Furthermore, we claim that the first
and last positions of each $\rho^{\prime}_{j}$ belong to a given set of
bounded size, which can be detected a lookaround which has access to $i$. For
the $\rho^{\prime}_{j}$ whose positions are in
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$, this is clear since
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}|$ is bounded (because the frontier of any node is bounded). For
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$ we use lemma 4, which implies that this set is a bounded union of
intervals. The last case is very similar.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

###### Lemma 4

Let $1\leqslant i\leqslant|u|$,
$\mathfrak{t}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
and $\mathfrak{t}_{1}$ (resp. $\mathfrak{t}_{2}$) be its immediate left (resp.
right) sibling (they exist whenever
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}$,
i.e. here $\mathfrak{t}\neq\mathcal{F}$). Then:

$\displaystyle{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}=[\min({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{1})):\max({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{2}))]\smallsetminus\\{{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{1}),{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}),{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{2})\\}.$

This analysis justifies why each $\rho^{\prime}_{j}$ can be encoded in a
bounded way. Now, we show how to implement the inlinings while using $i$ as
the current position:

  * •

if
$i_{1},\dots,i_{n}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$, then $n$ is bounded (because
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}|$ is bounded). We can thus inline
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}{\rho^{\prime}_{j}}}}{}{}\leavevmode\nobreak\
(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$
while staying in position $i$. However, when $\mathscr{T}^{\prime}$ calls some
$\mathscr{L}^{\prime\prime}$ (of head $\mathscr{T}^{\prime\prime}$) on
position $i_{\ell}$, we would need to call
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime\prime}{{\textsf{-along-}}}\rho^{\prime\prime}}}{}{}(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{\ell}{}{})$
(where $\rho^{\prime\prime}$ is the accepting run of
$\mathscr{T}^{\prime\prime}$ along
${\vdash}u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{\ell}{}{}{\dashv}$).
But we cannot do this operation, since we are in position $i$ and not in
$i_{\ell}$. The solution is that the inlined code calls
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{normal-}}}\mathscr{T}^{\prime\prime}{{\textsf{-along-}}}\rho^{\prime\prime}{{\textsf{-pebble-}}}i_{\ell}}}{}{}(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$
instead, which simulates an accepting run $\rho^{\prime\prime}$ of
$\mathscr{T}$ on
$u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{\ell}{}{}$,
even if its input is
$u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}$.
Note that $i_{\ell}$ can be represented as a bounded information and recovered
by a lookaround given
$u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{}$
as input, since $i$ observes $i_{\ell}$;

  * •

if
$i_{1},\dots,i_{n}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$, then the nodes
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{1}),\dots,{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{n})$
are “below”
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
in $\mathcal{F}$ (see fig. 5). We inline
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}{\rho^{\prime}_{j}}}}{}{}\leavevmode\nobreak\
(u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i{}{})$,
by moving along $i_{1},\dots,i_{n}$ as $\rho^{\prime}_{j}$ does. We can keep
track of the height of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
above the current
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{\ell})$
(it is a bounded information). With the lookaround, we can detect the end of
$\rho^{\prime}_{j}$, and go back to position $i$.

It remains to justify that $\overline{\mathscr{U}}$ is correct. For this, we
only need to show that when it reaches algorithm 4 in algorithm 4, the output
of $\mathscr{T}^{\prime}$ along $\rho^{\prime}_{j}$ is indeed empty.
Otherwise, the conditions of lemma 5 would hold (since we never execute two
successive recursive calls in dependent positions). It provides a
contradiction.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

######  Lemma 5 (Key lemma)

Let $u\in A^{*}$ and
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$.
Assume that there exists a sequence $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of
submachines of $\mathscr{U}$ and a sequence of positions $1\leqslant
i_{1},\dots,i_{k}\leqslant|u|$ such that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$;

  * •

$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{1}}^{u}{}{}(i_{1})|_{\mathscr{T}_{2}}\neq
0$ and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{k-1}{}{}}{}{}(i_{k})\neq\varepsilon$;

  * •

for all $2\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{j-1}{}{}}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$;

  * •

for all $1\leqslant j\leqslant k{-}1$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j+1})$
are independent;

Then $\mathscr{U}$ is pumpable.

######  Proof (idea)

As for lemma 2, the key observation is that pumpability follows as soon as the
nodes
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
are two by two independent. Furthermore, this condition can be obtained by
duplicating some nodes in $\mathcal{F}$.

##  7 Making the two last pebbles visible

We can define a similar model to that of last $k$-pebble transducer, which
sees the two last calling positions instead of only the previous one. Let us
name this model a last-last $k$-pebble transducer. A very natural question is
to know whether we can show an analog of theorem 3.1 for these machines.

\begin{picture}(0.0,0.0)\put(0.0,1.1){\put(0.0,0.0){\put(-0.05,-1.18){}}}\end{picture}

Note that for $k=1,2$ and $3$, a last-last $k$-pebble transducer is exactly
the same as a $k$-pebble transducer. Hence the function
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{inner-
squaring}}}{}{}$ of section 1.0.2 is such that
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{inner-
squaring}}}{}{}(u)|=\mathcal{O}(|u|^{2})$ and can be computed by a last-last
$3$-pebble transducer, but it cannot be computed by a last-last $2$-pebble
transducer. It follows that the connection between minimal recursion height
and growth of the output fails. However, this result is somehow artificial.
Indeed, a last-last $2$-pebble transducer is a degenerate case, since it can
only see one last pebble. More interestingly, we show that the connection
fails for arbitrary heights.

###### Theorem 7.1

For all $k\geqslant 2$, there exists a function $f:A^{*}\rightarrow B^{*}$
such that $|f(u)|=\mathcal{O}(|u|^{2})$ and that can be computed by a last-
last $(2k{+}1)$-pebble transducer, but not by a last-last $2k$-pebble
transducer.

######  Proof (idea)

We re-use a counterexample introduced by Bojańczyk in [2] to show a similar
failure result for the model of $k$-pebble transducers.

##  8 Outlook

This paper somehow settles the discussion concerning the variants of pebble
transducers for which the minimal recursion height only depends on the growth
of the output. As soon as two marks are visible, the combinatorics of the
output also has to be taken into account, hence minimizing the recursion
height in this context seems to be out of reach (e.g. for last-last pebble
transducers).

As observed in [13], one can extend last pebble transducers by allowing the
recursion height to be unbounded (in the spirit of marble transducers [9]).
This model enables to produce outputs whose size grows exponentially in the
size of the input. A natural question is to know whether a function computed
by this model, but whose output size is polynomial, can in fact be computed by
a recursion stack of bounded height (i.e. a last $k$-pebble transducer).

####  8.0.1 Acknowledgements.

The author is grateful to Tito Nguyên for suggesting the study of the
recursion height for last pebble transducers.

## References

  * [1] Bojańczyk, M.: Polyregular functions. arXiv preprint arXiv:1810.08760 (2018)
  * [2] Bojańczyk, M.: The growth rate of polyregular functions (2022)
  * [3] Bojańczyk, M.: Transducers of polynomial growth. In: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 1–27 (2022)
  * [4] Bojańczyk, M., Kiefer, S., Lhote, N.: String-to-string interpretations with polynomial-size output. In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (2019)
  * [5] Chytil, M.P., Jákl, V.: Serial composition of 2-way finite-state transducers and simple programs on strings. In: 4th International Colloquium on Automata, Languages, and Programming, ICALP 1977. pp. 135–147. Springer (1977)
  * [6] Colcombet, T.: Green’s relations and their use in automata theory. In: International Conference on Language and Automata Theory and Applications. pp. 1–21. Springer (2011)
  * [7] Dave, V., Gastin, P., Krishna, S.N.: Regular transducer expressions for regular transformations. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 315–324. ACM (2018)
  * [8] Douéneau-Tabot, G.: Pebble transducers with unary output. In: 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021 (2021)
  * [9] Douéneau-Tabot, G., Filiot, E., Gastin, P.: Register transducers are marble transducers. In: 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 (2020)
  * [10] Douéneau-Tabot, G.: Hiding pebbles when the output alphabet is unary. In: 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022 (2022)
  * [11] Engelfriet, J.: Two-way pebble transducers for partial functions and their composition. Acta Informatica 52(7-8), 559–571 (2015)
  * [12] Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL) 2(2), 216–254 (2001)
  * [13] Engelfriet, J., Hoogeboom, H.J., Samwel, B.: Xml transformation by tree-walking transducers with invisible pebbles. In: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 63–72. ACM (2007)
  * [14] Gurari, E.M.: The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal on Computing 11(3), 448–452 (1982)
  * [15] Hopcroft, J.E., Ullman, J.D.: An approach to a unified theory of automata. The Bell System Technical Journal 46(8), 1793–1829 (1967)
  * [16] Nguyên, L.T.D., Noûs, C., Pradic, P.: Comparison-free polyregular functions. In: 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 (2021)
  * [17] Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM Journal of Research and Development 3(2), 198–200 (1959)
  * [18] Simon, I.: Factorization forests of finite height. Theor. Comput. Sci. 72(1), 65–94 (1990). https://doi.org/10.1016/0304-3975(90)90047-L, https://doi.org/10.1016/0304-3975(90)90047-L

##  Appendix 0.A Omitted proofs of section 5

###  0.A.1 Proof of lemma 1

Let $w_{i}\in A^{*}$ be such that $\mu(w_{i})=\ell_{i}$, $w^{\prime}_{i}\in
A^{*}$ be such that $\mu(w^{\prime}_{i})=r_{i}$ and $u_{i}\coloneqq
w_{i}a_{i}w^{\prime}_{i}$, for $1\leqslant i\leqslant k$. Let
$v_{0},\dots,v_{k}\in A^{*}$ such that $\mu(v_{i})=m_{i}$ for all $1\leqslant
i\leqslant k$. Let $f_{i}$ be the function computed by $\mathscr{T}_{i}$ for
all $1\leqslant i\leqslant k$.

It is easy to see that $|f_{k}(v_{0}u_{1}^{X}\cdots
u_{k}^{X}v_{k})|\geqslant(X{-}2)$. Indeed, $\mathscr{T}_{k}$ must produce at
least one letter when reading the letter $a_{\sigma(k)}$ of each factor
$u_{\sigma(k)}$ (with possibly an exception for the borders, hence the
${-}2$). We then show by induction on $k\geqslant i\geqslant 1$ that
$|f_{i}(v_{0}u_{1}^{X}\cdots u_{k}^{X}v_{k})|\geqslant(X{-}2)^{k-i+1}$. The
upper bound follows since $\mathscr{B}$ is a blind $k$-pebble transducer, thus
$|f(v_{0}u_{1}^{X}\cdots u_{k}^{X}v_{k})|=\theta(X^{k})$.

###  0.A.2 Additional arguments in section 5.2

We first justify that the construction of $\overline{\mathscr{U}}$ in section
5.2 indeed reduces the recursion height of $\mathscr{U}$ by $1$. This
statement was claimed on algorithm 2.

###### Claim

The machine $\overline{\mathscr{U}}$ described in section 5.2 has recursion
height $k{-}1$.

###### Proof

Recall that the recursion height corresponds to the number of nested Call
instructions, plus $1$ (due to the head). We first show by (decreasing)
induction on $1\leqslant\ell\leqslant k$ that if $\mathscr{T}$ is the root of
a subtree of $\mathscr{U}$ whose recursion height is $1\leqslant\ell\leqslant
k$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}}}{}{}$
has recursion height $\ell$ as well.
Then, we show by (decreasing) induction on $1\leqslant\ell\leqslant k$ that if
$\mathscr{T}$ is the root of a subtree of $\mathscr{U}$ whose recursion height
is $\ell$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
has recursion height $\ell{-}1$. Indeed, the base case $\ell=2$ is justified
by algorithm 2 in algorithm 2 (there are no calls since we inline all the
computations). For $\ell>2$ the function
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
inlines
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}}}{}{}$
of recursion height $\ell{-}1$ and makes a recursive call to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}^{\prime}}}{}{}$
whose height is $\ell{-}2$ by induction hypothesis.
The result follows since the head of $\mathscr{U}$ is the root of the tree
describing $\mathscr{U}$, which has recursion height $k$ by definition of a
blind $k$-pebble transducer.

Since we have justified in the main paper how each function of
$\overline{\mathscr{U}}$ can be implemented by a two-way transducer, then
$\overline{\mathscr{U}}$ is indeed a blind $(k{-}1)$-pebble transducer. Now,
we justify a claim of • ‣ section 5.2, that is used to show that the output in
algorithm 2 of algorithm 2 must be bounded.

###### Claim

Assume that, in the execution of $\overline{\mathscr{U}}$ on input $u\in
A^{*}$, we reach algorithm 2 in algorithm 2 and that
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}^{\prime}}^{u}{}{}(i^{\prime})\neq\varepsilon$
for
$i^{\prime}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$.
Then the conditions of lemma 2 hold, that is there exists
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$,
a sequence $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of submachines of
$\mathscr{U}$ and a sequence of positions $1\leqslant
i_{1},\dots,i_{k}\leqslant|u|$ such that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$;

  * •

for all $1\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$ and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}^{u}{}{}(i_{k})\neq\varepsilon$;

  * •

for all $1\leqslant j\leqslant k$,
$i_{j}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
(i.e.
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}$).

###### Proof

Let $\mathscr{T}$ be a submachine of $\mathscr{U}$ which is not a leaf (i.e.
it labels the root of a subtree of height $>1$). We claim that for
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}(u)$
to be called when executing $\overline{\mathscr{U}}$ on input $u\in A^{*}$,
there must exist a sequence $\mathscr{T}_{1},\dots,\mathscr{T}_{\ell}$ of
submachines of $\mathscr{U}$ and a sequence of positions $1\leqslant
i_{1},\dots,i_{\ell-1}\leqslant|u|$ such that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$ and
$\mathscr{T}_{\ell}=\mathscr{T}$;

  * •

for all $1\leqslant j\leqslant\ell{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$;

  * •

for all $1\leqslant j\leqslant\ell{-}1$,
$i_{j}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$
where
$\mathcal{F}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$.

This result can be checked by induction. Intuitively, it means that to
systematically avoid inlinings, we have to make recursive calls in a sequence
of positions which are never in the frontier on the root.
Finally, by considering $\mathscr{T}$ the root of a subtree of height $2$, we
see that the conditions of lemma 2 must hold if we reach we reach algorithm 2
in
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}}}{}{}$
and if
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}^{\prime}}^{u}{}{}(i^{\prime})\neq\varepsilon$
for
$i^{\prime}\not\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathcal{F})$.

To conclude about the omitted proofs in section 5.2, it remains to show lemma
2. This is the purpose of section 0.A.3.

###  0.A.3 Proof of lemma 2

Assume that the conditions of lemma 2 hold and let
$\mathfrak{t}_{j}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
for all $1\leqslant j\leqslant k$. If the $\mathfrak{t}_{j}$ are two by two
independent, then each $\mathfrak{t}_{j}$ is surrounded by two nodes whose
frontiers cannot contain a position $i_{j^{\prime}}$ for some $1\leqslant
j^{\prime}\leqslant k$. The image of the factor of $u$ which is below these
nodes provides an idempotent $e_{j}$. It can easily be concluded that
$\mathscr{U}$ is pumpable (see also [10, Lemma E.5]).

$\mathfrak{t}_{\ell_{2}}$$\mathfrak{t}_{\ell_{1}}$ (a) Original $\mu$-forest
$\mathcal{F}$

$\mathfrak{t}^{\prime}_{\ell_{2}}$$\mathfrak{t}^{\prime}_{\ell_{1}}$ (b)
Modified $\mu$-forest $\mathcal{F}^{\prime}$

Figure 9:  Duplicating a subtree in $\mathcal{F}$ so that
$\mathfrak{t}^{\prime}_{\ell_{1}}$ and $\mathfrak{t}^{\prime}_{\ell_{2}}$ are
not dependent.

Now, we suppose that the $\mathfrak{t}_{j}$ are not necessarily two by two
independent. Let us show how to make the number of dependent couples of
$(\mathfrak{t}_{j_{1}},\mathfrak{t}_{j_{2}})$ decrease strictly, while
preserving the properties of lemma 2. Indeed, repeating this process will
enable us to make all the nodes two by two independent. Assume that
$\mathfrak{t}_{\ell_{1}}$ observes $\mathfrak{t}_{\ell_{2}}$ for some
$1\leqslant\ell_{1}\neq\ell_{2}\leqslant k$. To simplify the proof, we assume
that $\mathfrak{t}_{\ell_{2}}$ is an ancestor of $\mathfrak{t}_{\ell_{1}}$
(the case of the immediate sibling of an ancestor is similar). Let
$\mathcal{F}^{\prime}$ be $\mathcal{F}$ in which the subtree
$\mathfrak{t}_{\ell_{2}}$ has been copied $3$ times (since
$\mathfrak{t}_{\ell_{2}}$ is an iterable node, then $\mathcal{F}^{\prime}$
still a $\mu$-forest), see fig. 9. We define for $1\leqslant j\leqslant k$ the
nodes
$\mathfrak{t}^{\prime}_{j}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}^{\prime}}{}{}$
as follows:

  * •

if $j=\ell_{2}$, then $\mathfrak{t}^{\prime}_{j}$ is (the root of) the third
copy of $\mathfrak{t}_{j}$;

  * •

else if $j$ is such that $\mathfrak{t}_{j}$ was a descendant of
$\mathfrak{t}_{\ell_{2}}$ (including $\mathfrak{t}_{\ell_{1}}$), then we let
$\mathfrak{t}^{\prime}_{j}$ be the corresponding node in the first copy of
$\mathfrak{t}_{j}$;

  * •

else $\mathfrak{t}_{j}$ was in the rest of $\mathcal{F}$, and we let
$\mathfrak{t}^{\prime}_{j}$ be the corresponding node in
$\mathcal{F}^{\prime}$.

Observe that now, $\mathfrak{t}^{\prime}_{\ell_{1}}$ and
$\mathfrak{t}^{\prime}_{\ell_{2}}$ are not dependent. Furthermore if
$\mathfrak{t}_{j_{1}}$ and $\mathfrak{t}_{j_{2}}$ were independent, then
$\mathfrak{t}^{\prime}_{j_{1}}$ and $\mathfrak{t}^{\prime}_{j_{2}}$ are also
independent. Let $u^{\prime}\in A^{*}$ be the word such that
$\mathcal{F}^{\prime}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u^{\prime})$.
We also define $1\leqslant
i^{\prime}_{1},\dots,i^{\prime}_{k}\leqslant|u^{\prime}|$ as the positions
which correspond to the former $1\leqslant i_{1},\dots,i_{k}\leqslant|u|$ in
the frontiers of $\mathfrak{t}_{1}^{\prime},\dots,\mathfrak{t}^{\prime}_{k}$
in the new $\mu$-forest $\mathcal{F}^{\prime}$. The conditions of lemma 2
still hold, because
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u}{}{}(i_{j})={\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u^{\prime}}{}{}(i^{\prime}_{j})$
(indeed, we have only duplicated an iterable node, which does neither modify
the context around $i^{\prime}_{j}$ nor its crossing sequence).

##  Appendix 0.B Omitted proofs of section 6

###  0.B.1 Proof of lemma 3

The proof is similar to that of lemma 1. Let $w_{i}\in A^{*}$ be such that
$\mu(w_{i})=\ell_{i}$, $w^{\prime}_{i}\in A^{*}$ be such that
$\mu(w^{\prime}_{i})=r_{i}$, $u_{i}\coloneqq w_{i}a_{i}w^{\prime}_{i}$ and
$\underline{u_{i}}\coloneqq w_{i}\underline{a_{i}}w^{\prime}_{i}$, for
$1\leqslant i\leqslant k$. Let $v_{0},\dots,v_{k}\in A^{*}$ such that
$\mu(v_{i})=m_{i}$ for all $1\leqslant i\leqslant k$. Let $f_{i}$ be the
function computed by $\mathscr{T}_{i}$ for all $1\leqslant i\leqslant k$.

To simply the proof, we assume that $\sigma:[1{:}k]\rightarrow[1{:}k]$ is the
identity function. We then observe that for all $X\geqslant 2$, for all
$1\leqslant Y\leqslant X{-}2$:

$\displaystyle f_{k}(v_{0}u_{1}^{X}\cdots
v_{k-2}(u_{k-1}^{Y}\underline{u_{k-1}}u_{k-1}^{X-Y-1})v_{k-1}u_{k}^{X})\geqslant(X-2).$

Observe that the use of $u_{k-1}^{Y}\underline{u_{k-1}}u_{k-1}^{X-Y-1}$ means
that the result holds independently from the factor in which the call (i.e.
the mark) to $\mathscr{T}_{k}$ was done. Finally, we conclude by induction in
a similar way to lemma 1.

###  0.B.2 Additional arguments in section 6.2

We first justify that the construction of $\overline{\mathscr{U}}$ in section
5.2 indeed reduces the recursion height of $\mathscr{U}$ by $1$. This
statement was claimed on section 6.2.

###### Claim

The machine $\overline{\mathscr{U}}$ described in section 6.2 has recursion
height $k{-}1$.

###### Proof

Recall that the recursion height corresponds to the number of nested Call
instructions, plus $1$ (due to the head). We first show by (decreasing)
induction on $1\leqslant\ell\leqslant k$ that if $\mathscr{T}$ is the root of
a subtree of $\mathscr{U}$ whose recursion height is $1\leqslant\ell\leqslant
k$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
has recursion height $\ell$ as well.
Then, we show by (decreasing) induction on $2\leqslant\ell\leqslant k$ that if
$\mathscr{T}$ is the root of a subtree of $\mathscr{U}$ whose recursion height
is $\ell$, then
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
has recursion height $\ell{-}1$. Indeed, the base case $\ell=2$ is justified
by algorithm 4 in algorithm 4 (there are no calls). For $\ell>2$ the function
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
inlines some
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{old-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho^{\prime}_{j}}}{}{}$
of recursion height $\ell{-}1$ and makes recursive calls to
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}^{\prime}{{\textsf{-along-}}}\rho_{j}}}{}{}$
whose height is $\ell{-}2$ by induction hypothesis.
The result follows since the head of $\mathscr{U}$ is the root of the tree
describing $\mathscr{U}$, which has recursion height $k$ by definition of a
last $k$-pebble transducer.

Now, let us justify a claim of lemma 4, that is used to show that the output
of algorithm 4 in algorithm 4 is indeed empty.

###### Claim

Assume that, in the execution of $\overline{\mathscr{U}}$ on input $u\in
A^{*}$, we reach algorithm 4 in algorithm 4 and that the output of
$\mathscr{T}^{\prime}$ along $\rho^{\prime}_{j}$ is not empty. Then the
conditions of lemma 5 hold, that is there exists
$\mathcal{F}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u)$,
a sequence $\mathscr{T}_{1},\dots,\mathscr{T}_{k}$ of submachines of
$\mathscr{U}$ and a sequence of positions $1\leqslant
i_{1},\dots,i_{k}\leqslant|u|$ such that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$;

  * •

$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{1}}^{u}{}{}(i_{1})|_{\mathscr{T}_{2}}\neq
0$ and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{k}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{k-1}{}{}}{}{}(i_{k})\neq\varepsilon$;

  * •

for all $2\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{j-1}{}{}}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$;

  * •

for all $1\leqslant j\leqslant k{-}1$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j+1})$
are independent;

###### Proof

Let $\mathscr{T}$ be a submachine of $\mathscr{U}$ which is neither a leaf
(i.e. it labels the root of a subtree of height $>1$) nor the head of
$\mathscr{U}$ (i.e. not the root of $\mathscr{U}$). We claim that for
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}\leavevmode\nobreak\
(v)$ to be called whithin the execution of $\overline{\mathscr{U}}$ on input
$u\in A^{*}$, there must exist a sequence
$\mathscr{T}_{1},\dots,\mathscr{T}_{\ell}$ of submachines of $\mathscr{U}$ and
a sequence of positions $1\leqslant i_{1},\dots,i_{\ell-1}\leqslant|u|$ such
that:

  * •

$\mathscr{T}_{1}$ is the head of $\mathscr{U}$;

  * •

$v=u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{\ell-1}{}{}$;

  * •

$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{1}}^{u}{}{}(i_{1})|_{\mathscr{T}_{2}}\neq
0$ and for all $2\leqslant j\leqslant k{-}1$,
$|{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{j-1}{}{}}{}{}(i_{j})|_{\mathscr{T}_{j+1}}\neq
0$;

  * •

for all $1\leqslant j\leqslant\ell{-}2$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j+1})$
are independent, where we define
$\mathcal{F}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{forest}}}_{\mu}{}{}(u)$;

  * •

for all $(i,q)\in\rho$,
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{\ell-1})$
and
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
are independent

This result can be checked by induction. Intuitively, the two crucial last
point follows from the fact that we only make recursive calls in portions of
runs whose positions are not dependent on the calling position.
Finally, by considering $\mathscr{T}$ the root of a subtree of height $2$, we
see that the conditions of lemma 5 must hold if we reach algorithm 4 in some
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{{\textsf{accelerate-}}}\mathscr{T}{{\textsf{-along-}}}\rho}}{}{}$
called in $\overline{\mathscr{U}}$ and if the output of $\mathscr{T}^{\prime}$
along $\rho^{\prime}_{j}$ is not empty.

To conclude about the omitted proofs in section 6.2, it remains to show lemmas
5 and 4. This is the purpose of sections 0.B.4 and 0.B.3.

###  0.B.3 Proof of lemma 4

Let $1\leqslant i\leqslant|u|$,
$\mathfrak{t}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i)$
and $\mathfrak{t}_{1}$ (resp. $\mathfrak{t}_{2}$) be its immediate left (resp.
right) sibling (they exist whenever
$\mathfrak{t}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Iter}}}^{\mathcal{F}}{}{}$,
i.e. here $\mathfrak{t}\neq\mathcal{F}$). We show that:

$\displaystyle{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}=[\min({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{1})):\max({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{2}))]\smallsetminus\\{{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{1}),{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}),{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{2})\\}.$

Let us assume that $\mathfrak{t}_{1}$ and $\mathfrak{t}_{2}$ are iterable
nodes of $\mathcal{F}$ (the other cases are similar). By considering the
forest of fig. 5, it can be noted that
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}$ is the interval
$[\min({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{1})):\max({\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Fr}}}^{\mathcal{F}}{}{}(\mathfrak{t}_{2}))]$.
We conclude since $\mathfrak{t},\mathfrak{t}_{1}$ and $\mathfrak{t}_{2}$ are
the only iterable nodes that both observe $\mathfrak{t}$ and that
$\mathfrak{t}$ observes.

Therefore
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\downarrow
i}{}{}\smallsetminus{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\uparrow
i}{}{}$ is the union of a bounded number of intervals (since the frontiers
have bounded size). It is easy to observed that the “borders” of these
intervals can easily be recovered by a lookaround, if $\mathfrak{t}$ (or $i$)
is given.

###  0.B.4 Proof of lemma 5

The proof is similar to that of lemma 2. The goal is to show that the for
$1\leqslant j\leqslant k$, the
$\mathfrak{t}_{j}\coloneqq{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{origin}}}^{\mathcal{F}}{}{}(i_{j})$
can be chosen two by two independent (in the hypothesis, it is only assumed
for the consecutive pairs $(\mathfrak{t}_{j},\mathfrak{t}_{j+1})$).

For this, we show once more how to make the number of dependent nodes decrease
strictly, while preserving the properties of lemma 5. Assume that
$\mathfrak{t}_{\ell_{1}}$ observes $\mathfrak{t}_{\ell_{2}}$ for some
$1\leqslant\ell_{1}\neq\ell_{2}\leqslant k$ (note that $\ell_{1}$ and
$\ell_{2}$ are not consecutive). To simplify the proof, we assume that
$\mathfrak{t}_{\ell_{2}}$ is an ancestor of $\mathfrak{t}_{\ell_{1}}$ (the
case of the immediate sibling of an ancestor is similar). We build
$\mathcal{F}^{\prime}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Forests}}}_{\mu}{}{}(u^{\prime})$
as in the proof of lemma 2 (see fig. 9), and define the new nodes
$\mathfrak{t}^{\prime}_{1},\dots,\mathfrak{t}^{\prime}_{k}\in{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\textsf{Nodes}}}^{\mathcal{F}^{\prime}}{}{}$
in the same way. We also define $1\leqslant
i^{\prime}_{1},\dots,i^{\prime}_{k}\leqslant|u^{\prime}|$ as the positions
which correspond to the former $1\leqslant i_{1},\dots,i_{k}\leqslant|u|$
adapted to the new nodes
$\mathfrak{t}^{\prime}_{1},\dots,\mathfrak{t}^{\prime}_{k}$.

Now, we justify that
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i_{j-1}{}{}}{}{}(i_{j})={\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{prod}}}}}_{\mathscr{T}_{j}}^{u^{\prime}{\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\bullet}i^{\prime}_{j-1}{}{}}{}{}(i^{\prime}_{j})$
for all $2\leqslant j\leqslant k$. This is the only difference with the proof
of of lemma 2 that we need to treat:

  * •

if both $i_{j-1}$ and $i_{j}$ belong to the subtree rooted in $i_{\ell_{2}}$,
then $j\neq\ell_{2}$ (since otherwise $i_{j}$ and $i_{j-1}$ would be
dependent) and similarly $j{-}1\neq\ell_{2}$. The result holds because we only
iterate an iterable node;

  * •

if both $i_{j-1}$ and $i_{j}$ do not belong to this subtree, the argument is
similar;

  * •

if $i_{j-1}$ is in the subtree but not $i_{j}$ (the converse is similar), we
use the fact that these two nodes are independent. Indeed, it implies that
$i_{j}$ cannot be “below” an immediate sibling of $\mathfrak{t}_{\ell_{2}}$.
Hence duplicating this iterable node will not change the monoid value between
positions $i_{j-1}$ and $i_{j}$.

##  Appendix 0.C Proof of theorem 7.1

Let $A$ be an alphabet and $k\geqslant 1$. We define the tree language
$T^{k}_{A}$ as the set of trees such that all root-to-leaf branches have
exactly $k$ nodes (hence the tree has height $k$), whose leaves are labelled
by words of $A^{*}$ and whose inner nodes have no labels. As observed for
factorization forests, $T^{k}_{A}$ can be seen as a regular word language over
the alphabet ${\widehat{A}}\coloneqq A\uplus\\{\langle,\rangle\\}$. Given such
a tree, we say that the root has _height_ $1$, its children height $2$, etc.
and the leaves have height $k$.

Now, we describe for all $k\geqslant 1$ a function
$\immediate\immediate\immediate\mathbf{{\color[rgb]{0.3671875,0.5078125,0.67578125}\definecolor[named]{pgfstrokecolor}{rgb}{0.3671875,0.5078125,0.67578125}{{\textsf{{zebra}}}}}}^{k}{}{}:T^{k+1}_{A}\rightarrow
T^{2k+1}_{A\uplus\\#}$ which goes from words to words (i.e. it works on the
word representation of the trees). This function was introduced by Bojańczyk
in [2]. Intuitively, it produces a tree whose leaves labels are tuples $u\\#v$
for $u,v$ labels of the original tree, but the ordering of these tuples is
very specific.

Let us first describe the function
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{zebra}}}}}^{1}{}{}$.
It takes as input a tree of height $2$ of shape $\langle\langle
u_{1}\rangle,\langle u_{2}\rangle,\cdots,\langle u_{n}\rangle\rangle$ and it
produces a tree of height $3$ whose $i$-th child of the root is
$\langle\langle u_{i}\\#u_{1}\rangle,\cdots,\langle
u_{i}\\#u_{n}\rangle\rangle$ (i.e. the tuples are ordered lexicographically).
This function be implemented by a $3$-pebble transducer (i.e. a last-last
$3$-pebble transducer) which uses its two first pebble to see which leaves
have to be produced, and the last layer to indeed output these leaves. Observe
that
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}{{\textsf{{zebra}}}}}^{1}{}{}$
can be seen as a variant of
${\color[rgb]{0.384375,0.40625,0.45625}\definecolor[named]{pgfstrokecolor}{rgb}{0.384375,0.40625,0.45625}\operatorname{\mathsf{unmarked-
square}}}{}{}$ (see example 2).

Now, the function