A Linear Bound for the Size of the Finite Terminal Assembly of a Directed Non-Cooperative Tile Assembly System

From this point on, we focus on non-cooperative aTAM. In this variant, there is no mechanism to synchronise different parts of the assembly beyond concurrency: the first path to grow blocks and prevents the growth of others. Non-cooperative aTAM can be seen as a variant of Wang tiles [30] where the computation starts from a seed and mismatches are allowed. Surprisingly, this model proved very hard to study, and very few results were known for a long time. Concerning decidability seen as the limit of what can be achieved, slight modifications are enough to simulate the Turing machine. In [6] simulation of Turing machines was achieved in $3D$ and was done almost surely by introducing probabilities. It was also achieved by introducing negative glue weights [24], by considering polyomino tiles [10], polygonal tiles [13], detachable glues [15], or by performing the assembly in several steps [4]. Nevertheless, the question is still open for non-cooperative aTAM. Several recent studies hint that it is likely decidable: non-cooperative aTAM is not intrinsically universal [18, 22], it is not able to simulate the Turing machine in the classical way [22], and a $2D$ pumping lemma was published in [21]. A weaker version of non-cooperative aTAM called directed where only one final terminal assembly is allowed was shown to be decidable by combining [8] and [21].

Although all these results point towards a negative answer, if non-cooperative aTAM were undecidable, it would be a surprising breakthrough and could lead to surprising results. It is worth remembering that such a scenario had already occurred for Wang tiles: the domino problem was initially conjectured to be undecidable, and proving this conjecture wrong required exhibiting aperiodic tilings. In this context, aperiodicity is an unusual way of initializing computation. Subsequently, aperiodic tilings were extensively studied and became a model of crystallography.

Concerning the complexity of non-cooperative aTAM, assembling rectangles and squares in $3D$ was achieved in [11, 12], and the upper and lower bounds on the number of tile types almost match. In $2D$, lower bounds are known for the case in which mismatches are disallowed [16]. Concerning the main $2D$ model, the existence of efficient paths of size $n\log n$ was shown in [19] (improving on a previous construction in [17]). An efficient path appears in every terminal assembly and only requires a tile set of size $n$, whereas an auxiliary path may appear somewhere else in the terminal assembly. A limitation of this approach was also obtained in [21]: it is impossible to construct efficient paths of arbitrary lengths. Concerning the directed non-cooperative aTAM, the work [20] – an update of [8] – shows that only four kinds of terminal assemblies exist, one of them being a bi-periodic grid which must be hardcoded in the tile set.

In this paper, we consider another one of this four kinds of assemblies: the finite terminal assembly. Our main result is a linear bound (in the number of tile types) on the size of finite terminal assemblies. Besides advancing the understanding of directed non-cooperative aTAM, this result has several major implications. Firstly, it partially solves a conjecture stated in [27, 32] about the asymptotic bound on assembling a square which is now proven to be linear. Note that finding the exact multiplicative constant is still an open question. Secondly, it is another hint that directed non-cooperative aTAM is not able to perform any complex computation. Thirdly, our result highlights a fundamental difference with non-cooperative aTAM: concurrency is required to assemble the efficient paths exhibited in [19]. Fourthly, our bound opens new perspectives for improving several previous results such as the pumping lemma in [21]. Indeed, multiple major results rely on understanding the “information flow” in an assembly, like for example the window movie lemma stated in [18]. Intuitively, a window delimits an area of the plane and a window movie is the order of placement, position, and glue types appearing along the window. The main theorem in [21] was obtained by focusing on a particular window movie and two of its critical glues. In this paper, we improve on the previous reasoning by showing that some information flowing through the window cannot be new and is therefore redundant. A similar approach has also recently been used to show that some fractals cannot be assembled in the cooperative case [3]. Using such improved tools may have consequences for other model and results.

Due to space constraints, we present only here the key ideas arranged in a roadmap and explain how they articulate in the proof of the main result which is available on arXiv [14].

A tile type is a unit square with four sides, each consisting of a glue type and a nonnegative integer strength. Let $T$ be a finite set of tile types. The sides of a tile type are respectively called north, east, south, and west.

An assembly is a partial function $\alpha :{\mathbb{Z}}^2⇢T$ where $T$ is a set of tile types and the domain of $\alpha$ (denoted $dom(\alpha )$) is connected.¹¹1Intuitively, an assembly is a positioning of unit-sized tiles, each from some set of tile types $T$, so that their centers are placed on (some of) the elements of the discrete plane ${\mathbb{Z}}^2$ and such that those elements of ${\mathbb{Z}}^2$ form a connected set of points. Two tile types in an assembly are said to bind (or interact, or to be stably attached) if the glue types on their abutting sides are equal, and have strength $\ge 1$. An assembly $\alpha$ induces an undirected weighted binding graph $G_{\alpha }=(V,E)$, where $V=dom(\alpha )$, and there is an edge $\{a,b\}\in E$ if and only if the tiles at positions $a$ and $b$ interact, and this edge is weighted by the glue strength of that interaction. The assembly is said to be $\tau$-stable if every cut of $G_{\alpha }$ has weight at least $\tau$.

Given two $\tau$-stable assemblies $\alpha$ and $\beta$, the union of $\alpha$ and $\beta$, written $\alpha \cup \beta$, is an assembly defined if and only if and for all $p\in dom(\alpha )\cap dom(\beta )$, $\alpha (p)=\beta (p)$ and either at least one tile of $\alpha$ binds with a tile of $\beta$ or $dom(\alpha )\cap dom(\beta )\ne \mathrm{\varnothing }$. Then, for all $p\in dom(\alpha )$, we have $(\alpha \cup \beta )(p)=\alpha (p)$ and for all $p\in dom(\beta )$, we have $(\alpha \cup \beta )(p)=\beta (p)$.

A tile assembly system is a triple $𝒯=(T,\sigma ,\tau )$, where $T$ is a finite set of tile types, $\sigma$ is a $\tau$-stable assembly called the seed, and $\tau \in \mathbb{N}$ is the temperature. Throughout this article, $\tau =1$.

Given two $\tau$-stable assemblies $\alpha$ and $\beta$, we say that $\alpha$ is a subassembly of $\beta$, and write $\alpha ⊑\beta$, if $dom(\alpha )\subseteq dom(\beta )$ and for all $p\in dom(\alpha )$, $\alpha (p)=\beta (p)$. We also write $\alpha {\to }_1^{𝒯}\beta$ if we can obtain $\beta$ from $\alpha$ by the binding of a single tile type, that is: $\alpha ⊑\beta$, $|dom(\beta )\setminus dom(\alpha )|=1$ and the tile type at the position $dom(\beta )\setminus dom(\alpha )$ binds to $\alpha$ at that position. We say that $\gamma$ is producible from $\alpha$ if there is a (possibly empty) sequence ${\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_n$ where $n\in \mathbb{N}\cup \{\mathrm{\infty }\}$, $\alpha ={\alpha }_1$ and ${\alpha }_n=\gamma$, such that ${\alpha }_1{\to }_1^{𝒯}{\alpha }_2{\to }_1^{𝒯}\mathrm{\dots }{\to }_1^{𝒯}{\alpha }_n$.

The set of productions, or producible assemblies, of a tile assembly system $𝒯=(T,\sigma ,\tau )$ is the set of all assemblies producible from the seed assembly $\sigma$ and is written $𝒜[𝒯]$. An assembly $\alpha$ is called terminal if there is no $\beta$ such that $\alpha {\to }_1^{𝒯}\beta$. The set of all terminal assemblies of $𝒯$ is denoted ${𝒜}_{\mathrm{\square }}[𝒯]$. If there is a unique terminal assembly, i.e. $|{𝒜}_{\mathrm{\square }}[𝒯]|=1$, then $𝒯$ is directed and its unique terminal assembly is called $\gamma$ along this paper.

The easternmost column of a finite assembly $\alpha$ is designated by $e_{\alpha }=\max \{x:\exists y,(x,y)\in dom\{\alpha \}\}$, $w_{\alpha }$, $n_{\alpha }$, $s_{\alpha }$ are defined similarly for the westernmost, northernmost and southernmost columns of the assembly respectively. The horizontal width of an assembly $\alpha$ is $e_{\alpha }-w_{\alpha }$ and its vertical height $n_{\alpha }-s_{\alpha }$. The following theorem is the main contribution of this paper.

For the rest of the article, we consider a directed tile assembly system $𝒯=(T,\sigma ,1)$ and we suppose that its terminal assembly $\gamma$ is finite. Also, we assume that the assembly grows the furthest away from the seed to the east, i.e.:

With this assumption it is sufficient to bound $e_{\alpha }-e_{\sigma }$ by $3|\sigma |+29|T|+15$ to prove the main theorem. The proof of this result is constructive: we design an algorithm which takes as input an assembly $\gamma$ such that $e_{\gamma }>3|\sigma |+29|T|+15$ and it will either:

• $\mathrm{■}$

  output a certificate that the tile assembly system is not directed;

• $\mathrm{■}$

  bind a new tile to the assembly, showing that $\gamma$ is not terminal.

By iterating this algorithm on a large enough finite assembly, we are able to make it grow arbitrarily large. Note that, by using the pumping lemma of [21], an infinite periodic path can be built when the assembly is large enough. We do not explicitly write the algorithm in this paper, but it can be directly derived from the constructive proofs, which are concluded by exhibiting a contradiction: either $\gamma$ is not terminal, or the tile assembly system is not directed.

Since there is no possible synchronization between the tiles in the non-cooperative case, we focus on paths instead of assemblies. Formally, a path $P$ is a finite sequence of tiles ${(P_i)}_{0\le i\le |P|-1}$ such that each tile $P_i$ interacts with the next one $P_{i+1}$ of the sequence. Moreover, a path does not intersect with the seed and is simple: two different tiles of $P$ do not occupy the same position. The length of $P$ is the size $|P|-1$ of the sequence. If the first tile of the path interacts with a tile of the seed $\sigma$ then the path is producible. The last tile of a producible path is the easternmost one if and only if it is the only tile of $P$ on column $e_P$ with $e_P>e_{\sigma }$; moreover, a producible path is extremal if $e_P=e_{\gamma }$ (we remind that $\gamma$ is the unique terminal assembly). We say that a path $P$ is a subassembly of $\gamma$ if and only if each tile of $P$ belongs to $\gamma$. Of course, producible and extremal paths are subassemblies of $\gamma$.

We now introduce some basic operations on paths. The concatenation of a finite path $P$ with a path $Q$ is the concatenation $PQ$ of these two paths as sequences. $PQ$ is a path if and only if (1) the last tile of $P$ interacts with the first tile of $Q$ and (2) $P$ and $Q$ do not intersect. For a path $P=P_0\mathrm{\dots }{P}_i{P}_{i+1}\mathrm{\dots }{P}_j\mathrm{\dots }$, we define the subpath of P between indices $i$ and $j$, both included, in the following way: $P_{i,i+1,\mathrm{\dots },j}=P_i{P}_{i+1}\mathrm{\dots }{P}_j$. In the special case of a subpath where $i=0$ (resp. $j=|P|-1$), we say that $P_{0,1,\mathrm{\dots },j}$ (resp. $P_{j,\mathrm{\dots },|P|-1}$) is a prefix (resp. suffix) of $P$. Consider a vector $\overrightarrow{v}\in {\mathbb{Z}}^2$ and a tile $A$, the translation of $A$ by $\overrightarrow{v}$ is the tile $A+\overrightarrow{v}=(\mathrm{pos}(A)+\overrightarrow{v},\mathrm{type}(A))$. The translation of a path $P$ by $\overrightarrow{v}$ is $P+\overrightarrow{v}=(P_0+\overrightarrow{v})(P_1+\overrightarrow{v})\mathrm{\dots }(P_{|P|-1}+\overrightarrow{v})$. Consider two indices $0\le i\le j\le |P|-1$, by abuse of notation we designate by $\overrightarrow{P_i{P}_j}$ the vector $\overrightarrow{\mathrm{pos}(P_i)\mathrm{pos}(P_j)}$. Also, we denote by $\mathrm{glue}(P_i{P}_j)$ the glue used to bind tile $P_i$ with $P_{i+1}$. It is situated on a glue column $c$ between the two tiles (and thus between two columns ). The assembly $\mathrm{asm}(P)$ is the representation of the path $P$ as an assembly (the order of the tiles is not taken into account anymore). This notation allows to merge two paths $P$ and $Q$ as $\mathrm{asm}(P)\cup \mathrm{asm}(Q)$. This operation can be done even if $P$ and $Q$ intersect and thus is more general than the concatenation.

The previous results of [21] and the ones of this paper are obtained by showing that the farther away a path grows from the seed, the more it is constrained. Figure 1 shows an extremal path and several bounds. The main one ${ℬ}_5$ is the bound used to prove the main Theorem 1: if a path crosses this column then the terminal assembly is infinite. The bound ${ℬ}_0$ shows that an extremal path cannot grow too far to the west of the seed, i.e. on the opposite side of the seed from its last tile.

This result was also proven in [36], in a slightly different context. A simplified proof of this result in [14].

The path $P$ will be cut in three parts. The first one is its beginning (in pale green in Figure 1) which is too close to the seed to be useful²²2That is because the visible glues between the columns $B_0$ and $B_1$ will point east. The notion of a visible glue is formally introduced in the next subsection.. The middle of the path $P$ (in green in Figure 1) will start on a column with index at least ${ℬ}_1=e_{\sigma +|T|+1.5}$ and will end on a column with index at most ${ℬ}_2=e_{\sigma +5|T|+1.5}$ (the exact beginning and ending of this subpath of $P$ are explained in Figure 2 and Subsection 3.4). In this subpath of $P$, we aim to locate two indices $0\le i\le j\le |P|-1$ such that $\mathrm{glue}(P_i{P}_{i+1})$ and $\mathrm{glue}(P_j{P}_{j+1})$ have the same type, allowing us to try to assemble $P_{0,\mathrm{\dots },i}(P_{j+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_j{P}_i})$ or $P_{0,\mathrm{\dots },j}(P_{i+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_i{P}_j})$. Note that copying and pasting the end of $P$ is not always possible due to possible intersections between the beginning of $P$ and its translated suffix. Thus, one key step explained in Subsections 3.4 and 3.5 is to select $i$ and $j$ such that $P_{0,\mathrm{\dots },i}(P_{j+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_j{P}_i})$ is always a producible path. Finally, the end of the path $P$ (in dark green in Figure 1) has to be large enough such that when it is copied and pasted, it will create a large obstacle, called a shield. This shield will be used to find other indices where different parts of $P$ can be copied and pasted. Repeating this reasoning will eventually lead to a contradiction. The role of bounds ${ℬ}_3$ and ${ℬ}_4$ will be explained in Subsection 3.6, we do not give here their explicit definition since their values depend on the positions of $P_i$ and $P_j$.

All results of this paper rely on the notion of visible glues introduced in [22]. Consider an index $0\le i\le |P|-1$, $\mathrm{glue}(P_i{P}_{i+1})$ is horizontal if both tiles are on the same line or vertical if both tiles are on the same column. A horizontal glue points east if $P_i$ is west of $P_{i+1}$ otherwise it points west. The glue is visible from the south (resp. north) in $P$ if and only it is the southernmost (northernmost) glue of $P$ on its column and if there are no tiles of the seed on both adjacent columns. We designate by $l^i$ the glue ray associated to $\mathrm{glue}(P_i{P}_{i+1})$: $l^i$ is a ray starting at the position of $\mathrm{glue}(P_i{P}_{i+1})$ going south (resp. north) if $\mathrm{glue}(P_i{P}_{i+1})$ is visible from the south (resp. north). If the last tile of a producible path $P$ is the easternmost one (which is the case for an extremal path) then we have the following properties (see Figure 2):

If $P$ is an extremal path, then these three lemmas and Lock 2 imply that all glues which are visible from the north or south in $P$ on a glue column $c\ge {ℬ}_1$ point east. The proofs of these lemmas are, now, classic results available in [21, 22] and will not be proven here again. The proof of Lock 2 is available in [21] and relies on a complex intermediate lemma whose proof is simplified in [14].

Combining two visible glues of a producible path $P$ allows us to delimit a part of ${\mathbb{Z}}^2$ which is an entire vertical half-plane, plus some other parts depending on the exact shape of $P$ between the two visibles glues. When the visible glues are chosen appropriately, this area does not contain any tile of $\sigma$ or any tile of $P$ before the first visible glue. Then, we are free to edit $P$ in this area without fearing a conflict with one of its previous parts or the seed. More formally, consider two indices $0\le s\le |P|-2$ and $0\le n\le |P|-2$ such that $\mathrm{glue}(P_s{P}_{s+1})$ and $\mathrm{glue}(P_n{P}_{n+1})$ are visible from the south and from the north respectively in $P$. If $s\le n$ (resp. $n\le s$), $(s,n)$ (resp. $(n,s)$) is called an upward (resp. downward) cut of $P$ because the bi-infinite curve made of $l^s$, $P_{s,\mathrm{\dots },n+1}$ and $l^n$ cuts the space in two areas, see Figure 3. If $\mathrm{glue}(P_s{P}_{s+1})$ (resp. $\mathrm{glue}(P_n{P}_{n+1})$) points east then the seed and the beginning of $P$ are in the west side of the cut and cannot block the growth of new paths in the east side of the cut. The east side of the cut is called the workspace of the cut $(s,n)$ (resp. $(n,s)$) of $P$, denoted by $𝒞$:

Along the paper, we will often consider the special case where the two visible glues $s$ and $n$ are on the same glue column. In this case, the cut is called the span of $P$ on glue column $c$. The type of a span is the type of $\mathrm{glue}(P_s{P}_{s+1})$ (resp. $\mathrm{glue}(P_n{P}_{n+1})$), it points in the same direction as $\mathrm{glue}(P_s{P}_{s+1})$ (resp. $\mathrm{glue}(P_n{P}_{n+1})$), and its width is $y_{P_n}-y_{P_s}$.

The result of [21] is obtained by combining two spans of the same type and direction. Indeed, consider an extremal path $P$ and two glue columns such that the spans $(s,n)$ and $(s^{\prime },n^{\prime })$ of $P$ on glue columns $c$ and $c^{\prime }$ respectively have the same characteristics (they are both upward or downward spans, point east and have the same type). Then we can try to assemble $P_{0,\mathrm{\dots },s}(P_{s^{\prime }+1,\mathrm{\dots },|P|-1}-\overrightarrow{P_s{P}_s^{\prime }})$ or $P_{0,\mathrm{\dots },s^{\prime }}(P_{s+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_s{P}_s^{\prime }})$. To explain what may occur when trying to assemble such paths, we use the extremal path $P$ of Figure 4(a) as an example.

In Figure 4(a), the spans $(s,n)$ and $(s^{\prime },n^{\prime })$ are upward spans and $𝒟$ is the workspace of $(s^{\prime },n^{\prime })$. In Figure 4(b), we try to assemble the path $Q=P_{s+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_s{P}_s^{\prime }}$ at the end of $P_{0,\mathrm{\dots },s^{\prime }}$. While doing so, the following important events occur in this example. Firstly, there exists an index $0\le i\le |Q|-1$ such that $Q_{0,\mathrm{\dots },i}$ grows along $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}$ by putting its tiles in the same positions, i.e. for all $0\le t\le i$, we have $\mathrm{pos}(Q_t)=\mathrm{pos}(P_{s^{\prime }+1+t})$ (the tiles in orange in Figure 4(b)). Secondly, $Q$ turns right of $P_{s^{\prime },\mathrm{\dots },|P|-1}$ at $\mathrm{pos}(Q_i)$ (for a formal definition of this notion see [21, 22]) and stays inside $𝒟$ until it intersects with $P$ at $\mathrm{pos}(P_k)=\mathrm{pos}(Q_j)$. Thirdly, $Q$ leaves $𝒟$ after $Q_j$, i.e. no tiles of $Q_{j+1,\mathrm{\dots },|Q|-1}$ are inside $𝒟$. Fourthly, $Q$ intersects with $P_{0,\mathrm{\dots },s^{\prime }}$. Thus $P_{0,\mathrm{\dots },s^{\prime }}Q$ is not self-avoiding and is not a path but $P_{0,\mathrm{\dots },s^{\prime }}{Q}_{0,\mathrm{\dots },j}$ is a path and it is producible by Fact 2. Moreover, since the tile assembly system is directed then we have $P_k=Q_j$ and $Q_{0,\mathrm{\dots },i}=P_{s^{\prime }+1,\mathrm{\dots },s^{\prime }+1+i}$ is the largest common prefix of $Q$ and $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}$.

Now, we focus on the fact that $Q$ turns right of $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}$. This event implies that $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}-\overrightarrow{P_s{P}_{s^{\prime }}}$ turns left of $P_{s,\mathrm{\dots },|P|-1}$, see Figure 4(d). By doing so, $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}-\overrightarrow{P_s{P}_{s^{\prime }}}$ immediately leaves the workspace $𝒞$ of the span $(s,n)$ of $P$. In this example, $P_{s^{\prime }+1,\mathrm{\dots },|P|-1}-\overrightarrow{P_s{P}_{s^{\prime }}}$ quickly collides with $P_{0,\mathrm{\dots },s}$. Then, in the general case we have three possibilities:

When the first case of Fact 3 occurs, a suffix of $(P_{s^{\prime }+1,\mathrm{\dots },|P|-1}-\overrightarrow{P_s{P}_{s^{\prime }}})$ will be used as a shield. For the third case of Fact 3, it was proven in [21] that in this case the path $P$ is pumpable or fragile which means that either the tile assembly system is not directed or that the terminal assembly is infinite. These events cannot occur in our setting. We do not explain this argument in the roadmap.

In Subsection 3.5, we will consider a specific setting where the second case of Fact 3 also leads to a contradiction. To do so, consider the tile $P_k=Q_j$ of Figure 4: it is the only intersection between $Q_{i+1,\mathrm{\dots },|Q|-1}$ and $P_{s^{\prime }+1+i,\mathrm{\dots },|P|-1}$ in this simple example. Since the tile assembly system is directed, it is possible to “merge” these two paths together. Indeed, $R=P_{0,\mathrm{\dots },s^{\prime }}{Q}_{0,\mathrm{\dots },j}{P}_{k+1,\mathrm{\dots },|P|-1}$ is a producible extremal path, see Figure 4(c). In [21], this operation is repeated several times to build a path called a shield. From this point on, our reasoning differs from [21] and we introduce a setting where shields take a very simple form. Indeed, $P$ and $R$ are both extremal paths. Moreover, they share the common prefix $P_{0,\mathrm{\dots },s^{\prime }+1+i}$. Nevertheless the path $R$ turns right of $P$ at tile $P_i$. Then, we say that $R$ is more right-priority than $P$. This notion of right-priority implies an order on extremal paths. Moreover, since we consider a finite terminal assembly, there is a finite number of extremal paths. Thus, it is possible to choose a rightmost-priority one. For such a path, it is not possible to be in a case like in Figure 4(c) where there is an intersection between $P_{s^{\prime }+i+1,\mathrm{\dots },|P|-1}$ and $Q_{i+1,\mathrm{\dots },|Q|-1}$.

Our aim is to work in a setting where only the first case of Fact 3 is possible. To achieve this goal, we consider an extremal path $P$, two glue columns , and we let $(s,n)$ be the span of $P$ on glue column $c$ and $(s^{\prime },n^{\prime })$ the span of $P$ on glue column $c^{\prime }$, for an example see Figure 5.

To eliminate the second case of Fact 3 where $P_{s^{\prime }}(P_{s+1,\mathrm{\dots },|P|-1}+\overrightarrow{P_s{P}_{s^{\prime }}})$ turns right of $P_{s^{\prime },\mathrm{\dots },|P|-1}$, we consider that $P$ is not an arbitrary chosen path but that $P$ is chosen wisely to have the following property.

In the extended version of the paper [14], we will use a slightly weaker version of this property and we will consider canonical paths instead of good paths. Nevertheless, we do not enter into this level of details here. The following lemma explains how to find a good path.

We consider the span $(s,n)$ of a path $P$ on a glue column ${ℬ}_1\le c\le {ℬ}_2$. In this subsection, we explain how a shield $S$ of this span can be used to find a protected and pseudo-visible glue on glue column $c$, and we list the assumptions done to obtain this result. Such a glue will have properties similar to those of a visible glue. Then, when Fact 3 is used on two spans with the same characteristics, either a shield or a contradiction is obtained. If a shield is obtained then a new protected and pseudo-visible glue can be found. This glue behaves as a visible glue and will replace the one consumed by using Fact 3. We start by defining a pseudo-visible glue, see Figure 9.

Consider $s\le d\le u\le |P|-1$ such that $\mathrm{glue}(P_d{P}_{d+1})$ is pseudo-visible from the south (resp. north) on glue column $c$ and $\mathrm{glue}(P_u{P}_{u+1})$ is visible from the north (resp. south) in $P_{d,\mathrm{\dots },|P|+1}$ on glue column $c$ then $(u,d)$ is an upward (resp. downward) pseudo-span. Consider, the workspace ${𝒞}^{\prime }$ associated to the cut $(d,u)$ of $P_{d,\mathrm{\dots },|P|-1}$. The pseudo-span $(d,u)$ is visible if and only if, for any path $Q$ such that $Q$ is in ${𝒞}^{\prime }$ and $Q_0$ interacts with $P_d$, $P_{0,\mathrm{\dots },d}Q$ is producible. Note that any span is a visible pseudo-span but a pseudo-span is not necessarily visible, see Figures 10 and 11. Intuitively, a visible pseudo-span behaves like a span. Shields will be used to find new visible pseudo-spans (in particular those which are not spans).

The proof of the main Theorem 1 is done by showing that the larger the path is, the more constrained it is. The first proven bound, in [21], uses only two glues per glue column: the glue visible from the north and the glue visible from the south. When the proof requires more glues to find a contradiction, a new glue column is considered. Here, shields will be used to locate visible pseudo-span, allowing to work with more than two glues per glue column. Now, we explain how to locate a visible pseudo-span on a simple case where several hypotheses on the shield are assumed. These hypotheses will allow a shield to protect a glue of $P$. The general case is far more complex and is solved in [14].

Let $S$ be a shield of the span $(s,n)$ of $P$ and consider of $P$ such that $\mathrm{glue}(P_d{P}_{d+1})$ is on glue column $c$ and pointing east. If there exists $0\le i\le |S|-1$ such that $\mathrm{glue}(S_i{S}_{i+1})$ is on glue column $c$ and no glue of $P$ is on glue column $c$ between $\mathrm{glue}(P_d{P}_{d+1})$ and $\mathrm{glue}(S_i{S}_{i+1})$, then $\mathrm{glue}(P_d{P}_{d+1})$ is protected by shield $S$, see Figure 9. Note that, we propose here a simplified definition of a protected glue which is sufficient for the roadmap. The formal definition is given in [14]. First, remark that shield $S$ must intersect glue column $c$ to be useful according to this definition.

How to find a protected glue when a shield satisfies the hypothesis of Lock 4 is explained in [14]. In this roadmap, we assume that this protected glue is pseudo-visible.

Moreover, we also add this condition to avoid complex cases which are discussed later.

It follows from Locks 5 and 6 that $(d,n)$ is a pseudo-span. According to Lock 4, shield $S$ protects $\mathrm{glue}(P_d{P}_{d+1})$. These hypotheses are sufficient to show that the pseudo-span $(s,n)$ is visible.

To obtain this result, consider a path $Q$ such that $Q_0$ interacts with $P_d$ and $Q$ is inside the workspace ${𝒞}^{\prime }$ of the pseudo-span $(d,n)$ of $P$ as shown in Figures 10 and 11. In this example, $P_{0,\mathrm{\dots },d}Q$ is not a path since the last tile of $Q$ intersects with $P_{0,\mathrm{\dots },d}$. Note furthermore that $Q$ also intersects shield $S$ (Figure 12). Then, by merging parts of $P$, $Q$, and $S$, we obtain a more right-priority path as shown in Figure 13, which contradicts the assumption that $P$ is a good path for glue column $c$.

Another way for $Q$ to collide with $P_{0,\mathrm{\dots },d}$ is to avoid $S$ by turning around it. To do so, $Q$ must grow to the east and then go back to the west, see Figure 13. This pattern is called a U-turn and a key point of the proof of the pumping lemma [21] is to prove that there is a contradiction if the U-turn is long enough. A quadratic bound was proven in [21]. To obtain the main result of this work, we must improve this bound to a linear one. Solving Lock 7 is done in two steps, see Figure 13 for an illustration.

Informally, these two locks capture the intuition that shield $S$ is an obstacle preventing any collision between $Q$ and $P_{0,\mathrm{\dots },d}$, and ensures that pseudo-span $(d,n)$ is visible.

If all these arguments hold then we can consider $2|T|+1$ spans of $P$ which are located on different glue columns between ${ℬ}_1=e_{\sigma +|T|+1.5}$ and ${ℬ}_2=e_{\sigma +5|T|+1.5}$. By the pigeonhole principle, two of these spans have the same direction and type. According to the reasoning presented so far, either there is a contradiction ($P$ is not extremal or $P$ is not a good path for a given column) or a shield can be assembled which can be used to find a visible pseudo-span. In the considered collection of $2|T|+1$ spans, one of them can be replaced by this new visible pseudo-span. Note that the new pseudo-span is narrower than the replaced one. By iterating this reasoning, we eventually find a contradiction.

In Section $4$ of the extended version [14], we start by explaining how to build a canonical path for a glue column ${ℬ}_1\le c\le {ℬ}_2$, solving Lock 3. A canonical path is obtained by slightly modifying a good path. These modifications are done to deal with Lock 6. In Section $5$ of [14], we give a linear bound on the length of U-turns, solving Locks 8 and 9 (and thus Lock 7). Alongside the tools developed in this section, we remind the arguments of [36] to solve Lock 1 and the arguments of [21] to solve Lock 2. Thirdly, we introduce in Section $6$ of [14] the decomposition of a canonical path $P$ on glue column $c$ into arcs⁵⁵5This decomposition was first introduced in [36] but was later abandoned in the final version of the paper after some simplifications. to solve Lock 5. This decomposition allows to find protected glues which are not pseudo-visible. In Section $7$ of [14], we give the formal definition of a shield and put all arguments together to prove the main Theorem 1 by following the reasoning of this roadmap. The proof of the extended version [14] ends with the special case of Lock 4.