\axiom{\recprefixed{\vec{p}\prefixcon x^\v\fs{\dots,f^{\w}=\L,\dots}}{\L}}
\infLabel{\rec~~\sideCondition{\w is fresh}}
\unaryInf{\recprefixed{\vec{p}\prefixcon x^\v\fs{\dots,f=\L,\dots}}{f}}
\end{bprooftree}
\\
\begin{bprooftree}
\axiom{\recprefixed{\vec{p} \prefixcon x^\v\fs{B,f_1=\L_1,\dots,f_k=\L_k}}{\L_0}}
\infLabel{\Let}
\unaryInf{\recprefixed{\vec{p} \prefixcon x^\v\fs{B}}{\letin{f_1=\L_1,\dots,f_k=\L_k}{\L_0}}}
\end{bprooftree}
\caption{Formulation of the local translation rules in \cref{fig:trans-local} in the form of inference rules.}
\label{fig:trans-local-proof-system}
\end{figure}

%TODO:  term graph translation steps are, roughly speaking, converse to readback steps.
%   This, however, is not true for the term graph translation defined in \cref{fig:def:graphsem:lhotgs}
%   because the readback synthesises \Let-expressions by local rule application during a post-order traversal over the spanning tree,
%   whereas the translation of a \Let-expression spawns binding translations immediately.
%   The solution is to define a variant of the graph translation
%   in which bindings in \Let-expressions are only translated when their calls have been reached during
%   the translation of the body or the definitions of other already translated bindings.
%   See \cref{fig:trans-local} for modifications.

%   The idea is that there is a close relationship
%   between readback steps and term graph translations steps
%   in the sense that they are each others converse.
%   However, this is not true for the term graph translation defined in \cref{fig:def:graphsem:lhotgs}
%   because the readback synthesises \Let-expressions by local rule application during a post-order traversal over the spanning tree,
%   whereas the translation of a \Let-expression spawns binding translations immediately.
%   The solution is to define a variant of the graph translation
%   in which bindings in \Let-expressions are only translated when their calls have been reached during
%   the translation of the body or the definitions of other already translated bindings.
%   See \cref{fig:trans-local} for modifications.

%TODO: Readback is a proper inverse for readback terms!
%TODO: This warrants an alternative approach!
\begin{proof}[Proof Idea]
Graph translation steps can be linked with corresponding readback steps in order to establish that the former roughly reverse the latter. Roughly, because e.g.\ reversing a λ-readback step necessitates both a λ- and a \Let-translation step. Therefore, this correspondence holds only for a modification of the translation rules \rulestranslambdaletreccaltoltgs from \cref{fig:def:graphsem:lhotgs}, shown in \cref{fig:def:graphsem:ltgs} where the rules \Let (for \Let-expressions) and \f (for occurrences of function variables) are replaced by the locally-operating versions in \cref{fig:trans-local}. Moreover, the translation rules need to store entire function bindings in the prefix (not just function variables) as the readback rules do. To the augmented rules we also add a initiating rule
\begin{center}
\translation
\ltgnode{root}{\top};
\addPos{root}{\star};
%\node[above=of root](rb){\recprefixed{\starfs{}}{\L}}; \draw[->](rb) to (root);
\node[below=of root,shape=transbox,draw](body){\recprefixed{\starfs{}}{\L}};
\draw[->](root) to (body.north);
\draw[<-](root.north) to +(0mm,4mm);
\hspace*{3ex}
(start of translation of \lambdaletrec-term \L)
\end{center}
for creating a top vertex. Now the translation of a \Let-expression does no longer directly spawn translations of the bindings, but the bindings will only be translated later once their calls have been reached during the translation process of the body, or of the definitions of other already translated bindings. Note that in the \Let-rule in \cref{fig:trans-local} function bindings are associated with the rightmost variable in the prefix, which corresponds to choosing \m{l_i = n} in the \Let-rule in \cref{fig:def:graphsem:lhotgs}. While such a stipulation does not guarantee the eager-scope translation of every term, it actually does so for all \lambdaletrec-terms that are obtained by the readback (on these terms the such defined translation coincides with \graphsemC{\classltgs}{} from \cref{def:graphsem:lhotgs}).
\par Please find in \cref{fig:proof:thm:readback} a graphical argument for the stepwise reversal of readback steps through (augmented) translation steps. This establishes that graph translation steps reverse readback steps, and is the crucial step in the proof of the theorem. The proof uses induction on access paths, and an invariant that relates the eager-scope property localised for a vertex \v with the applicability of the \S-rule to the readback term synthesised at \v. Note that in most cases the sets of function bindings on the left-hand side (\m{\bar{B}_i}) and the right-hand side (\m{B_i}) differ, due to the freedoms of the function definition's positions in the translated \lambdaletrec-term (see \cref{readback-inverse}).
\par Note that \m{\cupdot} denotes a join of two sets of function definitions where a defined function always overrules an undefined function, such that for instance the following holds: \m{\set{f=x, g=?} \cupdot \set{f=?, g=?} = \set{f=x, g=?}}.
\end{proof}

\begin{figure}
\begin{hspread}
\fusionstepsimple{
\ltgnode{root}{\top};
\addPrefix{root}{};
\addPos{root}{\star};
\node[below=of root,shape=transbox,draw](body){\recprefixed{\starfs{}}{L}};
\draw[->](root) to (body.north);
\draw[<-](root.north) to +(0mm,4mm);
\ltgnode{root}{\top};
\addPos{root}{\star};
\addPrefix{root}{};
\node[above=of root](rb){\recprefixed{\starfs{}}{L}}; \draw[->](rb) to (root);
\node[below=of root](body){\recprefixed{\starfs{}}{L}}; \draw[->](root) to (body);
\node[above=of rb](text){\mlSideCondition{\L not a\\\Let-expression}};
\node[below=of body](antitext){\phantom{\mlSideCondition{\L not a\\\Let-expression}}};
\fusionstep{
\ltgnode{root}{\top};
\addPrefix{root}{};
\addPos{root}{\star};
\draw[<-](root.north) to +(0mm,4mm);
\node[below=of root,shape=transbox,draw](body){\recprefixed{\starfs{}}{\letin{B}{L}}};
\draw[->](root.south) to (body.north);
\ltgnode{root}{\top};
\addPrefix{root}{};
\addPos{root}{\star};
\draw[<-](root.north) to +(0mm,4mm);
\node[below=of root,shape=transbox,draw](body){\recprefixed{\starfs{B}}{L}};
\draw[->](root.south) to (body.north);
\ltgnode{root}{\top};
\addPrefix{root}{};
\addPos{root}{\star};
\node[above=of root](rb){\recprefixed{\starfs{}}{\letin{B}{L}}}; \draw[->](rb) to (root);
\node[below=of root](body){\recprefixed{\starfs{B}}{L}}; \draw[->](root) to (body);
\\
\fusionstepclap{
\node[draw,shape=transbox](lhs){\recprefixed{\vec{p}}{\app{\L_0}{\L_1}}};
\draw[<-](lhs.north) to +(0,4mm);
\node[node distance=6mm, above=of lhs]{\sideCondition{\m{\vec{p} = \v_0\fs{\bar{B}_0}\mcdots\v_n\fs{\bar{B}_n}}}};
\ltgnode{app}{@}; \node[node distance=4mm,below=of app](middle){};
\node[node distance=1mm,draw,shape=transbox,left=of middle](l){\recprefixed{\vec{p}}{\L_0}};
\node[node distance=1mm,draw,shape=transbox,right=of middle](r){\recprefixed{\vec{p}}{\L_1}};
\addPrefix{app}{\v_1 \dots \v_n};
\draw[->](app) to (l.north); \draw[->](app) to (r.north); \draw[<-](app.north) to +(0,4mm);
\ltgnode{app}{@};
\addPrefix{app}{\v_1 \dots \v_n};
\node[above=of app](rb){\recprefixed{\v_0\fs{B^l_0 \cupdot B^r_0}\mcdots\v_n\fs{B^l_n \cupdot B^r_n}}{\app{\L_0}{\L_1}}}; \draw[->](rb) to (app);
\node[below=of app](args){};
\node[node distance=0mm,left=of args] (l){\recprefixed{\v_0\fs{B^l_0}\mcdots\v_n\fs{B^l_n}}{\L_0}}; \draw[->,dashed](app) to (l);
\node[node distance=0mm,right=of args](r){\recprefixed{\v_0\fs{B^r_0}\mcdots\v_n\fs{B^r_n}}{\L_1}}; \draw[->,dashed](app) to (r);
\end{hspread}
\caption{Reversal of readback steps through translation steps}
\label{fig:proof:thm:readback}
\end{figure}

\begin{figure}
\ContinuedFloat
\begin{hspread}
\fusionstep
\node[draw,shape=transbox](lhs){\recprefixed{v_0\fs{\bar{B}_0}\mcdots v_{n-1}\fs{\bar{B}_{n-1}}}{\abs{v_n}{L}}};
\draw[<-](lhs.north) to +(0mm,4mm);
\node[draw,shape=transbox](body){\recprefixed{v_0\fs{\bar{B}_0}\mcdots v_{n-1}\fs{\bar{B}_{n-1}}\prefixcon v_n\fs{}}{L}};
\ltgnode[node distance=3mm,above=of body.north]{abs}{λ};
\addPos{abs}{v_n};
\addPrefix{abs}{v_1 \dots v_{n-1}};
\draw[<-](abs.north) to +(0mm,4mm);
\draw[->](abs) to (body.north);
\ltgnode{abs}{λ};
\addPos{abs}{v_n};
\addPrefix{abs}{v_1 \dots v_{n-1}};
\node[above=of abs](rb){\recprefixed{v_0\fs{B_0}\mcdots v_{n-1}\fs{B_{n-1}}}{\abs{v_n}{L}}}; \draw[->](rb) to (abs);
\node[below=of abs](body){\recprefixed{v_0\fs{B_0}\mcdots v_{n-1}\fs{B_{n-1}} \prefixcon v_n\fs{}}{L}}; \draw[->](abs) to (body);
\\
\\
\fusiontwostep{
\node[draw,shape=transbox](lhs){\recprefixed{\v_0\fs{\bar{B}_0}\mcdots\v_{n-1}\fs{\bar{B}_{n-1}}}{\abs{v_n}{\letin{\bar{B}}{\L}}}};
\draw[<-](lhs.north) to +(0mm,4mm);
\node[draw,shape=transbox](rhs){\recprefixed{\v_0\fs{\bar{B}_0}\mcdots\v_{n-1}\fs{\bar{B}_{n-1}}\prefixcon\v_n\fs{}}{\letin{\bar{B}}{\L}}};
\ltgnode[node distance=3mm,above=of rhs.north]{abs}{λ}; \addPos{abs}{\v_n};
\addPrefix{abs}{\v_1 \dots\,\v_{n-1}};
\draw[<-](abs.north) to +(0mm,4mm);
\draw[->](abs) to (rhs.north);
\node[draw,shape=transbox](rhs){\recprefixed{\v_0\fs{\bar{B}_0}\mcdots\v_{n-1}\fs{\bar{B}_{n-1}}\prefixcon\v_n\fs{\bar{B}}}{\L}};
\ltgnode[node distance=3mm,above=of rhs.north]{abs}{λ}; \addPos{abs}{\v_n};
\addPrefix{abs}{\v_1 \dots\,\v_{n-1}};
\draw[<-](abs.north) to +(0mm,4mm);
\draw[->](abs) to (rhs.north);
\ltgnode{abs}{λ};
\addPos{abs}{\v_n};
\addPrefix{abs}{\v_1 \dots\,\v_{n-1}};
\node[above=of abs](rb){\recprefixed{\vec{p}}{\abs{v_n}{\letin{B}{\L}}}}; \draw[->](rb) to (abs);
\node[below=of abs](body){\recprefixed{\vec{p} \prefixcon \v_n\fs{B}}{\L}}; \draw[->](abs) to (body);
\node[below=of body]{\sideCondition{\m{\vec{p} = \v_0\fs{B_0}\mcdots\v_{n-1}\fs{B_{n-1}}}}};
\end{hspread}
\caption[]{(continued) Reversal of readback steps through translation steps}
\end{figure}

\begin{figure}
\ContinuedFloat
\begin{hspread}
\fusionstep
\node[draw,shape=transbox](lhs){\recprefixed{\starfs{B_{0}}\:v_{1}\fs{B_{1}}\mcdots v_{n}\fs{B_{n}}}{v_{n}}};
\draw[<-](lhs.north) to +(0,4mm);
\ltgnode{var}{\0}; \draw[<-](var.north) to +(0,5mm);
\addPrefix{var}{v_{1}\mcdots v_{n}};
\node[node distance=4mm,right=of var](left){};
\ltgnode[node distance=3mm,above=of left,densely dashed]{abs}{λ}; \addPos{abs}{v_{n}};
\draw[->](var) -| (abs);
\ltgnode{var}{\0};
\addPrefix{var}{v_1 \dots v_n};
\node[node distance=10mm,above=of var](rb){\m{\recprefixed{\starfs{}\prefixcon v_{1}\fs{}\mcdots v_{n}\fs{}}{v_{n}}}};
\draw[->](rb) to (var);
\ltgnode[right=of var,yshift=5ex]{abs}{λ}; \draw[->,dotted](var) -| (abs);
\addPos{abs}{v_{n}};
\\
\\
\fusionthreestep{
\node[draw,shape=transbox](rhs){\m{\recprefixed{\starfs{\dots,f=f,\dots}}{f}}};
\draw[<-](rhs.north) to +(0,4mm);
\ltgnode{indir}{\indir};
\addPos{indir}{f};
\addPrefix{indir}{};
\draw[<-](indir.north) to +(0,4mm);
\node[node distance=3mm,draw,shape=transbox,below=of indir](rhs){\m{\recprefixed{\starfs{\dots,f=f,\dots}}{f}}};
\draw[->](indir) to (rhs.north);
\ltgnode{indir}{\indir};
\draw[->,bend right=120, looseness=8] (indir.south) to (indir.north);
\phantom{\draw[->,bend left=120, looseness=8] (indir.south) to (indir.north);}
\addPos{indir}{f};
\addPrefix{indir}{};
\draw[<-](indir.north) to +(0,4mm);
\ltgnode{bh}{\bh};
\addPrefix{bh}{};
\addPrefixswphantom{bh}{}; % for layouting
\draw[<-](bh.north) to +(0,4mm);
\ltgnode{bh}{\bh};
\addPrefix{bh}{};
\node[above=of bh](rb){\m{\recprefixed{\starfs{f=f}}{f}}}; \draw[->](rb) to (bh);
\node[below=of bh](bhb){\phantom{\m{\recprefixed{\starfs{f=f}}{f}}}}; \draw[color=white](bh) to (bhb);
\end{hspread}
\caption[]{(continued) Reversal of readback steps through translation steps}
\end{figure}

\begin{figure}
\ContinuedFloat
\begin{hspread}
\fusionstepclap{
\node[draw,shape=transbox](rhs){\m{\recprefixed{v_0\fs{\bar{B}_{0}}\mcdots v_{n-1}\fs{\bar{B}_{n-1} \prefixcon }v_n\fs{\bar{B}_{n},f=L}}{f}}};
\draw[<-](rhs.north) to +(0,4mm);
\ltgnode{indir}{\indir};
\addPos{indir}{f};
\addPrefix{indir}{v_{1}\mcdots v_{n}};
\draw[<-](indir.north) to +(0,4mm);
\node[node distance=3mm,draw,shape=transbox,below=of indir](rhs){\m{\recprefixed{v_0\fs{\bar{B}_{0}}\mcdots v_{n-1}\fs{\bar{B}_{n-1}}\prefixcon v_n\fs{\bar{B}_{n},f=L}}{f}}};
\draw[->](indir) to (rhs.north);
\ltgnode{I}{\indir};
\addPrefix{I}{v_{1}\mcdots v_{n}};
\addPos{I}{f};
\node[above=of I](rb){\m{\recprefixed{\twolines{v_0\fs{B_{0}}\mcdots v_{n-1}\fs{B_{n-1}}}{v_{n}\fs{B_{n}, f=L}}}{f}}}; \draw[->](rb) to (I);
\node[below=of I](succ){\m{\recprefixed{v_{0}\fs{B_{0}}\mcdots v_{n}\fs{B_{n}}}{L}}}; \draw[->] (I) to (succ);
\\
\\
\fusionstepclap{
\node[draw,shape=transbox](rhs){\m{\recprefixed{v_{0}\fs{\bar{B}_{0}}\mcdots v_{n-1}\fs{\bar{B}_{n-1}}\prefixcon v_{n}\fs{\bar{B}_{n},\,f = L}}{f}}};
\draw[<-](rhs.north) to +(0,4mm);
\ltgnode[densely dashed]{indir}{\indir};
\addPos{indir}{f};
\addPrefix{indir}{v_{1}\mcdots v_{n}};
\addPrefixswphantom{indir}{v_{1}\mcdots v_{n}};
\draw[<-,dotted](indir.north) to +(0,4mm);
\draw[->](indir.south) to +(0,-4mm);
\ltgnode{I}{\indir};
\addPrefix{I}{v_{1}\mcdots v_{n}};
\addPos{I}{f};
\node[above=of I](rb){\m{\recprefixed{v_{0}\fs{}\mcdots v_{n-1}\fs{}\prefixcon v_{n}\fs{f=\nodef}}{f}}};
\draw[->,dotted](rb) to (I);
\node[below=of I](succ){\phantom{\m{\recprefixed{\vec{p}\prefixcon v_{n+1}[B]}L}}}; \draw[->] (I) to (succ);
\end{hspread}
\caption[]{(continued) Reversal of readback steps through translation steps}
\end{figure}

\section{Complexity analysis}\label{sec:complexity}

Here we report on the complexity for the individual operations from the previous sections used form implementing maximal sharing and determining unfolding-equivalence.

In the lemma below, \cref{lem:complexity:graphsem} and \cref{lem:complexity:readback} justify \cref{methods:properties:efficiency} of our methods. Items \cref{lem:complexity:collapse} and \cref{lem:complexity:bisimilarity} detail the complexity of standard methods when used for computing bisimulation collapse and bisimilarity of λ-term-graphs. Note that first-order term graphs can be modelled by deterministic process graphs, and hence by DFAs [28]. Therefore bisimilarity of term graphs can be computed via language equivalence of the corresponding DFAs (in time \bigO{n α(n)} [43], where \m{α} is the quasi-constant \emph{inverse Ackermann function}) and bisimulation collapse via state minimisation of DFAs (in time \bigO{n \log n}) [27].

By \termsize{\L} we denote the size (number of symbols) of a \lambdaletrec-term \L. Also we denote by \graphsize{G} the size (number of vertices) of a term graph \G.

\begin{lemma}\label{lem:complexity}
\begin{enumerate}[(i)]
\item\label{lem:complexity:length:graphsem}
\m{\graphsize{\graphsemC{\classltgs}{\L}} ∈ \bigO{\termsize{\L}^2}} for \m{\L ∈ \Ter{\lambdaletreccal}}.
\item\label{lem:complexity:graphsem}
Translating \m{\L ∈ \Ter{\lambdaletreccal}} into \m{\graphsemC{\classltgs}{\L} ∈ \classltgs} takes time \bigO{\termsize{\L}^2}.
\item\label{lem:complexity:collapse}
Collapsing \m{\altg ∈ \classltgs} to \coll{\altg} is in \bigO{\graphsize{\altg} \log \graphsize{\altg}}.
\item\label{lem:complexity:bisimilarity}
Deciding bisimilarity of \m{\altg_1,\altg_2 ∈ \classltgs}
requires time \bigO{n α(n)} for \m{n = \max \set{\graphsize{\altg_1}, \graphsize{\altg_2}}}. %,
% and \sinvAck the quasi-constant inverse Ackermann function.
\item\label{lem:complexity:readback}
Computing the readback
\readback{\altg} for a given \m{\altg ∈ \classltgs} requires time
\bigO{n \log n}, for \m{n = \graphsize{\altg}}.
\end{enumerate}
\end{lemma}

See \cref{fig:ex:translation:quadratic} for an example that the size bound in item \cref{lem:complexity:length:graphsem} of the lemma is tight.

\begin{proposition}
\m{\graphsize{\graphsemC{\classltgs}{\L}} ∈ \bigO{\termsize{\L}^2}} for \lambdaletrec-terms \L.
\end{proposition}

\begin{figure}
Consider the finite λ-terms \m{\M_n} with \n occurrences of bindings \abs{x_2}{}:
\begin{equation*}
\abs{x_0}{\abs{x_1}{\app{\app{x_0}{x_1}}
\end{equation*}
\m{\termsize{\M_n} ∈ \bigO{n}}. But both the transformation of \m{\M_n} into de-Bruijn notation
\begin{equation*}
\abs{}{\abs{}{\app{\app{\S(\0)}{\0}}
\end{equation*}
and the rendering of \m{\M_n} with respect to the eager scope-delimiting strategy:
\begin{equation*}
\abs{}{\abs{}{\app{\app{\S(\0)}{\0}}
\end{equation*}
have size \bigO{n^2}.
\caption{Example of a sequence \m{\set{\M_n}_n} of finite λ-terms \m{\M_n} whose translation into λ-term-graphs grows quadratically in the size of \m{\M_n}.}
\label{fig:ex:translation:quadratic}
\end{figure}

Based on this lemma, and on further considerations, we obtain the following
complexity statements for our methods.

\begin{theorem}\label{thm:methods:complexity}
\begin{enumerate}[(i)]
\item
The computation, for a \lambdaletrec-term \L with \m{\termsize{\L} = n},
of a maximally compactified form
\m{{(\readback{} \circ \scoll \circ \graphsemC{\classltgs}{})}(\L)}
requires time \bigO{n^2 \log n}.
\newcommand\sSunsh{\m{\textsf{unsh}_{\S}}}
By using an \S-unsharing operation \sSunsh after the collapse,
a (typically smaller) \lambdaletrec-term \m{((\readback{} ∘ {{\sSunsh} ∘ {\scoll}} ∘ {\graphsemC{\classltgs}{})}){\L}}
of size \bigO{n \log n} can be obtained,
with the same time complexity.
\item
The decision of whether two \lambdaletrec-terms \m{\L_1} and \m{\L_2} are unfolding equivalent
requires time \m{\bigO{n^2} α(n)} for \m{n = \max \set{\termsize{\L_1},\termsize{\L_2}}}.
\end{enumerate}
\end{theorem}

% \begin{para}[algorithm for free variable analysis.]
% In the sequel the following concepts and notations are used.
% For this let \altg be a λ-term-graph with indirection vertices
% that is the translation of a \lambdaletrec-term
% according to the naive translation without \S-vertices.
% Let \V be the set of vertices of \altg.
% Note that \altg is a term graph that can be viewed as a directed graph with the edges directed
% from a vertex to its successors.
% Furthermore let \m{T} be a spanning tree of \altg, and \w a vertex of \altg.
% Then we define:
% % \begin{description}
% %   \item[\locfreevarsin{\altg}{\w}, the \emph{locally free λ-variable at \w in \altg}:]
% %     the set of λ-variable with free occurrences (as labellings of variable vertices)
% %     that are reachable on paths from \w in \altg
% %     before occurrences of indirection vertices (the start of translations of binding groups);
% %   \item[\locfreerecvarsin{\altg}{\w}, the \emph{locally free function variables at \w in \altg}:]
% %     the set of function variables that are directly reachable
% %     (as the labellings of indirection vertices, marking graph translations of binding groups)
% %     on paths from \w when reaching indirection vertices, but without trespassing any of them;
% %   \item[\globfreevarsin{\altg}{\w}, the \emph{free λ-variable at \w in \altg}:]
% %     λ-variable that have free occurrences (as labellings of variable vertices) reachable on paths from \w in \altg
% %     (the paths now also may trespass indirection vertices);
% %   \item[\reachfreevarsalong{T}{\w}, the \emph{reachable free λ-variable from \w along spanning tree T}:]
% %     λ-variable with free occurrences (as labellings of variable vertices)
% %     that are reachable from \w along a traversal of the spanning tree T below \w.
% % \end{description}
% Algorithm for computing \globfreevarsin{\altg}{\w} for all vertices \w in \altg,
% informal description:
% \begin{enumerate}
%   \item\label{alg:free:vars:step:1}
%     Perform a depth-first search of \altg, and thereby:
%     \begin{itemize}
%       \item
%         produce a spanning tree \m{T} of \altg;
%       \item
%         synthesise along the depth-first search (which defines
%         a traversal of the arising spanning tree \m{T}),
%         for every vertex \w,
%         the set \reachfreevarsalong{T}{\w}
%         in the form of search-tables;
%       \item
%         produce, by using Tarjan's scc (strongly connected compenents) algorithm \cite{tarj:1972},
%         for every vertex \w,
%         a link to the representative \sccrep{\w}
%         of the scc (strongly connected component) of \w in \altg
%         (implicitly a function \m{\ssccrep : \V → \V} is
%          constructed that maps a vertex u of \altg
%          to the representative \sccrep{u} of its scc)
%     \end{itemize}
%     After this phase it holds for every representative \v of an scc in \altg,
%     that is, for every vertex \v with \m{\sccrep{\v} = \v}:
%     \begin{gather}
%       \globfreevarsin{\altg}{\v}
%         =
%       \reachfreevarsalong{T}{\v}
%       \label{eq:reachfreevars}
%       \\
%       \text{\v is an indirection vertex (start of translation of \Let-binding)}
%       \notag
%     \end{gather}
%     (Note that \cref{eq:reachfreevars} does typically not hold for vertices
%      that are not representatives of scc's.)
%   \item\label{alg:free:vars:step:2}
%     Carry out a traversal of the spanning tree \m{T}, and thereby:
%     \begin{itemize}
%       \item
%         synthesise, for all vertices \w of \altg,
%         the set \freevarsin{\altg}{\w},
%         in the form of search-tables, making use of:
%         \begin{itemize}
%           \item
%             thereby also synthesised search tables for the sets \locfreevarsin{\altg}{\w} of locally free variables at \w, and
%             \locfreerecvarsin{\altg}{\w} of locally reachable function variables at \w, and
%           \item
%             looking up, for every locally reachable function variable \f defined at indirection vertex u,
%             the free variables \freevarsin{\altg}{\sccrep{u}} at the representative \sccrep{u} of u,
%             which have already been computed in step \cref{alg:free:vars:step:1}
%             (note that it holds:
%              \m{\freevarsin{\altg}{u}
%                 =
%               \freevarsin{\altg}{\sccrep{u}}}).
%         \end{itemize}
%     \end{itemize}
% \end{enumerate}

\section{Implementation}\label{sec:implementation}

We have implemented our methods in Haskell using the \href{http://www.cs.uu.nl/wiki/bin/view/HUT/AttributeGrammarSystem}{Utrecht University Attribute Grammar System}. The implementation is available at \url{http://hackage.haskell.org/package/maxsharing/}. Output produced for a number of examples from this thesis can be found in \cref{app:impl:showcase}. The output includes translations into λ-term-graphs (in DFA-form) according to different semantics, complete derivations w.r.t.\ these semantics, the bisimulation collapse of the λ-term-graphs and the readback thereof.

\section{Modifications, extensions and applications}\label{sec:applications}

We conclude by describing straightforward modifications, extensions, and promising areas of application for our methods.

\subsection{Modifications}\label{sec:conclusion:subsec:modifications}

\begin{para}[implicit sharing of λ-variable]
Our method introduces explicit sharing via \Let for multiple occurences of the same λ-variable. For instance the term \abs{x}{\app{x}{x}} is compactified into \abs{x}{\letin{f=x}{\app{f}{f}}}. Such explicit sharing of abstraction variables is excessive for many applications. This is easily resolved, by unsharing variable vertices before applying the readback, or by preventing the readback from introducing function bindings when only a variable vertex is shared.
\end{para}

\begin{para}[avoiding aliases produced by the readback]
The readback function in \cref{sec:readback} is sensitive to the degree of sharing of \S-vertices in the given λ-term-graph: it maps two λ-term-graphs that only differ in what concerns sharing of \S-vertices to different \lambdaletrec-terms. Typically, for λ-term-graphs with maximal sharing of \S-vertices this can produce function bindings that are just `aliases', such as \g is alias for \m{I} in \m{\L'_3} from \cref{ex:translations}. This can be avoided in two ways: by slightly adapting the readback function, or by performing maximal unsharing of \S-vertices before applying the readback as defined.
\end{para}

\begin{para}[preventing disadvantageous sharing]
Introducing sharing at compile-time can cause `space leaks', i.e.\ a needlessly high memory footprint, at run-time, because `a large data structure becomes shared [\dots], and therefore its space which before was reclaimed by garbage collection now cannot be reclaimed until its last reference is used' [50]. For this reason, realisations of CSE [11] prevent the introduction of such undesired sharing by suitable conditions that account for the type of potentially shared subexpressions, and their strictness in the program.
\par As our approach generalises CSE, it inherits this weakness, and the introduction sharing needs to be restricted in a similar fashion. Technically this can easily achieved by adding additional backlinks to prevent parts of the λ-term-graph from collapsing.
%	\par Here the bisimulation collapse can be restricted so that sharing is not introduced at vertices that should not be shared.
%   The bisimulation collapse can be restricted by modifying the graph interpretation
%   of \lambdaletrec-terms with subexpressions that should not be shared,
%   as identified by a preceding syntactical analysis.
%	More precisely, it can be prevented that any unshared vertex (in-degree one) from a pre-determined set of `sharing-unfit' vertices would have a shared vertex (in-degree greater than one) as its image in the bisimulation collapse.
%	This can be achieved by modifying the graph semantics \graphsemC{\classltgs}{}. Any set of sharing-unfit positions in \L gives rise to a set of sharing-unfit vertices in \graphsemC{\classltgs}{\L}. In the modification of \graphsemC{\classltgs}{\L}, special backlinks are added from every sharing-unfit vertex with in-degree one to its immediate successor. These backlinks prevent that such a sharing-unfit vertex \v can collapse with another vertex \m{\v'} without that also the predecessors of \v and \m{\v'} would collapse as well.
\end{para}

% \begin{para}[a more general notion of readback]
% Condition \cref{methods:properties:readback} is rather rigorous in that it
% imposes sharing structure on \lambdaletreccal that is particular to
% λ-term-graphs (degrees of \S-sharing). For a weaker definition of
% \cref{methods:properties:readback} based on \bisim^\S in
% place of isomorphism, a readback needs not be injective and readbacks exist for
% all translations.
% %For a given λ-term-graph \altg there exists a number of corresponding
% %\lambdaletrec-terms which could be related by a convertibility relation.
% \end{para}

\begin{para}[a more general notion of readback]
\cref{methods:properties:readback} is rather rigorous in that it imposes sharing structure on \lambdaletreccal that is specific to λ-term-graphs (degrees of \S-sharing). For a weaker definition of \cref{methods:properties:readback} with \m{\bisim^\S} in place of isomorphism, a readback does not have to be injective and independently of the degree of \S-sharing a readback function always exists.
\end{para}

\begin{para}[scope-closure strategies]
We focused on eager-scope translations since they maximise sharing. However, every scope-closure strategy [19] induces a translation and its own notion of maximal sharing.
\end{para}

\subsection{Extensions}\label{sec:conclusion:subsec:extensions}

\begin{para}[full functional languages]
In order to support programming languages that are based on \lambdaletreccal like Haskell, additional language constructs need to be supported. Such languages can typically be desugared into a core language, which comprises only a small subset of language constructs such as constructors, case statements, and primitives. These constructs can be represented in an extension of \lambdaletreccal\ by additional function symbols. In conjunction with a desugarer our methods are applicable to full programming languages.
\end{para}

\begin{para}[other programming languages, and calculi with binding constructs]
Most programming languages feature constructs for grouping definitions that are similar to \letrec. We therefore expect that our methods can be adapted to many imperative languages in particular, and may turn out to be fruitful for optimising compilers. Our methods for achieving maximal sharing certainly generalise to theoretical frameworks and calculi with binding constructs, such as the \pi-calculus [41], and higher-order rewrite systems (e.g.\ CRSs and HRSs, [51]) as used here for the formalisation of \lambdaletreccal.
\end{para}

\begin{para}[fully-lazy λ-lifting]
\newcommand\sreadbackC[1]{\m{\readback{}_{#1}}}
There is a close connection between our methods and fully-lazy λ-lifting [30, 33]. In particular, the required-variable and scope analysis of a \lambdaletrec-term \L on which the λ-term-graph translation \graphsemC{\classltgs}{\L} is based is analogous to the one needed for extracting from \L the supercombinators in the result \Hat{\L} of fully-lazy λ-lifting \L. Moreover, the fully-lazy λ-lifting transformation can even be implemented in a natural way on the basis of our methods. Namely as the composition \m{\sreadbackC{\textit{LL}} ∘ \graphsemC{\classltgs}{\cdot}} of the translation \graphsemC{\classltgs}{\cdot} into λ-term-graph, where \sreadbackC{\textit{LL}} is a variant readback function that, for a given λ-term-graph, synthesises the system \Hat{\L} of supercombinators, instead of the \lambdaletrec-term \readback{\L}.
\end{para}

\begin{para}[maximal sharing on supercombinator translations of \lambdaletrec-terms]
\lambdaletrec-terms \L correspond to supercombinator systems \m{S}, the result of fully-lazy lambda-lifting \L: the combinators in \m{S} correspond with `extended scopes' in \L, and supercombinator reduction steps on \m{S} correspond with weak β-reduction steps \L. In the case of λ-calculus this has been established by Balabonski [5]. Via this correspondence the maximal-sharing method for \lambdaletrec-terms can be lifted to obtain a maximal-sharing method systems of supercombinators obtained by fully-lazy lambda-lifting.
\end{para}

\begin{para}[non-eager scope-closure strategies]
We focused on eager-scope translations, because they facilitate maximal sharing, and guarantee that interpretations of unfolding-equivalent \lambdaletrec-terms are bisimilar. Yet every scope-closure strategy induces a translation and its own notion of maximal sharing. For adapting our maximal sharing method it however necessary to modify the translation into first-order term graphs in such a way that the image class obtained is closed under functional bisimulation (\classtgssiglambdaij{1}{2} is not closed under functional bisimulation, unlike its subclass \m{\eag{\classtgssiglambdaij{1}{2}} = \classltgs}). This can be achieved by using delimiter vertices also below variable vertices to close scopes that are still open \cite[report]{grab:roch:representations}.
\end{para}

% \begin{para}[weaker notions of sharing]
% The presented methods deal with sharing as expressed by \letrec
% that can be horizontal, vertical, or `twisted' (the superimposition of the former) [8].
% In contrast, μ expresses only vertical, and the
% traditional \Let only horizontal sharing. By restricting
% bisimulation, our methods can be adapted to languages with μ or \Let.
% % As the \letrec-construct does, our method supports vertical sharing,
% % horizontal sharing, as well as a superimposition of the two (`twisted sharing')
% % [8]. In contrast, μ supports only vertical sharing, and the
% % traditional \Let supports only horizontal sharing. By restricting
% % bisimulation our method can be adapted to languages with μ or \Let.

\begin{para}[weaker notions of sharing]
The presented methods deal with sharing as expressed by \letrec that is horizontal, vertical, or twisted (see \cref{horiz-vert-twisted-sharing}). By contrast, the μ-construct [8, 20] expresses only vertical, and the non-recursive \Let only horizontal, sharing (see \cref{horiz-vert-twisted-sharing}). By restricting bisimulation (either artificially or by adding special backlinks), our methods can be adapted to the λ-calculus with μ [20], or with \Let.
\end{para}

\subsection{Applications}\label{sec:conclusion:subsec:applications}

\begin{para}[maximal sharing at run-time]
Maximal sharing can be applied repeatedly at run-time in order to regain a maximally shared form, thereby speeding up evaluation. This is reminiscent of `collapsed tree rewriting' [49] for evaluating first-order term graphs represented as maximally shared dags. Since the state of a program in the memory at run-time is typically represented as a supercombinator graph, compactification by bisimulation collapse can take place directly on that graph (see \cref{sec:conclusion:subsec:extensions}), no translation is needed. Compactification can be coupled with garbage collection as bisimulation collapse subsumes some of the work required for a mark and sweep garbage collector. However, a compromise needs to be found between the costs for the optimisation and the gained efficiency.
%TODO: Superoptimality
\end{para}

% SUPER-OPTIMALITY (asperti, levy)
% One might even consider to apply maximal sharing dynamically to increase
% run-time efficiency of an evaluator much in the likeness of collapsed tree
% rewriting [49].
% Since at run-time the state of a program is not represented in the memory as a
% \lambdaletrec-term but say as a supercombinator graph, the compactification
% could take place directly on that graph; no translation would be necessary. The
% compactification could be coupled with the garbage collection process. As
% stated in \cref{rem:garbage} maximal sharing already subsumes some of the
% work required for a mark and sweep garbage collector.
% As with the compile-time optimisation the problem of finding a good balance
% between the costs for the optimisation and the gained efficiency remains to be
% addressed.
%If applied to an optimal evaluator in the sense of L\'evy's concept of
%\emph{family reduction} or \emph{optimal reduction} for λ-calculus
%[39] we could arrive at a super-optimal evaluator:
%However, implementations of optimal reduction
%only share redex families with the same creation history
%and do not
%  ``dynamically look for common subexpressions.
%    Levy's theory of optimality does not cover these cases,
%    which are neglected as a form of `syntactical coincidence'~'' \cite[fn.\hspace*{1.5pt}1]{aspe:copp:simo:2000},
%and hence:
%  ``theoretically, there could be super-optimal implementations''~(Ibid.).
%      \noindent
%      ``Theoretically, there could be super-optimal implementations,
%        where one dynamically looks for common subexpressions.
%        Levy's theory of optimality does not cover these cases,
%        which are neglected as a form of `syntactical coincidence'.''
%        \cite[fn.\hspace*{1.5pt}1]{aspe:copp:simo:2000}

\begin{para}[additional prevention of disadvantageous sharing]
While static analysis methods for preventing sharing that may be disadvantageous at run-time can be adapted from CSE to the maximal-sharing method (see \cref{sec:conclusion:subsec:modifications}), this has yet to be investigated for binding-time analysis [48] and a sharing analysis of partial applications [16].
for fine-tuning sharing of partial applications in supercombinator translations [16].
\end{para}

\begin{para}[compile-time optimisation]
Increasing sharing facilitates potential gains in efficiency. Our method generalises common subexpression elimination, but therefore it also inherits its shortcomings: the cost of sharing (e.g.\ of very small functions) might exceed the gain. In non-strict functional languages, sharing can cause `memory leaks' [11]. Therefore, similar as for CSE, additional dynamic analyses like binding-time analysis [48], and heuristics to restrict sharing in cases when it is disadvantageous [33, 16] are in order.
\end{para}

\begin{para}[code improvement]
In programming it is generally desirable to avoid duplication of code. As an extension of CSE, our method is able to detect code duplication. The bisimulation collapse of the term graph interpretation of a program can, together with the readback, provide guidance on how code can be written more compactly with less duplication. This optimisation has to be fine-tuned to avoid excessive behaviour like the explicit sharing of variable occurrences (see \cref{sec:conclusion:subsec:modifications}). Yet for this only lightweight additional machinery is needed, such as size constraints or annotations to restrict the bisimulation collapse.
\end{para}

\begin{para}[function equivalence]
Recognising whether two programs are equivalent in the sense that they implement the same function is undecidable. Still, this problem is tackled by proof assistants, and by automated theorem provers used in type-checkers of compilers for dependently-typed programming languages such as Agda. For such systems coinductive proofs are more difficult to find than inductive ones, and require more effort by the user. Our method for deciding unfolding-equivalence could contribute to finding coinductive proofs.
\end{para}

%TODO: auf generiertem Code gibt es noch mehr Gelegenheit zur Optimierung.

\bibliographystyle{thesis}
\begin{thebibliography}{10}

[1]
Zena~M. Ariola and Stefan Blom.
\newblock Cyclic Lambda Calculi.
\newblock In {\em Theoretical Aspects of Computer Software}, volume 1281 of
{\em Lecture Notes in Computer Science}, pages 77--106. Springer Berlin
Heidelberg, 1997.
\newblock \href {http://dx.doi.org/10.1007/BFb0014548}

[2]
Zena~M. Ariola and Jan~Willem Klop.
\newblock Equational Term Graph Rewriting.
\newblock {\em Fundamenta Informaticae}, 26(3):207--240, 1996.
\newblock \href {http://dx.doi.org/10.3233/FI-1996-263401}
{\path{doi:10.3233/FI-1996-263401}}, extended version as Vrije Universiteit
Amsterdam Technical Report IR--391.

[3]
Zena~M. Ariola and Jan~Willem Klop.
\newblock Lambda Calculus with Explicit Recursion.
\newblock {\em Information and Computation}, 139(2):154--233, 1997.
\newblock \href {http://dx.doi.org/10.1006/inco.1997.2651}

[4]
Andrea Asperti and Stefano Guerrini.
\newblock {\em The Optimal Implementation of Functional Programming Languages}.
\newblock Cambridge University Press, 1998.

[5]
Thibaut Balabonski.
\newblock A Unified Approach to Fully Lazy Sharing.
\newblock In {\em Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium
on Principles of Programming Languages}, pages 469--480. ACM, 2012.
\newblock \href {http://dx.doi.org/10.1145/2103656.2103713}

[6]
Henk~P. Barendregt.
\newblock {\em The lambda calculus: its syntax and semantics}.
\newblock Studies in logic and the foundations of mathematics. North-Holland,
\newblock \url{http://mathgate.info/cebrown/notes/barendregt.php}.

[7]
Richard~S. Bird and Ross Paterson.
\newblock de Bruijn notation as a nested datatype.
\newblock {\em Journal of Functional Programming}, 9:77--91, 1999.
\newblock \href {http://dx.doi.org/10.1017/S0956796899003366}

[8]
Stefan Blom.
\newblock {\em Term Graph Rewriting -- Syntax and Semantics}.
\newblock PhD thesis, Vrije Universiteit Amsterdam, 2001.

[9]
Mark van~den Brand and Paul Klint.
\newblock ATerms for manipulation and exchange of structured data: It's all
about sharing.
\newblock {\em Information and Software Technology}, 49(1):55--64, 2007.
\newblock \href {http://dx.doi.org/10.1016/j.infsof.2006.08.009}

[10]
N.~G. de~Bruijn.
\newblock Lambda Calculus Notation with Nameless Dummies, a Tool for Automatic
Formula Manipulation, with Application to the Church-Rosser Theorem.
\newblock {\em Indagationes Mathematicae}, 34:381--392, 1972.

[11]
Olaf Chitil.
\newblock Common Subexpressions Are Uncommon in Lazy Functional Languages.
\newblock In {\em Selected Papers from the 9th International Workshop
(IFL'97)}, Implementation of Functional Languages, pages 53--71. Springer
Berlin Heidelberg, 1998.
\newblock \href {http://dx.doi.org/10.1007/BFb0055424}

[12]
Alonzo Church.
\newblock {\em The Calculi of Lambda-Conversion}.
\newblock Number~6 in Annals of Mathematical Studies. Princeton University
Press, 1941.

[13]
Bruno Courcelle.
\newblock Fundamental properties of infinite trees.
\newblock {\em Theoretical Computer Science}, 25(2):95--169, 1983.
\newblock \href {http://dx.doi.org/10.1016/0304-3975(83)90059-2}

[14]
Olivier Danvy and Ulrik~Pagh Schultz.
\newblock Lambda-Lifting in Quadratic Time.
\newblock {\em Journal of Functional and Logic Programming}, 2004, 2004.
\newblock \href {http://dx.doi.org/10.1007/978-3-540-85373-2_3}

[15]
Jörg Endrullis, Clemens Grabmayer, Jan~Willem Klop, and Vincent van Oostrom.
\newblock On Equal \mu-Terms.
\newblock In {\em Festschrift in Honour of Jan Bergstra}, Special Issue of TCS,
412 (28), pages 3175--3202. Elsevier, 2011.

[16]
Benjamin Goldberg and Paul Hudak.
\newblock Detecting Sharing of Partial Applications in Functional Programs.
\newblock Technical Report YALEU/DCS/RR-526, Department of Computer Science,
Yale University, 1987.

[17]
Clemens Grabmayer and Jan Rochel.
\newblock Confluent Let-Floating.
\newblock In {\em Proceedings of IWC~2013 (2$^{\text{nd}}$ International
Workshop on Confluence)}, 2013.

[18]
Clemens Grabmayer and Jan Rochel.
\newblock Confluent unfolding in the λ-calculus with \letrec.
\newblock In {\em Proceedings of IWC~2013 (2$^{\text{nd}}$ International
Workshop on Confluence)}, 2013.

[19]
Clemens Grabmayer and Jan Rochel.
\newblock Expressibility in the Lambda Calculus with \letrec.
\newblock Technical report, Universiteit Utrecht, 2012.
\newblock \href {http://arxiv.org/abs/1208.2383} {\path{arXiv:1208.2383}},
\emph{Note:} generalises results from [20].

[20]
Clemens Grabmayer and Jan Rochel.
\newblock Expressibility in the Lambda Calculus with \mu.
\newblock Technical report, Universiteit Utrecht, 2013.
\newblock \href {http://arxiv.org/abs/1304.6284} {\path{arXiv:1304.6284}},
\emph{Note:} extended version of [21].

[21]
Clemens Grabmayer and Jan Rochel.
\newblock Expressibility in the Lambda Calculus with \mu.
\newblock In {\em 24th International Conference on Rewriting Techniques and
Applications, {RTA} 2013, June 24-26, 2013, Eindhoven, The Netherlands},
volume~21 of {\em LIPIcs}, pages 206--222. Schloss Dagstuhl - Leibniz-Zentrum
fuer Informatik, 2013.
\newblock \href {http://dx.doi.org/10.4230/LIPIcs.RTA.2013.206}

[22]
Clemens Grabmayer and Jan Rochel.
\newblock Maximal Sharing in the Lambda Calculus with \letrec.
\newblock Technical report, Vrije Universiteit Amsterdam and Universiteit
Utrecht, 2014.
\newblock \href {http://arxiv.org/abs/1401.1460} {\path{arXiv:1401.1460}},
\emph{Note:} extended version of [23].

[23]
Clemens Grabmayer and Jan Rochel.
\newblock Maximal sharing in the Lambda calculus with \letrec.
\newblock In {\em Proceedings of the 19th {ACM} {SIGPLAN} international
conference on Functional programming, Gothenburg, Sweden, September 1-3,
2014}, pages 67--80. ACM, 2014.
\newblock \href {http://dx.doi.org/10.1145/2628136.2628148}

[24]
Clemens Grabmayer and Jan Rochel.
\newblock Term Graph Representations for Cyclic Lambda-Terms.
\newblock Technical report, Universiteit Utrecht, 2013.
\newblock \href {http://arxiv.org/abs/1308.1034} {\path{arXiv:1308.1034}},
\emph{Note:} extended version of [25].

[25]
Clemens Grabmayer and Jan Rochel.
\newblock Term Graph Representations for Cyclic Lambda-Terms.
\newblock In {\em Proceedings 7th International Workshop on Computing with
Terms and Graphs, {TERMGRAPH} 2013, Rome, Italy, 23th March 2013.}, number
110 in EPTCS, pages 56--73, 2013.
\newblock \href {http://dx.doi.org/10.4204/EPTCS.110.7}

[26]
Dimitri Hendriks and Vincent van Oostrom.
\newblock \reflectbox{λ}.
\newblock In {\em Automated Deduction – CADE-19}, volume 2741 of {\em Lecture
Notes in Computer Science}, pages 136--150. Springer Berlin Heidelberg, 2003.
\newblock \href {http://dx.doi.org/10.1007/978-3-540-45085-6_11}

[27]
J.~E. Hopcroft.
\newblock An $n \log n$ Algorithm for Minimizing States in a Finite Automata.
\newblock In {\em Proceedings of an International Symposium on the Theory of
Machines and Computations, Haifa, Isreal}, pages 189--196. Academic Press,

[28]
J.~E. Hopcroft and R.~E. Karp.
\newblock A Linear Algorithm for Testing Equivalence of Finite Automata.
\newblock Technical report, Cornell University, 1971.

[29]
John Hughes.
\newblock Graph Reduction with Supercombinators.
\newblock Technical Report PRG28, Oxford University Computing Laboratory, 1982.
\newblock \url{http://www.cs.ox.ac.uk/files/3294/PRG28.pdf}.

[30]
R.~J.~M. Hughes.
\newblock Supercombinators: A new implementation method for applicative
\newblock In {\em LFP '82: Proceedings of the 1982 ACM symposium on LISP and
functional programming}, pages 1--10, 1982.
\newblock \emph{Note:} see also [29].

[31]
Jeroen Ketema and Jakob~Grue Simonsen.
\newblock Infinitary Combinatory Reduction Systems.
\newblock {\em Information and Computation}, 209(6):893 -- 926, 2011.
\newblock \href {http://dx.doi.org/10.1016/j.ic.2011.01.007}

[32]
Thomas Johnsson.
\newblock Lambda lifting: Transforming programs to recursive equations.
\newblock In {\em Functional Programming Languages and Computer Architecture},
volume 201 of {\em Lecture Notes in Computer Science}, pages 190--203.
Springer Berlin Heidelberg, 1985.
\newblock \href {http://dx.doi.org/10.1007/3-540-15975-4_37}

[33]
Simon L.~Peyton Jones.
\newblock {\em The Implementation of Functional Programming Languages}.
\newblock Prentice-Hall International Series in Computer Science.
Prentice-Hall, Inc., 1987.

[34]
Jeroen Ketema and Jakob~Grue Simonsen.
\newblock Infinitary combinatory reduction systems: confluence.
\newblock {\em Logical Methods in Computer Science}, 5(4:3):1--29, 2009.
\newblock \href {http://dx.doi.org/10.2168/LMCS-5(4:3)2009}

[35]
Jeroen Ketema and Jakob~Grue Simonsen.
\newblock Infinitary Combinatory Reduction Systems: Normalising Reduction
\newblock {\em Logical Methods in Computer Science}, 6(1:7):1--35, 2010.
\newblock \href {http://dx.doi.org/10.1145/2528934}

[36]
Jan~Willem Klop.
\newblock {\em Combinatory Reduction Systems}.
\newblock PhD thesis, Universiteit Utrecht, 1980.

[37]
Jan~Willem Klop, Vincent van Oostrom, and Femke van Raamsdonk.
\newblock Combinatory reduction systems: introduction and survey.
\newblock {\em Theoretical Computer Science}, 121(1-2):279 -- 308, 1993.
\newblock \href {http://dx.doi.org/10.1016/0304-3975(93)90091-7}

[38]
Dénes Kőnig.
\newblock {\em Theorie der Endlichen und Unendlichen Graphen}.
\newblock AMS Chelsea Publishing, 2001.

[39]
Jean-Jacques Lévy.
\newblock {\em Réductions correctes et optimales dans le $\lambda$-calcul}.
\newblock PhD thesis, Université, Paris~VII, 1978.

[40]
P.-A. Melliès.
\newblock {\em Description Abstraite des Systèmes de Réécriture}.
\newblock PhD thesis, l'Université Paris 7, 1996.

[41]
Robin Milner.
\newblock {\em Communicating and mobile systems: the $\pi$-calculus}.
\newblock Cambridge University Press, 1999.

[42]
Marco~T. Morazán and Ulrik~Pagh Schultz.
\newblock Optimal Lambda Lifting in Quadratic Time.
\newblock In {\em 19th International Workshop on Implementation and Application
of Functional Languages}, number 5083 in LNCS. Springer Berlin Heidelberg,
\newblock \href {http://dx.doi.org/10.1007/978-3-540-85373-2_3}

[43]
Daphne~A. Norton.
\newblock Algorithms for Testing Equivalence of Finite Automata, with a Grading
Tool for JFLAP.
\newblock Master's thesis, Department of Computer Science, Rochester Institute
of Technology, 2009.
\newblock \url{http://scholarworks.rit.edu/theses/6939/}.

[44]
Enno Ohlebusch.
\newblock Church-Rosser theorems for abstract reduction modulo an equivalence
\newblock In {\em Rewriting Techniques and Applications}, volume 1379 of {\em
Lecture Notes in Computer Science}, pages 17--31. Springer Berlin Heidelberg,
\newblock \href {http://dx.doi.org/10.1007/BFb0052358}

[45]
Vincent van Oostrom.
\newblock {\em Confluence for Abstract and Higher-Order Rewriting}.
\newblock PhD thesis, Vrije Universiteit Amsterdam, 1994.

[46]
Vincent van Oostrom.
\newblock FD à la Melliès, 1997.
\newblock \url{http://www.phil.uu.nl/~oostrom/publication/ps/FDalaMellies.ps},
{Vrije Universiteit Amsterdam}.

[47]
Vincent van Oostrom, Kees-Jan van~de Looij, and Marijn Zwitserlood.
\newblock Lambdascope.
\newblock Extended Abstract for the Workshop on Algebra and Logic on
Programming Systems (ALPS), Kyoto, April 10th 2004, 2004.
\newblock \url{http://www.phil.uu.nl/~oostrom/publication/pdf/lambdascope.pdf}.

[48]
J.~Palsberg and M.~I. Schwartzbach.
\newblock Binding-time analysis: abstract interpretation versus type inference.
\newblock In {\em International Conference on Computer Languages}, pages
289--298, 1994.
\newblock \href {http://dx.doi.org/10.1109/ICCL.1994.288372}

[49]
Detlef Plump.
\newblock {\em Evaluation of Functional Expressions by Hypergraph Rewriting}.
\newblock PhD thesis, Universit\"{a}t Bremen, 1993.

[50]
André~Lu\iacute{}s de~Medeiros~Santos.
\newblock {\em Compilation by Transformation in Non-Strict Functional
\newblock PhD thesis, University of Glasgow, 1995.

[51]
\newblock {\em Term Rewriting Systems}, volume~55 of {\em Cambridge Tracts in
Theoretical Computer Science}.
\newblock Cambridge University Press, 2003.
\newblock \url{https://www.cs.vu.nl/~terese/}.

[52]
Michael~Jonathan Thyer.
\newblock {\em Lazy specialization}.
\newblock PhD thesis, University of York, 2003.

[53]
Christopher~Peter Wadsworth.
\newblock {\em Semantics and pragmatics of the lambda-calculus}.
\newblock PhD thesis, University of Oxford, 1971.

\end{thebibliography}

\appendix
\renewcommand\thetheorem{\thechapter .\arabic {theorem}}

\chapter{Examples: Graph Translation}\label{app:translation}

%TODO: Auf diese Übersetzung verweisen

\begin{para}[overview]
For two terms from \cref{chap:maxsharing} we provide the fully worked out stepwise translation of \lambdaletrec-terms according to \rulestranslambdaletreccaltolhotgs from \cref{fig:def:graphsem:lhotgs} producing λ-ap-ho-term-graphs and for the rules \rulestranslambdaletreccaltoltgs from \cref{fig:def:graphsem:ltgs} producing λ-term-graphs. Note that in each step of the translation we apply not only one but multiple translation rules (indicated as subscripts of the steps), one for each translation box of the current graph. When no more rules are applicable, indirection vertices are erased.
\end{para}

\begin{para}
We start off by a simple example, namely the translation (\cref{fig:ex:compact}) of the term \P from \cref{ex:fix}. There is no application of the \S-rule, thus it yields the exact same translation sequence for \rulestranslambdaletreccaltolhotgs as for \rulestranslambdaletreccaltoltgs producing a λ-term-graph.
\end{para}

\newcommand\eraseIndirectionVertices{\multilinebox{\scriptsize erase indirection\\[-1ex]\scriptsize vertices}}

\begin{transenv}
\transinit{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}}{\abs{f}{\letin{r=\app{f}{(\app{f}{r})}}{r}}}};
\draw[<-](t.north) to +(0mm,6mm);
\transstep{λ}{
\node[draw,shape=transbox](t){\recprefixed{\starfs{} \prefixcon f^v\fs{}}{\letin{r=\app{f}{(\app{f}{r})}}{r}}};
\ltgnode[above=of t.north]{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[<-](f.north) to +(0mm,4mm);
\draw[->](f) to (t.north);
\transstep{\Let}{
\node[draw,shape=transbox](in){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{r}};
\ltgnode[above=of in.north]{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[->](f) to (in.north);
\draw[<-](f.north) to +(0mm,4mm);
\node[draw,shape=transbox,left=of in](ffr){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{\app{f}{(\app{f}{r})}}};
\ltgnode[above=of ffr]{indir}{\indir}; \addPos{indir}{w};
\draw[->](indir) to (ffr.north);
\transstep{@,\f}{
\ltgnode{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[<-](f.north) to +(0mm,4mm);
\node[below=of f](in){};
\node[left=of in](inwest){};
\draw(f) |- (inwest.center);
\node[left=of f](indireast){};
\ltgnode[left=of indireast]{indir}{\indir}; \addPos{indir}{w};
\draw[->](indireast.center) to (indir.east);
\draw(indireast.center) -| (inwest.center);
\ltgnode[below=of indir]{f@fr}{@}; \addPrefix{f@fr}{v};
\draw[->](indir) to (f@fr);
\node[below=of f@fr](ffr){};
\node[node distance=0mm, left=of ffr,draw,shape=transbox](l){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{f}};
\node[node distance=0mm,right=of ffr,draw,shape=transbox](ffr){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{\app{f}{r}}};
\draw[->](f@fr) to (l.north);
\draw[->](f@fr) to (ffr.north);
\transstep{\0,@}{
\ltgnode{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[<-](f.north) to +(0mm,4mm);
\node[below=of f](in){};
\ltgnode[below=of f]{indir}{\indir}; \addPos{indir}{w};
\draw[->](f) to (indir.north);
\ltgnode[below=of indir]{f@fr}{@}; \addPrefix{f@fr}{v};
\draw[->](indir) to (f@fr);
\node[below=of f@fr](ffr){};
\ltgnode[left=of ffr]{l}{\0}; \addPrefix{l}{v};
\draw[->](f@fr) to (l);
\node[left=of l](lwest){}; \draw(l) to (lwest.center); \draw[->](lwest.center) |- (f);
\ltgnode[right=of ffr]{f@r}{@}; \addPrefix{f@r}{v};
\node[below=of f@r](fr){};
\draw[->](f@fr) to (f@r.north);
\node[node distance=0mm, left=of fr,draw,shape=transbox](f1){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{f}};
\draw[->](f@r) to (f1.north);
\node[node distance=0mm,right=of fr,draw,shape=transbox](r){\recprefixed{\starfs{}\prefixcon f^v\fs{r^w\commentOut{=\app{f}{(\app{f}{r})}}}}{r}};
\draw[->](f@r) to (r.north);
\transstep{\0,f}{
\ltgnode{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[<-](f.north) to +(0mm,4mm);
\node[below=of f](in){};
\ltgnode[below=of f]{indir}{\indir}; \addPos{indir}{w};
\draw[->](f) to (indir.north);
\ltgnode[below=of indir]{f@fr}{@}; \addPrefix{f@fr}{v};
\draw[->](indir) to (f@fr);
\node[below=of f@fr](ffr){};
\ltgnode[left=of ffr]{l}{\0}; \addPrefix{l}{v};
\draw[->](f@fr) to (l);
\node[left=of l](lwest){}; \draw(l) to (lwest.center); \draw[->](lwest.center) |- (f);
\ltgnode[right=of ffr]{f@r}{@}; \addPrefix{f@r}{v};
\node[below=of f@r](fr){};
\draw[->](f@fr) to (f@r.north);
\ltgnode[left=of fr]{f1}{\0}; \addPrefix{f1}{v};
\draw[->](f@r) to (f1);
\draw(f1) -| (lwest.center);
\node[right=of fr](r){};
\draw(f@r) to (r.center);
\node[node distance=1mm,right=of r](reast){};
\draw(r.center) to (reast.center);
\draw[->](reast.center) |- (indir.east);
\transstep{\eraseIndirectionVertices}{
\ltgnode{f}{λ}; \addPos{f}{v}; \addPrefix{f}{};
\draw[<-](f.north) to +(0mm,4mm);
\node[below=of f](in){};
\ltgnode[below=of f]{f@fr}{@}; \addPrefix{f@fr}{v};
\draw[->](f) to (f@fr);
\node[below=of f@fr](ffr){};
\ltgnode[left=of ffr]{l}{\0}; \addPrefix{l}{v};
\draw[->](f@fr) to (l);
\node[left=of l](lwest){}; \draw(l) to (lwest.center); \draw[->](lwest.center) |- (f);
\ltgnode[right=of ffr]{f@r}{@}; \addPrefix{f@r}{v};
\node[below=of f@r](fr){};
\draw[->](f@fr) to (f@r.north);
\ltgnode[left=of fr]{f1}{\0}; \addPrefix{f1}{v};
\draw[->](f@r) to (f1);
\draw(f1) -| (lwest.center);
\node[right=of fr](r){};
\draw(f@r) to (r.center);
\node[node distance=1mm,right=of r](reast){};
\draw(r.center) to (reast.center);
\draw[->](reast.center) |- (f@fr.east);
\end{transenv}

\begin{para}\label{translation:translations}
We continue with the term  \m{\L_2} from \cref{ex:translations}. We translate it in two different ways correspoding to the first-order term graph semantics \graphsemCmin{\classltgs}{} from \cref{def:graphsem-min:ltgs} and \graphsemC{\classltgs}{} from \cref{def:graphsem:ltgs}, respectively. Both sequences of translation steps yield the same λ-ap-ho-term-graph \graphsemC{\classlhotgs}{\L_2},\footnote{This is due to \cref{thm:corr:aphotgs:ltgs}, \cref{prop:graphsem:ltgs:min:graphsem:ltgs}, and \cref{prop:graphsem:ltgs:min:graphsem:ltgs:S}.} but we obtain two different λ-term-graphs \graphsemCmin{\classltgs}{\L_2} and \graphsemC{\classltgs}{\L_2} as in \cref{fig:translations}.
\end{para}

\begin{para}[dotted \S-vertices]
Since we want to illustrate translations w.r.t.\ \rulestranslambdaletreccaltolhotgs which produces λ-ap-ho-term-graphs (which do not contain \S-vertices) and w.r.t.\ \rulestranslambdaletreccaltoltgs which produces λ-term-graphs (which contain \S-vertices) at the same time, in the graphs \S-vertices drawn with dotted lines.
\end{para}

\begin{para}[prefix lengths in the \Let-rule]
Both translations are eager-scope (i.e. applications of \S-rules are given priority, and prefixes lengths are chosen small enough in the \Let-rule, see \cref{short-enough-prefixes}) but differ in how they resolve the non-determinism due to different possible choices for the prefix lengths \m{l_1,\dots,l_k} in the \Let-rule.
\end{para}

\begin{para}[translation 1: no \S-sharing]\label{translation-1}
First we consider the translations of \m{\L_2} with \graphsemC{\classlhotgs}{} and \graphsemCmin{\classltgs}{}, i.e.\ the translation process in which prefix lengths are chosen minimally when applying the \Let-rule resulting in no sharing of \S-vertices.
\end{para}

\newcommand\vx{u}
\newcommand\vy{v}
\newcommand\vz{w}
\newcommand\vI{s}
\newcommand\vf{t}

\begin{transenv}
\transinit{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}}{\abs{x}{\abs{y}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}}}};
\draw[<-](t.north) to +(0mm,6mm);
\transstep{λ}{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}\prefixcon x^\vx\fs{}}{\abs{y}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}}};
\ltgnode[above=of t.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[<-](x.north) to +(0mm,4mm);
\draw[->](x) to (t.north);
\transstep{λ}{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}\prefixcon x^\vx\fs{}\prefixcon y^\vy\fs{}}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}};
\ltgnode[above=of t.north]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (t.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\transstep{\Let}{
\node[draw,shape=transbox](yIIyff){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{ }}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}};
\ltgnode[above=of yIIyff.north]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vy};
\draw[->](y) to (yIIyff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[left=of yIIyff]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\node[draw,shape=transbox,below=of Iindir](I){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}}{\abs{z}{z}}};
\draw[->](Iindir) to (I.north);
\ltgnode[right=of yIIyff]{findir}{\indir}; \addPos{findir}{\vf};
\node[draw,shape=transbox,below=of findir](f){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{x}};
\draw[->](findir) to (f.north);
\transstep{λ,@,\0}{
\node(yIIyff){};
\node[node distance=0mm,draw,shape=transbox,left=of yIIyff](yIIy){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{\app{\app{y}{I}}{(\app{I}{y})}}};
\node[node distance=0mm,draw,shape=transbox,right=of yIIyff](ff){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{\app{f}{f}}};
\ltgnode[above=of yIIyff.north]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yIIy.north); \draw[->](yIIy@ff) to (ff.north);
\ltgnode[above=of<EMAIL_ADDRESS>\addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=4cm,left=of y]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\ltgnode[above=of z]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\draw[->](Iindir) to (z.north);
\node[draw,shape=transbox,below=of z](I){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon z^\vz\fs{}}{z}};
\draw[->](z) to (I.north);
\ltgnode[node distance=3cm,right=of yIIy@ff]{f}{\0}; \addPrefix{f}{\vx};
\ltgnode[above=of f]{findir}{\indir}; \addPos{findir}{\vf};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\0, @, @}{
\node(yIIyff){};
\ltgnode[dotted,node distance=2cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\node[draw,shape=transbox,below=of Sff](ff){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{\app{f}{f}}};
\draw[->](Sff) to (ff.north);
\ltgnode[node distance=2cm,left=of ff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy};
\node[below=of yI@Iy](yIIy){};
\node[node distance=0mm,draw,shape=transbox, left=of yIIy](yI){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{\app{y}{I}}};
\draw[->](yI@Iy) to (yI.north);
\node[node distance=0mm,draw,shape=transbox,right=of yIIy](Iy){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{\app{I}{y}}};
\draw[->](yI@Iy) to (Iy.north);
\ltgnode[above=of yIIyff.north]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of<EMAIL_ADDRESS>\addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=2cm,left=of y]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[below=of Iindir]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Iindir) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=2cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\mathrlap{@,@,@}}{
\node(yIIyff){};
\ltgnode[dotted,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=0mm,draw,shape=transbox, left=of ff](f1){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{f}};
\draw[->](f@f) to (f1.north);
\node[node distance=0mm,draw,shape=transbox,right=of ff](f2){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{f}};
\draw[->](f@f) to (f2.north);
\ltgnode[node distance=1cm,left=of f1]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy};
\ltgnode[node distance=2.5cm,below=of yIIyff]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\node[node distance=0mm,draw,shape=transbox, left=of Iy](I2){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{I}};
\draw[->](I@y) to (I2.north);
\node[node distance=0mm,draw,shape=transbox,right=of Iy](y2){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{y}};
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=1cm, left=of I2]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy};
\node[node distance=8mm,below=of y@I](y@@I){}; \node[node distance=8mm,right=of y@@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\node[node distance=0mm,draw,shape=transbox, left=of yI](y1){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{y}};
\draw[->](y@I) to (y1.north);
\node[node distance=0mm,draw,shape=transbox, right=of yI](I1){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{}}{I}};
\draw[->](y@I) to (I1.north);
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=5cm,left=of y]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[below=of Iindir]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Iindir) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=2cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\mathrlap{\0, \S, \S, \0, f, f}}{
\node(yIIyff){};
\ltgnode[node distance=1.5cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[node distance=1.5cm,right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\ltgnode[dotted,left=of Iy]{SI2}{\S}; \addPrefix{SI2}{\vx\prefixcon \vy};
\draw[->](I@y) to (SI2.north);
\node[draw,shape=transbox, below=of SI2](I2){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{I}};
\draw[->](SI2) to (I2.north);
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx\prefixcon \vy};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=2.5cm, left=of SI2]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\ltgnode[dotted,right=of yI]{SI1}{\S}; \addPrefix{SI1}{\vx\prefixcon \vy};
\draw[->](y@I) to (SI1.north);
\node[draw,shape=transbox, below=of SI1](I1){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{I}};
\draw[->](SI1) to (I1.north);
\ltgnode[dotted,node distance=2.5cm,right=of I@y]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=1cm,right=of ff](fmerge){};
\node[ left=of ff](f1){}; \draw(f@f) to (f1.south); \draw(f1.south) |- (fmerge.south);
\node[right=of ff](f2){}; \draw(f@f) to (f2.center); \draw(f2.center) to (fmerge.center);
\ltgnode[above=of yIIyff.north]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of<EMAIL_ADDRESS>\addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=5.5cm,left=of x]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[below=of Iindir]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Iindir) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=3cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\draw[->](fmerge.south) |- (findir.east);
\transstep{\S,\S}{
\node(yIIyff){};
\ltgnode[node distance=1cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[node distance=1cm,right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\ltgnode[dotted,left=of Iy]{SI2}{\S}; \addPrefix{SI2}{\vx\prefixcon \vy};
\draw[->](I@y) to (SI2.north);
\ltgnode[dotted,below=of SI2]{SSI2}{\S}; \addPrefix{SSI2}{\vx};
\draw[->](SI2) to (SSI2.north);
\node[draw,shape=transbox, below=of SSI2](I2){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}}{I}};
\draw[->](SSI2) to (I2.north);
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=2.2cm, left=of SI2]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\ltgnode[dotted,right=of yI]{SI1}{\S}; \addPrefix{SI1}{\vx\prefixcon \vy};
\draw[->](y@I) to (SI1.north);
\ltgnode[dotted,below=of SI1]{SSI1}{\S}; \addPrefix{SSI1}{\vx};
\draw[->](SI1) to (SSI1.north);
\node[draw,shape=transbox, below=of SSI1](I1){\recprefixed{\starfs{I^\vI\commentOut{=\abs{z}{z}}}}{I}};
\draw[->](SSI1) to (I1.north);
\ltgnode[dotted,node distance=2cm,right=of I@y]{Sff}{\S}; \addPrefix{Sff}{\vx};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=1cm,right=of ff](fmerge){};
\node[ left=of ff](f1){}; \draw(f@f) to (f1.south); \draw(f1.south) |- (fmerge.south);
\node[right=of ff](f2){}; \draw(f@f) to (f2.center); \draw(f2.center) to (fmerge.center);
\ltgnode[above=of yIIyff.north]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of<EMAIL_ADDRESS>\addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y.north]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=5.2cm,left=of x]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[below=of Iindir]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Iindir) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=2.3cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\draw[->](fmerge.south) |- (findir.east);
\transstep{f,f}{
\node(yIIyff){};
\ltgnode[node distance=1.5cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[node distance=1cm,right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\ltgnode[dotted,left=of Iy]{SI2}{\S}; \addPrefix{SI2}{\vx\prefixcon \vy};
\draw[->](I@y) to (SI2.north);
\ltgnode[dotted,below=of SI2]{SSI2}{\S}; \addPrefix{SSI2}{\vx};
\draw[->](SI2) to (SSI2.north);
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=1cm, left=of yIIy]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\ltgnode[dotted,right=of yI]{SI1}{\S}; \addPrefix{SI1}{\vx\prefixcon \vy};
\draw[->](y@I) to (SI1.north);
\ltgnode[dotted,below=of SI1]{SSI1}{\S}; \addPrefix{SSI1}{\vx};
\draw[->](SI1) to (SSI1.north);
\node[below=of SSI1](Imerge){};
\ltgnode[dotted,node distance=2cm,right=of I@y]{Sff}{\S}; \addPrefix{Sff}{\vx};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=1cm,right=of ff](fmerge){};
\node[ left=of ff](f1){}; \draw(f@f) to (f1.south); \draw(f1.south) |- (fmerge.south);
\node[right=of ff](f2){}; \draw(f@f) to (f2.center); \draw(f2.center) to (fmerge.center);
\ltgnode[above=of yIIyff.north]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=5.5cm,left=of y]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[below=of Iindir]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Iindir) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=1.8cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\draw[->](fmerge.south) |- (findir.east);
\draw(SSI1) to (Imerge.center);
\draw(SSI2) |- (Imerge.center);
\node[right=of Iindir](Iindireast){};
\draw[->](Iindireast.center) to (Iindir.east);
\draw(Imerge.center) -| (Iindireast.center);
\transstep{\eraseIndirectionVertices}{
\node(yIIyff){};
\ltgnode[node distance=1.5cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[node distance=1cm,right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\ltgnode[dotted,left=of Iy]{SI2}{\S}; \addPrefix{SI2}{\vx\prefixcon \vy};
\draw[->](I@y) to (SI2.north);
\ltgnode[dotted,below=of SI2]{SSI2}{\S}; \addPrefix{SSI2}{\vx};
\draw[->](SI2) to (SSI2.north);
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=1cm, left=of yIIy]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\ltgnode[dotted,right=of yI]{SI1}{\S}; \addPrefix{SI1}{\vx\prefixcon \vy};
\draw[->](y@I) to (SI1.north);
\ltgnode[dotted,below=of SI1]{SSI1}{\S}; \addPrefix{SSI1}{\vx};
\draw[->](SI1) to (SSI1.north);
\ltgnode[dotted,node distance=1.6cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=1.4cm,right=of ff](fmerge){};
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=2.5cm,below=of yIIy]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[below=of ff]{f}{\0}; \addPrefix{f}{\vx};
\draw[->, bend right](f@f) to (f.north);
\draw[->, bend left](f@f) to (f.north);
\node[right=of f](feast){}; \draw(f.east) to (feast.center); \draw[->] (feast.center) |- (x.east);
\draw[->](SSI1) to (z.north);
\draw[->](SSI2) to (z.north);
\end{transenv}

\begin{para}[translation 2: maximal \S-sharing]
Second, we give the translation of the same term \m{\L_2} (from \cref{ex:translations}) with the process needed for the first-order term graph semantics \graphsemC{\classltgs}{}, yielding \graphsemC{\classltgs}{\L_2} in \cref{fig:def:graphsem:lhotgs}, and the corresponding λ-ap-ho-term-graph \graphsemC{\classlhotgs}{\L_2}. The obtained λ-term-graph \graphsemC{\classltgs}{\L_2} differs from the λ-term-graph \graphsemCmin{\classltgs}{\L_2} obtained in \cref{translation-1} by a higher degree of \S-sharing.
\end{para}

\begin{transenv}
\transinit{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}}{\abs{x}{\abs{y}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}}}};
\draw[<-](t.north) to +(0mm,6mm);
\transstep{λ}{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}\prefixcon x^\vx\fs{}}{\abs{y}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}}};
\ltgnode[above=of t]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[<-](x.north) to +(0mm,4mm);
\draw[->](x) to (t.north);
\transstep{λ}{
\node[draw,shape=transbox](t){\recprefixed{\starfs{}\prefixcon x^\vx\fs{}\prefixcon y^\vy\fs{}}{\letin{I=\abs{z}{z},f=x}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}}};
\ltgnode[above=of t]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (t.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\transstep{\Let}{
\node[draw,shape=transbox](yIIyff){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\app{\app{\app{y}{I}}{(\app{I}{y})}}{(\app{f}{f})}}};
\ltgnode[above=of yIIyff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vy};
\draw[->](y) to (yIIyff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[left=of yIIyff]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\node[draw,shape=transbox,below=of Iindir](I){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\abs{z}{z}}};
\draw[->](Iindir) to (I.north);
\ltgnode[right=of yIIyff]{findir}{\indir}; \addPos{findir}{\vf};
\node[draw,shape=transbox,below=of findir](f){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{x}};
\draw[->](findir) to (f.north);
\transstep{\S,@,\0}{
\node(yIIyff){};
\node[node distance=0mm,draw,shape=transbox,left=of yIIyff](yIIy){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\app{\app{y}{I}}{(\app{I}{y})}}};
\node[node distance=0mm,draw,shape=transbox,right=of yIIyff](ff){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\app{f}{f}}};
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yIIy.north); \draw[->](yIIy@ff) to (ff.north);
\ltgnode[node distance=6mm,above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[dotted,node distance=4cm,left=of y]{z}{\S}; \addPrefix{z}{\vx\prefixcon \vy};
\ltgnode[above=of z]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\draw[->](Iindir) to (z.north);
\node[draw,shape=transbox,below=of z](I){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{\abs{z}{z}}};
\draw[->](z) to (I.north);
\ltgnode[node distance=3cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\S, @, \S}{
\node(yIIyff){};
\ltgnode[dotted,node distance=1.5cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\node[draw,shape=transbox,below=of Sff](ff){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{\app{f}{f}}};
\draw[->](Sff) to (ff.north);
\ltgnode[node distance=1.5cm,left=of ff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy};
\node[node distance=7mm,below=of yI@Iy](yIIy){};
\node[node distance=0mm,draw,shape=transbox, left=of yIIy](yI){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\app{y}{I}}};
\draw[->](yI@Iy) to (yI.north);
\node[node distance=0mm,draw,shape=transbox,right=of yIIy](Iy){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{\app{I}{y}}};
\draw[->](yI@Iy) to (Iy.north);
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[dotted,node distance=4cm,left=of y]{z}{\S}; \addPrefix{z}{\vx\prefixcon \vy};
\ltgnode[above=of z]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\draw[->](Iindir) to (z.north);
\ltgnode[dotted,below=of z]{zS}{\S}; \addPrefix{zS}{\vx};
\node[draw,shape=transbox,below=of zS](I){\recprefixed{\starfs{}}{\abs{z}{z}}};
\draw[->](z) to (zS.north);
\draw[->](zS) to (I.north);
\ltgnode[node distance=3cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\mathrlap{λ,@,@,@}}{
\node(yIIyff){};
\ltgnode[dotted,node distance=2cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=0mm,draw,shape=transbox, left=of ff](f1){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{f}};
\draw[->](f@f) to (f1.north);
\node[node distance=0mm,draw,shape=transbox,right=of ff](f2){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}}{f}};
\draw[->](f@f) to (f2.north);
\ltgnode[node distance=1cm,left=of f1]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy};
\node[node distance=7mm,below=of yI@Iy](yIIy){};
\ltgnode[node distance=2.4cm,right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\node[node distance=0mm,draw,shape=transbox, left=of Iy](I2){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{I}};
\draw[->](I@y) to (I2.north);
\node[node distance=0mm,draw,shape=transbox,right=of Iy](y2){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{y}};
\draw[->](I@y) to (y2.north);
\ltgnode[node distance=1cm, left=of I2]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy};
\node[node distance=7mm,below=of y@I](y@@I){}; \node[node distance=8mm,right=of y@@I](yI){}; \draw[->](yI@Iy) to (y@I.north);
\node[node distance=0mm,draw,shape=transbox, left=of yI](y1){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{y}};
\draw[->](y@I) to (y1.north);
\node[node distance=0mm,draw,shape=transbox, right=of yI](I1){\recprefixed{\starfs{}\prefixcon x^\vx\fs{f^\vf\commentOut{=x}}\prefixcon y^\vy\fs{I^\vI\commentOut{=\abs{z}{z}}}}{I}};
\draw[->](y@I) to (I1.north);
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=3.2cm,left=of x]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\ltgnode[dotted,below=of Iindir]{SSz}{\S}; \addPrefix{SSz}{\vx\prefixcon \vy};
\draw[->](Iindir) to (SSz.north);
\ltgnode[dotted,below=of SSz]{Sz}{\S}; \addPrefix{Sz}{\vx};
\draw[->](SSz) to (Sz.north);
\ltgnode[below=of Sz]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Sz) to (z.north);
\node[draw,shape=transbox,below=of z](I){\recprefixed{\starfs{}\prefixcon z^\vz\fs{}}{z}};
\draw[->](z) to (I.north);
\ltgnode[node distance=4cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\transstep{\0, \0, f, f, \0, f, f}{
\node(yIIyff){};
\ltgnode[node distance=1.2cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\node[left=of Iy](SI2){};
\draw(I@y) to (SI2.center);
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx\prefixcon \vy};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[left=of yIIy]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\node[right=of yI](SI1){};
\draw(y@I) to (SI1.center);
\node[below=of SI1](Imerge){};
\draw(SI1.center) to (Imerge.center);
\draw(SI2.center) |- (Imerge.center);
\ltgnode[dotted,node distance=1.3cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\node[node distance=1cm,right=of ff](fmerge){};
\node[ left=of ff](f1){}; \draw(f@f) to (f1.south); \draw(f1.south) |- (fmerge.south);
\node[right=of ff](f2){}; \draw(f@f) to (f2.center); \draw(f2.center) to (fmerge.center);
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[node distance=5cm,left=of y]{Iindir}{\indir}; \addPos{Iindir}{\vI};
\node[right=of Iindir](Ieast){};
\draw[->](Ieast.center) to (Iindir);
\ltgnode[dotted,below=of Iindir]{SSz}{\S}; \addPrefix{SSz}{\vx\prefixcon \vy};
\draw[->](Iindir) to (SSz.north);
\ltgnode[dotted,below=of SSz]{Sz}{\S}; \addPrefix{Sz}{\vx};
\draw[->](SSz) to (Sz.north);
\ltgnode[below=of Sz]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Sz) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[node distance=1.5cm,right=of y]{findir}{\indir}; \addPos{findir}{\vf};
\ltgnode[below=of findir]{f}{\0}; \addPrefix{f}{\vx};
\draw[->](findir) to (f.north);
\node[left=of f](fwest){}; \draw(f.west) to (fwest.center); \draw[->] (fwest.center) |- (x.east);
\draw[->](fmerge.south) |- (findir.east);
\draw(Imerge.center) -| (Ieast.center);
\transstep{\eraseIndirectionVertices}{
\node(yIIyff){};
\ltgnode[node distance=1.2cm,left=of yIIyff]{yI@Iy}{@}; \addPrefix{yI@Iy}{\vx\prefixcon \vy}; \node[below=of yI@Iy](yIIy){};
\ltgnode[right=of yIIy]{I@y}{@}; \addPrefix{I@y}{\vx\prefixcon \vy}; \node[below=of I@y](Iy){};
\draw[->](yI@Iy) to (I@y.north);
\node[left=of Iy](SI2){};
\ltgnode[right=of Iy]{y2}{\0}; \addPrefix{y2}{\vx\prefixcon \vy};
\node[right=of y2](y2l){}; \draw(y2) to (y2l.center);
\draw[->](I@y) to (y2.north);
\ltgnode[left=of yIIy]{y@I}{@}; \addPrefix{y@I}{\vx\prefixcon \vy}; \node[below=of y@I](yI){};
\draw[->](yI@Iy) to (y@I.north);
\ltgnode[left=of yI]{y1}{\0}; \addPrefix{y1}{\vx\prefixcon \vy};
\node[left=of y1](y1l){}; \draw(y1) to (y1l.center);
\draw[->](y@I) to (y1.north);
\node[right=of yI](SI1){};
\ltgnode[dotted,node distance=1.3cm,right=of yIIyff]{Sff}{\S}; \addPrefix{Sff}{\vx\prefixcon \vy};
\ltgnode[below=of Sff]{f@f}{@}; \addPrefix{f@f}{\vx\prefixcon \vy}; \node[below=of f@f](ff){};
\draw[->](Sff) to (f@f.north);
\ltgnode[above=of yIIyff]{yIIy@ff}{@}; \addPrefix{yIIy@ff}{\vx\prefixcon \vy};
\draw[->](yIIy@ff) to (yI@Iy.north); \draw[->](yIIy@ff) to (Sff.north);
\ltgnode[above=of yIIy@ff]{y}{λ}; \addPos{y}{\vy}; \addPrefix{y}{\vx};
\draw[->](y2l.center) |- (y.east); \draw[->](y1l.center) |- (y.west);
\draw[->](y) to (yIIy@ff.north);
\ltgnode[above=of y]{x}{λ}; \addPos{x}{\vx}; \addPrefix{x}{};
\draw[->](x) to (y.north);
\draw[<-](x.north) to +(0mm,4mm);
\ltgnode[distance=2.5cm,dotted,below=of yIIy]{SSz}{\S}; \addPrefix{SSz}{\vx\prefixcon \vy};
\draw[->](y@I) to (SSz);
\draw[->](I@y) to (SSz);
\ltgnode[dotted,below=of SSz]{Sz}{\S}; \addPrefix{Sz}{\vx};
\draw[->](SSz) to (Sz.north);
\ltgnode[below=of Sz]{z}{λ}; \addPos{z}{\vz}; \addPrefix{z}{};
\draw[->](Sz) to (z.north);
\ltgnode[below=of z]{I}{\0}; \addPrefix{I}{\vz};
\node[left=of I](Iwest){}; \draw(I.west) to (Iwest.center); \draw[->] (Iwest.center) |- (z.west);
\draw[->](z) to (I.north);
\ltgnode[below=of ff]{f}{\0}; \addPrefix{f}{\vx};
\node[right=of f](feast){}; \draw(f.east) to (feast.center); \draw[->] (feast.center) |- (x.east);
\draw[->,bend right](f@f) to (f);
\draw[->,bend left](f@f) to (f);
\end{transenv}

\chapter{Implementation Showcase}\label{app:impl:showcase}

To demonstrate the realisability of our method, we have implemented the methods from \cref{chap:maxsharing}. The implementation is called \href{http://hackage.haskell.org/package/maxsharing/}{maxsharing} and is available on Hackage: \url{http://hackage.haskell.org/package/maxsharing/}. It is written in Haskell and therefore requires the \href{http://www.haskell.org/platform/}{Haskell Platform} to be installed. Then, maxsharing can be installed via \href{http://www.haskell.org/haskellwiki/Cabal-Install}{cabal-install} using the commands \texttt{cabal update} and \texttt{cabal install maxsharing} from the terminal. Invoke the executable \texttt{maxsharing} in your cabal-directory with a file as an argument that contains a \lambdaletrec-term. Run \texttt{maxsharing -h} for help on run-time flags.

For further illustration we provide the output of the \href{http://hackage.haskell.org/package/maxsharing/}{maxsharing} tool
for a number of examples from the thesis. Since the volume of the output is too large to include here it is supplied as an external appendix available at \url{http://rochel.info/thesis/}.

\chapter{Confluence of unfolding \lambdaletrec-terms}\label{app:conf_proof}

Here we present a proof of \cref{prop:unf-confluence} which is an adaptation of [18] where we prove the confluence of a precursor of \unfCRS. Here the proof below is written out for \unfbhCRS, but works for \unfCRS as well if the critical pairs involving the rules \rulep{\tighten} and \rulep{\bh} are left out.

\begin{proof}[Proof of \cref{prop:unf-confluence}]
\newcommand\TL{}
\newcommand\TR{\m{\,\begin{picture}(-1,1)(-1,-2)\circle*{1.5}\end{picture}\ }} % small bullet (between a \bullet and a \cdot)
\newcommand\BL{\m{\,\begin{picture}(-1,1)(-1,-2)\circle{3.5}\end{picture}\ }}
\newcommand\BR{\m{\odot}}
%	 a `three-line context'
\newcommand\atlcxtBRTRTL[6]{\m{\begin{array}{l}\sacxt[\L_{#1}^{\BR},\dots,\L_{#2}^{\BR},\\\indent \phantom{\sacxt[}\L_{#3}^{\TR},\dots,\L_{#4}^{\TR},\\\indent\indent \phantom{\sacxt[}\L_{#5}^{\TL},\dots,\L_{#6}^{\TL}]\end{array}}}
\newcommand\atlcxtBRBLTL[6]{\m{\begin{array}{l}\sacxt[\L_{#1}^{\BR},\dots,\L_{#2}^{\BR},\\\indent \phantom{\sacxt[}\L_{#3}^{\BL},\dots,\L_{#4}^{\BL},\\\indent\indent \phantom{\sacxt[}\L_{#5}^{\TL},\dots,\L_{#6}^{\TL}]\end{array}}}
\newcommand\tilerowsep{1.2cm}
\newcommand\tilecolsep{1.5cm}
\newcommand\vpar{\m{=}}
\newcommand\hpar{\m{||}}

First of all, we cannot use Newman's Lemma to prove confluence, because \unfbhCRS is not terminating. To show confluence of \unfbhCRS we use the method of `decreasing diagrams' \cite[Section 2.3]{oost:1994} \cite[Section 14.2]{terese:2003}. We use it however not to prove confluence of the rewriting relation \m{\red_\unfold} induced by \unfbhCRS directly, but of the abstract reduction system \m{\aARS = (\Ter\lambdaletreccal, \setcompr{\parred_{\wDepth\arule{d}}}{(d,\arule) \in ℕ \times R})} with \m{R} as the set of rules of \unfbhCRS where \m{\parred_{\wDepth\arule{d}}} denotes the parallel rewriting relation on \Ter\lambdaletreccal induced by rule \arule at \letrec-depth \m{d}. As a precedence order we consider the order induced by the \letrec-depth:
\[ \parred_{\wDepth\arule{d}} ~≥~ \parred_{\wDepth\brule{d'}} ~ \Longleftrightarrow ~ d \geq d'\]

The \letrec-depth of a redex in \lambdaletrec-term denotes the number of \Let-nodes passed on the path from the root of the term tree to the corresponding position. We write \m{\red_{\wDepth\arule{d}}} to denote the relation induced by applying rule \arule contracting a redex at \letrec-depth \m{d}.

Let us denote the rewriting relation induced by \aARS by \m{\red_\aARS}:
\[ \red_\aARS = \bigcup\,\setcompr{\parred_{\wDepth\arule{d}}}{(d,\arule) \in ℕ \times R}\]

If \m{\red_\aARS} is confluent then \m{\red_\unfold} is confluent because it holds: \m{\red_\unfold \subseteq \red_\aARS \subseteq \mred_\unfold} or equivalently \m{\mred_\aARS = \mred_\unfold} (see also \cite[Lemma 2.2.5]{oost:1994}).

We use parallel steps because the preceding attempt to prove confluence of \unfbhCRS-steps themselves by decreasing diagrams was unsuccessful. As a precedent order we considered an ordering on the rules and lexicographic extensions of such orderings with the \letrec-depth of the contracted redex. We came to the conclusion that no such order could ensure decreasingness of the elementary diagrams of both the critical pairs as well as the strictly nested redexes. This was due to redex duplication induced by the diverging steps, so that joining the diagram required a many-step that disrupted decreasingness. In order to resolve this problem we considered parallel steps such that the problematic multi-step would become a single parallel step. This led to more intricate diagrams but turned out to be a viable solution.

We will show that two diverging parallel steps in \unfbhCRS can be joined in an elementary diagram of the following form with \m{d \leq e}.

\begin{figure}
\begin{tikzpicture}
\matrix[row sep=0.8cm,column sep=1.3cm]{
\emptynode{tl};&&
\emptynode{tr};\\
\emptynode{bl};&
\emptynode{bm};&
\emptynode{br};\\
\draw[->       ](tl) to node{\hpar} node[above]{\wDepth\arule{d}}   (tr);
\draw[->       ](tl) to node{\vpar} node[left ]{\wDepth\brule{e}}   (bl);
\draw[->,dotted](bl) to node{\hpar} node[below]{\wDepth\brule{e-1}} (bm);
\draw[->,dotted](bm) to node{\hpar} node[below]{\wDepth\arule{d}}   (br);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\brule{e}}   (mr);
\draw[->,dotted](mr) to node{\vpar} node[right]{\wDepth\brule{e-1}} (br);
\end{tikzpicture}
\caption{Elementary diagram}
\label{fig:elem_dia}
\end{figure}

If we pick as the precedence order on the steps the order that is induced by their \letrec-depth, the diagram is decreasing. Note that in all the diagrams we implicitly assume the reflexive closure for all arrows. The rest of the proof is structured as follows. To justify the diagram we distinguish the cases \m{d = e} and \m{d < e}, for which we construct diagrams that are instances of the diagram in \cref{fig:elem_dia}.

\section*{Case 1}

For \m{d = e} we need to consider parallel diverging steps contracting redexes at the same \letrec-depth \m{d}. We construct the diagram below which is an instance of the diagram above where the diverging parallel steps are in sequentialised form. We write terms as fillings of a multihole context \sacxt with all its holes at \letrec-depth \m{d} such that the contracted \wDepth\arule{d}- and \wDepth\brule{d}-redexes are filled into these holes. In this way we can make explicit at which position a step takes place, i.e. at the root of the context hole fillings. The topmost row and the leftmost column are respective sequentialisations of the parallel diverging \wDepth\arule{d}- and \wDepth\brule{d}-steps into single steps.

\noindent
\begin{tikzpicture}
\matrix[row sep=1.2cm,column sep=0.5cm]{
\node(00){\acxt{\L_0^{\TL}, \dots, \L_n^{\TL}}};&
\node(10){\acxt{\L_0^{\TR}, \L_1^{\TL} \dots, \L_n^{\TL}}};&
\node(i0){\dots};&
\node(n0){\acxt{\L_0^{\TR}, \dots, \L_n^{\TR}}};\\
\node(01){\acxt{\L_0^{\BL}, \L_1^{\TL}, \dots, \L_n^{\TL}}};&
\node(11){\acxt{\L_0^{\BR}, \L_1^{\TL}, \dots, \L_n^{\TL}}};&
\node(i1){\dots};&
\node(n1){\acxt{\L_0^{\BR}, \L_1^{\TR}, \dots, \L_n^{\TR}}};\\
\node(0i){\vdots};&
\node(1i){\vdots};&
\node(ii){\ddots};&
\node(ni){\vdots};\\
\node(0n){\acxt{\L_0^{\BL}, \dots, \L_n^{\BL}}};&
\node(1n){\acxt{\L_0^{\BR}, \L_1^{\BL}, \dots, \L_n^{\BL}}};&
\node(in){\dots};&
\node(nn){\acxt{\L_0^{\BR}, \dots, \L_n^{\BR}}};\\
\draw[->       ](00)  to            node[above]{\wDepth\arule{d}}    (10);
\draw[->       ](10)  to            node[above]{\wDepth\arule{d}}    (i0);
\draw[->       ](i0)  to            node[above]{\wDepth\arule{d}}    (n0);
\draw[->,dotted](01)  to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->,dotted](11)  to            node[above]{\wDepth\arule{d}}    (i1);
\draw[->,dotted](i1)  to            node[above]{\wDepth\arule{d}}    (n1);
\draw[->,dotted](0n)  to node{\hpar} node[above]{\wDepth\arule{d}}    (1n);
\draw[->,dotted](1n)  to node{\hpar} node[above]{\wDepth\arule{d}}    (in);
\draw[->,dotted](in)  to node{\hpar} node[above]{\wDepth\arule{d}}    (nn);
\draw[->       ](00)  to            node[left ]{\wDepth\brule{d}}    (01);
\draw[->,dotted](10)  to node{\vpar}  node[left ]{\wDepth\brule{d}}    (11);
\draw[->,dotted](n0)  to node{\vpar}  node[left ]{\wDepth\brule{d}}    (n1);
\draw[->       ](01)  to            node[left ]{\wDepth\brule{d}}    (0i);
\draw[->,dotted](11)  to            node[left ]{\wDepth\brule{d}}    (1i);
\draw[->,dotted](n1)  to node{\vpar}  node[left ]{\wDepth\brule{d}}    (ni);
\draw[->       ](0i)  to            node[left ]{\wDepth\brule{d}}    (0n);
\draw[->,dotted](1i)  to            node[left ]{\wDepth\brule{d}}    (1n);
\draw[->,dotted](ni)  to node{\vpar}  node[left ]{\wDepth\brule{d}}    (nn);
\end{tikzpicture}

\noindent
In this diagram the tiles at \m{(i,j)} for \m{i,j ∈ \set{0,\dots,n-1}} below the diagonal (\m{i<j}) look as follows:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep,column sep=\tilecolsep]{
\node(00){\atlcxtBRBLTL{0}{i-1}{i}{j-1}{j}{n}};&
\node(10){\atlcxtBRBLTL{0}{i}{i+1}{j-1}{j}{n}};\\
\node(01){\atlcxtBRBLTL{0}{i-1}{i}{j}{j+1}{n}};&
\node(11){\atlcxtBRBLTL{0}{i}{i+1}{j}{j+1}{n}};\\
\draw[->       ](00)  to node{\hpar} node[above]{\wDepth\arule{d}}    (10);
\draw[->,dotted](01)  to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->       ](00)  to              node[left ]{\wDepth\brule{d}}    (01);
\draw[->,dotted](10)  to              node[left ]{\wDepth\brule{d}}    (11);
\end{tikzpicture}

\noindent
The tiles at \m{(i,j)} for \m{i,j ∈ \set{0,\dots,n-1}} above the diagonal (\m{i>j}) look as follows:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep,column sep=\tilecolsep]{
\node(00){\atlcxtBRTRTL{0}{j-1}{j}{i-1}{i}{n}};&
\node(10){\atlcxtBRTRTL{0}{j-1}{j}{i}{i+1}{n}};\\
\node(01){\atlcxtBRTRTL{0}{j}{j+1}{i-1}{i}{n}};&
\node(11){\atlcxtBRTRTL{0}{j}{j+1}{i}{i+1}{n}};\\
\draw[->       ](00)  to             node[above]{\wDepth\arule{d}}    (10);
\draw[->,dotted](01)  to             node[above]{\wDepth\arule{d}}    (11);
\draw[->       ](00)  to node{\vpar} node[left ]{\wDepth\brule{d}}    (01);
\draw[->,dotted](10)  to node{\vpar} node[left ]{\wDepth\brule{d}}    (11);
\end{tikzpicture}

\noindent
For \m{i ∈ \set{0,\dots,n-1}} the \i-th diagonal tile looks like this:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep,column sep=\tilecolsep/2]{
\node(00){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\TL}, \dots, \L_n^{\TL}}};&
\node(10){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\TR}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};\\
\node(01){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\BL}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};&
\node(11){\acxt{\L_0^{\BR}, \dots, \L_i^{\BR}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};\\
\draw[->       ](00)  to            node[above]{\wDepth\arule{d}}    (10);
\draw[->,dotted](01)  to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->       ](00)  to            node[left ]{\wDepth\brule{d}}    (01);
\draw[->,dotted](10)  to node{\vpar}  node[left ]{\wDepth\brule{d}}    (11);
\end{tikzpicture}

Only the tiles on the diagonal require closer attention because for all other tiles the vertical and horizontal steps take place in different holes of the context, therefore they are disjoint and consequently commute. In the tiles on the diagonal the diverging steps may be either due to a critical pair or to identical steps. In the latter case the diagram is easily joined. In case of a critical pair, since all steps take place at the same \letrec-depth any such critical pair must arise from a root overlap. Exhaustive scrutiny of all these critical pairs reveals that they can be joined in a way that conforms to the tiles on the diagonal. Note that the \letrec-depths of the steps have to be increased by \m{d} according to the lifting into a context with its hole at \letrec-depth \m{d}.

\begin{remark}
Note, that in the critical pair analysis below, we are not always faithful to the actual formulation of the rules, in the sense that we sometimes assume that a binding appears at a specific position in the list of bindings of a \Let-expression. This is merely to save page space and can be easily generalised.
\end{remark}

\subsection{Critical pairs due to \wDepth{λ}{0}/\wDepth{\arule}{0}}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{}{\abs{x}\L}};&
\node(tr){\abs{x}{\letin{}\L}};\\
\node(bl){\abs{x}\L};&
\node(br){\abs{x}\L};\\
\draw[->       ](tl) to node[above]{\wDepth{λ}{0}}    (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\nil}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\nil}{0}} (br);
\draw[double   ](bl) to                               (br);
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B}{\abs{x}\L}};&
\node(tr){\abs{x}{\letin{B}\L}};\\
\node(bl){\letin{B'}{\abs{x}\L}};&
\node(br){\abs{x}{\letin{B'}\L}};\\
\draw[->       ](tl) to node[above]{\wDepth{λ}{0}}     (tr);
\draw[->       ](tl) to node[left ]{\wDepth\reduce{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\reduce{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{λ}{0}}     (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{\abs{x}\L}};&
\node(tr){\abs{x}{\letin{B,f=g}\L}};\\
\node(bl){\letin{\subst{B}{f}{g}}{\abs{x}{\subst{\L}{f}{g}}}};&
\node(br){\abs{x}{\letin{\subst{B}{f}{g}}{\subst{\L}{f}{g}}}};\\
\draw[->       ](tl) to node[above]{\wDepth{λ}{0}}      (tr);
\draw[->       ](tl) to node[left ]{\wDepth\tighten{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\tighten{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{λ}{0}}      (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{\abs{x}\L}};&
\node(tr){\abs{x}{\letin{B,f=f}\L}};\\
\node(bl){\letin{\subst{B}{f}{\bh}}{\abs{x}{\subst{\L}{f}{\bh}}}};&
\node(br){\abs{x}{\letin{\subst{B}{f}{\bh}}{\subst{\L}{f}{\bh}}}};\\
\draw[->       ](tl) to node[above]{\wDepth{λ}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth\bh{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\bh{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{λ}{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{@}{0}/\wDepth{\brule}{0}}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{}{\app{L}{P}}};&
\node(tr){\appbreak{\letin{}\L}{\letin{}{P}}};\\
\node(bl){\app\L{P}};&
\node(br){\app\L{P}};\\
\draw[->       ](tl) to           node[above]{\wDepth{@}{0}} (tr);
\draw[->       ](tl) to           node[left ]{\wDepth\nil{0}}  (bl);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\nil{0}}  (br);
\draw[double   ](bl) to                                              (br);
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B}{\app\L{P}}};&
\node(tr){\appbreak{\letin{B}\L}{\letin{B}{P}}};\\
\node(bl){\letin{B'}{\app\L{P}}};&
\node(br){\appbreak{\letin{B'}\L}{\letin{B'}{P}}};\\
\draw[->       ](tl) to           node[above]{\wDepth{@}{0}}   (tr);
\draw[->       ](tl) to           node[left ]{\wDepth\reduce{0}} (bl);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\reduce{0}} (br);
\draw[->,dotted](bl) to           node[below]{\wDepth{@}{0}}   (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{\app\L{P}}};&
\node(tr){\appbreak{\letin{B,f=g}\L}{\letin{B}{P}}};\\
\node(bl){\letin{\subst{B}{f}{g}}{\app{\subst{\L}{f}{g}}{\subst{P}{f}{g}}}};&
\node(br){\appbreak{\letin{\subst{B}{f}{g}}{\subst{\L}{f}{g}}}{\letin{\subst{B}{f}{g}}{\subst{P}{f}{g}}}};\\
\draw[->       ](tl) to             node[above]{\wDepth{@}{0}}      (tr);
\draw[->       ](tl) to             node[left ]{\wDepth\tighten{0}} (bl);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\tighten{0}} (br);
\draw[->,dotted](bl) to             node[below]{\wDepth{@}{0}}      (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{\app\L{P}}};&
\node(tr){\appbreak{\letin{B,f=f}\L}{\letin{B}{P}}};\\
\node(bl){\letin{\subst{B}{f}{\bh}}{\app{\subst{\L}{f}{\bh}}{\subst{P}{f}{\bh}}}};&
\node(br){\appbreak{\letin{\subst{B}{f}{\bh}}{\subst{\L}{f}{\bh}}}{\letin{\subst{B}{f}{\bh}}{\subst{P}{f}{\bh}}}};\\
\draw[->       ](tl) to             node[above]{\wDepth{@}{0}} (tr);
\draw[->       ](tl) to             node[left ]{\wDepth\bh{0}} (bl);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\bh{0}} (br);
\draw[->,dotted](bl) to             node[below]{\wDepth{@}{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{\merg}{0}/\wDepth{\brule}{0}}

\begin{tikzpicture}
\matrix{
\node(tl){\letin{}{\letin{B}\L}};&
\node(tr){\letin{B}\L};\\
\node(bl){\letin{B}\L};&
\node(br){\letin{B}\L};\\
\draw[->    ](tl) to node[above]{\wDepth\merg{0}} (tr);
\draw[->    ](tl) to node[left ]{\wDepth\nil{0}}    (bl);
\draw[double](tr) to                                      (br);
\draw[double](bl) to                                      (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B}{\letin{C}\L}};&
\node(tr){\letin{B,C}\L};\\
\node(bl){\letin{B'}{\letin{C}\L}};&
\node(br){\letin{B',C}\L};\\
\draw[->       ](tl) to node[above]{\wDepth\merg{0}}   (tr);
\draw[->       ](tl) to node[left ]{\wDepth\reduce{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\reduce{0}}   (br);
\draw[->,dotted](bl) to node[below]{\wDepth\merg{0}}   (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{\letin{C}\L}};&
\node(tr){\letin{B,f=g,C}\L};\\
\node(bl){\subst{(\letin{B}{\letin{C}{\L}})}{f}{g}};&
\node(br){\subst{(\letin{B,C}{\L})}{f}{g}};\\
\draw[->       ](tl) to node[above]{\wDepth\merg{0}}   (tr);
\draw[->       ](tl) to node[left ]{\wDepth\tighten{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\tighten{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth\merg{0}}   (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{\letin{C}\L}};&
\node(tr){\letin{B,f=f,C}\L};\\
\node(bl){\subst{(\letin{B}{\letin{C}{\L}})}{f}{\bh}};&
\node(br){\subst{(\letin{B,C}{\L})}{f}{\bh}};\\
\draw[->       ](tl) to node[above]{\wDepth\merg{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth\bh{0}}    (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\bh{0}}    (br);
\draw[->,dotted](bl) to node[below]{\wDepth\merg{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{\rec}{0}/\wDepth{\brule}{0}}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B}{f_i}};&
\node(tr){\letin{B}{\L_i}};\\
\node(bl){\letin{B'}{f_i}};&
\node(br){\letin{B'}{\L_i}};\\
\draw[->       ](tl) to            node[above]{\wDepth\rec{0}}    (tr);
\draw[->       ](tl) to            node[left ]{\wDepth\reduce{0}} (bl);
\draw[->,dotted](tr) to            node[right]{\wDepth\reduce{0}} (br);
\draw[->,dotted](bl) to            node[below]{\wDepth\rec{0}}    (br);
\end{tikzpicture}

\noindent
There is a \wDepth{\rec}{0}/\wDepth{\tighten}{0} critical pair. We distinguish the cases, whether the body consists of the `tightened' variable:\\*
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{f}};&
\node(tr){\letin{B,f=g}{g}};\\
\node(bl){\letin{\subst{B}{f}{g}}{g}};&
\node(br){\letin{\subst{B}{f}{g}}{g}};\\
\draw[->       ](tl) to node[above]{\wDepth{\rec}{0}}     (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\tighten}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\tighten}{0}} (br);
\draw[double   ](bl) to                                   (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g,h=L}{h}};&
\node(tr){\letin{B,f=g,h=L}{L}};\\
\node(bl){\letin{\subst{B}{f}{g},h=\subst{L}{f}{g}}{h}};&
\node(br){\subst{\letin{B,h=L}{L}}{f}{g}};\\
\draw[->       ](tl) to node[above]{\wDepth{\rec}{0}}     (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\tighten}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\tighten}{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\rec}{0}}     (br);
\end{tikzpicture}

\noindent
Likewise, there is a \wDepth{\rec}{0}/\wDepth{\bh}{0} critical pair. We distinguish the cases, whether the body consists of the `blackholed' variable:\\*
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{f}};&
\node(tr){\letin{B,f=f}{f}};\\
\node(bl){\letin{\subst{B}{f}{\bh}}{\bh}};&
\node(br){\letin{\subst{B}{f}{\bh}}{\bh}};\\
\draw[->       ](tl) to node[above]{\wDepth{\rec}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\bh}{0}}  (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\bh}{0}}  (br);
\draw[double   ](bl) to                               (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f,h=L}{h}};&
\node(tr){\letin{B,f=f,h=L}{L}};\\
\node(bl){\letin{\subst{B}{f}{\bh},h=\subst{L}{f}{\bh}}{h}};&
\node(br){\subst{\letin{B,h=L}{L}}{f}{\bh}};\\
\draw[->       ](tl) to node[above]{\wDepth{\rec}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\bh}{0}}  (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\bh}{0}}  (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\rec}{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{\nil}{0}/\wDepth{\brule}{0}}

There are no additional \wDepth{\nil}{0}/\wDepth{\brule}{0} critical pairs on top of the ones already scrutinised above.

\subsection{Critical pairs due to \wDepth{\reduce}{0}/\wDepth{\brule}{0}}

There is a \wDepth{\reduce}{0}/\wDepth{\tighten}{0} critical pair, for which we distinguish the cases whether the `tightened' binding is used.\\
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{\L}};&
\node(tr){\letin{B',f=g}{\L}};\\
\node(bl){\letin{\subst{B}{f}{g}}{\subst{\L}{f}{g}}};&
\node(br){\letin{\subst{B'}{f}{g}}{\subst{\L}{f}{g}}};\\
\draw[draw=none](tl) to node{\m{f ≠ g}} (br);
\draw[->       ](tl) to node[above]{\wDepth{\reduce}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\tighten}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\tighten}{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\reduce}{0}} (br);
\end{tikzpicture}

\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g}{\L}};&
\node(tr){\letin{B'}{\L}};\\
\node(bl){\letin{B}{\L}};&
\node(br){\letin{B'}{\L}};\\
\draw[->       ](tl) to node[above]{\wDepth{\reduce}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\tighten}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\tighten}{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\reduce}{0}} (br);
\end{tikzpicture}

Likewise, there is a \wDepth{\reduce}{0}/\wDepth{\bh}{0} critical pair, for which we distinguish the cases whether the `blackholed' binding is used.\\
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{\L}};&
\node(tr){\letin{B',f=f}{\L}};\\
\node(bl){\letin{\subst{B}{f}{\bh}}{\subst{\L}{f}{\bh}}};&
\node(br){\letin{\subst{B'}{f}{\bh}}{\subst{\L}{f}{\bh}}};\\
\draw[->       ](tl) to node[above]{\wDepth{\reduce}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\bh}{0}}     (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\bh}{0}}     (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\reduce}{0}} (br);
\end{tikzpicture}

\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f}{\L}};&
\node(tr){\letin{B'}{\L}};\\
\node(bl){\letin{B}{\L}};&
\node(br){\letin{B'}{\L}};\\
\draw[->       ](tl) to node[above]{\wDepth{\reduce}{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth{\bh}{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth{\bh}{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth{\reduce}{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{\tighten}{0}/\wDepth{\brule}{0}}

\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g,h=i}{\L}};&
\node(tr){\subst{(\letin{B,h=i}{\L})}{f}{g}};\\
\node(bl){\subst{(\letin{B,f=g}{\L})}{h}{i}};&
\node(br){\subst{\subst{(\letin{B}{\L})}{f}{g}}{h}{i}};\\
\draw[draw=none](tl) to node{\m{f ≠ g ~~ h ≠ i}} (br);
\draw[->       ](tl) to node[above]{\wDepth\tighten{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth\tighten{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\tighten{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth\tighten{0}} (br);
\end{tikzpicture}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=g,h=h}{\L}};&
\node(tr){\subst{(\letin{B,h=h}{\L})}{f}{g}};\\
\node(bl){\subst{(\letin{B,f=g}{\L})}{h}{\bh}};&
\node(br){\subst{\subst{(\letin{B}{\L})}{f}{g}}{h}{\bh}};\\
\draw[draw=none](tl) to node{\m{f ≠ g}} (br);
\draw[->       ](tl) to node[above]{\wDepth\tighten{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth\bh{0}}      (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\bh{0}}      (br);
\draw[->,dotted](bl) to node[below]{\wDepth\tighten{0}} (br);
\end{tikzpicture}

\subsection{Critical pairs due to \wDepth{\bh}{0}/\wDepth{\brule}{0}}

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B,f=f,g=g}{\L}};&
\node(tr){\subst{(\letin{B,g=g}{\L})}{f}{\bh}};\\
\node(bl){\subst{(\letin{B,f=f}{\L})}{g}{\bh}};&
\node(br){\subst{\subst{(\letin{B}{\L})}{f}{\bh}}{g}{\bh}};\\
\draw[->       ](tl) to node[above]{\wDepth\bh{0}} (tr);
\draw[->       ](tl) to node[left ]{\wDepth\bh{0}} (bl);
\draw[->,dotted](tr) to node[right]{\wDepth\bh{0}} (br);
\draw[->,dotted](bl) to node[below]{\wDepth\bh{0}} (br);
\end{tikzpicture}

%	Kein kritisches Paar, weil wir immer ALLE möglichen Bindungen löschen.
%	\noindent
%	\begin{tikzpicture}
%		\matrix{
%			\node(tl){\letin{B}\L};&
%			\node(tr){\letin{B^{\TR}}\L};\\
%			\node(bl){\letin{B^{\BL}}{\L}};&
%			\node(br){\letin{B^{\BR}}\L};\\
%		};
%		\draw[->       ](tl) to node[above]{\wDepth\reduce{0}}   (tr);
%		\draw[->       ](tl) to node[left ]{\wDepth\reduce{0}} (bl);
%		\draw[->,dotted](tr) to node[right]{\wDepth\reduce{0}} (br);
%		\draw[->,dotted](bl) to node[below]{\wDepth\reduce{0}}   (br);
%	\end{tikzpicture}

\section*{Case 2}

For \m{d < e} we use the same approach as for \m{d = e}, the diagram is however more involved. Again, we use a context \sacxt with context holes at \letrec-depth \m{d}. But since \m{e > d}, more than one \wDepth\brule{e}-contraction may take place in one such hole. Therefore a per-hole partitioning of the vertical steps requires a sequence of parallel steps.

The diagram below fits the scheme of the elementary diagram (\cref{fig:elem_dia}) when interleaving the \wDepth\brule{e}-steps with the \wDepth\brule{e-1}-steps in the rightmost column such that steps at depth \m{e} preceed those at depth \m{e-1}. Similarly for the bottommost row where the \wDepth\arule{e-1}-steps have to preceed the \wDepth\brule{d}-steps. These reorderings are possible since the segments represent contractions within different holes of \sacxt. As in the previous diagram the tiles which do not lie on the diagonal are unproblematic, which leaves us to complete the proof by constructing the tiles on the diagonal.

\noindent
\hspace{-1.2cm}
\begin{tikzpicture}
\matrix[row sep=0.7cm,column sep=0.45cm]{
\node(00){\acxt{\L_0^{\TL}, \dots, \L_n^{\TL}}};&
\node(10){\acxt{\L_0^{\TR}, \L_1^{\TL} \dots, \L_n^{\TL}}};&
\node(i0){\dots};&
\emptynode{ih0};&
\node(n0){\acxt{\L_0^{\TR}, \dots, \L_n^{\TR}}};\\
\emptynode{00h};&&
\emptynode{10h};&&
\emptynode{i0h};&
\emptynode{ih0h};&
\emptynode{n0h};\\
\node(01){\acxt{\L_0^{\BL}, \L_1^{\TL}, \dots, \L_n^{\TL}}};&
\emptynode{0h1};&
\node(11){\acxt{\L_0^{\BR}, \L_1^{\TL}, \dots, \L_n^{\TL}}};&
\node(i1){\dots};&
\emptynode{ih1};&
\node(n1){\acxt{\L_0^{\BR}, \L_1^{\TR}, \dots, \L_n^{\TR}}};\\
\emptynode{01h};&&
\emptynode{11h};&&
\emptynode{i1h};&
\emptynode{ih1h};&
\emptynode{n1h};\\
\node(0i){\vdots};&&
\node(1i){\vdots};&&
\node(ii){\ddots};&
\emptynode{ihi};&
\node(ni){\vdots};\\
\emptynode{0ih};&&
\emptynode{1ih};&&
\emptynode{iih};&
\emptynode{ihih};&
\emptynode{nih};\\
\node(0n){\acxt{\L_0^{\BL}, \dots, \L_n^{\BL}}};&
\emptynode{0hn};&
\node(1n){\acxt{\L_0^{\BR}, \L_1^{\BL}, \dots, \L_n^{\BL}}};&
\emptynode{1hn};&
\node(in){\dots};&
\emptynode{ihn};&
\node(nn){\acxt{\L_0^{\BR}, \dots, \L_n^{\BR}}};\\
\draw[->       ](00)  to            node[above]{\wDepth\arule{d}}    (10);
\draw[->       ](10)  to            node[above]{\wDepth\arule{d}}    (i0);
\draw[->       ](i0)  to            node[above]{\wDepth\arule{d}}    (n0);
\draw[->,dotted](01)  to            node[above]{\wDepth\brule{e-1}}    (0h1);
\draw[->,dotted](0h1) to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->,dotted](11)  to            node[above]{\wDepth\arule{d}}    (i1);
\draw[->,dotted](i1)  to            node[above]{\wDepth\arule{d}}    (n1);
\draw[->,dotted](0n)  to            node[above]{\wDepth\brule{e-1}}    (0hn);
\draw[->,dotted](0hn) to node{\hpar} node[above]{\wDepth\arule{d}}    (1n);
\draw[->,dotted](1n)  to            node[above]{\wDepth\brule{e-1}}    (1hn);
\draw[->,dotted](1hn) to node{\hpar} node[above]{\wDepth\arule{d}}    (in);
\draw[->,dotted](in)  to            node[above]{\wDepth\brule{e-1}}    (ihn);
\draw[->,dotted](ihn) to node{\hpar} node[above]{\wDepth\arule{d}}    (nn);
\draw[->       ](00)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (01);
\draw[->,dotted](10)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (10h);
\draw[->,dotted](10h) to node{\vpar}  node[left ]{\wDepth\brule{e-1}}  (11);
\draw[->,dotted](n0)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (n0h);
\draw[->,dotted](n0h) to node{\vpar}  node[left ]{\wDepth\brule{e-1}}  (n1);
\draw[->       ](01)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (0i);
\draw[->,dotted](11)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (1i);
\draw[->,dotted](n1)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (n1h);
\draw[->,dotted](n1h) to node{\vpar}  node[left ]{\wDepth\brule{e-1}}  (ni);
\draw[->       ](0i)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (0n);
\draw[->,dotted](1i)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (1n);
\draw[->,dotted](ni)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (nih);
\draw[->,dotted](nih) to node{\vpar}  node[left ]{\wDepth\brule{e-1}}  (nn);
\end{tikzpicture}

\noindent
In this diagram the tiles at \m{(i,j)} for \m{i,j ∈ \set{0,\dots,n-1}} below the diagonal (\m{i<j}) look as follows:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep,column sep=\tilecolsep/2]{
\node(00){\atlcxtBRBLTL{0}{i-1}{i}{j-1}{j}{n}};&&
\node(10){\atlcxtBRBLTL{0}{i}{i+1}{j-1}{j}{n}};\\
\node(01){\atlcxtBRBLTL{0}{i-1}{i}{j}{j+1}{n}};&
\emptynode{0h1};&
\node(11){\atlcxtBRBLTL{0}{i}{i+1}{j}{j+1}{n}};\\
\draw[->](00)  to              node[above]{\wDepth\arule{d}}    (10);
\draw[->](00)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (01);
\draw[->](01)  to              node[above]{\wDepth\brule{e-1}}    (0h1);
\draw[->](0h1) to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->](10)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (11);
\end{tikzpicture}

\noindent
The tiles at \m{(i,j)} for \m{i,j ∈ \set{0,\dots,n-1}} above the diagonal (\m{i>j}) look as follows:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep/2,column sep=\tilecolsep/2]{
\node(00){\atlcxtBRTRTL{0}{i-1}{i}{j-1}{j}{n}};&
\node(10){\atlcxtBRTRTL{0}{i-1}{i}{j}{j+1}{n}};\\
\emptynode{00h};&\emptynode{10h};\\
\node(01){\atlcxtBRTRTL{0}{i}{i+1}{j-1}{j}{n}};&
\node(11){\atlcxtBRTRTL{0}{i}{i+1}{j}{j+1}{n}};\\
\draw[->](00)  to             node[above]{\wDepth\arule{d}}    (10);
\draw[->](00)  to node{\vpar} node[left ]{\wDepth\brule{e}}    (00h);
\draw[->](00h) to node{\vpar} node[left ]{\wDepth\brule{e-1}}    (01);
\draw[->](10)  to node{\vpar} node[left ]{\wDepth\brule{e}}    (10h);
\draw[->](10h) to node{\vpar} node[left ]{\wDepth\brule{e-1}}    (11);
\draw[->](01)  to             node[above]{\wDepth\arule{d}}    (11);
\end{tikzpicture}

\noindent
For \m{i ∈ \set{0,\dots,n-1}} the \i-th diagonal tile looks like this:\\*
\begin{tikzpicture}
\matrix[row sep=\tilerowsep,column sep=\tilecolsep/2]{
\node(00){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\TL}, \dots, \L_n^{\TL}}};&&
\node(10){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\TR}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};\\
\node(01){\acxt{\L_0^{\BR}, \dots, \L_{i-1}^{\BR}, \L_i^{\BL}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};&
\emptynode{0h1};&
\node(11){\acxt{\L_0^{\BR}, \dots, \L_i^{\BR}, \L_{i+1}^{\TL}, \dots, \L_n^{\TL}}};\\
\draw[->](00)  to            node[above]{\wDepth\arule{d}}    (10);
\draw[->](00)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (01);
\draw[->](01)  to              node[above]{\wDepth\brule{e-1}}    (0h1);
\draw[->](0h1)  to node{\hpar} node[above]{\wDepth\arule{d}}    (11);
\draw[->](10)  to node{\vpar}  node[left ]{\wDepth\brule{e}}    (10h);
\draw[->](10h)  to node{\vpar}  node[left ]{\wDepth\brule{e-1}}    (11);
\end{tikzpicture}

\vspace{2ex}
Every hole on the diagonal is filled with at most one \wDepth\arule{d}-redex (at the root of the context hole fillings) but because of \m{d < e} with possibly many \wDepth\brule{e}-redexes (properly inside of the fillings). There may or may not be an overlap between the \wDepth\arule{d}-step and a \wDepth\brule{e}-step, but there can be at most one, which is due to the rules of \unfbhCRS.

Therefore \wDepth\brule{e} contracts either an overlap and a number of nested redexes, or only nested redexes without an overlap. These constellations are depicted on the figure below. There is one \wDepth\arule{d}-redex and three \wDepth\brule{e}-redexes. On the left, one of the \wDepth\brule{e}-redexes overlaps with the \wDepth\arule{d}-redex while on the right all \wDepth\brule{e}-redexes are strictly nested inside the \wDepth\arule{d}-redex.

\begin{hspread}
\fig{overlap}
\end{hspread}

For the critical pairs due to a non-root overlap, and for all situations with nested redexes, we construct diagrams of the following shape, respectively:

\noindent
\begin{tikzpicture}
\matrix[row sep=1.2cm,column sep=1.1cm]{
\emptynode{tl};&&
\emptynode{tr};\\
\emptynode{bl};&
\emptynode{bm};&
\emptynode{br};\\
\\
\draw[->       ](tl) to            node[above]{\wDepth\arule{0}}   (tr);
\draw[->       ](tl) to            node[left ]{\wDepth\brule{1}}   (bl);
\draw[->,dotted](bl) to            node[below]{\wDepth\brule{0}} (bm);
\draw[->,dotted](bm) to node{\hpar} node[below]{\wDepth\arule{0}}   (br);
\draw[->,dotted](tr) to            node[right]{\wDepth\brule{0}} (br);
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\matrix[row sep=1.2cm,column sep=2.2cm]{
\emptynode{tl};&
\emptynode{tr};\\
\emptynode{bl};&
\emptynode{br};\\
\\
\draw[->       ](tl) to            node[above]{\wDepth\arule{0}}   (tr);
\draw[->       ](tl) to            node[left ]{\wDepth\brule{e}}   (bl);
\draw[->,dotted](bl) to            node[below]{\wDepth\arule{0}}   (br);
\draw[->,dotted](tr) to            node[right]{\m{\wDepth\brule{e'} ~~~~ e' \in \set{e,e-1}}} (br);
\end{tikzpicture}

When lifted into a context of \letrec-depth \m{d} both of the diagrams comply to the shape necessary for the diagonal tiles, but we need to be able to handle situations as on as on the left of the above figure, where both nested redexes as well as the overlapping redex are contracted. Firstly, since all \brule-redexes occur at the same \letrec-depth, it must hold that \m{d = 0} and \m{e = 1}, which is due to the rules of \unfbhCRS. Secondly, none of the involved redex contractions affect any of the nested redexes except for duplicating or erasing them, which means that the residuals of the \brule-steps after these steps are part of a parallel \wDepth\brule{e'}-step (mind that we assume the reflexive closure of all steps). Or as a diagram:

\noindent
\begin{tikzpicture}
\matrix[row sep=0.5cm,column sep=1.4cm]{
\emptynode{tl};&&
\emptynode{tr};\\
\node(ir){\vdots};\\
\emptynode{ml};&&
\emptynode{mr};\\
\\
\emptynode{bl};&
\emptynode{bm};&
\emptynode{br};\\
\draw[->       ](tl) to            node[above]{\wDepth\arule{0}}   (tr);
\draw[->       ](tl) to node{\vpar} node[left ]{\wDepth\brule{1}}   (ml);
\draw[->       ](ml) to            node[left ]{\wDepth\brule{1}}   (bl);
\draw[->,dotted](ml) to            node[above]{\wDepth\arule{0}}   (mr);
\draw[->,dotted](mr) to            node[right]{\wDepth\brule{0}}   (br);
\draw[->,dotted](bl) to            node[below]{\wDepth\brule{0}}   (bm);
\draw[->,dotted](bm) to node{\hpar} node[below]{\wDepth\arule{0}}   (br);
\draw[->,dotted](tr) to node{\vpar} node[right]{\wDepth\brule{e_1}}   (ir);
\draw[->,dotted](ir) to node{\vpar} node[right]{\m{\wDepth\brule{e_n} ~~~~~ e_i \in \set{0,1}}} (mr);
\end{tikzpicture}

The diagram is composed from the previous two diagrams. A parallel version of the right one constitutes the top part, while the bottom part is an exact replica of the left one. The top part settles the portion arising from the nested redexes, the bottom part settles the portion arising from the overlapping redex.

At last in order to fit that diagram into the scheme of the diagonal tiles the steps on the right have to be reordered such that \wDepth\brule{e_i}-steps with \m{e_i = 1} preceed \wDepth\brule{e_i}-steps with \m{e_i = 0}. The reordering is viable because every \wDepth\brule{e_i}-step takes place in its own residual of the \wDepth\brule1-step from the left.

We conclude the proof by a comprehensive analysis all critical pairs that arise from non-root overlaps in \unfbhCRS as well as the diagrams for joining nested redexes.

\subsection{Diagrams for joining critical pairs}

\wDepth{\arule}{0}/\wDepth{\brule}{0} critical pairs only arise for \m{\arule=\merg}.

\noindent
\begin{tikzpicture}
\matrix{
\node(tl){\letin{B}{\letin{C}{\abs{x}{\L}}}};&
\node(tr){\letin{B,C}{\abs{x}{\L}}};\\
\node(ml){\letin{B}{\abs{x}{\letin{C}\L}}};\\
\node(bl){\abs{x}{\letin{B}{\letin{C}\L}}};&
\node(br){\abs{x}{\letin{B,C}\L}};\\