

\section{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 \reintro{deterministic two-way transducer} is a two-way automaton
with outputs. This model describes the class of \reintro{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~\cite{chytil1977serial}, equivalence
with logical transductions~\cite{engelfriet2001mso} or
regular expressions~\cite{dave2018regular}, decidable
equivalence problem~\cite{gurari1982equivalence}, etc.

\subsubsection{Pebble transducers and polyregular functions.} 
\kl{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 \kl{two-way transducers}.
In particular, the model of \intro{$k$-pebble transducer} has been studied
for a long time \cite{engelfriet2007xml}. For $k=1$, a \kl{$1$-pebble transducer}
is just a \kl{two-way transducer}. For $k \ge 2$, a \kl{$k$-pebble transducer}
is a \kl{two-way transducer} that, when 
on any position $i$ of its input word, can call
a \kl{$(k{-}1)$-pebble transducer}. The latter takes as input
the original input where position $i$ is marked by a ``pebble''.
The main \kl{two-way transducer} then outputs the concatenation
of all the outputs produced along its calls.
The intuitive behavior of a \kl{$3$-pebble transducer} is
depicted in \cref{fig:pebble}. It can be seen
as recursive program whose recursion stack has  height $3$.
The class of functions computed
by \kl{pebble transducers} is known as \intro{polyregular functions}.
It has been intensively studied due to its properties such as
closure under composition~\cite{engelfriet2015two},
equivalence with logical interpretations~\cite{bojanczyk2019string}, etc.


\vspace*{0.4cm}

\input{parts/fig-pebble-transducer.tex}



\subsubsection{Optimization of pebble transducers.} Given a \kl{$k$-pebble transducer}
computing a function $f$, a very natural problem
is to compute the least possible $1 \le \ell \le k$ such that $f$
can be computed by an \kl{$\ell$-pebble transducer}. Furthermore,
we can be interested in effectively building an
\kl{$\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.

\AP
It is easy to observe that if $f$ is computed by
a \kl{$k$-pebble transducer}, then $|f(u)| = \mc{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 \kl{$\ell$-pebble transducer}) was exactly
the least possible $\ell$ such that $|f(u)| = \mc{O}(|u|^{\ell})$. However,
Boja\'nczyk recently disproved this statement in  \cite[Theorem 6.3]{bojanczyk2022transducers}:
the function \label{page:isq}$\intro*\isqK : u_1 \# \cdots \# u_n 
\mapsto (u_1\#)^n \cdots (u_n\#)^n$ can be computed by 
a \kl{$3$-pebble transducer} and is such that
$|\isqK(u)| = \mc{O}(|u|^2)$, but it cannot be computed by
a \kl{$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.




\subsubsection{Optimization of blind pebble transducers.}  \AP
A subclass of \kl{pebble transducers}, named 
\reintro{blind pebble transducers}, was recently
introduced in~\cite{nous2020comparison}.
A \kl{blind $k$-pebble transducer} is somehow
a \kl{$k$-pebble transducer}, with the difference
that the positions are no longer marked when
making recursive calls. The behavior of
a \kl{blind $3$-pebble transducer} is depicted in \cref{fig:3-blind-transducer}.
The  class of functions computed by \kl{blind pebble transducers}
is strictly included in \kl{polyregular functions}
\cite{doueneau2022hiding,nous2020comparison}.
The main result of \cite{nous2020comparison} shows that 
for \kl{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 \kl{blind $k$-pebble transducer}, then
the least possible $1 \le \ell \le k$ such that $f$ can be computed by
an \kl{blind $\ell$-pebble transducer} is the least possible $\ell$ such that
 $|f(u)| = \mc{O}(|u|^{\ell})$.




\input{parts/fig-blind-transducer.tex}

\vspace*{-0.7cm}



\subsubsection{Contributions.} \AP In this paper, we first
give a new proof of the connection between minimal recursion height
and growth of the output for \kl{blind pebble transducers}. Furthermore,
our proof provides an algorithm that, given a function computed
by a \kl{blind $k$-pebble transducer}, builds
a \kl{blind $\ell$-pebble transducer} which computes it,
for the least possible $1 \le \ell \le k$.
This effective result is not claimed in \cite{nous2020comparison},
and our proof techniques significantly differ  from  
theirs. Indeed, we make a heavy use of \reintro{factorization forests},
which have already been used as a powerful tool
in the study of \kl{pebble transducers}
\cite{bojanczyk2022growth,doueneau2021pebble,doueneau2022hiding}.







\AP
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 \reintro{last pebble transducers}
(introduced in \cite{engelfriet2007xml}).
Intuitively, a \kl{last $k$-pebble transducer} is a 
\kl{$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 \kl{last $3$-pebble transducer}
is depicted in \cref{fig:3-last-transducer}. Observe that
a \kl{blind $k$-pebble transducer} is a restricted 
version of a \kl{last $k$-pebble transducer}.
Formally, we show that if $f$ is computed by a
\kl{last $k$-pebble transducer}, then the least possible $\ell$ such that 
$f$ can be computed by a \kl{last $\ell$-pebble transducer}
is the least possible $\ell$ such that $|f(u)| = \mc{O}(|u|^{\ell})$.
Furthermore, our proof gives an algorithm that
effectively builds a \kl{last $\ell$-pebble transducer}
computing $f$.



\input{parts/fig-last-transducer.tex}


\vspace*{-0.5cm}

\AP
As a third theorem, we show that our
result for \kl{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
\reintro{last-last $k$-pebble transducers},
which extends \kl{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 \ge 1$, there exists
a function $f$ such that $|f(u)| = \mc{O}(|u|^2)$
and that is computed by a 
\kl{last-last $(2k{+}1)$-pebble transducer},
but cannot be computed by a \kl{last-last $2k$-pebble transducer}.
In this setting, minimizing the recursion height
seems to be out of reach.

\vspace*{-0.25cm}


\subsubsection{Outline.} \AP We introduce
\kl{two-way transducers} in \cref{sec:two-way}.
In \cref{sec:blind-last} we describe \kl{blind pebble transducers}
and \kl{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
\cref{sec:forests,sec:blind-proof,sec:last-proof}.
In \cref{sec:last-last}, we finally show that these results
cannot be extended to two visible marks.





















\section{Preliminaries on two-way transducers}

\label{sec:two-way}

\AP
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 \mb{N}$ be its length,
and for $1 \le i \le |u|$ let $u[i]$ be its $i$-th letter.
If $ i \le 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$).

\AP
The machines described in this paper are always
\intro{deterministic}.



\begin{definition}
\label{def:det-two-way}
	\AP
	A \intro{two-way transducer}
	$\transfont{T} = (A,B,Q,q_0,F,\delta,\lambda)$ consists of:

	\begin{itemize}
	\item an input alphabet $A$ and an output alphabet $B$;
	\item a finite set of states $Q$
	with $q_0 \in Q$ initial and $F \subseteq Q$ final;
	\item a transition function $\delta: Q \times (A \uplus \{{\lmark}, {{\dashv}}\})
	\rightharpoonup Q \times \{\triangleleft, \triangleright\}$;
	\item an output function $\lambda: Q \times (A \uplus \{{\lmark}, {{\dashv}}\}) \rightharpoonup B^*$ with same domain as $\delta$.

	\end{itemize}

\end{definition}



\AP
The semantics of a \kl{two-way transducer} $\transfont{T}$ is defined
as follows. When given as input a word $u \in A^*$, 
$\transfont{T}$ disposes of a read-only input tape containing
${\lmark} u {{\dashv}}$. The marks ${\lmark}$ 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  ${\lmark} u {{\dashv}}$ is a tuple $(q,i)$
where $q \in Q$ is the current state and $0 \le i \le |u|{+}1$ is the
position of the reading head. The transition relation $\runs{}$
is defined as follows. Given a configuration $(q,i)$,
let $(q',\star):= \delta(q,u[i])$. Then $(q, i) \runs{} (q', i')$ whenever
either $\star = \triangleleft$ and  $i' = i{-}1$ (move left), or $\star = \triangleright$
and $i' = i{+}1$ (move right), with $0 \le i' \le |u|{+}1$. A run is a
sequence of configurations $(q_1,i_1) \runs{} \cdots \runs{} (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).

\AP
The partial function $f: A^* \rightharpoonup B^*$ computed by
the  \kl{two-way transducer}  $\transfont{T}$ is defined as follows:
for $u \in A^*$, if there exists an accepting run on ${\lmark} u {{\dashv}}$,
then it is unique, and $f(u)$ is defined as
$\lambda(q_1,(\lmark u {\dashv})[i_1]) \cdots \lambda(q_n,(\lmark u {\dashv})[i_n]) \in B^*$.
The class of functions computed by
\kl{two-way transducers} is called
\intro{regular functions}.


\begin{example}
Let $\wt{u}$ be the mirror image of $u \in A^*$. Let $\# \not \in A$
be a fresh symbol. The function $\intro*\mapRevK : u_1 \# \cdots \# u_n \mapsto
\wt{u_1} \# \cdots \# \wt{u_n}$
can be computed by a \kl{two-way transducer},
that reads each factor $u_j$ from right to left.
\end{example}

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

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

\begin{definition}
Let $u \in A^*$ and $1 \le i \le |u|$ .
Let $(q_1,i_1) \runs{} \cdots \runs{} (q_n,i_n)$ be the accepting
run of $\transfont{T}$ on $\lmark u {\dashv}$. The \intro{crossing sequence}
of $\transfont{T}$ in $i$, denoted $\intro*\crossK{\transfont{T}}{u}(i)$,
is defined as the sequence $(q_j)_{1 \le j \le n \teq{ and } i_j = i}$.
\end{definition}
\AP
If $\mu : A^* \rightarrow \mb{M}$ is a monoid morphism,
we say that any $m,m' \in \mb{M}$ and $a \in A$ define a \intro{$\mu$-context}
that we denote by $m \cro{a} m'$. It is well-known that the
\kl{crossing sequence} in a position of the input only depends
on the \kl{context} of this position, for a well-chosen monoid,
as claimed in \cref{prop:transition-morphism}
(see e.g. \cite{dave2018regular}).


\begin{proposition}
\label{prop:transition-morphism}
One can build a finite monoid $\mb{T}$ and a
monoid morphism $\mu : A^* \rightarrow \mb{T}$, called the
 \intro(TDT-F){transition morphism} of $\transfont{T}$, such that
for all $u \in A^*$ and $1 \le i \le |u|$,
$\crossK{\transfont{T}}{u}(i)$ only depends on
$\mu(u[1{:}i{-}1]), u[i]$ and $\mu(u[i{+}1{:}|u|])$.\\
Thus we denote it $\reintro*\crossK{\transfont{T}}{}(\mu(u[1{:}i{-}1]) \cro{u[i]} \mu(u[i{+}1{:}|u|])$.
\end{proposition}


Finally,  let us define ``the output produced below position $i$''.

\begin{definition}
Let $u \in A^*$ and $1 \le i \le |u|$ and
$q_1 \cdots q_n \coloneqq \crossK{\transfont{T}}{u}(i)$. We define
the \intro{production} of $\transfont{T}$ in $i$, denoted $\intro*\valK{\transfont{T}}{u}(i)$,
as $\lambda(q_1, u[i]) \cdots \lambda(q_n, u[i])$.
\end{definition}
By \cref{prop:transition-morphism}, it also makes sense to define 
$\reintro*\valK{\transfont{T}}{}(m \cro{a} m') \in B^*$ to be $\valK{\transfont{T}}{u}(i)$ whenever
$m = \mu(u[1{:}i{-}1])$, $m' = \mu(u[i{+}1{:}|u|])$ and $a = u[i]$.






















\section{Blind and last pebble transducers}

\label{sec:blind-last}

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

\begin{definition}[Blind pebble transducer \cite{nous2020comparison}]
\label{def:blind-pebble} \AP
For $k \ge 1$, a \intro{\mbox{blind $k$-pebble} transducer} with input alphabet $A$
and output alphabet $B$ is:
\begin{itemize}
\item if $k =1$, a \kl{two-way transducer} with input alphabet $A$
and output $B$;
\item if $k \ge 2$, a tree $\transfont{T}\tree{\transfont{B}_1, \cdots ,\transfont{B}_p}$ where
$\transfont{B}_1, \dots, \transfont{B}_p$ are \kl{blind $(k{-}1)$-pebble transducers}
with input $A$ and output $B$; and $\transfont{T}$ is a \kl{two-way transducer}
with input $A$ and output alphabet $\{\transfont{B}_1, \dots, \transfont{B}_p\}$.
\end{itemize}
\end{definition}
\AP
The (total) function $f:A^* \rightarrow B^*$
computed by the \kl{blind $k$-pebble transducer} 
of \cref{def:blind-pebble} is built in a recursive fashion, as
follows:
\begin{itemize}
\item for $k=1$, $f$ is the function computed by the \kl{two-way transducer};
\item for $k\ge 2$, let $u \in A^*$ and  $(q_1,i_1) \runs{} \cdots \runs{} (q_n,i_n)$ be the
accepting run of $\transfont{T} = (A,B,Q,q_0,F,\delta,\lambda)$ on $\lmark u {\dashv}$.
For all $1 \le j \le n$, let $f_j : A^* \rightarrow B^*$ be the concatenation of the functions
recursively computed by the sequence $\lambda(q_j,(\lmark u{\dashv})[i_j]) \in \{\transfont{B}_1, \dots, \transfont{B}_p\}^*$.
Then $f(u) \coloneqq f_1 (u) \cdots f_n(u)$.
\end{itemize}
The behavior of a \kl{blind $3$-pebble transducer} is depicted
in \cref{fig:3-blind-transducer}.


\begin{example}  \AP \label{ex:ulsq}
The function $\intro*\ulsq : A^* \rightarrow A^* \uplus \{\#\}, u \mapsto (u\#)^{|u|}$
can be computed by a \kl{blind $2$-pebble transducer}.
This machine has shape $\transfont{T} \tree{\transfont{T}'}$:
$\transfont{T}$ calls $\transfont{T}'$ on each position
$1 \le i \le |u|$ of its input $u$, and $\transfont{T}'$ outputs $u\#$.
\end{example}
\AP
The class of functions computed by a 
\kl{blind $k$-pebble transducer} for some $k \ge 1$
is called \intro{polyblind functions} \cite{doueneau2022hiding}.
They form a strict subclass of \kl{polyregular functions}
\cite{doueneau2021pebble,doueneau2022hiding,nous2020comparison} which is closed
under composition \cite[Theorem 6.1]{nous2020comparison}.

\AP
Now, let us define \kl{last pebble transducers}. They corresponds to
\kl{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
$\intro*\omarK{u}{i} \coloneqq u[1] \cdots u[i{-}1] \marq{u[i]} u[i{+}1] \cdots u[|u|]$
for $u \in A^*$ and $1 \le i \le |u|$.



\begin{definition}[Last pebble transducer \cite{engelfriet2007xml}]
\label{def:last-pebble} \AP
For $k \ge 1$, a \intro{last $k$-pebble transducer}
with input alphabet $A$
and output alphabet $B$ is:
\begin{itemize}
\item if $k =1$, a \kl{two-way transducer} with input alphabet $A \uplus \marq{A}$
and output $B$;
\item if $k \ge 2$, a tree $\transfont{T}\tree{\transfont{L}_1, \cdots ,\transfont{L}_p}$ where
$\transfont{L}_1, \dots, \transfont{L}_p$ are \kl{last $(k{-}1)$-pebble transducers}
with input $A$ and output $B$; 
and $\transfont{T}$ is a \kl{two-way transducer} with input $A \uplus \marq{A}$
and output alphabet $\{\transfont{L}_1, \dots, \transfont{L}_p\}$.
\end{itemize}
\end{definition}
\AP
The (total) function  $f:(A \uplus \marq{A})^* \rightarrow B^*$ computed by
the \kl{last $k$-pebble transducer} of \cref{def:last-pebble} is defined in a recursive
fashion, as follows:
\begin{itemize}
\item for $k=1$, $f$ is the function computed by
the \kl{two-way transducer};
\item for $k\ge 2$, let $u \in A^*$ and  $(q_1,i_1) \runs{} \cdots \runs{} (q_n,i_n)$ be the
accepting run of $\transfont{T}= (A \uplus \marq{A},B,Q,q_0,F,\delta,\lambda)$ on $\lmark u {\dashv}$.
For all $1 \le j \le n$, let $f_j : A^* \rightarrow B^*$ be the concatenation of the functions
recursively computed by $\lambda(q_j,(\lmark u {\dashv})[i_j]) \in \{\transfont{L}_1, \dots, \transfont{L}_p\}^*$.
Let   $\tau : (A \uplus \marq{A})^* \rightarrow A^*$ be
the morphism which erases the underlining (i.e.
$\tau(\marq{a})=a$), then
$f(u) \coloneqq f_1(\omarK{\tau(u)}{i_1}) \cdots f_n(\omarK{\tau(u)}{i_n})$.
\end{itemize}
The behavior of a \kl{last $3$-pebble transducer} is depicted
in \cref{fig:3-last-transducer}. Observe that our definition
builds a function of type $(A \uplus \marq{A})^* \rightarrow B^*$,
but at shall in fact consider its restriction to $A^*$ (the marks
are only used within the induction step).

\begin{example}[\cite{bojanczyk2018polyregular}]
\label{ex:square}
The function $\intro*\sqK :  u \mapsto (\omarK{u}{1})\# \cdots
 (\omarK{u}{|u|})\#$ can be computed by a \kl{last $2$-pebble transducer},
 which successively marks and makes recursive calls in positions $1, 2$, etc.
However this function is not \kl{polyblind} \cite{nous2020comparison}.
\end{example}

\AP
We are ready to state our main result. Its proof goes
over \cref{sec:forests,sec:blind-proof,sec:last-proof}.


\begin{theorem}[Minimization of the recursion height]
\label{the:minimize-main}
Let $1 \le \ell \le k$. Let $f : A^* \rightarrow B^*$ be
computed by a  \kl{blind $k$-pebble transducer} (resp.
by a \kl{last $k$-pebble transducer}).
Then $f$ can be computed by a \kl{blind $\ell$-pebble transducer}
 (resp. by a \kl{last $\ell$-pebble transducer})
if and only if $|f(u)| = \mc{O}(|u|^{\ell})$.\\
This property is decidable and the construction
is effective.
\end{theorem}

\AP
As an easy consequence, the class of functions
computed by \kl{last pebble transducers} form a strict subclass
of the \kl{polyregular functions} (because \cref{the:minimize-main}
does not hold for the full model of \kl{pebble transducers} \cite[Theorem 6.3]{bojanczyk2022transducers})
and therefore it is not closed under composition (because
any \kl{polyregular function} can be obtained
as a composition of \kl{regular functions} and $\sqK$s
\cite{bojanczyk2018polyregular}).

\AP
Even if a (non-effective) \cref{the:minimize-main} was already known for \kl{blind pebble transducers}
\cite[Theorem 7.1]{nous2020comparison}, we shall first present
our proof of this case. Indeed, it is a new proof (relying on
\kl{factorization forests}) which is simpler than the original one.
Furthermore, understanding the techniques used is a key step
for understanding the proof for \kl{last pebble transducers}
presented afterwards.














\section{Factorization forests}

\label{sec:forests}

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


\begin{definition}[{Factorization forest} \cite{simon1990factorization}]%
\label{def:facto} \AP
Given a morphism $\mu: A^* \rightarrow \mb{M}$ and $u\in A^*$, we say that
$\mc{F}$ is a  \intro{$\mu$-forest} of $u$ if:
\begin{itemize}
\item either $u = \varepsilon$ and $\mc{F} = \varepsilon$; or $u = \tree{a}  \in A $ and $\mc{F} = a$;
\item or $\mc{F} = \tree{\mc{F}_1, \cdots ,\mc{F}_n}$,
$u = u_1 \cdots u_n$, for all $1 \le i \le n$,
$\mc{F}_i$ is a \kl{$\mu$-forest} of $u_i \in A^+$,
and if $n \ge 3$ then $\mu(u) = \mu(u_1) = \dots = \mu(u_n)$ is idempotent.
\end{itemize}
\end{definition}
\AP
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 $\intro*\NodK{\mc{F}}$ the set of nodes of $\mc{F}$.
In order to simplify the statements, we identify a node $\mf{t} \in \NodK{\mc{F}}$ with
the subtree rooted in this node. Thus $\NodK{\mc{F}}$ can also
be seen as the set of subtrees of $\mc{F}$, and $\mc{F} \in \NodK{\mc{F}}$.
We say that a node is \intro(NOD){idempotent} if it has
at least $3$ children. We denote by $\intro*\FacK{\mu}{}(u)$ (resp. $\reintro*\FacK{\mu}{d}(u)$)
the set of \kl{$\mu$-forests} of $u \in A^*$ (resp. 
\kl{$\mu$-forests} of $u \in A^*$ of height at most $d$).
We write $\reintro*\FacK{\mu}{}$ and $\reintro*\FacK{\mu}{d}$
of all \kl{forests} (of any word).



A $\mu$-forest of $u \in A^*$ can also be seen as
``the word $u$ with brackets'' in \cref{def:facto}.
Therefore $\FacK{\mu}{}$ can be seen as a language over
 $\apar{A} \coloneqq A \uplus \{\langle,\rangle\}$. In this setting,
 it is well-known that \kl{$\mu$-forests} of bounded height can
 effectively be computed by a \intro{rational function}, i.e. a
 particular case of \kl{regular function} that can be computed
 by a non-deterministic one-way transducer (see e.g. \cite{doueneau2021pebble}).



\begin{theorem}[Simon \cite{simon1990factorization,colcombet2011green}]%
	\label{the:simon}
	\AP
	Given a morphism $\mu : A^* \to \mb{M}$ into
	a finite monoid $\mb{M}$, one can effectively build a \kl{rational function}
	$\intro*\forK{\mu} : A^* \to (\apar{A})^*$
	such that for all $u \in A^*$, $\forK{\mu}(u) \in \FacK{\mu}{3|\mb{M}|}(u)$.
\end{theorem}

\AP
Building \kl{$\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 \cite{doueneau2021pebble,doueneau2022hiding}.
First, we define \kl{iterable nodes} as the middle
children of \kl{idempotent nodes}. 


\begin{definition}%
\label{def:iterables}
\AP
Let $\mc{F} \in \FacK{\mu}{}(u)$. Its \intro{iterable nodes},
denoted $\intro*\IteK{\mc{F}}$, are:
\begin{itemize}
\item if $\mc{F} = \tree{a}\in A$ or $\mc{F} = \varepsilon$,
then $\IteK{\mc{F}} \coloneqq \varnothing$;
\item otherwise if $\mc{F} = \tree{\mc{F}_1, \cdots ,\mc{F}_n}$, then:
\begin{equalign*}
\IteK{\mc{F}} \coloneqq \{\mc{F}_i: 2 \le i \le n{-}1\} \cup  \bigcup_{1 \le i \le n} \IteK{\mc{F}_i}.
\end{equalign*}
\end{itemize}
\end{definition}
\AP
Now, we define the notion of \kl{skeleton} of a node $\mf{t}$,
which contains all the descendants
of $\mf{t}$ except those which are \kl(NOD){iterable}.


\begin{definition}[Skeleton, frontier]%
\label{def:skeleton}
\AP
Let $\mc{F} \in \FacK{\mu}{}(u)$, $\mf{t} \in \NodK{\mc{F}}$, we define
the \intro{skeleton}  of $\mf{t}$, denoted $\intro*\SkeK{\mc{F}}(\mf{t})$, by:
\begin{itemize}
\item if $\mf{t} = \tree{a}\in A$ is a leaf, then $\SkeK{\mc{F}}(\mf{t}) \coloneqq \{ \mf{t} \}$;
\item otherwise if $\mf{t} = \tree{\mc{F}_1, \cdots, \mc{F}_n}$, then
$\SkeK{\mc{F}}(\mf{t}) \coloneqq \{\mf{t}\} \cup \SkeK{\mc{F}}(\mc{F}_1) \cup \SkeK{\mc{F}}(\mc{F}_n)$.
\end{itemize}
The \intro{frontier} of $\mf{t}$ is the set $\intro*\FroK{\mc{F}}(\mf{t}) \subseteq [1{:}|u|]$
containing the positions of $u$ which belong to $\SkeK{\mc{F}}(\mf{t})$
(when seen as leaves of the \kl{$\mu$-forest} $\mc{F}$ over $u$).
\end{definition}



\begin{example}
Let $\mb{M} \coloneqq (\{-1,1,0\}, \times)$ and
$\mu: \mb{M}^* \rightarrow \mb{M}$ the product.
A \kl{$\mu$-forest} $\mc{F}$ of the
word $(-1)(-1)0(-1)000000$ is depicted
in Figure~\ref{fig:ex:skel}. Double lines
denote \kl{idempotent nodes}. The set of
blue nodes is the \kl{skeleton} of the topmost
blue node.
\end{example}

\input{parts/fig-factorization-forest.tex}


\AP
It is easy to observe that for $\mc{F} \in \FacK{\mu}{d}(u)$, the size
of a \kl{skeleton}, or of a \kl{frontier}, is bounded independently
from $\mc{F}$. Furthermore,
the set of \kl{skeletons} $\{ \SkeK{\mc{F}}(\mf{t}) : \mf{t} \in \IteK{\mc{F}} \cup \{\mc{F}\} \}$
is a partition of $\NodK{\mc{F}}$ \cite[Lemma 33]{doueneau2021pebble}.
As a consequence, the set of \kl{frontiers} 
$ \{\FroK{\mc{F}}(\mf{t}): \mf{t} \in \IteK{\mc{F}} \cup \{\mc{F}\}\}$
is a partition of $[1{:} |u|]$.
Given a position $1 \le i \le |u|$, we can
thus define the \intro{origin} of $i$ in $\mc{F}$,
denoted $\intro*\originK{\mc{F}}(i)$, as the 
unique $\mf{t} \in \IteK{\mc{F}} \cup \{\mc{F}\}$
such that  $i \in \FroK{\mc{F}}{}(\mf{t})$.



\begin{definition}[Observation]{}
	Let $\mc{F} \in \FacK{\mu}{}$ and $\mf{t}, \mf{t}' \in \NodK{\mc{F}}$.
	We say that $\mf{t} \in  \NodK{\mc{F}}$  \intro(NOD){observes} $\mf{t}' \in \NodK{\mc{F}}$
	if either $\mf{t}'$ is an ancestor of $\mf{t}$, or $\mf{t}'$ is the immediate
	right or left sibling of an ancestor of $\mf{t}$.
\end{definition}



\input{parts/fig-observable.tex}

\AP
The intuition behind the notion of \kl(NOD){observation}
(which is \emph{not} symmetrical) is depicted in \cref{fig:observation}.
Note that in a forest of bounded height,
the number of nodes that some $\mf{t}$ \kl(NOD){observes} is bounded.
This will be a key argument in the following.
We say that $\mf{t}$ and $\mf{t}'$ are \intro(NOD){dependent} if
either $\mf{t}$ \kl(NOD){observes} $\mf{t}'$ or the converse.
Given $\mc{F}$, we can translate these notions
to the positions of $u$: we say that $i$ \intro(POS){observes}
(resp. \intro(POS){depends} on) $i'$ if
$\originK{\mc{F}}(i)$ \kl(NOD){observes} (resp.
\kl(NOD){depends} on) $\originK{\mc{F}}(i')$.






















\section{Height minimization of blind pebble transducers}

\label{sec:blind-proof}

\AP
In this section, we show \cref{the:minimize-main} for \kl{blind pebble transducers}.
We say that a \kl{two-way transducer} $\transfont{T}$ is a  \intro(BLIND){submachine} of a
\kl{blind pebble transducer} $\transfont{B}$ if $\transfont{T}$ labels a node in 
the tree description of $\transfont{B}$. If $\transfont{B} = \transfont{T} \tree{\transfont{B}_1, \dots, \transfont{B}_n}$,
we say that the \kl(BLIND){submachine} $\transfont{T}$ is the \intro(BLIND){head} of $\transfont{B}$.
We let the \intro(BLIND){transition morphism} 
of $\transfont{B}$ be the cartesian product of all the
 \kl(TDT-F){transition morphisms}
of all the \kl(BLIND){submachines} of $\transfont{B}$.
Observe that it makes sense to consider the \kl{production}
of a \kl(BLIND){submachine} $\transfont{T}$ in a  \kl{context} defined
using the \kl(BLIND){transition morphism} of $\transfont{B}$.


\subsection{Pumpability}

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


\begin{definition}
\label{def:pumpable-blind}
\AP
Let $\transfont{B}$ be a  \kl{blind $k$-pebble transducer}
whose \kl(BLIND){transition morphism} is $\mu : A^* \rightarrow \mb{T}$.
We say that the transducer $\transfont{B}$ is \intro(BLIND){pumpable} if there exists:
\begin{itemize}
\item \kl(BLIND){submachines} $\transfont{T}_1, \dots, \transfont{T}_k$ of $\transfont{B}$,
such that $\transfont{T}_1$ is the \kl(BLIND){head} of $\transfont{B}$;
\item  $m_0, \dots, m_k, {\ell}_1, \dots, {\ell_k}, r_1, \dots, r_k \in \mu(A^*)$;
\item $a_1,\dots, a_k \in A$  such that for all $1 \le j \le k$,
$e_i \coloneqq {\ell}_j \mu(a_j) r_j$ is an idempotent;
\item  a permutation $\sigma : \inter{1}{k} \rightarrow  \inter{1}{k}$;
\end{itemize}
such that if $\Mblock{i}{j}  \coloneqq
m_{i} e_{i + 1} m_{i + 1} \cdots e_{j} m_{j}$
 for all $0 \le i \le j \le k$,  and
 if we define the following \kl{context} for all $1 \le j \le k$:
\begin{equalign*}
\mc{C}_j \coloneqq \Mblock{0}{\sigma(j)-1} e_{\sigma(j)} \ell_{\sigma(j)}
\cro{a_{\sigma(j)}} r_{\sigma(j)} e_{\sigma(j)} \Mblock{\sigma(j)}{k}
\end{equalign*}
then for all $1 \le j \le k{-}1$, $|\valK{\transfont{T}_j}{}(\mc{C}_j)|_{\transfont{T}_{j+1}} \neq 0$,
and $\valK{\transfont{T}_k}{}(\mc{C}_k) \neq \varepsilon$.
\end{definition}



\input{parts/fig-blind-pumpable.tex}


\Cref{lem:growth-blind} follows
by choosing inverse images in $A^*$
for the $m_i$, $\ell_i$ and $r_i$.

\begin{lemma}
\label{lem:growth-blind}
Let $f$  be computed by a
\kl(BLIND){pumpable} \kl{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)$.
\end{lemma}

\AP
Now, we use \kl(BLIND){pumpability} as a key ingredient
for showing  \cref{the:minimize-main}, which directly follows
 by induction from the more precise \cref{the:blind-minimize}.


\begin{theorem}[Removing one layer]
\label{the:blind-minimize}
Let $k \ge 2$ and $f : A^* \rightarrow B^*$ be
computed by a  \kl{blind $k$-pebble transducer} $\transfont{B}$. 
The following are equivalent:
\begin{enumerate}
\item \label{it:bm:growth} $|f(u)| = \mc{O}(|u|^{k-1})$;
\item \label{it:bm:pumpable} $\transfont{B}$ is not \kl(BLIND){pumpable};
\item \label{it:bm:blind} $f$ can be computed by a \kl{blind $(k{-}1)$-pebble transducer}.
\end{enumerate}
Furthermore, this property is decidable and the construction
is effective.
\end{theorem}

\begin{proof} \Cref{it:bm:blind} $\implies$ \cref{it:bm:growth} is obvious.
\Cref{it:bm:growth} $\implies$ \cref{it:bm:pumpable} is \cref{lem:growth-blind}.
Furthermore, \kl(BLIND){pumpability} can be tested by an enumeration of $\mu(A^*)$ and $A$.
It remains to show \cref{it:bm:pumpable} $\implies$ \cref{it:bm:blind}
(in an effective fashion): this is the purpose of \cref{ssec:minimize-blind}.
\end{proof}



\subsection{Algorithm for removing a recursion layer}


\label{ssec:minimize-blind}



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

\AP
Let $\mu : A^* \rightarrow \mb{T}$ be the \kl(BLIND){transition morphism}
of $\transfont{U}$. We shall consider that, on input $u \in A^*$,
the \kl(BLIND){submachines} of $\ov{\transfont{U}}$ can in fact use
$\forK{\mu}(u) \subseteq (\apar{A})^*$ as input.
Indeed $\forK{\mu}$ is a \kl{rational function}
(by \cref{the:simon}), hence its information can
be recovered by using a \intro{lookaround}. Informally, the \kl{lookaround} feature
enables a \kl{two-way transducer} to chose its transitions
not only depending on its current state and current letter $u[i]$
in position $1 \le i \le |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 \kl{two-way transducer} $\transfont{T}$
with \kl{lookarounds}, one can build an equivalent $\transfont{T}'$ that
does not have this feature (see e.g.  \cite{hopcroft1967approach,engelfriet2001mso}).
Furthermore, even if the accepting runs of $\transfont{T}$ and $\transfont{T}'$ may differ,
they produce the same outputs from the same positions (this observation
will be critical for \kl{last pebble transducers}, in order to ensure that
the marked positions of the recursive calls will be preserved).


\AP
Now, we describe the \kl{two-way transducers}
that are the  \kl(BLIND){submachines} of $\ov{\transfont{U}}$.
First, it has  \kl(BLIND){submachines} $\reintro*\normalK{\transfont{T}}$
for $\transfont{T}$ a  \kl(BLIND){submachine}  of $\transfont{U}$,
which are described in  \cref{algo:blind-minimization-original}.
Intuitively, $\normalK{\transfont{T}}$ is just a copy of $\transfont{T}$.
It is clear that if $\transfont{T}$ is a \kl(BLIND){submachine} of $\transfont{U}$,
then $\normalK{\transfont{T}}(u)$ is the concatenation of the outputs produced by (the recursive
calls of) $\transfont{T}$ along its accepting run on $\lmark u {\dashv}$.


\input{parts/algo-blind-minimization-normal.tex}


\AP
$\ov{\transfont{U}}$ also has \kl(BLIND){submachines} $\reintro*\simBlindK{\transfont{T}}$
for $\transfont{T}$ a  \kl(BLIND){submachine}  of $\transfont{U}$,
which are described in  \cref{algo:blind-minimization-simplify}.
Intuitively, $\simBlindK{\transfont{T}}$ simulates $\transfont{T}$
while trying to inline recursive calls in its own run.
More precisely, let $u \in A^*$ be the input and $\mc{F} \coloneqq \forK{\mu}(u)$.
If $\transfont{T}$ calls $\transfont{B}'$ in $1 \le i \le |u|$ that belongs to the  \kl{frontier}
of the root node  $\mc{F}$ of $\mc{F}$, then $\simBlindK{\transfont{T}}$
inlines the behavior of the \kl(LAST){head} of $\transfont{B}'$. Otherwise
it makes a recursive call, except if $\transfont{B}'$ is a leaf of $\transfont{U}$.
Hence if $\transfont{T}$ is a \kl(BLIND){submachine} of $\transfont{U}$ which is not a leaf,
$\simBlindK{\transfont{T}}(u)$ is the concatenation of the outputs produced by the calls
of $\transfont{T}$ along its accepting run.



\input{parts/algo-blind-minimization-simplify.tex}

\AP
Finally, the transducer $\ov{\transfont{U}}$ is
obtained by defining $\simBlindK{\transfont{T}}$
to be its  \kl(BLIND){head}, where $\transfont{T}$
is the \kl(BLIND){head} of $\transfont{U}$. Furthermore,
we remove the \kl(BLIND){submachines} $\normalK{\transfont{T}}$
or $\simBlindK{\transfont{T}}$ which are never called.
Observe that $\ov{\transfont{U}}$ indeed computes the function $f$.
Furthermore, we observe that $\ov{\transfont{U}}$ has recursion height (i.e. the number
of nested \textbf{Call} instructions, plus $1$ for the \kl(BLIND){head}) $k{-}1$,\label{sta:k:blind} since each
inlining of \cref{line:fril,line:2-way-blind,line:no-2dt-without-inline} in \cref{algo:blind-minimization-simplify}
removes exactly one recursion layer of $\transfont{U}$.

\AP
It remains to justify that each $\simBlindK{\transfont{T}}$ can
be implemented by a \kl{two-way transducer} (i.e. with \kl{lookarounds}
but a bounded memory). We represent
variable $i$  by the current position of the transducer.
Since it has access to $\mc{F}$, the \kl{lookaround}
can be used to check whether $i \in \FroK{\mc{F}}(\mc{F})$ or not
(since the size of $\FroK{\mc{F}}(\mc{F})$ is bounded).
It remains to explain how the inlinings are performed:
\begin{itemize}
\item if $i \in \FroK{\mc{F}}(\mc{F})$, 
the \kl{two-way transducer} inlines
$\normalK{\transfont{T}'}$ by executing the same moves
and calls as $\transfont{T}'$ does. Once its computation is ended,
it has to go back to position $i$. This is indeed possible
since belonging to $\FroK{\mc{F}}(\mc{F})$ is a property
that can be detected by using the \kl{lookaround},
hence the machine only needs to remember
 that $i$ was the $\ell$-th position of $\FroK{\mc{F}}(\mc{F})$ ($\ell$ being bounded);
\item else if $\transfont{B}' = \transfont{T}'$ is a \kl{blind $1$-pebble transducer},
we produce the output of $\transfont{T}'$ without moving.
This is possible since for all
$i' \not \in \FroK{\mc{F}}(\mc{F})$, 
$\valK{\transfont{T}'}{u}(i') = \varepsilon$ 
(hence the output of $\transfont{T}'$ on $u$ is bounded,
and its value can be determined without moving, just by using the \kl{lookaround}).
Indeed, if $\valK{\transfont{T}'}{u}(i') \neq \varepsilon$ for such an $i' \not \in \FroK{\mc{F}}(\mc{F})$
when reaching \cref{line:2-way-blind} 
of  \cref{algo:blind-minimization-simplify}, then
 the conditions of \cref{lem:k-nodes-blind-key}
hold,\label{sta:k:2} which yields a contradiction.
This lemma is the key argument of this proof, relying on
the non-\kl(BLIND){pumpability} of $\transfont{U}$.
\end{itemize}

\begin{lemma}[Key lemma]%
\label{lem:k-nodes-blind-key}%
Let $u \in A^*$ and $\mc{F} \in \FacK{\mu}{}(u)$.
Assume that there exists a sequence $\transfont{T}_1, \dots, \transfont{T}_k$
of \kl(BLIND){submachines}
of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_k \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(BLIND){head} of $\transfont{U}$;
\item  for all $1 \le j \le k{-}1$, $|\valK{\transfont{T}_j}{u}(i_j)|_{\transfont{T}_{j+1}} \neq 0$
and $\valK{\transfont{T}_k}{u}(i_k) \neq \varepsilon$;
\item for all $1 \le j \le k$, $i_j \not \in \FroK{\mc{F}}(\mc{F})$
(i.e. $\originK{\mc{F}}(i_j) \in \IteK{\mc{F}}$).
\end{itemize}
Then $\transfont{B}$ is \kl(BLIND){pumpable}.
\end{lemma}

\begin{proof}[idea] We first observe that \kl(BLIND){pumpability}
follows as soon as the nodes $\originK{\mc{F}}(i_j)$ are
two by two \kl(NOD){independent}. We then
show that this \kl(NOD){independence} condition
can always be obtained, up to duplicating
some \kl(NOD){iterable} subtrees of $\mc{F}$ (and some factors of $u$),
because the behavior of a \kl(BLIND){submachine}
in a \kl{blind pebble transducer} does not depend
on the positions of the above recursive calls.
\end{proof}






















\section{Height minimization of last pebble transducers}


\label{sec:last-proof}


\AP
In this section, we show \cref{the:minimize-main} for \kl{last pebble transducers}.
The notions of \intro(LAST){submachine}, \intro(LAST){head}
and \intro(LAST){transition morphism} for
a \kl{last pebble transducer} are defined as in \cref{sec:blind-proof}.
The \kl(LAST){transition morphism}
is now defined over $(A \uplus \marq{A})^*$.




\subsection{Pumpability}

\AP
The sketch of the proof is similar to \cref{sec:blind-proof}.
We first give an equivalent of \kl(BLIND){pumpability}
for \kl{last pebble transducers}. The intuition behind this notion
is depicted in \cref{fig:last-pumpable}. The formal definition is however
more cumbersome, since we need to keep track of the fact
that the calling position is marked.


\begin{definition}%
\label{def:pumpable-last}
\AP
Let $\transfont{L}$ be a  \kl{last $k$-pebble transducer}
whose \kl(LAST){transition morphism} is $\mu : (A \cup \marq{A})^* \rightarrow \mb{T}$.
We say that the transducer $\transfont{L}$ is \intro(LAST){pumpable} if there exists:
\begin{itemize}
\item \kl(LAST){submachines} $\transfont{T}_1, \dots, \transfont{T}_k$ of $\transfont{L}$,
such that $\transfont{T}_1$ is the \kl(LAST){head} of $\transfont{L}$;
\item  $m_0, \dots, m_k, {\ell}_1, \dots, {\ell_k}, r_1, \dots, r_k \in \mu(A^*)$;
\item $a_1,\dots, a_k \in A$  such that for all $1 \le j \le k$
$e_j \coloneqq {\ell}_j \mu(a_j) r_j$ is idempotent;
\item  a permutation $\sigma : \inter{1}{k} \rightarrow  \inter{1}{k}$;
\end{itemize}
such that if we let
$\Mblock{i}{j}  \coloneqq
m_{i} e_{i + 1} m_{i + 1} \cdots e_{j} m_{j}$
 for all $0 \le i \le j \le k$,  and  if we define the following \kl{context}:
\begin{equalign*}
\mc{C}_1 \coloneqq \Mblock{0}{\sigma(1)-1} e_{\sigma(1)} \ell_{\sigma(1)} \cro{a_{\sigma(1)}} r_1
e_{\sigma(1)} \Mblock{\sigma(1)}{k}
\end{equalign*}
and for all $1 \le j \le k{-}1$ the \kl{context}:
\begin{equalign*}
\mc{C}_{j+1} & \coloneqq  \Mblock{0}{\sigma(j)-1}
e_{\sigma(j)} \ell_{\sigma(j)} \mu(\marq{a_{\sigma(j)}}) r_{\sigma(j)} e_{\sigma(j)}
\Mblock{\sigma(j)}{\sigma(j+1)-1}&\\
&e_{\sigma(j+1)} \ell_{\sigma(j+1)}  \cro{a_{\sigma(j+1)}} r_{\sigma(j+1)} e_{\sigma(j+1)}
\Mblock{\sigma(j+1)}{k}
&\teq{\normalfont~if $\sigma(j) < \sigma(j+1)$;}\\
\mc{C}_{j+1} & \coloneqq  \Mblock{0}{\sigma(j)-1}
e_{\sigma(j+1)} \ell_{\sigma(j+1)} \cro{a_{\sigma(j+1)}} r_{\sigma(j+1)}  e_{\sigma(j+1)} &\\
& \Mblock{\sigma(j+1)}{\sigma(j)-1}  e_{\sigma(j)} \ell_{\sigma(j)}
\mu(\marq{a_{\sigma(j)}}) r_{\sigma(j)} e_{\sigma(j)}
\Mblock{\sigma(j)}{k}
&\teq{\normalfont~otherwise;}\\
\end{equalign*}
then for all $1 \le j \le k{-}1$, $|\valK{\transfont{T}_j}{}(\mc{C}_j)|_{\transfont{T}_{j+1}} \neq 0$,
and $\valK{\transfont{T}_k}{}(\mc{C}_k) \neq \varepsilon$.
\end{definition}



\input{parts/fig-last-pumpable.tex}


We obtain \cref{lem:growth-last} by
a proof which is similar to that of \cref{lem:growth-blind}. 

\begin{lemma}%
\label{lem:growth-last}%
Let $f$ be computed by a \kl(LAST){pumpable} \kl{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)$.
\end{lemma}




\begin{theorem}[Removing one layer]
\label{the:last-minimization}
Let $k \ge 2$ and $f : A^* \rightarrow B^*$ be
computed by a  \kl{last $k$-pebble transducer} $\transfont{L}$. 
The following are equivalent:
\begin{enumerate}
\item \label{it:lm:growth} $|f(u)| = \mc{O}(|u|^{k-1})$;
\item \label{it:lm:pumpable} $\transfont{L}$ is not \kl(LAST){pumpable};
\item \label{it:lm:blind} $f$ can be computed by a \kl{last $(k{-}1)$-pebble transducer}.
\end{enumerate}
Furthermore, this property is decidable and the construction
is effective.
\end{theorem}


\begin{proof} \Cref{it:lm:blind} $\implies$ \cref{it:lm:growth} is obvious.
\Cref{it:lm:growth} $\implies$ \cref{it:lm:pumpable} is \cref{lem:growth-last}.
Furthermore, \kl(LAST){pumpability} can be tested by an enumeration of $\mu(A^*)$ and $A$.
It remains to show \cref{it:lm:pumpable} $\implies$ \cref{it:lm:blind}
(in an effective fashion): this is the purpose of \cref{ssec:minimize-last}.
\end{proof}


\subsection{Algorithm for removing a recursion layer}

\label{ssec:minimize-last}



\AP
Let $k \ge 2$ and $\transfont{U}$ be a \kl{last $k$-pebble transducer} that is not
\kl(LAST){pumpable}, and that computes $f : A^* \rightarrow B^*$.
We build a \kl{last $(k{-}1)$-pebble transducer} $\ov{\transfont{U}}$ for $f$.
Let $\mu : (A \uplus \marq{A})^* \rightarrow \mb{T}$ be the \kl(LAST){transition morphism}
of $\transfont{U}$. As before (using a \kl{lookaround}), the \kl(LAST){submachines}
of $\ov{\transfont{U}}$ will use $\forK{\mu}(u)$ as input
instead of $u \in A^*$.

\AP
Now, we describe the \kl(LAST){submachines} of $\ov{\transfont{U}}$.
It has  \kl(LAST){submachines} $\reintro*\normalongK{\transfont{T}}{\rho}$
for $\transfont{T}$ a  \kl(LAST){submachine}  of $\transfont{U}$ and $\rho$
a run of $\transfont{T}$, which are described in  \cref{algo:blind-minimization-original}.
Intuitively, these machines mimics the behavior of $\transfont{T}$
along the run $\rho$ (which is not necessarily accepting)
of $\transfont{T}$ over $\lmark v {\dashv}$ with $v \in (A \uplus \marq{A})^*$.


\AP
Since they are indexed by a run $\rho$, it may seem that
we create an infinite number of  \kl(LAST){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 =  \omarK{u}{i}$ and we shall guarantee that the
$i_1$ and $i_n$ can be detected by the \kl{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 \kl{lookaround} of the \kl(LAST){submachine}.

\AP
By \cref{algo:blind-minimization-original},
it is clear that if $\transfont{T}$ is a \kl(LAST){submachine}
of $\transfont{U}$, then for all $v \in (A \cup \marq{A})^*$
and $\rho$ run of $\transfont{T}$ on $\lmark v {\dashv}$,
$\normalongK{\transfont{T}}{\rho}~(v)$ is the concatenation
of the outputs produced by (the recursive
calls of) $\transfont{T}$ along $\rho$.

\AP
We also define a \kl(LAST){submachine}
$\reintro*\normalongpebK{\transfont{T}}{\rho}{i}$
that is similar to $\normalongK{\transfont{T}}{\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).


\input{parts/algo-last-minimization-normal.tex}




$\ov{\transfont{U}}$ also has \kl(LAST){submachines} $\reintro*\simLastK{\transfont{T}}{\rho}$
for $\transfont{T}$ a  \kl(LAST){submachine}  of $\transfont{U}$,
which are described in  \cref{algo:last-minimization-simplify}.
Intuitively, $\simLastK{\transfont{T}}{\rho}$ simulates $\transfont{T}$ along $\rho$
while trying to inline some recursive calls.
Whenever it is in position $i$ and needs to call recursively
$\transfont{L}'$ whose \kl(LAST){head}
is $\transfont{T}'$, it first \kl{slices} the accepting run $\rho'$ of $\transfont{T}'$
on $\lmark \omarK{u}{i} {\dashv}$, with respect to
$\forK{\mu}{}(u)$ and $i$, as explained
in \cref{def:slice-run} and depicted in \cref{fig:slicing}.
Intuitively, this operation splits $\rho'$ into a bounded number of
runs whose positions either all \kl(POS){observe} $i$,
or $i$ \kl(POS){observes} all of them, or none of these cases
occur (the positions are either $0$, $|u|{+}1$ or \kl(POS){independent} of $i$).


\begin{definition}[Slicing]
\label{def:slice-run}
\AP
Let $u \in A^*$, $\mc{F} \in \FacK{\mu}{}(u)$ and $1 \le i \le |u|$.
We let  $\intro*\ObUpK{i}$ (resp. $\intro*\ObDoK{i}$) be the set of positions
that $i$ \kl(POS){observes} (resp. that  \kl(POS){observe} $i$).\\
Let $\rho = (q_1, i_1) \runs{} \cdots \runs{} (q_n,i_n)$ be a run of a \kl{two-way
transducer} $\transfont{T}$ on $\lmark \omarK{u}{i} {\dashv}$.
We build by induction a sequence $\ell_1, \dots, \ell_{N+1}$ with
$\ell_1 \coloneqq 1$ and:
\begin{itemize}
\item if $\ell_j =  n {+} 1$ then $j \coloneqq N$ and the process ends;
\item else if $i_{\ell_{j}} \in \ObUpK{i}$
(resp. $i_{\ell_{j}} \in \ObDoK{i} \smallsetminus \ObUpK{i}$,
resp. $i_{\ell_{j}} \in [0{:}|u|{+}1] \smallsetminus (\ObUpK{i} \cup \ObDoK{i})$),
then $\ell_{j+1}$ is the largest index such that for all $\ell_{j} \le \ell \le \ell_{j+1}{-}1$,
$i_{\ell} \in \ObUpK{i}$ (resp. $i_{\ell} \in \ObDoK{i} \smallsetminus \ObUpK{i}$,
resp. $i_{\ell} \in [0{:}|u|{+}1] \smallsetminus (\ObUpK{i} \cup \ObDoK{i})$).
\end{itemize}
Finally the \intro{slicing} of $\rho$ ,with respect to $\mc{F}$ and $i$,
is the sequence of runs $\rho_1, \dots, \rho_{N}$ where
$\rho_j \coloneqq (q_{\ell_j}, i_{\ell_j}) \runs{} (q_{\ell_j+1}, i_{\ell_j+1})
\runs{} \cdots \runs{} (q_{\ell_{j+1}-1}, i_{\ell_{j+1}-1})$.
\end{definition}

\vspace*{-0.8cm}

\input{parts/fig-slicing.tex}

{\setlength{\parindent}{0pt}
Now, let $\rho'_1, \dots, \rho'_N$ be  \kl{slicing} of the run $\rho'$ of $\transfont{T}'$
on the input $\omarK{u}{i}$. For all $1 \le j \le N$, there are mainly two cases.
Either  the positions of $\rho'_j$ all are in $\ObUpK{i}$ or
$\ObDoK{i}$. In this case, $\simLastK{\transfont{T}}{\rho}$  directly inlines $\normalongK{\transfont{T}'}{\rho'_j}$
within its own run (i.e. without making a recursive call).
Otherwise, it makes a recursive call to $\simLastK{\transfont{T}'}{\rho'_j}$,
except if $\transfont{L}'$ is a leaf of $\transfont{U}$ (thus $\transfont{L}' = \transfont{T}'$).


\input{parts/algo-last-minimization-simplify.tex}




Finally, $\ov{\transfont{U}}$  is described as follows: on input 
$u \in A^*$, its \kl(LAST){head} is the \kl(LAST){submachine} $\simLastK{\transfont{T}}{\rho}~(u)$,
where $\transfont{T}$ is the \kl(LAST){head} of $\transfont{U}$
and $\rho$ is the accepting run of $\transfont{T}$ on $\lmark u {\dashv}$
(represented by the bounded information that it is both initial and final).
As before, we remove the \kl(LAST){submachines}
which are never called in $\ov{\transfont{U}}$.
Observe that we have created a machine with recursion height $k{-}1$\label{sta:last:k}
(because \cref{line:testtest-no2DT}
in \cref{algo:last-minimization-simplify} prevents from calling
a $k$-th layer).



\AP
Let us justify that each $\simLastK{\transfont{T}}{\rho}$
can indeed be implemented by a \kl{two-way transducer}.
First, let us observe that since $\mc{F}$ has bounded
height, the number $N$ of \kl{slices} given in \cref{line:N-slice}
of \cref{algo:last-minimization-simplify}
is bounded. Furthermore, we claim that the first and
last positions of each $\rho'_j$ belong to a given
set of bounded size, which can be detected a \kl{lookaround} which has
access to $i$. For the $\rho'_j$ whose positions are
in $\ObUpK{i}$, this is clear since $|\ObUpK{i}|$ is bounded
(because the frontier of any node is bounded).
For $\ObDoK{i} \smallsetminus \ObUpK{i}$ we use
\cref{lem:struct-O2}, which implies that this set is a bounded
union of intervals. The last case is very similar.

\begin{lemma} \label{lem:struct-O2} Let $1 \le i \le |u|$,
$\mf{t} \coloneqq \originK{\mc{F}}(i)$ and $\mf{t}_{1}$ (resp. $\mf{t}_2$)
be its immediate left (resp. right) sibling (they exist whenever $\mf{t} \in \IteK{\mc{F}}$,
i.e. here $\mf{t} \neq \mc{F}$). Then:
\begin{equalign*}
\ObDoK{i} \smallsetminus \ObUpK{i}  = [\min(\FroK{\mc{F}}(\mf{t}_1)) : \max(\FroK{\mc{F}}(\mf{t}_2))] \smallsetminus \{\FroK{\mc{F}}(\mf{t}_1), \FroK{\mc{F}}(\mf{t}),
\FroK{\mc{F}}(\mf{t}_2)\}.
\end{equalign*}
\end{lemma}
This analysis justifies why each $\rho'_j$ can be encoded in a bounded way.
Now, we show how to implement the inlinings while
using $i$ as the current position:
\begin{itemize}
\item if $i_1, \dots, i_n \in \ObUpK{i}$,
then $n$ is bounded (because $|\ObUpK{i}|$ is bounded).
We can thus inline $\normalongK{\transfont{T}'}{{\rho'_j}}~(\omarK{u}{i})$
while staying in position $i$. However, when $\transfont{T}'$ calls
some $\transfont{L}''$ (of \kl(LAST){head} $\transfont{T}''$) on
position $i_{\ell}$, we would need to call
$\normalongK{\transfont{T}''}{\rho''}(\omarK{u}{i_{\ell}})$
(where $\rho''$ is the accepting run of $\transfont{T}''$ along
$\lmark \omarK{u}{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 $\normalongpebK{\transfont{T}''}{\rho''}{i_{\ell}}(\omarK{u}{i})$
instead, which simulates an accepting run $\rho''$
of $\transfont{T}$ on $\omarK{u}{i_{\ell}}$, even if its input is $\omarK{u}{i}$.
Note that $i_{\ell}$ can be represented as a bounded information
and recovered by a \kl{lookaround} given $\omarK{u}{i}$ as input,
since $i$ \kl(POS){observes} $i_{\ell}$;

 \item if $i_1, \dots, i_n \in \ObDoK{i} \smallsetminus \ObUpK{i}$, then
 the nodes $\originK{\mc{F}}(i_{1}), \dots, \originK{\mc{F}}(i_{n})$
 are \linebreak ``below''  $\originK{\mc{F}}(i)$ in $\mc{F}$ (see \cref{fig:observation}).
 We inline $\normalongK{\transfont{T}'}{{\rho'_j}}~(\omarK{u}{i})$,
 by moving along $i_1, \dots, i_n$ as $\rho'_j$ does.
We can keep track of the height of $\originK{\mc{F}}(i)$
 above the current $\originK{\mc{F}}(i_{\ell})$
 (it is a bounded information). With the
\kl{lookaround}, we can detect the end of $\rho'_j$, and
 go back to position $i$.

\end{itemize}

\AP
It remains to justify that $\ov{\transfont{U}}$
is correct. For this, we only need to show that
when it reaches \cref{line:key-blind-minimization}
in \cref{algo:last-minimization-simplify}, the output of
$\transfont{T}'$ along $\rho'_j$ is indeed empty.
Otherwise, the conditions of \cref{lem:k-nodes-last-key}
would hold \label{sta:last:2}(since we never execute two successive recursive
calls in \kl(POS){dependent} positions). 
It provides a contradiction.



\begin{lemma}[Key lemma]%
\label{lem:k-nodes-last-key}
Let $u \in A^*$ and $\mc{F} \in \FacK{\mu}{}(u)$.
Assume that there exists a sequence $\transfont{T}_1, \dots, \transfont{T}_k$
of \kl(LAST){submachines}
of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_k \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(LAST){head} of $\transfont{U}$;
\item $|\valK{\transfont{T}_1}{u}(i_1)|_{\transfont{T}_2} \neq 0$ and
$\valK{\transfont{T}_k}{\omarK{u}{i_{k-1}}}(i_k) \neq \varepsilon$;
\item for all $2 \le j \le k{-}1$, $| \valK{\transfont{T}_j}{\omarK{u}{i_{j-1}}}(i_j) |_{\transfont{T}_{j+1}} \neq 0$;
\item for all $1 \le j \le k{-}1$, $\originK{\mc{F}}(i_j)$
and $\originK{\mc{F}}(i_{j+1})$ are \kl(NOD){independent};
\end{itemize}
Then $\transfont{U}$ is \kl(LAST){pumpable}.
\end{lemma}

\begin{proof}[idea] As for \cref{lem:k-nodes-blind-key},
the key observation is that \kl(LAST){pumpability}
follows as soon as the nodes $\originK{\mc{F}}(i_j)$ are
two by two \kl(NOD){independent}. Furthermore, this condition
can be obtained by duplicating some nodes  in $\mc{F}$.
\end{proof}









\section{Making the two last pebbles visible}

\label{sec:last-last}

\AP
We can define a similar model to that of \kl{last $k$-pebble
transducer}, which sees the two last calling positions instead of only the previous one.
Let us name this model a \intro{last-last $k$-pebble transducer}.
A very natural question is to know whether we can
show an analog of \cref{the:minimize-main} for these machines.

Note that for $k=1,2$ and $3$, a \kl{last-last $k$-pebble transducer} is
exactly the same as a \kl{$k$-pebble  transducer}. Hence the function
$\isqK$ of \cpageref{page:isq} is such that $|\isqK(u)| = \mc{O}(|u|^2)$
and can be computed by  a \kl{last-last $3$-pebble transducer}, but it cannot be computed by
a \kl{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 \kl{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.

\begin{theorem}
\label{the:fail-last-last}
For all $k \ge 2$, there exists a function $f:A^* \rightarrow B^*$ such that 
$|f(u)| = \mc{O}(|u|^2)$ and that can be computed by
a \kl{last-last $(2k{+}1)$-pebble transducer},
but not by a \kl{last-last $2k$-pebble transducer}.
\end{theorem}

\begin{proof}[idea] We re-use a counterexample introduced by
Boja{\'{n}}czyk in \cite{bojanczyk2022growth} to show a similar
failure result for the model of \kl{$k$-pebble transducers}.
\end{proof}







\section{Outlook}

This paper somehow settles the discussion concerning the variants
of \kl{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 \kl{last-last pebble transducers}).


As observed in \cite{engelfriet2007xml}, one can extend
\kl{last pebble transducers} by allowing the recursion height
to be unbounded  (in the spirit of
\intro{marble transducers} \cite{doueneau2020register}).
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 \kl{last $k$-pebble transducer}).


\subsubsection{Acknowledgements.} The author is grateful to Tito Nguy{\^{e}}n
for suggesting the study of the recursion height for \kl{last pebble transducers}.



\newpage

 \bibliographystyle{splncs04}
















\section{Omitted proofs of \cref{sec:blind-proof}}


\subsection{Proof of \cref{lem:growth-blind}}

Let $w_i \in A^*$ be such that $\mu(w_i) = \ell_i$,
 $w'_i \in A^*$ be such that $\mu(w'_i) = r_i$ and
$u_i \coloneqq w_i a_i w'_i$, for $1 \le i \le k$.
Let $v_0, \dots, v_k \in A^*$ such that
$\mu(v_i) = m_i$ for all $1 \le i \le k$.
Let $f_i$ be the function
computed by $\transfont{T}_i$ for all $1 \le i \le k$.

It is easy to see that $|f_k(v_0 u_1^{X} \cdots u_k^{X} v_k)| \ge (X{-}2)$.
Indeed, $\transfont{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 \ge i \ge 1$
that $|f_i(v_0 u_1^{X} \cdots u_k^{X} v_k)| \ge (X{-}2)^{k-i+1}$.
The upper bound follows since $\transfont{B}$ is
a \kl{blind $k$-pebble transducer}, thus
$|f(v_0 u_1^{X} \cdots u_k^{X} v_k)| = \theta(X^k)$. 



\subsection{Additional arguments in \cref{ssec:minimize-blind}}


We first justify that the construction of  $\ov{\transfont{U}}$ in \cref{ssec:minimize-blind} indeed
reduces the recursion height of $\transfont{U}$ by $1$. This statement was claimed
on \cpageref{sta:k:blind}.


\begin{claim} The machine $\ov{\transfont{U}}$ described in  \cref{ssec:minimize-blind}
has recursion height $k{-}1$.
\end{claim}


\begin{proof} Recall that the recursion height corresponds to the
number of nested \textbf{Call} instructions, plus $1$ (due to the \kl(BLIND){head}).
We first show by (decreasing) induction on $1 \le \ell \le k$
that if  $\transfont{T}$ is the root of a subtree of $\transfont{U}$ whose
recursion height is $1 \le \ell \le k$, then
$\normalK{\transfont{T}}$ has recursion height
$\ell$ as well.\\
Then, we show by (decreasing) induction on $1 \le \ell \le k$
that if  $\transfont{T}$ is the root of a subtree of $\transfont{U}$ whose
recursion height is $\ell$, then $\simBlindK{\transfont{T}}$ has recursion
height $\ell{-}1$. Indeed, the base case $\ell = 2$ is justified by
\cref{line:2-way-blind} in \cref{algo:blind-minimization-simplify}
(there are no calls since we inline all the computations).
For $\ell > 2$ the function $\simBlindK{\transfont{T}}$ inlines 
$\normalK{\transfont{T}'}$ of recursion height $\ell{-}1$ and
makes a recursive call to $\simBlindK{\transfont{T}'}$ whose
height is $\ell{-}2$  by induction hypothesis.\\
The result follows since the \kl(BLIND){head} of $\transfont{U}$ is
the root of the tree describing  $\transfont{U}$,
which has  recursion height $k$ by definition of a \kl{blind $k$-pebble transducer}.
\end{proof}


Since we have justified in the main paper how each function of $\ov{\transfont{U}}$ 
can be implemented by a \kl{two-way transducer}, then $\ov{\transfont{U}}$ is indeed a
\kl{blind $(k{-}1)$-pebble transducer}. Now, we justify a claim 
of \cpageref{sta:k:2}, that is used to show that the output in \cref{line:2-way-blind}
of  \cref{algo:blind-minimization-simplify} must be bounded.

\begin{claim} Assume that, in the execution of $\ov{\transfont{U}}$ on input $u \in A^*$,
we reach \cref{line:2-way-blind}  in  \cref{algo:blind-minimization-simplify} and that
$\valK{\transfont{T}'}{u}(i') \neq \varepsilon$ for $i' \not \in \FroK{\mc{F}}(\mc{F})$.
Then the conditions of \cref{lem:k-nodes-blind-key} hold, that is
there exists $\mc{F} \in \FacK{\mu}{}(u)$, a sequence $\transfont{T}_1, \dots, \transfont{T}_k$
of \kl(BLIND){submachines} of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_k \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(BLIND){head} of $\transfont{U}$;
\item  for all $1 \le j \le k{-}1$, $|\valK{\transfont{T}_j}{u}(i_j)|_{\transfont{T}_{j+1}} \neq 0$
and $\valK{\transfont{T}_k}{u}(i_k) \neq \varepsilon$;
\item for all $1 \le j \le k$, $i_j \not \in \FroK{\mc{F}}(\mc{F})$
(i.e. $\originK{\mc{F}}(i_j) \in \IteK{\mc{F}}$).
\end{itemize}
\end{claim}

\begin{proof} Let $\transfont{T}$ be a \kl(BLIND){submachine} of $\transfont{U}$
which is not a leaf (i.e. it labels the root of a subtree of height $>1$).
We claim that for $\simBlindK{\transfont{T}}(u)$ to be called when executing
$\ov{\transfont{U}}$ on input $u \in A^*$, there must exist a sequence $\transfont{T}_1, \dots, \transfont{T}_{\ell}$
of \kl(BLIND){submachines} of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_{\ell-1} \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(BLIND){head} of $\transfont{U}$ and $\transfont{T}_{\ell} = \transfont{T}$;
\item  for all $1 \le j \le \ell{-}1$, $|\valK{\transfont{T}_j}{u}(i_j)|_{\transfont{T}_{j+1}} \neq 0$;
\item for all $1 \le j \le \ell{-}1$, $i_j \not \in \FroK{\mc{F}}(\mc{F})$
where $\mc{F} \coloneqq \forK{\mu}(u)$.
\end{itemize}
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 \kl{frontier} on the root.\\
Finally, by considering $\transfont{T}$ the root of a subtree of height $2$, we see that the conditions
of  \cref{lem:k-nodes-blind-key}  must hold if we reach
we reach \cref{line:2-way-blind}  in $\simBlindK{\transfont{T}}$ and if
$\valK{\transfont{T}'}{u}(i') \neq \varepsilon$ for $i' \not \in \FroK{\mc{F}}(\mc{F})$.
\end{proof}


To conclude about the omitted proofs in \cref{ssec:minimize-blind},
it remains to show \cref{lem:k-nodes-blind-key}.
This is the purpose of \cref{ssec:proof:lem-blind}.

\subsection{Proof of \cref{lem:k-nodes-blind-key}}

\label{ssec:proof:lem-blind}


Assume that the conditions of \cref{lem:k-nodes-blind-key} hold
and let $\mf{t}_j \coloneqq \originK{\mc{F}}(i_j)$ for all $1 \le j \le k$.
If the $\mf{t}_j$ are two by two \kl(NOD){independent},
then each $\mf{t}_j$ is surrounded by two nodes
whose \kl{frontiers} cannot contain a position $i_{j'}$
for some $1 \le j' \le k$. The image of the factor of $u$
which is below these nodes provides an idempotent $e_j$.
It can easily be concluded that $\transfont{U}$ is \kl(BLIND){pumpable}
(see also \cite[Lemma E.5]{doueneau2022hiding}).


\input{parts/fig-copy-forest.tex}



Now, we suppose that the $\mf{t}_j$ are
not necessarily two by two \kl(NOD){independent}.
Let us show how to make the number of \kl(NOD){dependent} couples
of $(\mf{t}_{j_1}, \mf{t}_{j_2})$ decrease strictly, while preserving the properties of \cref{lem:k-nodes-blind-key}.
Indeed, repeating this process will enable us to
make all the nodes two by two \kl(NOD){independent}.
Assume that $\mf{t}_{\ell_1}$ \kl(NOD){observes} $\mf{t}_{\ell_2}$
for some $1 \le \ell_1 \neq \ell_2 \le k$. To simplify the proof,
we assume that $\mf{t}_{\ell_2}$ is an ancestor
of $\mf{t}_{\ell_1}$ (the case of the immediate sibling of
an ancestor is similar).
Let $\mc{F}'$ be $\mc{F}$ in which the subtree
 $\mf{t}_{\ell_2}$ has been copied $3$ times
(since $\mf{t}_{\ell_2}$ is an \kl{iterable node},
then $\mc{F}'$ still a \kl{$\mu$-forest}), see \cref{fig:making-nodes-far}.
We define for $1 \le j \le k$ the nodes $\mf{t}'_{j} \in \NodK{\mc{F}'}$
as follows:
\begin{itemize}
\item if $j = \ell_2$, then $\mf{t}'_{j}$ is (the root of) the third copy
of $\mf{t}_j$;
\item else if $j$ is such that $\mf{t}_j$ was a descendant
of $\mf{t}_{\ell_2}$ (including $\mf{t}_{\ell_1}$), then we let $\mf{t}'_{j}$
be the corresponding node in the first copy of $\mf{t}_j$;
\item else $\mf{t}_j$ was in the rest of $\mc{F}$,
and we let  $\mf{t}'_j$ be the corresponding
node in $\mc{F}'$.
\end{itemize}


Observe that now, $\mf{t}'_{\ell_1}$ and $\mf{t}'_{\ell_2}$
are not \kl(NOD){dependent}. Furthermore if $\mf{t}_{j_1}$
and $\mf{t}_{j_2}$ were \kl(NOD){independent}, then 
$\mf{t}'_{j_1}$ and $\mf{t}'_{j_2}$ are also \kl(NOD){independent}.
Let $u' \in A^*$ be the word such that $\mc{F}' \in \FacK{\mu}{}(u')$.
We also define $1 \le i'_1, \dots, i'_k \le |u'|$ as the positions
which correspond to the former $1 \le i_1, \dots, i_k \le |u|$
in the \kl{frontiers} of $\mf{t}_1', \dots, \mf{t}'_k$
in the new \kl{$\mu$-forest} $\mc{F}'$. The conditions of \cref{lem:k-nodes-blind-key}
still hold, because $\valK{\transfont{T}_j}{u}(i_j) = \valK{\transfont{T}_j}{u'}(i'_j)$
(indeed, we have only duplicated an \kl{iterable node}, which does
neither modify the \kl{context} around $i'_j$ nor its \kl{crossing sequence}).




\section{Omitted proofs of \cref{sec:last-proof}}



\subsection{Proof of \cref{lem:growth-last}}

The proof is similar to that of \cref{lem:growth-blind}.
Let $w_i \in A^*$ be such that $\mu(w_i) = \ell_i$,
 $w'_i \in A^*$ be such that $\mu(w'_i) = r_i$,
$u_i \coloneqq w_i a_i w'_i$ and $\marq{u_i} \coloneqq w_i \marq{a_i} w'_i$,
for $1 \le i \le k$.
Let $v_0, \dots, v_k \in A^*$ such that
$\mu(v_i) = m_i$ for all $1 \le i \le k$.
Let $f_i$ be the function
computed by $\transfont{T}_i$ for all $1 \le i \le 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 \ge 2$,
for all $1 \le Y \le X{-}2$:
\begin{equalign*}
f_k(v_0 u_1^X \cdots v_{k-2} (u_{k-1}^Y \marq{u_{k-1}} u_{k-1}^{X-Y-1}) v_{k-1} u_k^X) \ge (X-2).
\end{equalign*}
Observe that the use of $u_{k-1}^Y \marq{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 $\transfont{T}_k$ was done. Finally, we conclude by induction
in a similar way to \cref{lem:growth-blind}.





\subsection{Additional arguments in \cref{ssec:minimize-last}}



We first justify that the construction of  $\ov{\transfont{U}}$ in \cref{ssec:minimize-blind} indeed
reduces the recursion height of $\transfont{U}$ by $1$. This statement was claimed
on \cpageref{sta:last:k}.


\begin{claim} The machine $\ov{\transfont{U}}$ described in  \cref{ssec:minimize-last}
has recursion height $k{-}1$.
\end{claim}


\begin{proof} Recall that the recursion height corresponds to the
number of nested \textbf{Call} instructions, plus $1$ (due to the \kl(LAST){head}).
We first show by (decreasing) induction on $1 \le \ell \le k$
that if  $\transfont{T}$ is the root of a subtree of $\transfont{U}$ whose
recursion height is $1 \le \ell \le k$, then
$\normalongK{\transfont{T}}{\rho}$ has recursion height
$\ell$ as well.\\
Then, we show by (decreasing) induction on $2 \le \ell \le k$
that if  $\transfont{T}$ is the root of a subtree of $\transfont{U}$ whose
recursion height is $\ell$, then $\simLastK{\transfont{T}}{\rho}$ has recursion
height $\ell{-}1$. Indeed, the base case $\ell = 2$ is justified by
\cref{line:key-blind-minimization} in \cref{algo:last-minimization-simplify}
(there are no calls).
For $\ell > 2$ the function $\simLastK{\transfont{T}}{\rho}$ inlines some
$\normalongK{\transfont{T}'}{\rho'_j}$ of recursion height $\ell{-}1$ and
makes recursive calls to $\simLastK{\transfont{T}'}{\rho_j}$ whose
height is $\ell{-}2$  by induction hypothesis.\\
The result follows since the \kl(LAST){head} of $\transfont{U}$ is
the root of the tree describing  $\transfont{U}$,
which has  recursion height $k$ by definition of a \kl{last $k$-pebble transducer}.
\end{proof}

Now, let us justify a claim  of \cpageref{sta:last:2}, that is used to show
that the output of \cref{line:key-blind-minimization}
in \cref{algo:last-minimization-simplify} is indeed empty.

\begin{claim} Assume that, in the execution of $\ov{\transfont{U}}$ on input $u \in A^*$,
we reach \cref{line:key-blind-minimization}
in \cref{algo:last-minimization-simplify} and that
the output of $\transfont{T}'$ along $\rho'_j$ is not empty.
Then the conditions of \cref{lem:k-nodes-last-key} hold, that is
there exists $\mc{F} \in \FacK{\mu}{}(u)$, a sequence $\transfont{T}_1, \dots, \transfont{T}_k$
of \kl(LAST){submachines} of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_k \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(LAST){head} of $\transfont{U}$;
\item $|\valK{\transfont{T}_1}{u}(i_1)|_{\transfont{T}_2} \neq 0$ and
$\valK{\transfont{T}_k}{\omarK{u}{i_{k-1}}}(i_k) \neq \varepsilon$;
\item for all $2 \le j \le k{-}1$, $| \valK{\transfont{T}_j}{\omarK{u}{i_{j-1}}}(i_j) |_{\transfont{T}_{j+1}} \neq 0$;
\item for all $1 \le j \le k{-}1$, $\originK{\mc{F}}(i_j)$
and $\originK{\mc{F}}(i_{j+1})$ are \kl(NOD){independent};
\end{itemize}
\end{claim}

\begin{proof} Let $\transfont{T}$ be a \kl(LAST){submachine} of $\transfont{U}$
which is neither a leaf (i.e. it labels the root of a subtree of height $>1$) nor the
\kl(LAST){head} of $\transfont{U}$ (i.e. not the root of $\transfont{U}$).
We claim that for $\simLastK{\transfont{T}}{\rho}~(v)$ to be called whithin
the execution of $\ov{\transfont{U}}$ on input $u \in A^*$, there must exist a sequence
$\transfont{T}_1, \dots, \transfont{T}_{\ell}$
of \kl(LAST){submachines} of $\transfont{U}$ and a sequence of positions 
$1 \le i_1, \dots, i_{\ell-1} \le |u|$ such that:
\begin{itemize}
\item $\transfont{T}_1$ is the \kl(LAST){head} of $\transfont{U}$;
\item $v = \omarK{u}{i_{\ell-1}}$;
\item $|\valK{\transfont{T}_1}{u}(i_1)|_{\transfont{T}_2} \neq 0$ and
for all $2 \le j \le k{-}1$, $| \valK{\transfont{T}_j}{\omarK{u}{i_{j-1}}}(i_j) |_{\transfont{T}_{j+1}} \neq 0$;
\item for all $1 \le j \le \ell{-}2$, $\originK{\mc{F}}(i_j)$
and $\originK{\mc{F}}(i_{j+1})$ are \kl(NOD){independent},
where we define $\mc{F} \coloneqq \forK{\mu}(u)$;
\item for all $(i,q) \in \rho$, $\originK{\mc{F}}(i_{\ell-1})$ and $\originK{\mc{F}}(i)$
are \kl(NOD){independent}
\end{itemize}
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 \kl(POS){dependent} on the calling position.\\
Finally, by considering $\transfont{T}$ the root of a subtree of height $2$, we see that the conditions
of  \cref{lem:k-nodes-last-key}  must hold if we reach
\cref{line:key-blind-minimization} in some $\simLastK{\transfont{T}}{\rho}$
called in $\ov{\transfont{U}}$ and if
the output of $\transfont{T}'$ along $\rho'_j$ is not empty.
\end{proof}



To conclude about the omitted proofs in \cref{ssec:minimize-last},
it remains to show \cref{lem:k-nodes-last-key,lem:struct-O2}.
This is the purpose of \cref{ssec:proof:lem-last,ssec:proof:lem-O2}.


\subsection{Proof of \cref{lem:struct-O2}}

\label{ssec:proof:lem-O2}

Let $1 \le i \le |u|$, $\mf{t} \coloneqq \originK{\mc{F}}(i)$ and $\mf{t}_{1}$ (resp. $\mf{t}_2$)
be its immediate left (resp. right) sibling (they exist whenever $\mf{t} \in \IteK{\mc{F}}$,
i.e. here $\mf{t} \neq \mc{F}$). We show that:
\begin{equalign*}
\ObDoK{i} \smallsetminus \ObUpK{i}  = [\min(\FroK{\mc{F}}(\mf{t}_1)) : \max(\FroK{\mc{F}}(\mf{t}_2))] \smallsetminus \{\FroK{\mc{F}}(\mf{t}_1), \FroK{\mc{F}}(\mf{t}),
\FroK{\mc{F}}(\mf{t}_2)\}.
\end{equalign*}


Let us assume that $\mf{t}_1$ and $\mf{t}_2$ are \kl{iterable nodes} of $\mc{F}$
(the other cases are similar). By considering the forest of \cref{fig:observation},
it can be noted that $\ObDoK{i}$ is the interval
$[\min(\FroK{\mc{F}}(\mf{t}_1)) : \max(\FroK{\mc{F}}(\mf{t}_2))]$. We conclude
since $\mf{t}, \mf{t}_1$ and $\mf{t}_2$ are the only \kl{iterable nodes}
that both \kl(NOD){observe} $\mf{t}$ and that $\mf{t}$ \kl(NOD){observes}.

Therefore $\ObDoK{i} \smallsetminus \ObUpK{i}$ is the union of a bounded
number of intervals (since the \kl{frontiers} have bounded size).
It is easy to observed that the ``borders'' of these intervals
can easily be recovered by a \kl{lookaround}, if $\mf{t}$ (or $i$) is given.





\subsection{Proof of \cref{lem:k-nodes-last-key}}

\label{ssec:proof:lem-last}

The proof is similar to that of \cref{lem:k-nodes-blind-key}.
The goal is to show that the for $1 \le j \le k$, the
$\mf{t}_j \coloneqq \originK{\mc{F}}(i_{j})$ 
can be chosen two by two \kl(NOD){independent} 
(in the hypothesis, it is only assumed for the consecutive pairs
$(\mf{t}_j, \mf{t}_{j+1})$).

For this, we show once more how to make the
number of \kl(NOD){dependent} nodes decrease strictly,
while preserving the properties of \cref{lem:k-nodes-last-key}.
Assume that $\mf{t}_{\ell_1}$ \kl(NOD){observes} $\mf{t}_{\ell_2}$
for some $1 \le \ell_1 \neq \ell_2 \le k$ (note that $\ell_1$
and $\ell_2$ are not consecutive). To simplify the proof,
we assume that $\mf{t}_{\ell_2}$ is an ancestor
of $\mf{t}_{\ell_1}$ (the case of the immediate sibling of
an ancestor is similar). We build $\mc{F}' \in \FacK{\mu}{}(u')$
as in the proof of \cref{lem:k-nodes-blind-key} (see \cref{fig:making-nodes-far}),
and define the new nodes $\mf{t}'_{1}, \dots, \mf{t}'_{k} \in \NodK{\mc{F}'}$
in the same way. We also define $1 \le i'_1, \dots, i'_k \le |u'|$ as the positions
which correspond to the former $1 \le i_1, \dots, i_k \le |u|$
adapted to the new nodes $\mf{t}'_{1}, \dots, \mf{t}'_{k}$.

Now, we justify that $\valK{\transfont{T}_j}{\omarK{u}{i_{j-1}}}(i_j) = \valK{\transfont{T}_j}{\omarK{u'}{i'_{j-1}}}(i'_j) $
for all $2 \le j \le k$. This is the only difference with the proof of
of \cref{lem:k-nodes-blind-key} that we need to treat:
\begin{itemize}
\item 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 \kl(NOD){dependent})
and similarly $j{-}1 \neq \ell_2$.
The result holds because we only iterate an \kl{iterable node};
\item if both $i_{j-1}$ and $i_{j}$ do not belong to this subtree,
the argument is similar;
\item 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 \kl(NOD){independent}.
Indeed, it implies that $i_j$ cannot be ``below'' an immediate sibling of
$\mf{t}_{\ell_2}$. Hence duplicating this \kl{iterable node} will not
change the monoid value between positions $i_{j-1}$ and $i_j$. 
\end{itemize}











\section{Proof of \cref{the:fail-last-last}}


Let $A$ be an alphabet and $k \ge 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 \kl{factorization forests},
$T^k_A$ can be seen as a regular word language
over the alphabet $\apar{A} \coloneqq A \uplus \{\langle, \rangle\}$.
Given such a tree, we say that the
root has \intro{height} $1$, its children \kl{height} $2$,
etc. and the leaves
have \kl{height} $k$.

Now, we describe for all $k \ge 1$ a
function $\intro*\zebraK{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{\'{n}}czyk in \cite{bojanczyk2022growth}.
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 $\zebraK{1}$.
It takes as input a tree of height $2$ of shape
$\tree{\tree{u_1},\tree{u_2}, \cdots, \tree{u_n}}$ and it produces
a tree of height  $3$ whose $i$-th child of the root
is $\tree{\tree{u_i\#u_1}, \cdots  ,\tree{u_i\#u_n}}$
(i.e. the tuples are ordered lexicographically).
This function be implemented by a \kl{$3$-pebble transducer}
(i.e.  a \kl{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 $\zebraK{1}$ can be seen as a variant
of $\ulsq$ (see \cref{ex:ulsq}).


Now, the function $\zebraK{2}$ is described formally
in \cref{algo:zebra}.


\input{parts/algo-zebra.tex}


Observe that $\zebraK{2}$ no longer produces
the tuples $u \# v$ in a lexicographic
ordering. Indeed, it corresponds to two ranges over the leaves
of the original tree (one with $i_{1},i_2$ and one with $j_1,j_2)$
which are highly entangled. It is easy to guess how to extend
 \cref{algo:zebra}, in order to define $\zebraK{k}$ using $2k$ nested loops.
 
 Originally, the  $\zebraK{k}$ functions were used in order
 to show that the minimal number of layers and the growth of the output
 do not coincide for \kl{pebble transducers}, as claimed
 in \cref{the:fail-pebble}. 



\begin{theorem}[{\cite[section 3]{bojanczyk2022growth}}]
\label{the:fail-pebble}
For all $k \ge 1$, the function $\zebraK{k}$ is such that
$|\zebraK{k}(u)| = \mc{O}(|u|^2)$. Furthermore, it
can be computed by a \kl{$(2k{+}1)$-pebble transducer}
but not by a \kl{$2k$-pebble transducer}.
\end{theorem}


As a consequence, $\zebraK{k}$ cannot be computed by
a \kl{last-last $2k$-pebble transducer}. To show \cref{the:fail-last-last},
we only need to justify that  $\zebraK{k}$ can be computed
by \kl{last-last $(2k{+}1)$-pebble transducer}. This is indeed
the case: it uses its $2k$ first layers to describe the nested loops on $i_1, j_1, i_2,j_2, \dots, i_k, j_k$
and the last one to range over the labels of the tuple of leaves and output them
(see \cref{algo:zebra}). The key observation is that it only needs to see the two last
loop indexes, since this information is sufficient to find their children.
