“backup”), a _type_ (belonging to the set of tile types $T$), a _protected
area_ (which is included into $\mathcal{C}$) and a _practical form_ (which is
a path of ${\bf{P}}[{\mathcal{\gamma}}]$ included into the protected area) and
a _restrained area_ (defined using the practical form and included into the
protected area). In order to achieve this goal, we introduce here the
_practical form_ of $P$:

######  Definition 19.

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider a path
$P$ which is canonical for some column $c$ with $e_{\sigma}+|T|+1\leq c\leq
e_{\sigma}+5|T|+1$ and let $f$ be the index of its first glue on column
$L(c)$. Also consider $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the
upward (resp. downward) decomposition of $P$ into dominants arcs on column $c$
and an index $p$ where $p$ is such that $p=m_{i}$ or $p=b_{i}-1$. Suppose that
an area called the protected area of $p$ is defined. The set of paths
${\bf{P}}[{p}]$ contains a path $Q$ if and only if:

  * •

$Q_{0}=P_{p}$, $Q_{1}=P_{p+1}$, $Q_{|Q|-2}=P_{f}$ and $Q_{|Q|-1}=P_{f+1}$;

  * •

$Q_{1,\ldots,|Q|-2}$ is in the protected area of $p$;

  * •

$P_{0,\ldots,p-1}Q$ is a producible path whose last tile is the easternmost
one.

  * •

$Q_{|Q|-1}$ is the only tile of $Q$ on column $L(c)+1$.

Let $R$ be the path such that $P_{p}R$ is the right (resp. left) priority path
of this set, this path is called the _practical form_ of $P$ at index $p$.

####  6.2.1 The visible glue is protected

######  Definition 20 (Notations for a visible glue).

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider a path
$P$ which is canonical for some column $c$ with $e_{\sigma}+|T|+1\leq c\leq
e_{\sigma}+5|T|+1$ and let $f$ be the index of its first glue on column
$L(c)$. Also consider $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the
upward (resp. downward) decomposition of $P$ into dominants arcs on column
$c$.

We remind that $\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$ is the glue visible from
the south (resp. north) in $P$ and we consider it as protected by default. It
is categorized as a “main” glue, its type is the type of
$\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$, its protected area
$\mathcal{P}_{m_{0}}$ is $\mathcal{C}$ (the workspace of the cut $(m_{0},f)$
of $P_{0,\ldots,f+1}$). Let $R$ be the practical form of $P$ at index $m_{0}$.
In this case, $R$ is in $\mathcal{P}_{m_{0}}$ and we define the restrained
area $\mathcal{R}_{m_{0}}$ as the cut $(m_{0},m_{0}+|R|-1)$ of the path
$P_{0,\ldots,m_{0}}R$ (whose last tile is the easternmost one by definition of
$R$). This restrained area is inside $\mathcal{C}$.

######  Lemma 31.

Consider a path $P$ and the notations 20. Let $\mathcal{P}_{m_{0}}$ be the
protected area of $\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$ and let $R$ the
practical form of $P$ at index $m_{0}$. Consider a path $Q$ such that
$Q_{0}=R_{0}$. If $P_{m_{g}}Q$ is more right-priority than $P_{m_{g}}R$ and if
there exist $0\leq u\leq v\leq|Q|-1$ such that $R_{0,\ldots,u}$ is the largest
common prefix between $R$ and $Q$ and such that $Q_{0,\ldots,v}$ intersects
with $R_{u+1,\ldots,|R|-1}$, then $Q_{0,\ldots,v}$ intersects with the glue
ray of $\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$ or $e_{Q_{0,\ldots,v}}\geq
L(c)+1$.

###### Proof.

Consider a path $Q$ such that $Q_{0}=R_{0}$ and let $0\leq u\leq|Q|-1$ such
that $R_{0,\ldots,u}$ is the largest common prefix between $R$ and $Q$. We
define $v=\max\\{i:\mathrm{pos}(R_{i})\text{ is occupied by a tile of }Q\\}$,
let $u\leq v^{\prime}\leq|Q|-1$ such that $Q_{v^{\prime}}=R_{v}$. If
$Q_{0,\ldots,v^{\prime}}$ does not intersect the glue ray of
$\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$ and if
$x_{Q_{0,\ldots,v^{\prime}}}<L(c)+1$ then $Q_{0,\ldots,v^{\prime}}$ is in
$\mathcal{P}_{m_{0}}$. Thus $P_{0,\ldots,m_{0}}Q_{0,\ldots,v^{\prime}}$ is
producible and we have $Q_{v^{\prime}}=P_{v}$ since the tile assembly system
is directed. Then $P_{m_{g}}Q_{0,\ldots,v^{\prime}}R_{v+1,\ldots,|R|-1}$ is a
producible path and if $u<v^{\prime}$ then this path is more right-priority
than $P_{m_{g}}R$ and satisfies all properties of 19. This is a contradiction
of the definition of $R$. ∎

######  Lemma 32.

Consider a path $P$, the notations 20 and the index $0\leq\ell\leq|P|-1$ of
the last glue of $P$ on column $c$. If there exists a path $B$ such that $B$
is in the restrained area $\mathcal{R}_{m_{0}}$ of
$\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$, $w_{B}>c$, $B_{0}$ is a tile of
$P_{\ell+1,\ldots,f}$ then B does not intersect with
$P_{m_{0}+1,\ldots,\ell}$.

###### Proof.

If $B$ intersects with $P_{m_{0}+1,\ldots,\ell}$ then let $B_{0,\ldots,v}$ be
the shortest prefix of $B$ which intersects with $P_{m_{0}+1,\ldots,\ell}$.
Let $B_{u,\ldots,v}$ be the shortest suffix of $B_{0,\ldots,v}$ which
intersects with $P_{\ell+1,\ldots,f}$. Since, $w_{B}>c$ then there exists
$i\leq j<k$ such that $P_{i,\ldots,k}$ is a dominant arc of $P$ on column $c$
and $P_{j}=B_{v}$ (since $B$ is in ${\bf{P}}[{\mathcal{\gamma}}]$). Since
$B_{u,\ldots,v}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ and in
$\mathcal{R}_{m_{0}}$ then there is a contradiction with Lemma 3 since $P$ is
canonical for column $c$. ∎

Note that, for the special case where the width of $P$ on column $c$ is $0$,
then $m_{0}=\ell$ and $\mathrm{glue}(P_{\ell}P_{\ell+1})$ is the only “main”
glue of the upward decomposition of $P$ into dominant arcs and the only “main”
glue of the downward decomposition of $P$ into dominant arcs.

####  6.2.2 Glues protected by a full-shield

Along this subsection, we will use the following notations:

######  Definition 21 (Notations for a glue protected by a full-shield).

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider a path
$P$ which is canonical for some column $c$ with $e_{\sigma}+|T|+1\leq c\leq
e_{\sigma}+5|T|+1$ and let $f$ be the index of its first glue on column
$L(c)$. Let $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the upward
(resp. downward) decomposition of $P$ into dominants arcs on column $c$ and
let $(b^{i})_{0\leq i\leq t+1}$ be the borders of this decomposition. Let $S$
be a full-shield associated to the cut $(m_{0},f)$ of $P_{0,\ldots,f+1}$ at
index $m_{0}<a\leq f$.

######  Lemma 33.

Consider the notation 23. If $S$ is a full-shield then, there exists $0\leq
e\leq|S|-1$ and $0<g\leq t$ such that the $\mathrm{glue}(S_{e}S_{e+1})$999If
$e=|S|-1$, we consider that $S_{e+1}=P_{a}$ by abuse of notation. intersects
the border $b^{g}$ and $x_{S_{0,\ldots,e}}>c$.

###### Proof.

By definition of a full-shield, we have $x_{SP_{a}}\leq c$. Thus, we can
define $e=\min\\{i:\mathrm{glue}(S_{i}S_{i+1})\text{ is on column $c$}\\}$.
Then, by definition of $e$, we have $x_{S_{e}}=c+1$ and $x_{S_{e+1}}=c$. Now,
the workspace $\mathcal{C}$ can be decomposed into its east-side $\mathcal{E}$
and the interiors $\mathcal{I}_{i}$ for all $0<i\leq t$. Since $x_{S_{e}}>c$
then $\mathrm{pos}(S_{e})$ is in $\mathcal{E}$. However, $x_{S_{e+1}}\leq c$
and $\mathrm{pos}(S_{e+1})\in\mathcal{C}$ thus $\mathrm{pos}(S_{e+1})$ belongs
to $\mathcal{I}_{g}$ for some $0<g\leq t$. Then, $\mathrm{glue}(S_{e}S_{e+1})$
must intersect with $b^{g}$. ∎

Thanks to Lemma 33, we now assume that there exists $0\leq e\leq|S|-1$ and
$0<g\leq t$ such that $\mathrm{glue}(S_{e}S_{e+1})$ intersects with the
segment $b^{g}$ and $x_{S_{0,\ldots,e}}>c$. In this case, we say that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is _protected_ by the beginning of the
full-shield $S_{0,\ldots,e}$. The category of this protected glue is “main”
and its type is the type of $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$. Its
_protected area_ $\mathcal{P}_{m_{g}}$ is defined as the finite area delimited
by:

  * •

$P_{m_{g},\ldots,f+1}$,

  * •

the vertical segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$,

  * •

$S_{0,\ldots,e}$;

  * •

the vertical segment between $\mathrm{glue}(P_{f}P_{f+1})$ and
$\mathrm{glue}(S_{0}S_{1})$.

Note that $\mathcal{P}_{m_{g}}$ may be included into the interior of the arc
$SP_{a,\ldots,f}$ but this is not always the case. Remark that
$P_{0,\ldots,m_{g}}$ is not inside $\mathcal{P}_{m_{g}}$. Indeed,
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ points east and thus $P_{m_{g}}$ is not
inside $\mathcal{P}_{m_{g}}$. Moreover, $P_{0,\ldots,m_{g}}$ cannot intersect
with $P_{m_{g}+1,\ldots,f+1}$ (since $P$ is self-avoiding), the vertical
segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$ (since this segment is part of the border
$b^{g}$), $S_{0,\ldots,e}$ (since, by definition, $S$ does not intersect
$P_{m_{0},\ldots,f}$ and is in $\mathcal{C}$) and the vertical segment between
$\mathrm{glue}(P_{f}P_{f+1})$ and $\mathrm{glue}(S_{0}S_{1})$ (since
$P_{0,\ldots,m_{g}}$ has no tile on column $L(c)+1$ by Lemma 23). This remark
implies the following fact:

######  Fact 9.

Consider the notation 23 and $0<g\leq t$ such that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is protected by the full-shield $S$. Let
$\mathcal{P}_{m_{g}}$ be its protected area. Consider a path $Q$ such that $Q$
is inside $\mathcal{P}_{m_{g}}$ and such that $Q_{0}=P_{m_{g}+1}$ then
$P_{0,\ldots,m_{g}}Q$ is a producible path.

######  Lemma 34.

Consider the notation 23, $0<g\leq t$ and $0\leq e\leq|S|-1$ such that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is protected by the beginning of the
full-shield $S_{0,\ldots,e}$. Let $\mathcal{P}_{m_{g}}$ be its protected area.
There exists no path $Q$ such that $Q$ is inside the area
$\mathcal{P}_{m_{g}}$, $Q_{0}=P_{m_{g}+1}$ and $Q$ intersects with
$S_{0,\ldots,e}$.

###### Proof.

For the sake of contradiction suppose that such a path $Q$ exists, then by
Fact 9, $P_{0,\ldots,m_{g}}Q$ is a producible path. Let $A$ be the arc
$SP_{a,\ldots,f+1}$. Firstly, consider the case where $a\leq m_{g}$. In this
case, $P_{m_{g}+1}$ is inside the interior $\mathcal{I}_{A}$ of arc $A$ and
let $0\leq j\leq|Q|-1$ be such that $Q_{0,\ldots,j}$ in the shortest prefix of
$Q$ which intersects with $S$ (by hypothesis, this index is correctly defined)
and let $0\leq i<j$ be such that $Q_{i,\ldots,j}$ is the shortest suffix of
$Q_{0,\ldots,j}$ which intersects with $P_{m_{g}+1,\ldots,f+1}$ (by
hypothesis, this index is correctly defined since $Q_{0}=P_{{m_{g}}+1}$). Let
$m_{g}+1\leq i^{\prime}\leq f$ be such that $P_{i^{\prime}}=Q_{i}$ and $0\leq
j^{\prime}\leq|S|-1$ be such that $S_{j^{\prime}}=Q_{j}$ then
$A^{\prime}=S_{0,\ldots,j^{\prime}-1}\text{rev}({Q_{i,\ldots,j}})P_{i^{\prime}+1,\ldots,f+1}$
is a simple path. Since $Q$ is in $\mathcal{P}_{m_{g}}$ then $x_{Q}\leq L(c)$
and thus $A^{\prime}_{1,\ldots,|A^{\prime}|-1}$ is inside $\mathcal{I}_{A}$
and is a negative arc of column $L(c)$. Moreover, $A^{\prime}$ does not pass
by $P_{m_{g}}$ since this tile is not inside $\mathcal{P}_{m_{g}}$. The
existence of this arc contradicts the definition of a shield, since $S$ should
be the prefix of $\min(\mathcal{I}_{A})$.

Secondly, consider the case where $a>m_{g}$. In this case, $P_{a}$ is inside
$\mathcal{P}_{m_{g}}$ but $S_{e+1}$ is not inside this area. Then, let
$e<h\leq|S|-1$ be such that $S_{h,\ldots,|S|-1}$ is the shortest suffix of $S$
such that $S_{h,\ldots,|S|-1}P_{a}$ is not inside $\mathcal{P}_{m_{g}}$.
Without loss of generality, we suppose that $h<|S|-1$ to ease the notation.
This definition implies that $\mathrm{glue}(S_{h}S_{h+1})$ intersects the
vertical segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$. Since $m_{g}<a$, the path $Q$ must intersect
with $S_{h+1,\ldots,|S|-1}P_{a}$ in order to reach $S_{0,\ldots,e}$. Let
$0\leq i\leq|Q|-1$ be such that $Q_{i,\ldots,|Q|-1}$ in the shortest suffix of
$Q$ which intersects with $S_{h+1,\ldots,|S|-1}P_{a}$ and let $i<j\leq|S|-1$
be such that $Q_{i,\ldots,j}$ is the shortest prefix of $Q_{i,\ldots,|Q|-1}$
which intersects with $S_{0,\ldots,h-1}$ (this index is correctly defined
since $Q$ intersects with $S_{0,\ldots,e}$). Let $h<i^{\prime}\leq|S|-1$ be
such that $S_{i^{\prime}}=Q_{i}$ and $0\leq j^{\prime}<h$ be such that
$S_{j^{\prime}}=Q_{j}$ then
$A^{\prime}=S_{0,\ldots,j^{\prime}-1}\text{rev}({Q_{i,\ldots,j}})S_{i^{\prime}+1,\ldots,|S|-1}P_{a,\ldots,f+1}$
is a simple path. Since $Q$ is in $\mathcal{P}_{m_{g}}$ then $x_{Q}\leq L(c)$
and thus $A^{\prime}_{1,\ldots,|A^{\prime}|-2}$ is inside $\mathcal{I}_{A}$
and $A^{\prime}$ is a negative arc of column $L(c)$. Moreover, this arc does
not pass by $S_{h}$ since this tile is not inside $\mathcal{P}_{m_{g}}$. Such
an arc contradicts the definition of a shield, since $S$ should be the prefix
of $\min(\mathcal{I}_{A})$. ∎

Let $R$ be the practical form of $P$ at index $m_{g}$. Lemma 34 implies that
$R$ does not intersect $S_{0,\ldots,e}$. Then, we can define
$\mathcal{R}_{m_{g}}$ as the _restrained protected area_ delimited by:

  * •

$P_{m_{g}}R$,

  * •

the vertical segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$,

  * •

$S_{0,\ldots,e}$,

  * •

the vertical segment between $\mathrm{glue}(P_{f}P_{f+1})$ and
$\mathrm{glue}(S_{0}S_{1})$.

This area is included into $\mathcal{P}_{m_{g}}$.

######  Lemma 35.

Consider the notation 23, $0<g\leq t$ and $0\leq e\leq|S|-1$ such that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is protected by the beginning of the
full-shield $S_{0,\ldots,e}$. Let $R$ be the practical form of $P$ at index
$m_{g}$ and let $\mathcal{R}_{m_{g}}$ be its restrained protected area.
Consider a path $Q$ such that $Q_{0}=R_{0}$. If $P_{m_{g}}Q$ is more right-
priority than $P_{m_{g}}R$ either $Q$ is in $\mathcal{R}_{m_{g}}$ or
$e_{Q}>L(c)$ or $Q$ intersects with the vertical segment between
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and $\mathrm{glue}(S_{e}S_{e+1})$.

###### Proof.

Let $0\leq v\leq|Q|-1$ such that $Q_{0,\ldots,v}$ is the largest prefix of $Q$
which is inside $\mathcal{R}_{m_{g}}$. Let $0\leq u\leq|Q|-1$ such that
$Q_{0,\ldots,u}$ is the largest common prefix between $Q$ and $R$. Since
$P_{m_{g}}Q$ is more right-priority than $P_{m_{g}}R$ then $u\leq v$. By lemma
34, $Q_{0,\dots,v}$ cannot intersect $S_{0,\ldots,e}$. If $Q_{0,\dots,v}$
intersects with $R_{u+1,\ldots,|R|-1}$ then let
$z=\max\\{i:\mathrm{pos}(R_{i})\text{ is occupied by a tile of
}Q_{0,\ldots,v}\\}$ and $u<z^{\prime}\leq v$ such that $P_{z}=Q_{z^{\prime}}$.
Then, $Q_{0,\dots,z^{\prime}}R_{z+1,\ldots,|R|-1}$ is in $\mathcal{R}_{t}$ and
$P_{0,\ldots,m_{g}}Q_{0,\dots,z^{\prime}}R_{z+1,\ldots,|R|-1}$ is producible
and $P_{m_{g}}Q_{0,\dots,z^{\prime}}R_{z+1,\ldots,|R|-1}$ is more right-
priority than $P_{m_{g}}R$ and satisfies all properties of definition 19. This
is a contradiction of the definition of $R$. Thus, if $v<|Q|-1$, then either
$Q_{v+1}$ is on column $L(c)+1$ or $\mathrm{glue}(Q_{v}Q_{v+1})$ is on the
vertical segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$. ∎

######  Lemma 36.

Consider the notation 23, $0<g\leq t$ and $0\leq e\leq|S|-1$ such that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is protected by the beginning of the
full-shield $S_{0,\ldots,e}$. Let $\mathcal{P}_{m_{g}}$ be the protected area
of $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$. Let $0\leq\ell\leq|P|-1$ be the
index of the last glue of $P$ on column $c$. If there exists a path $B$ such
that $B$ is in $\mathcal{P}_{m_{g}}$, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$, $w_{B}>c$, $B_{0}$ is a tile of
$P_{\ell+1,\ldots,f}$ then $B$ does not intersect with
$P_{m_{g}+1,\ldots,\ell}$ or $S_{0,\ldots,e}$.

###### Proof.

If $B$ intersects with $P_{m_{g}+1,\ldots,\ell}$ then let $B_{0,\ldots,v}$ be
the shortest prefix of $B$ which intersects with $P_{m_{g}+1,\ldots,\ell}$.
Let $B_{u,\ldots,v}$ be the shortest suffix of $B_{0,\ldots,v}$ which
intersects with $P_{\ell+1,\ldots,f}$. Since, $w_{B}>c$ then there exists
$i<j<k$ such that $P_{i,\ldots,k}$ is a dominant arc of $P$ on column $c$ and
$P_{j}=B_{v}$ (since $B$ is in ${\bf{P}}[{\mathcal{\gamma}}]$). Since
$B_{u,\ldots,v}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ and in
$\mathcal{P}_{m_{g}}$ then there is a contradiction with Lemma 3 since $P$ is
canonical for column $c$.

If $B$ intersects with $S_{0,\ldots,e}$ then let $B_{0,\ldots,v}$ be the
shortest prefix of $B$ which intersects with $S_{0,\ldots,e}$. Let
$B_{u,\ldots,v}$ be the shortest suffix of $B_{0,\ldots,v}$ which intersects
with $P_{\ell+1,\ldots,f}$. There exists $\ell+1\leq u^{\prime}\leq f$ such
that $P_{u^{\prime}}=B_{u}$. By the previous paragraph, $B_{u,\ldots,v}$ does
not intersect with $P_{m_{g}+1,\ldots,\ell}$. Thus
$P_{m_{g}+1,\ldots,u^{\prime}-1}B_{u,\ldots,v}$ is path which is in inside
$\mathcal{P}_{m_{g}}$. This path contradicts Lemma 34. ∎

####  6.2.3 Glues protected by an half-shield

Along this subsection, we will use the following notations:

######  Definition 22 (Notations for a glue protected by an half-shield).

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider a path
$P$ which is canonical for some column $c$ with $e_{\sigma}+|T|+1\leq c\leq
e_{\sigma}+5|T|+1$ and let $f$ be the index of its first glue on column
$L(c)$. Let $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the upward
(resp. downward) decomposition of $P$ into dominants arcs on column $c$ and
let $(b^{i})_{0\leq i\leq t+1}$ be the borders of this decomposition. Let $S$
be an half-shield associated to the cut $(m_{0},f)$ of $P_{0,\ldots,f+1}$ at
index $m_{0}<a\leq f$. Let $A=SP_{a,\ldots,f+1}$.

######  Lemma 37.

Consider the notation 22, there exists $0\leq g<t$ such that $m_{g}<a<b_{g}$.

###### Proof.

In this case, consider $\mathcal{C}$ the workspace of the cut $(m_{0},f)$ of
$P$ and its east-side $\mathcal{E}$. By definition of an half-shield,
$x_{SP_{a}}>c$ then $P_{a}$ is in $\mathcal{E}$. Thus, either $m_{t}<a\leq f$
or there exists $0\leq g<t$ such that $m_{g}<a<b_{g}$. If $g<t$ then the lemma
is true. Otherwise, we have $m_{t}<a\leq f$. In this case, remind that $m_{t}$
is the index of the last glue of $P$ on column $c$. Thus,
$x_{P_{a,\ldots,f+1}}>c$. Then, we would have $x_{A}>c$ which contradicts the
definition of a shield. ∎

Thanks to Lemma 37, we can now assume that there exists $0\leq g<t$ such that
$m_{g}<a<b_{g}$. In this case, we say that the glue $b_{g}$ is _protected_ by
the half-shield $S$. The category of this protected glue is a “backup”. The
index of the _hidden_ glue $h$ associated to $b_{g}$ is defined as the
northernmost (resp. southernmost) $\mathrm{glue}(P_{h}P_{h+1})$ among the
glues of $P_{0,\ldots,m_{g}+1}$ which are on column $c$ and strictly to the
south (resp. north) of $\mathrm{glue}(P_{b_{g}-1}P_{b_{g}})$, _i.e._ $0\leq
h\leq m_{g}$ and $\mathrm{glue}(P_{h}P_{h+1})$ is on column $c$ and its
$y$-coordinate is

$\displaystyle\max\\{y:\text{there }$ exists $0\leq i\leq m_{g}$ such that
$\mathrm{glue}(P_{i}P_{i+1})$ is $\displaystyle\text{on column $c$,
$y_{P_{i}}=y$ and $y<y_{P_{b_{g}}}$}\\}.$ $\displaystyle\text{(resp.
}\min\\{y:\text{there }$ exists $0\leq i\leq m_{g}$ such that
$\mathrm{glue}(P_{i}P_{i+1})$ is $\displaystyle\text{on column $c$,
$y_{P_{i}}=y$ and $y>y_{P_{b_{g}}}$}\\}.)$

Note that $h$ is correctly defined since $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$
is on column $c$ and strictly to the south (resp. north) of
$\mathrm{glue}(P_{b_{g}}P_{b_{g+1}})$101010In some case, $h$ can be $m_{g}$ or
in other cases, it is possible that $h<m_{0}$. Nevertheless, these different
cases are not relevant for the rest of the proof.. The _type_ of the protected
glue is the type of $\mathrm{glue}(P_{h}P_{h+1})$.

######  Fact 10.

Consider the notation 22, $0\leq g<t$ such that $m_{g}<a<b_{g}$ and let $h$ be
the index of the hidden glue $h$ associated to $b_{g}$. Then,
$H=P_{h,\ldots,b_{g}}$ is a hole of $P$ and the only tiles of $P$ inside its
interior $\mathcal{I}_{H}$ are $P_{h+1,\ldots,b_{g}-1}$. Thus, for any path
$Q$ such that $Q_{0}=P_{h+1}$ and $Q$ is in $\mathcal{I}_{H}$, the path
$P_{0,\ldots,h}Q$ is producible. Also, for any path $Q$ such that
$Q_{0}=P_{h+1}$, $Q_{|Q|-1}=P_{b_{g}-1}$ and $Q$ is in $\mathcal{I}_{H}$, the
path $P_{0,\ldots,h}QP_{b_{g},\ldots,|P|-1}$ is producible. In particular,
$P_{0,\ldots,h-1}LP_{b_{g}+1,\ldots,|P|-1}$ is producible where $L$ is the
minimum arc of this hole.

Along the article, the minimum arc $L$ of the hole $P_{h,\ldots,b_{g}}$ of $P$
is called _the hidden practical form_ of $P$ at index $h$. Also, by definition
$L_{|L|-2}=P_{b_{g}-1}$ then we can define $a\leq r<b_{g}$ such that
$SP_{a,\ldots,r}$ is the shortest prefix of $SP_{a,\ldots,b_{g}-1}$ which
intersects with $L$. Let $1\leq r^{\prime}<|L|-2$ such that
$P_{r}=L_{r^{\prime}}$. Then, the _practical form_ of the shield $S$ is
$SP_{a,\ldots,r-1}$ and $r^{\prime}$ is called its _practical index_. The
_protected area_ $\mathcal{P}_{b_{g}}$ of $b_{g}$ is the interior of the arc
$SP_{a,\ldots,r-1}L_{r^{\prime},\ldots,|L|-1}P_{b_{g}+1,\ldots,f+1}$.

######  Lemma 38.

Consider the notation 22, $0\leq g<t$ such that $m_{g}<a<b_{g}$ and let $h$ be
the index of the hidden glue $h$ associated to $b_{g}$. Let $L$ be the hidden
practical form of $P$ at index $h$ and $\mathcal{P}_{b_{g}}$ be the protected
area of $b_{g}$. Consider a path $Q$ such that $L_{0,\ldots,|L|-2}Q$ is a path
and $Q$ is in the protected area $\mathcal{P}_{b_{g}}$ then
$P_{0,\ldots,h-1}L_{0,\ldots,|L|-2}Q$ is a producible path and $Q$ does not
intersect with $SP_{a,\ldots,b_{g}-1}$.

###### Proof.

By definition of $\mathcal{P}_{b_{g}}$, the only tiles of
$P_{0,\ldots,h-1}L_{0,\ldots,|L|-2}$ which are inside this area are tiles of
$L$. Thus, since $L_{0,\ldots,|L|-2}Q$ is a path and since $Q$ is in
$\mathcal{P}_{b_{g}}$, then $P_{0,\ldots,h-1}L_{0,\ldots,|L|-2}Q$ is a
producible path.

For the sake of contradiction, suppose that $Q$ intersects with
$SP_{a,\ldots,b_{g}}$ then these intersections are agreements since the tile
assembly system is directed. Let $0\leq v\leq|Q|-1$ such that $Q_{0,\ldots,v}$
is the shortest prefix of $Q$ which intersects with $SP_{a,\ldots,b_{g}-1}$.
Let $0\leq u<v$ such that $Q_{u,\ldots,v}$ is the shortest suffix of
$Q_{0,\ldots,v}$ which intersects with $P_{b_{g}+1,\ldots,f+1}$ and let $0\leq
u^{\prime}\leq f$ such that $P_{u^{\prime}}=Q_{u}$. Now, if there exists
$0\leq v^{\prime}\leq|S|-1$ such that $S_{v}^{\prime}=Q_{v}$. In this case,
$S_{0,\ldots,v^{\prime}-1}\text{rev}({Q_{u,\ldots,v}})P_{u^{\prime}+1,\ldots,f}$
is an upward (resp. downward) arc of column $L(c)$ and this path is more right
priority than $SP_{a}$. This contradicts the definition of a shield. Finally,
if there exists $a\leq v^{\prime}\leq g-1$ such that $P_{v}^{\prime}=Q_{v}$
then there is a contradiction by lemma 3 since $P$ is canonical for column
$c$. ∎

Consider the practical form $R$ of $P$ at index
$\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$. A corollary of Lemma 38 is that
$SP_{a,\ldots,r}L_{r^{\prime},\ldots,|L|-1|}R$ is an arc of column $L(c)$. The
interior of this arc is the _restrained area_ $\mathcal{R}_{b_{g}}$ associated
to $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ is defined as the interior of this
arc. This area is included into $\mathcal{P}_{m_{g}}$.

######  Lemma 39.

Consider the notation 22, $0\leq g<t$ such that $m_{g}<a<b_{g}$ and let $h$ be
the index of the hidden glue $h$ associated to $b_{g}$. Let $L$ be the hidden
practical form of $P$ at index $h$ and let $R$ be the practical form of $P$ at
index $b_{g}$. Consider a path $Q$ such that $e_{Q}\leq L(c)$, such that
$L_{0,\ldots,|L|-2}Q$ is a path and such that $P_{b_{g}}Q$ is more right-
priority than $P_{b_{g}}R$ then $P_{0,\ldots,h-1}L_{0,\ldots,|L|-2}Q$ is a
producible path, $Q$ is inside the restrained area $\mathcal{R}_{b_{g}}$
associated to $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and $Q$ does not intersect
with $SP_{a,\ldots,b_{g}-1}$.

###### Proof.

Let $0\leq z\leq|Q|-1$ such that $Q_{0,\ldots,z}$ is the largest prefix of $Q$
which is inside the restrained area $\mathcal{R}_{b_{g}}$ associated to
$\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$. Then, by Lemma 38,
$P_{0,\ldots,h-1}L_{0,\ldots,|L|-2}Q_{0,\ldots,z}$ is a producible path and
$Q$ does not intersect with $SP_{a,\ldots,b_{g}-1}$. If $z=|Q|-1$ then the
lemma is true. For the sake of contradiction, suppose that $z<|Q|-1$. Let
$0\leq u\leq|Q|-1$ such that $Q_{0,\ldots,u}$ is the largest common prefix
between $Q$ and $R$. By hypothesis, we have $e_{Q}\leq L(c)$ and $P_{b_{g}}Q$
is more right-priority than $P_{b_{g}}R$. Then, $u<z$ and $Q_{u+1,\ldots,z}$
must intersect with $R_{u+1,\ldots,|R|-1}$. Then, let $0\leq v\leq|Q|-1$ such
that $Q_{u+1,\ldots,v}$ is the shortest prefix of $Q_{u+1,\ldots,|Q|-1}$ which
intersects with $R_{u+1,\ldots,|R|-1}$. Let $u<v^{\prime}\leq|R|-1$ such that
$R_{v^{\prime}}=Q_{v}$. Then $Q_{0,\ldots,v}R_{v^{\prime}+1,\ldots,|R|-1}$ is
more right-priority than $R$ and satisfies all the properties of Definition
19. This is a contradiction of the definition of $R$. ∎

######  Lemma 40.

Consider the notation 22, $0\leq g<t$ such that $m_{g}<a<b_{g}$ and let $h$ be
the index of the hidden glue $h$ associated to $b_{g}$. Let $L$ be the hidden
practical form of $P$ at index $h$ and let $S^{\prime}$ be the practical form
of the shield $S$. Consider two paths $Q$ and $Q^{\prime}$ such that
$T=QQ^{\prime}$ is a path, $e_{T}\leq L(c)$ and $Q$ is a positive upward
(resp. downward) minimum arc on column $c$ which is more right (resp. left)
priority than $L$. Moreover all intersections between $Q$ and $L$ are
agreements and all intersections between $Q$ and $S^{\prime}$ are agreements
Then $P_{0,\ldots,h-1}T$ is a producible path and $Q^{\prime}$ is inside the
restrained area $\mathcal{R}_{b_{g}}$ associated to
$\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and $Q^{\prime}$ does not intersect with
$SP_{a,\ldots,b_{g}-1}$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ is a
southern “backup” glue. Let $R$ be the practical form of $P$ at index $b_{g}$,
let $S^{\prime}$ be the practical form of the shield $S$ and $r^{\prime}$ be
its _practical index_. Note that the hypothesis $Q$ is more right-priority
than $L$ implies that $Q_{0}=L_{0}$ and $Q_{1}=L_{1}$ (which is coherent with
the fact that $Q$ is a positive arc on column $c$). Also note that we do not
suppose that $Q$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ (we will prove it later)
or an arc of $P$. We just suppose that $Q$ is minimum.

Firstly, let $0<u<|Q|-1$ such that $Q_{0,\ldots,u}$ is the largest common
prefix between $L$ and $Q$. Since $w_{L_{u,\ldots,|L|-2}}>c$, since $Q$ is a
minimum hole of column $c$ and since all intersections between $Q$ and $L$ are
agreements then $L_{u+1,\ldots,|L|-2}$ cannot intersect $Q$ (implying that
$L_{u+1,\ldots,|L|-1}$ cannot intersect $Q$). Similarly, let
$0<u^{\prime}<|Q|-1$ such that $Q_{0,\ldots,u^{\prime}}$ is the largest common
prefix between $Q$ and $U=L_{0,\ldots,r^{\prime}}\text{rev}({S^{\prime}})$.
For the sake of contradiction suppose that $Q$ is more-right priority than
$U$. Then since $e_{Q}\leq L(c)$ by hypothesis and $x_{S^{\prime}_{0}}=L(c)+1$
then $Q_{u^{\prime}+1,\ldots,|Q|-1}$ and $U_{u^{\prime}+1,\ldots,|U|-1}$
should intersect contradicting the fact that $Q$ is minimum. For the same
reason $u^{\prime}<|U|-1$. We can conclude that $u\geq r^{\prime}$ and
$u^{\prime}\geq r^{\prime}$, _i.e._ $L_{0,\ldots,r^{\prime}}$ is a prefix of
$Q$.

Let $v=\max\\{u,u^{\prime}\\}$ and thus $T_{r^{\prime},\ldots,v+1}$ is inside
by $\mathcal{R}_{b_{g}}$. We can define $v\leq z\leq|T|-1$ such that
$T_{v+1,\ldots,z}$ is the largest prefix of $T_{v+1,\ldots,|T|-1}$ which does
not intersect with $S^{\prime}L_{r^{\prime},\ldots,|L|-2}R$. Then
$T_{r^{\prime},\ldots,z}$ is inside $\mathcal{R}_{b_{g}}$ and if $z=|T|-1$
then the lemma is true. For the sake of contradiction, suppose that $z<|T|-1$.

Now, if $z\leq|Q|-1$ then $Q_{z}$ cannot be a tile of
$L_{r^{\prime},\ldots,|L|-1}$ (since $Q$ is self-avoiding and cannot intersect
$L_{u+1,\ldots,|L|-1}$). Thus $Q_{z}$ is a tile of $S^{\prime}$ (that is to
say $S$ or $P_{a,\ldots,b}$ (with $P_{b+1}=L_{r^{\prime}}$)) or $R$. Then
$Q_{z}$ is in the interior of the arc $SP_{a,\ldots,b_{g}-1}R$. Then we can
define $v\leq v^{\prime}<z$ such that $Q_{v^{\prime},\ldots,z-1}$ is the
shortest suffix of $Q_{v,\ldots,z-1}$ which intersects with
$SP_{a,\ldots,b_{g}-1}R$. Now if $Q_{z}$ or $Q_{v}$ is a tile of $S$, it would
contradict the definition of a shield as the prefix of the minimum arc of
$SP_{a,\ldots,f+1}$. If $Q_{z}$ or $Q_{v}$ is a tile of
$P_{a,\ldots,b_{g}-1}$, it would contradict Corollary 3. If $Q_{z}$ and
$Q_{v}$ are both tiles of $R$ then it would contradicts the definition of $R$.
All cases lead to contradiction.

Now, if $z>|Q|-1$ then $T_{|Q|-1}$ is in the interior of the arc
$SP_{a,\ldots,b_{g}-1}R$. Indeed $v\leq|Q|-1$ and thus $T_{|Q|-1}$ is not a
tile of $S^{\prime}L_{r^{\prime},\ldots,|L|-2}R$. Moreover, since
$w_{S^{\prime}L_{r^{\prime},\ldots,|L|-2}}>c$, $w_{SP_{a,\ldots,b_{g}-1}}>c$
and $x_{Q_{|Q|-1}}<c$ then $Q_{|Q|-1}$ is in the interior of the arc
$SP_{a,\ldots,b_{g}-1}R$. Thus we can define $|Q|-1<z^{\prime}\leq z$ such
that $T_{|Q|-1,\ldots,z^{\prime}}$ is the shortest prefix of
$T_{|Q|-1,\ldots,z}$ which intersects with $SP_{a,\ldots,b_{g}-1}R$ and $v\leq
v^{\prime}<|Q|-1$ such that $T_{v^{\prime},\ldots,|Q|-1}$ is the shortest
suffix of $T_{v,\ldots,|Q|-1}$ which intersects with $SP_{a,\ldots,b_{g}-1}R$.
We obtain a contradiction as in the previous paragraph since
$T_{v^{\prime},\ldots,z^{\prime}}$ is inside the interior of
$SP_{a,\ldots,b_{g}-1}R$ and $T_{v^{\prime}}$ and $T_{z^{\prime}}$ are the
only tiles of $P_{v^{\prime},\ldots,z^{\prime}}$ which are also tiles of in
the interior of the $SP_{a,\ldots,b_{g}-1}R$. ∎

######  Lemma 41.

Consider the notation 22, $0\leq g<t$ such that $m_{g}<a<b_{g}$ and let $h$ be
the index of the hidden glue $h$ associated to $b_{g}$. Let
$0\leq\ell\leq|P|-1$ be the index of the last glue of $P$ on column $c$. If
there exists a path $B$ such that $B$ is in $\mathcal{P}_{b_{g}}$, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$, $w_{B}>c$, $B_{0}$ is a tile of
$P_{\ell+1,\ldots,f}$ then $B$ does not intersect with $P_{a,\ldots,\ell}$ or
$S$.

###### Proof.

If $B$ intersects with $P_{m_{g}+1,\ldots,\ell}$ then let $B_{0,\ldots,v}$ be
the shortest prefix of $B$ which intersects with $P_{m_{g}+1,\ldots,\ell}$.
Let $B_{u,\ldots,v}$ be the shortest suffix of $B_{0,\ldots,v}$ which
intersects with $P_{\ell+1,\ldots,f}$. Since, $w_{B}>c$ then there exists
$i\leq j<k$ such $P_{i,\ldots,k}$ is a dominant arc of $P$ on column $c$ and
$P_{j}=B_{v}$ (since $B$ is in ${\bf{P}}[{\mathcal{\gamma}}]$). Since
$B_{u,\ldots,v}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ and in
$\mathcal{P}_{m_{g}}$ then there is a contradiction with Corollary 3 since $P$
is canonical for column $c$.

If $B$ intersects with $S$ then let $B_{0,\ldots,v}$ be the shortest prefix of
$B$ which intersects with $S$. Let $B_{u,\ldots,v}$ be the shortest suffix of
$B_{0,\ldots,v}$ which intersects with $P_{\ell+1,\ldots,f}$. There exists
$\ell+1\leq u^{\prime}\leq f$ such that $P_{u^{\prime}}=B_{u}$. By the
previous paragraph, $B_{u,\ldots,v}$ does not intersect with
$P_{m_{g}+1,\ldots,\ell}$. Thus
$P_{m_{g}+1,\ldots,u^{\prime}-1}B_{u,\ldots,v}$ is path which is in inside
$\mathcal{P}_{m_{g}}$. This path contradicts Lemma 38. ∎

###  6.3 Combining two identical “main” glues

Along this subsection, we will use the following notations:

######  Definition 23 (Notations for combining two “main” glues).

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider two paths
$P$ and $Q$ which are canonical for some columns $c$ and $c^{\prime}$
respectively with $e_{\sigma}+|T|+1\leq c<c^{\prime}\leq e_{\sigma}+5|T|+1$.
Let $0\leq f<|P|-1$ be the index of the first glue of $P$ on column $L(c)$.
Let $0\leq f^{\prime}<|Q|-1$ be the index of the first glue of $Q$ on column
$L(c^{\prime})$. Let $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the
upward (resp. downward) decomposition of $P$ into dominants arcs on column
$c$. Let $0\leq g\leq t$ such that $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is a
protected “main” glue of $P$. Let $R$ be the practical form of the protected
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and $\mathcal{R}_{m_{g}}$ its restrained
protected area. Consider the index $0\leq p\leq|Q|-1$ of a protected “main”
glue of the upward (resp. downward) decomposition of $Q$ into dominants arcs
on column $c^{\prime}$. Let $R^{\prime}$ be the practical form of the
protected $\mathrm{glue}(Q_{p}Q_{p+1})$ of $Q$ and $\mathcal{R}^{\prime}_{p}$
its restrained protected area. Suppose that
$\mathrm{glue}(P_{m_{g}}P_{m_{g+1}})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ have
the same type and let
$\overrightarrow{v}=\overrightarrow{\mathrm{pos}(P_{m_{g}})\mathrm{pos}(Q_{p})}$.

######  Lemma 42.

Consider the notation 23, $R_{0,\ldots,|R|-2}+\overrightarrow{v}$ is not
inside $\mathcal{R}^{\prime}_{p}$.

###### Proof.

Without loss of generality, we suppose that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ are
southern main glues. For the sake of contradiction, suppose that
$R_{0,\ldots,|R|-2}+\overrightarrow{v}$ is inside $\mathcal{R}^{\prime}_{p}$.
We remind that by definition of $R_{0}$, we have $R_{0}=P_{m_{g}+1}$. Also, by
definition of $\overrightarrow{v}$,
$\mathrm{pos}(R_{0})+\overrightarrow{v}=\mathrm{pos}(Q_{p}+1)$. By hypothesis,
$\mathrm{glue}(P_{m_{g}}P_{m_{g+1}})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ have
the same type thus $R_{0}+\overrightarrow{v}$ and $Q_{p}$ binds together. Then
by Fact 9, $Q_{0,\ldots,p}(R_{0,\ldots,|R|-2}+\overrightarrow{v})$ is a
producible path.

Firstly, suppose that there is no intersection between $R_{0,\ldots,|R|-2}$
and $P_{f+1,\ldots,|P|-1}$. By definition of $R$, we have $R_{|R|-2}=P_{f}$
then $R_{|R|-2}$ and $P_{f+1}$ binds together (which also true for
$R_{|R|-2}+\overrightarrow{v}$ and $P_{f+1}+\overrightarrow{v}$). Let
$0\leq\ell^{\prime}\leq|Q|-1$ be the index of the last glue of $Q$ on column
$c^{\prime}$. Since $\mathrm{glue}(Q_{p}Q_{p+1})$ is on column $c^{\prime}$,
we have $p\leq\ell^{\prime}$. Then, it is possible to apply Lemma 24 on
$Q_{0,\ldots,p}(R_{0,\ldots,|R|-2}+\overrightarrow{v})$ and
$P_{f+1,\ldots,|P|-1}+\overrightarrow{v}$ (the bound is satisfied by
definition of $L(c^{\prime})$, see Fact 7). We obtain that
$Q_{0,\ldots,p}(R_{0,\ldots,|R|-2}+\overrightarrow{v})P_{f+1,\ldots,|P|-1}+\overrightarrow{v}$
is in ${\bf{P}}[{\mathcal{\gamma}}]$. Nevertheless, since $P$ is canonical for
column $c$ then by definition $x_{P_{|P|-1}}=e_{\gamma}$ and then
$x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$. This is a contradiction.

Secondly, suppose that there are some intersections between
$R_{0,\ldots,|R|-2}$ and $P_{f+1,\ldots,|P|-1}$. Since, $P$ and
$P_{0,\ldots,m_{g}}R$ are producible path, then all intersections between $R$
and $P_{f+1,\ldots,|P|-1}$ are agreements. Let

$u=\max\\{i:\mathrm{pos}(P_{i})\text{ is occupied by a tile of }R\\}$

and let $u^{\prime}$ such that $R_{u^{\prime}}=P_{u}$. We are in case where
$u\geq f+1$ and by definition of $u$,
$R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is a path. For the sake of
contradiction suppose that $R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is
more left-priority than $R$ then $P_{u+1}$ is inside a finite area delimited
by $R$ and $P_{m_{g},\ldots,f+1}$. Nevertheless, since
$x_{P_{|P|-1}}=e_{\gamma}>L(c)+1$ and
$L(c)+1=\max\\{e_{R},e_{P_{m_{g},\ldots,f}}\\}$ then $P_{u+1,\ldots,|P|-1}$
must intersect with either $P_{m_{g},\ldots,f+1}$ (which cannot occur since
$P$ is self-avoiding) or $R$ (which cannot occur by definition of $u$). This
is a contradiction and then $R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is
more right-priority than $R$. Since $(R+\overrightarrow{v})$ is inside
$\mathcal{R}^{\prime}_{p}$ then
$Q_{p}(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1})+\overrightarrow{v}$ is
more right-priority than $Q_{p}R^{\prime}$. Note that $u\geq f$ and then
$x_{P_{u,\ldots,|P|-1}}>c$ (implying that
$x_{P_{u,\ldots,|P|-1}}+\overrightarrow{v}>c^{\prime}$). Then, by Lemma 35,
$(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1})+\overrightarrow{v}$ can leave
$\mathcal{R}^{\prime}_{p}$ only by intersecting with column $L(c^{\prime})$.
Let $u\leq v\leq|P|-1$ such that $\mathrm{glue}(P_{v}P_{v+1})$ is the first
glue of $(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1})+\overrightarrow{v}$ on
column $L(c^{\prime})$. then
$(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,v})+\overrightarrow{v}$ is inside
$\mathcal{R}^{\prime}_{p}$ and
$Q_{0,\ldots,p}(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,v})+\overrightarrow{v}$
is producible by Fact 9. We can now apply Lemma 24 on
$Q_{0,\ldots,p}(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,v})+\overrightarrow{v}$
and $(P_{v+1,\ldots,|P|-1})+\overrightarrow{v}$ and we obtain that
$Q_{0,\ldots,p}(R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1})+\overrightarrow{v}$
is producible. Nevertheless, since $P$ is canonical for column $c$ then by
definition $x_{P_{|P|-1}}=e_{\gamma}$ and then
$x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$. This is a contradiction.

∎

######  Lemma 43.

Consider the notation 23, then
$P_{0,\ldots,m_{g}}(R^{\prime}-\overrightarrow{v})$ is producible. Moreover,
there exists $0\leq a\leq|R|-1$ such that
$(\text{rev}({R^{\prime}_{a,\ldots,|R^{\prime}|-1}})-\overrightarrow{v})R_{a+1,|R|-1}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{R}_{m_{g}}$.

###### Proof.

Without loss of generality, we suppose that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ are
southern main glues. We remind that by definition of $R_{0}$, we have
$R_{0}=P_{m_{g}+1}$. Also, by definition of $\overrightarrow{v}$,
$\mathrm{pos}(R_{0})+\overrightarrow{v}=\mathrm{pos}(Q_{p}+1)$. By hypothesis,
$\mathrm{glue}(P_{m_{g}}P_{m_{g+1}})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ have
the same type thus $R_{0}+\overrightarrow{v}$ and $Q_{p}$ binds together.
Since the tile assembly system is directed, we have
$R_{0}+\overrightarrow{v}=R^{\prime}_{0}$. By Lemma 42,
$(R_{0,\ldots,|R|-2}+\overrightarrow{v})$ is not inside
$\mathcal{R}^{\prime}_{p}$. Thus $(R_{0,\ldots,|R|-2}+\overrightarrow{v})$
cannot be a prefix of $R^{\prime}$.

For the sake of contradiction, suppose that $Q_{p}(R+\overrightarrow{v})$ is
more right-priority than $Q_{p}R^{\prime}$. Consider $v$ such that
$(R_{0,\ldots,v}+\overrightarrow{v})$ is the largest prefix of
$(R+\overrightarrow{v})$ which is inside $\mathcal{R}^{\prime}_{p}$. Since
$(R_{0,\ldots,|R|-2}+\overrightarrow{v})$ is not inside
$\mathcal{R}^{\prime}_{p}$ then $v<|R|-1$. Moreover, since
$(R_{0,\ldots,|R|-2}+\overrightarrow{v})\leq L(c^{\prime})$, then by Lemma 35,
$\mathrm{glue}(R_{v}R_{v+1})$ is on the vertical ray starting at
$\mathrm{glue}(Q_{p}Q_{p+1})$ and going south. Note that this glue should
point west to leave $\mathcal{R}^{\prime}_{p}$. Then, consider $0\leq u\leq v$
such that $(R_{u,\ldots,v+1}+\overrightarrow{v})$ is a positive arc on column
$c^{\prime}$. Then $R_{u,\ldots,v+1}$ is a positive arc on column $c$ such
that $y_{R_{v}}<y_{P_{m_{g}}}$. If $g=0$ then $R_{u,\ldots,v+1}$ would
intersect the glue ray to the south of $\mathrm{glue}(P_{m_{0}}P_{m_{0}+1})$
contradicting the definition of $R$. If $g>0$ then there exists a shield $S$
and $0\leq e\leq|S|-1$ such that $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ is
protected by the end of the shield $S_{0,\ldots,e}$. In this case, either
$R_{u,\ldots,v+1}$ intersects $S_{0,\ldots,e}$ (which is a contradiction by
Lemma 34) or $R_{u,\ldots,v+1}$ leaves $\mathcal{R}_{m_{g}}$ by crossing the
vertical segment between $\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and
$\mathrm{glue}(S_{e}S_{e+1})$ (contradicting the definition of $R$).

The last possible case is that $R^{\prime}$ is more right-priority than
$(R+\overrightarrow{v})$. This means that $R^{\prime}-\overrightarrow{v}$ is
more right-priority than $R$. Remark that the paths $R$ and $R^{\prime}$ and
the protected areas $\mathcal{R}_{g}$ and $\mathcal{R}^{\prime}_{p}$ have the
same properties. Then with the same kind of reasoning, it is possible to prove
that $R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v}$ is inside
$\mathcal{P}_{m_{g}}$. By Fact 9, we obtain that
$P_{0,\ldots,m_{g}}(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})$
is producible. Since
$x_{R^{\prime}_{|R^{\prime}|-1}-\overrightarrow{v}}=L(c)+1$ and
$e_{P_{0,\ldots,m_{g}}(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})}\leq
L(c)$ then $P_{0,\ldots,m_{g}}(R^{\prime}-\overrightarrow{v})$ is also
producible. Consider $0\leq a\leq|R|-1$ such that $R_{0,\ldots,a}$ is the
largest common prefix between $R$ and $R^{\prime}-\overrightarrow{v}$. By
Lemma 31 (if $g=0$) or Lemma 35 (if $g>0$), $R_{a+1,\ldots,|R|-2}$ and
$R^{\prime}_{a+1,\ldots,|R^{\prime}|-2}-\overrightarrow{v}$ do not intersect.
Since
$x_{R_{|R|-1}}=x_{R^{\prime}_{|R^{\prime}|-1}}-\overrightarrow{v}=L(c)+1$ and
$y_{R_{|R|-2}}\neq y_{R^{\prime}_{|R^{\prime}|-2}}$, then we have
$\mathrm{pos}(R_{|R|-1})\neq\mathrm{pos}(R^{\prime}_{|R^{\prime}|-1})-\overrightarrow{v}$.
Then, $R_{a+1,\ldots,|R|-1}$ and
$R^{\prime}_{a+1,\ldots,|R^{\prime}|-1}-\overrightarrow{v}$ do not intersect.
To conclude, the path
$\text{rev}({R^{\prime}_{a,\ldots,|R^{\prime}|-1}-\overrightarrow{v}})R_{a+1,|R|-1}$
is a negative upward arc of column $L(c)$ and its interior is included into
$\mathcal{R}_{m_{g}}$. ∎

######  Lemma 44.

Consider the notation 23, there exists an upward (resp. downward) minimum arc
$A^{\prime}$ on column $L(c)$ such that its interior
$\mathcal{I}_{A^{\prime}}$ is included into $\mathcal{R}_{m_{g}}$, such that
$A^{\prime}$ is a path of ${\bf{P}}[{\mathcal{\gamma}}]$, such that
$A^{\prime}_{0}=Q_{f^{\prime}+1}-\overrightarrow{v}$ and
$A^{\prime}_{|A^{\prime}|-1}=P_{f+1}$.

###### Proof.

By Lemma 43, there exists a negative upward (resp. downward) arc $B$ of column
$L(c)$ such
$B_{0}=R^{\prime}_{|R^{\prime}|-1}-\overrightarrow{v}=Q_{f^{\prime}+1}-\overrightarrow{v}$
and $B_{|B|-1}=R_{|R|-1}=P_{f+1}$. Moreover, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$ and its interior is included into
$\mathcal{R}_{m_{g}}$. The path $A^{\prime}$ defined as
$\min(\mathcal{I}_{B})$ satisfies the condition of the lemma. ∎

######  Lemma 45.

Consider the notation 23 and the arc $A^{\prime}$ of Lemma 44. If
$w_{A^{\prime}}\leq c$, then either there exists $g\leq i<t$ such that $b_{i}$
is protected or there exists $g<i\leq t$ such that $m_{i}$ is protected.

###### Proof.

By definition, we have $A^{\prime}_{|A^{\prime}|-2}=P_{f}$, then $A^{\prime}$
intersects with $P_{m_{g},\ldots,f}$. Let $S^{\prime}$ be the largest prefix
of $A^{\prime}$ such that $S^{\prime}$ does not intersect
$P_{m_{g},\ldots,f}$. Note that, $S^{\prime}$ does not intersect with
$P_{0,\ldots,m_{g}-1}$ since the interior of $A^{\prime}$ is in
$\mathcal{R}_{m_{g}}$. Also, $S^{\prime}$ contains at least $S_{0}$ since
$x_{S_{0}}=L(c)+1$,
$\mathrm{pos}(S_{0})\neq\mathrm{pos}(A^{\prime}_{|A^{\prime}|-1})$ and
$x_{P_{m_{g},\ldots,f}}<L(c)+1$. Since $S^{\prime}_{1,\ldots,|S^{\prime}|-1}$
is in $\mathcal{P}_{m_{g}}$ and by definition of $S^{\prime}$ there exists
$m_{g}<a^{\prime}\leq f$ such $S^{\prime}P_{a^{\prime}}$ is a prefix of
$A^{\prime}$. Since $S^{\prime}=A^{\prime}_{0}$, then
$S^{\prime}P_{a^{\prime},\ldots,f+1}$ is also a negative upward (resp.
downward) arc of column $L(c)$. Moreover, since $A^{\prime}$ is minimum then
$A^{\prime}$ is inside the interior of the arc
$S^{\prime}P_{a^{\prime},\ldots,f+1}$. Then, we have
$w_{S^{\prime}P_{a^{\prime},\ldots,f+1}}\leq w_{A^{\prime}}\leq c$. This
implies that $S^{\prime}$ is a shield of the cut $(m_{0},f)$ of $P$. Now,
either $S^{\prime}$ is a full-shield but since $S^{\prime}$ is in
$\mathcal{P}_{m_{g}}$ then it cannot intersect $b^{i}$ for $i\leq g$. Thus, by
Lemma 33 there exists $i>g$ such that $m_{i}$ is protected and the lemma is
true. Now, if $S^{\prime}$ is an half-shield then $S^{\prime}P_{a^{\prime}}$
is in the east-side $\mathcal{E}$ of $\mathcal{C}$ and we have
$m_{i}<a^{\prime}<b_{i}$ for some $0\leq i\leq t$. Also, since
$S^{\prime}_{1,\ldots,|S^{\prime}_{|}-1}$ is in $\mathcal{P}_{m_{g}}$, then
$i\geq g$ and the glue $b_{i}$ is protected with $b_{i}>m_{g}$. ∎

######  Lemma 46.

Consider the notation 23 and the arc $A^{\prime}$ of Lemma 44. If there exists
an index $p^{\prime}\geq p$ such that the
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a protected glue (either a
“main” or “backup” one) of the northern (resp. southern) decomposition of $Q$
into dominant arcs then $w_{A^{\prime}}\leq c$.

###### Proof.

Without loss of generality, we suppose that
$\mathrm{glue}(P_{m_{g}}P_{m_{g}+1})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ are
southern main glues. For the sake of contradiction, assume that
$w_{A^{\prime}}>c$ and we denote by $0\leq\ell^{\prime}\leq|Q|-1$ the index of
the last glue of $Q$ of column $c^{\prime}$.

First of all, consider the protected area $\mathcal{P}_{p^{\prime}}$ (be
careful $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a northern main
glue). Note that $Q_{f^{\prime}+1}=A^{\prime}_{0}+\overrightarrow{v}$ and
$Q_{f^{\prime}}=A^{\prime}_{1}+\overrightarrow{v}$. Then we can defined
$0<v\leq|A^{\prime}|-1$ such that $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$
is the largest prefix of
$A^{\prime}_{1,\ldots,|A^{\prime}|-1}+\overrightarrow{v}$ which is inside
$\mathcal{P}_{p^{\prime}}$. Now, since
$P_{0,\ldots,m_{g}}(R^{\prime}-\overrightarrow{v})$ is producible (by Lemma
43) and since $A^{\prime}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ (by Lemma 44)
then all intersections between $A^{\prime}+\overrightarrow{v}$ and
$R^{\prime}$ are agreements. Since $p^{\prime}\geq p$ then the only tiles of
$Q_{0,\ldots,p}R^{\prime}$ which are inside $\mathcal{P}_{p^{\prime}}$ are
tiles of $R^{\prime}$. Then, since $Q_{0,\ldots,p}R^{\prime}$ is producible
(by definition of $R^{\prime}$), then
$\mathrm{asm}{(Q_{0,\ldots,p}R^{\prime})}\cup\mathrm{asm}{(A^{\prime}_{1,\ldots,v}+\overrightarrow{v})}$
is a producible assembly. Thus, $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$
is in ${\bf{P}}[{\mathcal{\gamma}}]$ and in particular, all intersections
between $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ and
$Q_{p^{\prime},\ldots,f^{\prime}}$ are agreements.

Since $w_{A^{\prime}}+\overrightarrow{v}>c^{\prime}$ then
$A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ cannot intersect with the ray
starting in $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ and going north.
By Lemma 32 (if $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is visible
from the north), Lemma 36 (if $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$
is a “ main” glue protected by a shield) or Lemma 41 (if
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a “backup” glue protected
by a shield) then $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ cannot
intersect with $Q_{p^{\prime}+1,\ldots,\ell^{\prime}}$ and the shield of
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ (in the relevant case).
Finally, if there exists $\ell^{\prime}\leq v^{\prime}\leq f^{\prime}$ such
that $Q_{v^{\prime}}=A^{\prime}_{v}+\overrightarrow{v}$ and
$\text{rev}({Q_{v^{\prime},\ldots,f^{\prime}+1}})(A^{\prime}_{v+1}+\overrightarrow{v})$
turns left of $\text{rev}({Q_{v^{\prime}-1,\ldots,f^{\prime}+1}})$ then there
exist $\ell^{\prime}\leq u^{\prime}\leq f^{\prime}$ and $1\leq u\leq v$ such
that $Q_{u^{\prime}}=A^{\prime}_{u}+\overrightarrow{v}$ and
$(A^{\prime}_{1,\ldots,u}+\overrightarrow{v})Q_{u^{\prime}+1}$ turns right of
$(A^{\prime}_{1,\ldots,u+1}+\overrightarrow{v})$. Since
$x_{Q_{\ell^{\prime}}}=c^{\prime}$ and
$w_{A^{\prime}+\overrightarrow{v}}>c^{\prime}$, then
$Q_{u^{\prime}+1,\ldots,\ell^{\prime}+1}$ intersects with
$A^{\prime}+\overrightarrow{v}$ contradicting the fact that
$A^{\prime}+\overrightarrow{v}$ (and $A^{\prime}$) is a minimum arc. Then,
$v\geq|A^{\prime}|-2$ and
$A^{\prime}_{1,\ldots,|A^{\prime}|-2}+\overrightarrow{v}$ is in
$\mathcal{P}_{p^{\prime}}$ and in ${\bf{P}}[{\mathcal{\gamma}}]$.

Since
$A^{\prime}_{1}+\overrightarrow{v}=Q_{f^{\prime}}=R^{\prime}_{|R^{\prime}|-2}$
then $A^{\prime}_{1,\ldots,|A^{\prime}|-2}+\overrightarrow{v}$ and
$R^{\prime}$ intersect. Let $0\leq b\leq R^{\prime}$ such that
$R^{\prime}_{0,\ldots,b}$ is the shortest prefix of $R^{\prime}$ which
intersects with $A^{\prime}+\overrightarrow{v}$. Let $0\leq
b^{\prime}\leq|A^{\prime}|-1$ such that
$A^{\prime}_{b^{\prime}}+\overrightarrow{v}=R^{\prime}_{b}$ and then
$T=R^{\prime}_{0,\ldots,b}(A^{\prime}_{b^{\prime}+1,\ldots,|A^{\prime}|-2}+\overrightarrow{v})$
is a path and $Q_{0,\ldots,p}T$ is a producible path. Note that
$P_{f+1}+\overrightarrow{v}=A^{\prime}_{|A^{\prime}|-1}$ and
$P_{f+1}+\overrightarrow{v}$ is on column $L(c^{\prime})+1$. By Lemma 24, if
$P_{f+1,\ldots,|P|-1}+\overrightarrow{v}$ does not intersect with $T$, then
$Q_{0,\ldots,p}T(P_{f+1,\ldots,|P|-1}+\overrightarrow{v})$ is a producible
path. Nevertheless, $x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$ and we have
a contradiction.

Finally, suppose that there is an intersection between $T$ and
$(P_{f+1,\ldots,|P|-1}+\overrightarrow{v})$. By definition
$P_{f+1,\ldots,|P|-1}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$, by Lemma 44
$A^{\prime}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ and by Lemma 43,
$R^{\prime}-\overrightarrow{v}$ is ${\bf{P}}[{\mathcal{\gamma}}]$ . Thus all
intersections between these paths are agreements. Let
$d=\max\\{i:\mathrm{pos}(P_{i})+\overrightarrow{v}\text{ is occupied by a tile
of }T\\}$, we are in a case where $d>f$. Let $0\leq d^{\prime}\leq|T|-1$ such
that $T_{d^{\prime}}=P_{d}+\overrightarrow{v}$. Let $d\leq
f^{\prime\prime}\leq|P|-1$ be the index of the first glue of
$P_{d,\ldots,|P|-1}+\overrightarrow{v}$ which is on column $L(c^{\prime})$. If
$T_{0,\ldots,d^{\prime}}(P_{d,\dots,f^{\prime\prime}}+\overrightarrow{v})$ is
more left-priority than $T$, then $P_{d,\dots,f^{\prime\prime}}$ is inside a
finite area delimited by $T-\overrightarrow{v}$ and $P_{m_{g},\ldots,f+1}$.
Nevertheless, $P_{d,\dots,f^{\prime\prime}}$ must leave this area but it
cannot intersect with $P_{m_{g},\ldots,f+1}$ (since $P$ is simple) or
$T-\overrightarrow{v}$ (by definition of $d$). Then
$T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v})$
is more right-priority than $T$. If
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ is inside
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ then

$Q_{0,\ldots,p}T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v})$

is producible and by Lemma 24,
$Q_{0,\ldots,p}T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,|P|-1}+\overrightarrow{v})$
is producible. Again, $x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$ and we
have a contradiction.

Suppose that $P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ leaves
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ by leaving
$\mathcal{P}_{p^{\prime}}$ first. Then since $w_{T}\leq
c^{\prime}<L(c^{\prime})\leq e_{T}$ and
$c^{\prime}<w_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}<e_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}\leq
L(c^{\prime})$, then $P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ must
intersect with $T$. This is a contradiction by the definition of $d$. If
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ leaves
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ by leaving
$\mathcal{R}^{\prime}_{p}$. Since
$w_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}>c^{\prime}$ then
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ should intersect with the
shield of $\mathrm{glue}(Q_{p}Q_{p+1})$. In this case, it is possible to find
a path in
$\mathrm{asm}{(T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}))}\cup\mathrm{asm}{(Q_{\ell^{\prime},\ldots,f^{\prime}})}$
which intersects with the shield and is in $\mathcal{R}^{\prime}_{p}$ which is
a contradiction by Lemma 34. All cases lead to contradiction and the lemma is
true.

∎

######  Lemma 47.

Consider the notation 23. If there exists an index $p^{\prime}\geq p$ such
that the $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a protected glue
(either a “main” or “backup” one) of the northern (resp. southern)
decomposition of $Q$ into dominant arcs then either there exists $g\leq i<t$
such that $b_{i}$ is protected or there exists $g<i\leq t$ such that $m_{i}$
is protected.

###### Proof.

By Lemma 44, there exists an upward (resp. downward) minimum arc $A^{\prime}$
on column $L(c)$ such that its interior $\mathcal{I}_{A^{\prime}}$ is included
into $\mathcal{P}_{m_{g}}$, such that $A^{\prime}$ is a path of
${\bf{P}}[{\mathcal{\gamma}}]$, such that
$A^{\prime}_{0}=Q_{f^{\prime}+1}-\overrightarrow{v}$ and
$A^{\prime}_{|A^{\prime}|-1}=P_{f+1}$. Moreover, by Lemma 46, we have
$w_{A^{\prime}}\leq c$. Then by Lemma 45, the lemma is true. ∎

###  6.4 Combining two Half-Shield

Along this subsection, we will use the following notations:

######  Definition 24 (Notations for combining two “half” glues).

Suppose that $e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$ and consider two paths
$P$ and $Q$ which are canonical for some columns $c$ and $c^{\prime}$ with
$e_{\sigma}+|T|+1\leq c<c^{\prime}\leq e_{\sigma}+5|T|+1$.

  * •

Let $0\leq f<|P|-1$ be the index of the first glue of $P$ on column $L(c)$.

  * •

Let $0\leq f^{\prime}<|Q|-1$ be the index of the first glue of $Q$ on column
$L(c^{\prime})$.

  * •

Let $(m_{i})_{0\leq i\leq t}$ and $(b_{i})_{0\leq i<t}$ the upward (resp.
downward) decomposition of $P$ into dominants arcs on column $c$. Let $0\leq
g<t$, a path $S$ and an index $m_{g}<a<b_{g}$ such that
$\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ is a “backup” glue of $P$ protected by
the half-shield $S$ at position $a$.

  * •

Let $0\leq p<|Q|-1$ such that $\mathrm{glue}(Q_{p}Q_{p+1})$ is a “backup” glue
of the upward (resp. downward) decomposition of $Q$ into dominants arcs on
column $c^{\prime}$. This $\mathrm{glue}(Q_{p}Q_{p+1})$ is protected by the
half-shield $S^{\prime}$ at position $a^{\prime}$.

  * •

Let $h$ be the index of the hidden glue associated to
$\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$, let $L$ be the hidden practical form of
$P$ at index $h$, let $R$ be the practical form of $P$ at index $b_{g}$ and
$\mathcal{R}_{m_{g}}$ its restrained protected area.

  * •

Let $h^{\prime}$ be the index of the hidden glue associated to
$\mathrm{glue}(Q_{p}Q_{p+1})$, let $L^{\prime}$ be the hidden practical form
of $Q$ at index $h^{\prime}$, let $R^{\prime}$ be the practical form of $Q$ at
index $p$ and $\mathcal{R}^{\prime}_{p}$ its restrained protected area.

  * •

$\mathrm{glue}(P_{b_{g}}P_{b_{g+1}})$ and $\mathrm{glue}(Q_{p}Q_{p+1})$ have
the same type and let
$\overrightarrow{v}=\overrightarrow{\mathrm{pos}(P_{b_{g}})\mathrm{pos}(Q_{p})}$.

######  Lemma 48.

Consider the notation 24, then it is not possible that
$(L_{0,\ldots,|L|-2}+\overrightarrow{v})(R+\overrightarrow{v})$ is more right-
priority (resp. left-priority) that
$L^{\prime}_{0,\ldots,|L^{\prime}|-2}R^{\prime}$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and
$\mathrm{glue}(Q_{p}Q_{p+1})$ are southern “backup” glues. For the sake of
contradiction, suppose that
$(L_{0,\ldots,|L|-2}+\overrightarrow{v})(R+\overrightarrow{v})$ is more right-
priority than $L^{\prime}_{0,\ldots,|L^{\prime}|-2}R^{\prime}$.

If $(L+\overrightarrow{v})$ is more right-priority than $L^{\prime}$, then it
is possible to apply Lemma 40. Indeed, $L^{\prime}-\overrightarrow{v}$ is more
left-priority than $L$ and $L^{\prime}-\overrightarrow{v}$ is in the interior
of $L$. Thus, all intersections between $L^{\prime}-\overrightarrow{v}$ and
$L$ would be agreements. Similarly all intersections between $L$ and the
translation of the practical shield of $\mathrm{glue}(Q_{p}Q_{p+1})$ by
$-\overrightarrow{v}$ are agreements. We obtain that
$Q_{0,\ldots,h^{\prime}-1}(L+\overrightarrow{v})(R_{1,\ldots,|R|-2}+\overrightarrow{v})$
is producible, $R_{0,\ldots,|R|-2}+\overrightarrow{v}$ is in
$\mathcal{R}^{\prime}_{p}$ and $R_{0,\ldots,|R|-2}+\overrightarrow{v}$ does
not intersect $S^{\prime}Q_{a^{\prime},\ldots,p-1}$. If
$(L+\overrightarrow{v})$ is not more right-priority than $L^{\prime}$ then we
have $(L+\overrightarrow{v})=L^{\prime}$. This implies that
$R+\overrightarrow{v}$ is more right-priority than $R^{\prime}$, then by Lemma
39 we have the same properties.

Firstly, suppose that there is no intersection between $R_{0,\ldots,|R|-2}$
and $P_{f+1,\ldots,|P|-1}$. By definition of $R$, we have $R_{|R|-2}=P_{f}$
then $R_{|R|-2}$ and $P_{f+1}$ binds together (which is also true for
$R_{|R|-2}+\overrightarrow{v}$ and $P_{f+1}+\overrightarrow{v}$). Let
$0\leq\ell^{\prime}\leq|Q|-1$ be the index of the last glue of $Q$ on column
$c^{\prime}$. Since $\mathrm{glue}(Q_{p}Q_{p+1})$ is on column $c^{\prime}$,
we have $p\leq\ell^{\prime}$. Then, it is possible to apply Lemma 24 on
$Q_{0,\ldots,h^{\prime}}(L_{1,\ldots,|L|-2}+\overrightarrow{v})(R_{0,\ldots,|R|-2}+\overrightarrow{v})$
and $P_{f+1,\ldots,|P|-1}+\overrightarrow{v}$ (the bound is satisfied by
definition of $L(c^{\prime})$, see Fact 7). We obtain that
$Q_{0,\ldots,h^{\prime}}(L_{1,\ldots,|L|-2}+\overrightarrow{v})(R_{0,\ldots,|R|-2}+\overrightarrow{v})(P_{f+1,\ldots,|P|-1}+\overrightarrow{v})$
is a producible path. Nevertheless, since $P$ is canonical for column $c$ then
by definition $x_{P_{|P|-1}}=e_{\gamma}$ and then
$x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$. This is a contradiction.

Secondly, suppose that there are some intersections between
$R_{0,\ldots,|R|-2}$ and $P_{f+1,\ldots,|P|-1}$. Since $P$ and
$P_{0,\ldots,h}L_{1,\ldots,|R|-2}R$ (see Lemma 38) are producible paths, then
all intersections between $R$ and $P_{f+1,\ldots,|P|-1}$ are agreements. Let

$u=\max\\{i:\mathrm{pos}(P_{i})\text{ is occupied by a tile of }R\\}$

and let $0\leq u^{\prime}\leq|R|-1$ such that $R_{u^{\prime}}=P_{u}$. We are
in a case where $u\geq f+1$ and by definition of $u$,
$R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is a path. For the sake of
contradiction suppose that $R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is
more left-priority than $R$ then $P_{u+1}$ is inside a finite area delimited
by $R$ and $P_{b_{g},\ldots,f+1}$. Nevertheless, since
$x_{P_{|P|-1}}=e_{\gamma}>L(c)+1$ and
$L(c)+1=\max\\{e_{R},e_{P_{b_{g},\ldots,f+1}}\\}$ then $P_{u+1,\ldots,|P|-1}$
must intersect with either $P_{b_{g},\ldots,f+1}$ (which cannot occur since
$P$ is self-avoiding) or $R$ (which cannot occur by definition of $u$). This
is a contradiction and then $R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is
more right-priority than $R$.

Let $u\leq v\leq|P|-1$ such that $\mathrm{glue}(P_{v}P_{v+1})$ is the first
glue of
$(R_{0,\ldots,u^{\prime}}+\overrightarrow{v})(P_{u+1,\ldots,|P|-1}+\overrightarrow{v})$
on column $L(c^{\prime})$. By Lemma 40 or Lemma 39, since
$R_{0,\ldots,u^{\prime}}P_{u+1,\ldots,|P|-1}$ is more right-priority than $R$
(which is in $\mathcal{R}^{\prime}_{p}$),
$Q_{0,\ldots,h^{\prime}}(L+\overrightarrow{v})(R_{0,\ldots,u^{\prime}}+\overrightarrow{v})(P_{u+1,\ldots,v}+\overrightarrow{v})$
is producible. We can now apply Lemma 24 on
$Q_{0,\ldots,h^{\prime}}(L+\overrightarrow{v})(R_{0,\ldots,u^{\prime}}+\overrightarrow{v})(P_{u+1,\ldots,v}+\overrightarrow{v})$
and $(P_{v+1,\ldots,|P|-1})+\overrightarrow{v}$ and we obtain that
$Q_{0,\ldots,h^{\prime}}(L+\overrightarrow{v})(R_{0,\ldots,u^{\prime}}+\overrightarrow{v})(P_{u+1,\ldots,|P|-1}+\overrightarrow{v})$
is producible. Nevertheless, since $P$ is canonical for column $c$ then by
definition $x_{P_{|P|-1}}=e_{\gamma}$ and then
$x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$. This is a contradiction. ∎

######  Lemma 49.

Consider the notation 24, If $L=L^{\prime}-\overrightarrow{v}$ then
$P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}-\overrightarrow{v})$
is a producible path and $R^{\prime}-\overrightarrow{v}$ does not intersect
with $SP_{a,\ldots,b_{g}-1}$. Moreover, there exists $b_{g}\leq b\leq|R|-1$
such that
$(\text{rev}({R^{\prime}_{b,\ldots,|R^{\prime}|-1}})-\overrightarrow{v})R_{b+1,\ldots,|R|-1}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{R}_{b_{g}}$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and
$\mathrm{glue}(Q_{p}Q_{p+1})$ are southern “backup” glues. Suppose that
$L=L^{\prime}-\overrightarrow{v}$ then
$P_{0,\ldots,h-1}L^{\prime}-\overrightarrow{v}$ and
$Q_{0,\ldots,h-1}L+\overrightarrow{v}$ are two producible paths. First, for
the sake of contradiction suppose that $R+\overrightarrow{v}$ is more right-
priority than $R^{\prime}$. Then by Lemma 39,
$Q_{0,\ldots,h-1}(L+\overrightarrow{v})(R+\overrightarrow{v})$ is a producible
path , $R+\overrightarrow{v}$ is inside $\mathcal{R}^{\prime}_{p}$ and
$R+\overrightarrow{v}$ does not intersect with $S^{\prime}$ which is
contradiction by Lemma 48. Similarly $R+\overrightarrow{v}$ cannot be equal to
$R^{\prime}$.

Then $R^{\prime}-\overrightarrow{v}$ is more right-priority than $R$. In this
case, by lemma 39,
$P_{0,\ldots,h}(L^{\prime}-\overrightarrow{v})(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})$
is a producible path,
$R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v}$ is in
$\mathcal{R}_{b_{g}}$ and $R^{\prime}-\overrightarrow{v}$ does not intersect
with $SP_{a,\ldots,b_{g}-1}$. Since
$x_{R^{\prime}_{|R^{\prime}|-1}-\overrightarrow{v}}=L(c)+1$ and
$e_{P_{0,\ldots,h}(L^{\prime}-\overrightarrow{v})(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})}\leq
L(c)$ then
$P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}-\overrightarrow{v})$
is also producible. Let $0\leq b\leq|R^{\prime}|-1$ such that
$b=\max\\{i:\mathrm{pos}(R^{\prime}_{i}-\overrightarrow{v})\text{ is occupied
by a tile of }P_{a,\ldots,f}\\}$. In this case,
$(\text{rev}({R^{\prime}_{b,\ldots,|R^{\prime}|-1}})-\overrightarrow{v})R_{b+1,\ldots,|R|-1}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{R}_{b_{g}}$. Moreover $b\geq b_{g}$ since by Lemma 39,
$R^{\prime}-\overrightarrow{v}$ cannot intersect with $P_{a,\ldots,b_{g}-1}$.
∎

######  Lemma 50.

Consider the notation 24, If $L^{\prime}-\overrightarrow{v}$ is more right-
priority (resp. left priority) that $L$ then
$P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}-\overrightarrow{v})$
is a producible path. Moreover, there exists $0\leq b\leq|L^{\prime}|-1$ and
$a\leq b^{\prime}\leq|P|-1$ such that
$(\text{rev}({R^{\prime}})-\overrightarrow{v})(\text{rev}({L^{\prime}_{b,\ldots,|L^{\prime}|-1}})-\overrightarrow{v})P_{b^{\prime}+1,\ldots,f}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{R}_{b_{g}}$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and
$\mathrm{glue}(Q_{p}Q_{p+1})$ are southern “backup” glues. If
$(L^{\prime}-\overrightarrow{v})$ is more right-priority than $L$ then
$L+\overrightarrow{v}$ is more left-priority than $L^{\prime}$. Thus,
$L+\overrightarrow{v}$ is in the interior of $L^{\prime}$. Thus, all
intersections between $L+\overrightarrow{v}$ and $L^{\prime}$ would be
agreements. Similarly all intersections between $L^{\prime}$ and the
translation of the practical shield of $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$
by $\overrightarrow{v}$ are agreements. Thus, by lemma 40,
$P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})$
is producible, is inside $\mathcal{R}_{b_{g}}$ and
$(R^{\prime}-\overrightarrow{v})$ does not intersect $S$. Since
$x_{R^{\prime}_{|R^{\prime}|-1}+\overrightarrow{v}}=L(c)+1$ and

$e_{P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}_{0,\ldots,|R^{\prime}|-2}-\overrightarrow{v})}<L(c)+1$

then
$P_{0,\ldots,h}(L^{\prime}_{1,\ldots,|L^{\prime}|-2}-\overrightarrow{v})(R^{\prime}-\overrightarrow{v})$
is also producible. Then let $0\leq b\leq|L^{\prime}|-1$ and $a\leq
b^{\prime}\leq|P|-1$ such that
$(\text{rev}({R^{\prime}})-\overrightarrow{v})(\text{rev}({L^{\prime}_{b,\ldots,|L^{\prime}|-1}})-\overrightarrow{v})P_{b^{\prime}+1,\ldots,f}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{P}_{b_{g}}$. ∎

######  Lemma 51.

Consider the notation 24, there exists an upward (resp. downward) minimum arc
$A^{\prime}$ on column $L(c)$ such that:

  * •

its interior $\mathcal{I}_{A^{\prime}}$ is included into
$\mathcal{R}_{m_{g}}$;

  * •

such that $A^{\prime}$ is a path of ${\bf{P}}[{\mathcal{\gamma}}]$;

  * •

$A^{\prime}_{0}=Q_{f^{\prime}+1}-\overrightarrow{v}$ and
$A^{\prime}_{|A^{\prime}|-1}=P_{f+1}$;

  * •

if there exists $0\leq i\leq|A^{\prime}|-1$ such that $A^{\prime}_{i}$ is a
tile of $SP_{a,\ldots,b_{g-1}}$ then $A^{\prime}_{0,\ldots,i-1}<c$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and
$\mathrm{glue}(Q_{p}Q_{p+1})$ are southern “backup” glues. By Lemma 48, it is
not possible that $L+\overrightarrow{v}$ is more right-priority that
$L^{\prime}$. By Lemma 49, if $L=L^{\prime}-\overrightarrow{v}$, there exists
$0\leq a\leq|R|-1$ such that
$B=(\text{rev}({R^{\prime}_{a,\ldots,|R^{\prime}|-1}})-\overrightarrow{v})R_{a+1,|R|-1}$
is a negative upward (resp. downward) arc of column $L(c)$ with
$B_{0}=R^{\prime}_{|R^{\prime}|-1}-\overrightarrow{v}=Q_{f^{\prime}+1}-\overrightarrow{v}$
and $B_{|B|-1}=R_{|R|-1}=P_{f+1}$. Moreover, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$ and its interior is included into
$\mathcal{R}_{m_{g}}$. The paths $R$ (by lemma 38) and
$R^{\prime}-\overrightarrow{v}$ (by lemma 49) cannot intersect with
$SP_{a,\ldots,b_{g}-1}$. Thus, no tile of $SP_{a,\ldots,b_{g}-1}$ is inside
the interior of the arc $B$. The path $A^{\prime}$ defined as
$\min(\mathcal{I}_{B})$ satisfies the condition of the lemma.

By Lemma 50, if $L^{\prime}-\overrightarrow{v}$ is more right-priority that
$L$ then there exists $0\leq b\leq|L^{\prime}|-1$ and $0\leq
b^{\prime}\leq|A|-1$ such that
$B=(\text{rev}({R^{\prime}})-\overrightarrow{v})(\text{rev}({L^{\prime}_{b,\ldots,|L^{\prime}|-1}})-\overrightarrow{v})P_{b^{\prime}+1,\ldots,f}$
is a negative upward (resp. downward) arc of column $L(c)$ and its interior is
included into $\mathcal{R}_{b_{g}}$. Moreover, $B$ is in
${\bf{P}}[{\mathcal{\gamma}}]$ and its interior is included into
$\mathcal{R}_{m_{g}}$. The path $A^{\prime}$ defined as
$\min(\mathcal{I}_{B})$ satisfies the condition of the lemma. Indeed, suppose
that there exists $0\leq i\leq|A^{\prime}|-1$ such that $A^{\prime}_{i}$ is a
tile of $P_{a,\ldots,b_{g-1}}$. Then to reach this tile,
$A^{\prime}_{0,\ldots,i}$ need to the pass to the west of
$(\text{rev}({R^{\prime}})-\overrightarrow{v})$ since this path is a prefix of
$B$. This means that $w_{A^{\prime}_{0,\ldots,i}}\leq
w_{\text{rev}({R^{\prime}})-\overrightarrow{v}}\leq c$. ∎

######  Lemma 52.

Consider the notation 24 and the arc $A^{\prime}$ of Lemma 51. If
$w_{A^{\prime}}\leq c$, then either there exists $g<i<t$ such that $b_{i}$ is
protected or there exists $g<i\leq t$ such that $m_{i}$ is protected.

###### Proof.

By definition, we have $A^{\prime}_{|A^{\prime}|-2}=P_{f}$, then $A^{\prime}$
intersects with $P_{a,\ldots,f}$. Let $T$ be the largest prefix of
$A^{\prime}$ such that $T$ does not intersect $P_{a,\ldots,f}$. Note that, $T$
does not intersect with $P_{0,\ldots,a-1}$ since the interior of $A^{\prime}$
is in $\mathcal{R}_{b_{g}}$. By definition of $T$ there exists $a\leq b\leq f$
such that $TP_{b}$ is a prefix of $A^{\prime}$. Since $T=A^{\prime}_{0}$, then
$TP_{b,\ldots,f}$ is also a negative upward (resp. downward) arc of column
$L(c)$. Moreover, since $A^{\prime}$ is minimum then $A^{\prime}$ is inside
the interior of the arc $TP_{b,\ldots,f}$. Then, we have
$w_{TP_{b,\ldots,f}}\leq w_{A^{\prime}}\leq c$. This implies that $T$ is a
shield of the cut $(m_{0},f)$ of $P$. Now, either $T$ is a full-shield but
since $T$ is in $\mathcal{P}_{b_{g}}$ then it cannot intersect $b^{i}$ for
$i\leq g$. Thus, by Lemma 33 there exists $g<i\leq t$ such that $m_{i}$ is
protected and the lemma is true. Now, if $T$ is an half-shield then $T$ is in
the east-side $\mathcal{E}$ of $\mathcal{C}$ and we have $m_{i}<b<b_{i}$ for
some $0\leq i\leq t$. Also, since $T_{1,\ldots,|T_{|}-1}$ is in
$\mathcal{P}_{b_{g}}$, then $i\geq g$. For the case $i=g$, it would mean that
$a\leq b<b_{g}$ but by the definition of $A^{\prime}$ (see Lemma 51), we would
have $w_{T}\leq c$ implying that $T$ is a full-shield. Thus, the glue $b_{i}$
is protected by the half-shield $T$ with $i>g$. ∎

######  Lemma 53.

Consider the notation 24 and the arc $A^{\prime}$ of Lemma 51. If there exists
an index $p^{\prime}\geq p$ such that the
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a protected glue (either a
“main” or “backup” one) of the northern (resp. southern) decomposition of $Q$
into dominant arcs then $w_{A^{\prime}}\leq c$.

###### Proof.

W. l. o. g., we suppose that $\mathrm{glue}(P_{b_{g}}P_{b_{g}+1})$ and
$\mathrm{glue}(Q_{p}Q_{p+1})$ are southern “backup” glues. For the sake of
contradiction, assume that $w_{A^{\prime}}>c$ and we denote by
$0\leq\ell^{\prime}\leq|Q|-1$ the index of the last glue of $Q$ of column
$c^{\prime}$.

First of all, consider the protected area $\mathcal{P}_{p^{\prime}}$ (be
careful $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a northern main
glue). Note that $Q_{f^{\prime}+1}=A^{\prime}_{0}+\overrightarrow{v}$ and
$Q_{f^{\prime}}=A^{\prime}_{1}+\overrightarrow{v}$. Then we can defined
$0<v\leq|A^{\prime}|-1$ such that $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$
is the largest prefix of
$A^{\prime}_{1,\ldots,|A^{\prime}|-1}+\overrightarrow{v}$ which is inside
$\mathcal{P}_{p^{\prime}}$. Now, since
$P_{0,\ldots,m_{g}}(R^{\prime}-\overrightarrow{v})$ is producible (by Lemma 49
or 50) and since $A^{\prime}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ (by Lemma
51) then all intersections between $A^{\prime}+\overrightarrow{v}$ and
$R^{\prime}$ are agreements. Since $p^{\prime}\geq p$ then the only tiles of
$Q_{0,\ldots,p}R^{\prime}$ which are inside $\mathcal{P}_{p^{\prime}}$ are
tiles of $R^{\prime}$. Then, since $Q_{0,\ldots,p}R^{\prime}$ is producible
(by definition of $R^{\prime}$), then
$\mathrm{asm}{(Q_{0,\ldots,p}R^{\prime})}\cup\mathrm{asm}{(A^{\prime}_{1,\ldots,v}+\overrightarrow{v})}$
is a producible assembly. Thus, $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$
is in ${\bf{P}}[{\mathcal{\gamma}}]$ and in particular, all intersections
between $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ and
$Q_{p^{\prime},\ldots,f^{\prime}}$ are agreements.

Since $w_{A^{\prime}}+\overrightarrow{v}>c^{\prime}$ then
$A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ cannot intersect with the ray
starting in $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ and going north.
By Lemma 32 (if $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is visible
from the north), Lemma 36 (if $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$
is a “ main” glue protected by a shield) or Lemma 41 (if
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a “backup” glue protected
by a shield) then $A^{\prime}_{1,\ldots,v}+\overrightarrow{v}$ cannot
intersect with $Q_{p^{\prime}+1,\ldots,\ell^{\prime}}$ and the shield of
$\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ (in the relevant case).
Finally, if there exists $\ell^{\prime}\leq v^{\prime}\leq f^{\prime}$ such
that $Q_{v^{\prime}}=A^{\prime}_{v}+\overrightarrow{v}$ and
$\text{rev}({Q_{v^{\prime},\ldots,f^{\prime}+1}})(A^{\prime}_{v+1}+\overrightarrow{v})$
turns left of $\text{rev}({Q_{v^{\prime}-1,\ldots,f^{\prime}+1}})$ then there
exist $\ell^{\prime}\leq u^{\prime}\leq f^{\prime}$ and $1\leq u\leq v$ such
that $Q_{u^{\prime}}=A^{\prime}_{u}+\overrightarrow{v}$ and
$(A^{\prime}_{1,\ldots,u}+\overrightarrow{v})Q_{u^{\prime}+1}$ turns right of
$(A^{\prime}_{1,\ldots,u+1}+\overrightarrow{v})$. Since
$x_{Q_{\ell^{\prime}}}=c^{\prime}$ and
$w_{A^{\prime}+\overrightarrow{v}}>c^{\prime}$, then
$Q_{u^{\prime}+1,\ldots,\ell^{\prime}+1}$ intersects with
$A^{\prime}+\overrightarrow{v}$ contradicting the fact that
$A^{\prime}+\overrightarrow{v}$ (and $A^{\prime}$) is a minimum arc. Then,
$v\geq|A^{\prime}|-2$ and
$A^{\prime}_{1,\ldots,|A^{\prime}|-2}+\overrightarrow{v}$ is in
$\mathcal{P}_{p^{\prime}}$ and in ${\bf{P}}[{\mathcal{\gamma}}]$.

Since
$A^{\prime}_{1}+\overrightarrow{v}=Q_{f^{\prime}}=R^{\prime}_{|R^{\prime}|-2}$
then $A^{\prime}_{1,\ldots,|A^{\prime}|-2}+\overrightarrow{v}$ and
$R^{\prime}$ intersect. Let $0\leq b\leq R^{\prime}$ such that
$R^{\prime}_{0,\ldots,b}$ is the shortest prefix of $R^{\prime}$ which
intersects with $A^{\prime}+\overrightarrow{v}$. Let $0\leq
b^{\prime}\leq|A^{\prime}|-1$ such that
$A^{\prime}_{b^{\prime}}+\overrightarrow{v}=R^{\prime}_{b}$ and then
$T=R^{\prime}_{0,\ldots,b}(A^{\prime}_{b^{\prime}+1,\ldots,|A^{\prime}|-2}+\overrightarrow{v})$
is a path and $Q_{0,\ldots,p}T$ is a producible path. Note that
$P_{f+1}+\overrightarrow{v}=A^{\prime}_{|A^{\prime}|-1}$ and
$P_{f+1}+\overrightarrow{v}$ is on column $L(c^{\prime})+1$. By Lemma 24, if
$P_{f+1,\ldots,|P|-1}+\overrightarrow{v}$ does not intersect with $T$, then
$Q_{0,\ldots,p}T(P_{f+1,\ldots,|P|-1}+\overrightarrow{v})$ is a producible
path. Nevertheless, $x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$ and we have
a contradiction.

Finally, suppose that there is an intersection between $T$ and
$(P_{f+1,\ldots,|P|-1}+\overrightarrow{v})$. By definition
$P_{f+1,\ldots,|P|-1}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$, by Lemma 51
$A^{\prime}$ is in ${\bf{P}}[{\mathcal{\gamma}}]$ and by Lemma 49 or 50,
$R^{\prime}-\overrightarrow{v}$ is ${\bf{P}}[{\mathcal{\gamma}}]$ . Thus all
intersections between these paths are agreements. Let
$d=\max\\{i:\mathrm{pos}(P_{i})+\overrightarrow{v}\text{ is occupied by a tile
of }T\\}$, we are in a case where $d>f$. Let $0\leq d^{\prime}\leq|T|-1$ such
that $T_{d^{\prime}}=P_{d}+\overrightarrow{v}$. Let $d\leq
f^{\prime\prime}\leq|P|-1$ be the index of the first glue of
$P_{d,\ldots,|P|-1}+\overrightarrow{v}$ which is on column $L(c^{\prime})$. If
$T_{0,\ldots,d^{\prime}}(P_{d,\dots,f^{\prime\prime}}+\overrightarrow{v})$ is
more left-priority than $T$, then $P_{d,\dots,f^{\prime\prime}}$ is inside a
finite area delimited by $T-\overrightarrow{v}$ and $P_{b_{g},\ldots,f+1}$.
Nevertheless, $P_{d,\dots,f^{\prime\prime}}$ must leave this area but it
cannot intersect with $P_{b_{g},\ldots,f+1}$ (since $P$ is simple) or
$T-\overrightarrow{v}$ (by definition of $d$). Then
$T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v})$
is more right-priority than $T$. If
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ is inside
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ then

$Q_{0,\ldots,p}T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v})$

is producible and by Lemma 24,
$Q_{0,\ldots,p}T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,|P|-1}+\overrightarrow{v})$
is producible. Again, $x_{P_{|P|-1}+\overrightarrow{v}}>e_{\gamma}$ and we
have a contradiction.

Suppose that $P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ leaves
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ by leaving
$\mathcal{P}_{p^{\prime}}$ first. Then since $w_{T}\leq
c^{\prime}<L(c^{\prime})\leq e_{T}$ and
$c^{\prime}<w_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}<e_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}\leq
L(c^{\prime})$, then $P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ must
intersect with $T$. This is a contradiction by the definition of $d$. If
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ leaves
$\mathcal{P}_{p^{\prime}}\cup\mathcal{R}^{\prime}_{p}$ by leaving
$\mathcal{R}^{\prime}_{p}$. Since
$w_{P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}}>c^{\prime}$ then
$P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}$ should intersect with
$S^{\prime}$ or $Q_{a^{\prime},\ldots,p}$. In this case, it is possible to
find a path in
$\mathrm{asm}{(T_{0,\ldots,d^{\prime}}(P_{d+1,\dots,f^{\prime\prime}}+\overrightarrow{v}))}\cup\mathrm{asm}{(Q_{\ell^{\prime},\ldots,f^{\prime}})}$
which intersects with $S^{\prime}$ or $Q_{a^{\prime},\ldots,p}$ and is in
$\mathcal{R}^{\prime}_{p}$ which is a contradiction by Lemma 39 or Lemma 40.
All cases lead to contradiction and the lemma is true.

∎

######  Lemma 54.

Consider the notation 24. If there exists an index $p^{\prime}\geq p$ such
that the $\mathrm{glue}(Q_{p^{\prime}}Q_{p^{\prime}+1})$ is a protected glue
(either a “main” or “backup” one) of the northern (resp. southern)
decomposition of $Q$ into dominant arcs then either there exists $g<i<t$ such
that $b_{i}$ is protected or there exists $g<i\leq t$ such that $m_{i}$ is
protected.

###### Proof.

By Lemma 51, there exists an upward (resp. downward) minimum arc $A^{\prime}$
on column $L(c)$. Moreover, by Lemma 53, we have $w_{A^{\prime}}\leq c$. Then
by Lemma 52, the lemma is true. ∎

###  6.5 Conclusion

######  Theorem 3.

Consider a directed tile assembly system $(T,\sigma,1)$, if its terminal
assembly $\gamma$ is finite then its horizontal width and vertical height are
bounded by $7|\sigma|+58|T|+30$.

###### Proof.

For the sake of contradiction, suppose that
$e_{\gamma}>e_{\sigma}+3|\sigma|+29|T|+15$. For each column
$e_{\sigma}+|T|+1\leq c\leq e_{\sigma}+5|T|+1$, we consider a canonical path
$P^{(c)}$. Note that there are $4|T|+1$ of these paths. For each path
$P^{(c)}$, we consider the index of the last protected glue of its northern
decomposition ${n_{c}}$ and the index of the last protected glue of its
southern decomposition $s_{c}$. The path $P^{(c)}$ is said to be be protected
from the south if $s_{c}\leq{n_{c}}$ and protected from the north if
$s_{c}\geq{n_{c}}$. In the special case where $s_{c}={n_{c}}$, we consider
that this path is protected from the north and from the south.

Among these paths, either at least $2|T|+1$ of them are protected from the
north or at least $2|T|+1$ of them are protected from the south. Without loss
of generality, we consider the later case. Consider the category of the last
protected glue of the southern decomposition of these paths: at least $|T|+1$
of these glues are in the category “main” or at least $|T|+1$ of these glues
are in the category “back-up”. Then, we can conclude that there exist
$e_{\sigma}+|T|+1\leq c<c^{\prime}\leq e_{\sigma}+5|T|+1$ such that $P^{(c)}$
and $P^{(c^{\prime})}$ are protected from the south, and their last protected
glue of their southern decomposition have the same category and type. Thus, by
Lemma 47 (if the category of these two glues is “main”) or 54 (if the category
of these two glues is “back-up”), we obtain the contradiction that $s_{c}$ is
not the last protected glue of the southern decomposition of $P^{(c)}$.

The value $w_{\gamma}$ can be bounded similarly and then the horizontal width
of $\gamma$ can be bounded by $7|\sigma|+58|T|+30$. The same reasoning can be
done for the vertical height. ∎

### Acknowledgments

We would like to thank Pierre-Étienne Meunier and Damien Woods: some results
presented here are based on our previous collaboration with them.

## References

  * [1] Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang.  Running time and program size for self-assembled squares.  In STOC: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 740–748, Hersonissos, Greece, 2001.
  * [2] Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods.  The two-handed tile assembly model is not intrinsically universal.  In ICALP: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, volume 7965 of LNCS, pages 400–412. Springer, July 2013.  Arxiv preprint: arXiv:1306.6710.
  * [3] David Doty, Matthew J. Patitz, and Scott M. Summers.  Limitations of self-assembly at temperature 1.  Theoretical Computer Science, 412(1--2):145--158, 2011.  Arxiv preprint: arXiv:0903.1857v1.
  * [4] Pierre-Étienne Meunier and Damien Regnault.  Non-cooperatively assembling large structures.  In DNA Computing and Molecular Programming - 25th International Conference, DNA 25, Seattle, WA, USA, August 5-9, 2019, Proceedings, 2019.
  * [5] Pierre-Etienne Meunier and Damien Regnault.  On the directed tile assembly systems at temperature 1.  arXiv preprint arXiv:2011.09675, 2020.  In submission with title ‘‘Directed non-cooperative tile assembly is decidable’’.
  * [6] Pierre-Étienne Meunier, Damien Regnault, and Damien Woods.  The program-size complexity of self-assembled paths.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 727--737. ACM, 2020.  Arxiv preprint: arXiv:2002.04012 [cs.CC].
  * [7] Pierre-Étienne Meunier and Damien Woods.  The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation.  In STOC: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 328--341, Montreal, Canada, 2017. ACM.  Arxiv preprint with full proofs: arXiv:1702.00353v2 [cs.CC].
  * [8] Hao Wang.  Proving theorems by pattern recognition -- II.  The Bell System Technical Journal, XL(1):1--41, 1961.
  * [9] Erik Winfree.  Algorithmic Self-Assembly of DNA.  PhD thesis, California Institute of Technology, June 1998.