A self-similar aperiodic set of 19 Wang tiles
S. Labbé]Sébastien Labbé
[S. Labbé]CNRS, LaBRI, UMR 5800, F-33400 Talence, France

We define a Wang tile set $\mathcal{U}$ of cardinality 19 and show that the set $\Omega_\mathcal{U}$ of all valid Wang tilings $\mathbb{Z}^2\to\mathcal{U}$ is self-similar, aperiodic and is a minimal subshift of $\mathcal{U}^{\mathbb{Z}^2}$. Thus $\mathcal{U}$ is the second smallest self-similar aperiodic Wang tile set known after Ammann's set of 16 Wang tiles.  The proof is based on the unique composition property.  We prove the existence of an expansive, primitive and recognizable $2$-dimensional morphism $\omega:\Omega_\mathcal{U}\to\Omega_\mathcal{U}$ that is onto up to a shift. The proof of recognizability is done in two steps using at each step the same criteria (the existence of marker tiles) for proving the existence of a recognizable one-dimensional substitution that sends each tile either on a single tile or on a domino of two tiles.

§ INTRODUCTION

Wang tiles are unit square tiles with colored edges
as in Figure <ref>.
Given a finite set
of Wang tiles, we consider tilings of the Euclidean plane using
arbitrarily many copies of the tiles. Tiles are placed on the integer lattice
points of the plane with their edges oriented horizontally and vertically. The
tiles may not be rotated. The tiling is valid if every
contiguous edges have the same color.
Given a finite set $\T$ of Wang tiles, we denote by $\Omega_\T$ the set of all
valid tilings $f:\Z^2\to\T$. The set
$\Omega_\T$ is a $2$-dimensional subshift as it
is invariant under translations and closed under taking limits.
Hence $\Omega_\T$ is called the Wang shift of $\T$.
A nonempty Wang shift $\Omega_\T$ is aperiodic if none of the tilings in
$\Omega_\T$ have a nontrivial period.

Chapters 10 and 11 of <cit.> and the more recent
book on aperiodic order <cit.> give an excellent overview of what is
known on aperiodic tilings (in $\Z^d$ as in $\R^d$) together with their
applications to physics and crystallography.

The set $\U$ of 19 Wang tiles.

A nonexhaustive list of aperiodic Wang tile sets is shown in
Table <ref>.  Examples of small aperiodic Wang tile
sets include Ammann's 16 tiles <cit.>, Kari's 14 tiles <cit.>  and Culik's 13 tiles <cit.>.  The
question of finding the smallest aperiodic set of Wang tiles was open until
Jeandel and Rao proved
the existence of an aperiodic set of 11 Wang tiles
and that no set of Wang tiles of cardinality $\leq10$ is aperiodic.
The proofs of their two results is based on transducers, which has proven to be
an excellent approach for the search of the smallest aperiodic Wang tile set.
A transducer is a finite-state machine with two memory tapes:
an input tape and an output tape. There is a natural way to construct a
transducer from a set of Wang tiles (see Figure <ref>)
which computes some row of tiles that can be placed above some other row of

In this contribution we introduce a set $\U$
of 19 Wang tiles (see Figure <ref>).
The main result of the current contribution is that
$\U$ is aperiodic and that it generates
tilings (Figure <ref>) of $\Z^2$ with a self-similar
With 19 tiles, this makes $\U$ the second smallest self-similar aperiodic
set after Ammann's tile set which has 16 only tiles.
The tile set $\U$ comes from the study of the structure
of Jeandel-Rao aperiodic tilings. The link with Jeandel-Rao tilings needs more
tools and space and will be done in a forthcoming paper
In this contribution, we prove the following

The Wang shift $\Omega_\U$ is self-similar, aperiodic and minimal.

To prove aperiodicity, we use the composition-decomposition method
also called the unique composition property
for tilings of $\R^d$ described in
<cit.> and <cit.>.
Let us cite <cit.> which summarizes informally the
composition-decomposition method as two conditions to be satisfied
for a tile set $\T$: if

in every tiling admitted by $\T$ there is a unique way in which the
tiles can be grouped into patches which lead to a tiling by supertiles;

the markings on the supertiles, inherited from the original tiles,
imply a matching condition for the supertiles which is exactly equivalent to
that originally specified for the tiles,

then $\T$ is aperiodic.
Condition <ref> was formalized with many vocabularies in the literature
including the term unambiguous in <cit.>. In this contribution
(see Proposition <ref>), we use the
notion of recognizability.
This method was used to prove aperiodicity of the
first discovered aperiodic examples (see Table <ref>).
The proof of aperiodicity of 104 Berger's tile set is
obtained by the use of two-by-two substitutions of the form $\square\mapsto\boxplus$, mapping each tile to a two-by-two square of 4 tiles.
The same holds for Knuth's and Robinson's tile sets, their constructions being
obtained as a simplification of Berger's tile set (see also <cit.>).
Note that the composition-decomposition method does not apply to all aperiodic
tile set, e.g. aperiodicity of Kari and Culik tile sets
<cit.> follows from arithmetic properties.

Author     Size     Year     Proof of aperiodicity     s.s.    $\lambda$     References

Berger     104     1964     unique composition property     yes     2     <cit.>

Knuth     92     1968     ”     yes     2     <cit.>

Robinson     56     1971      ”     yes     2     <cit.>

Grünbaum et al.     24     1987     ”     yes     $\frac{1+\sqrt{5}}{2}$     <cit.>

Ammann     16     1971     ”     yes     $\frac{1+\sqrt{5}}{2}$     <cit.>

Kari     14     1996     arithmetic properties     no     –     <cit.>

Culik     13     1996     ”     no     –     <cit.>

Jeandel, Rao     11     2015     transducers and Fibonacci word     no     –     <cit.>

A list of small aperiodic sets of Wang tiles.
Whether the tile set is self-similar (s.s.) is indicated.
When applicable, $\lambda$ denotes the expansion factor of the similarity
involved in the composition (see Section <ref> on stone
inflations). Ammann's tile set is the smallest known self-similar aperiodic
Wang tile set. The history includes many unpublished results and a more
complete story can be found in <cit.>.

As it is the case for Ammann set of 16 Wang tiles <cit.>, the
substitutive structure of tilings in $\Omega_\U$ have the form
$\square\mapsto\boxplus$, that is, the image of a tile is a tile, a vertical or
horizontal domino of two tiles, or a two-by-two square of 4 tiles.
More precisely, in this contribution, we show that any tiling of $\Z^2$ by the
19 tiles in $\U$ can be decomposed uniquely into a tilings by the supertiles shown in
Figure <ref>. It can be seen by comparing
Figure <ref> and
Figure <ref> that the markings on the supertiles imply a
matching condition which is equivalent to those specified for $\U$ (horizontal
color $KO$ in the supertiles plays the role of color $P$ in the tile set $\U$,
etc.), thus satisfying <ref> and <ref>.

Any tiling in $\Omega_\U$ can be decomposed uniquely into a tiling
by these 19 supertiles. Each of these supertiles is equivalent to one of the
tiles in $\U$ which explains the self-similar structure of tilings in
$\Omega_\U$. It is reminiscent of Figure 11.1.16 in <cit.>.

A $13\times 8$ rectangle tiled by tiles from $\U$.
It corresponds to $\omega^5(u_4)$ where $\omega=\alpha\beta\gamma$ is
defined in Section <ref>.
Notice that the sequence of colors at the top correspond to the sequence at
the bottom allowing a periodic tiling of a infinite vertical strip of
width 13.
Dashed lines identify the decomposition into supertiles.
Solid lines identify the decomposition into supertiles of the next level.

The particularity and the importance of this contribution stands in breaking
down the proof of unique composition property into smaller steps.
Thus, each step consists in proving recognizability and surjectivity up to a shift for a
substitution of the form $\square\mapsto\square,\square\mapsto\dominoV{none}{none}{}$
or of the form $\square\mapsto\square,\square\mapsto\dominoH{none}{none}{}$.
Each step has the effect of identifying special rows (or columns) made of marker tiles
(see Definition <ref>) that have to be adjacent in one direction but can not
be adjacent in the other direction.
The wider applicability of this method (Theorem <ref>) allowing
to be automated by computer check will be used in <cit.>.

Following the theory of $S$-adic systems on $\Z$ <cit.> and
hierarchical tilings of $\R^d$ <cit.>,
we desubstitute tilings in $\Omega_\U$ into tilings in
$\Omega_\V$ by a $2$-dimensional morphism $\alpha:\Omega_\V\to\Omega_\U$ for some Wang tile set $\V$
and we desubstitute tilings of $\Omega_\V$ into tilings in $\Omega_\W$
by a $2$-dimensional morphism $\beta:\Omega_\W\to\Omega_\V$ for some Wang tile set $\W$.
Finally we prove that $\alpha$ and $\beta$ are recognizable
thus satisfying <ref>
and that there is a
letter to letter bijection $\gamma:\Omega_\U\to\Omega_\W$
that satisfies <ref>.

(U) at (0,0) $\Omega_\U$;
(V) at (5,0) $\Omega_\V$;
(W) at (10,0) $\Omega_\W$;
(U2) at (13,0) $\Omega_\U$;
[to-,very thick] (U) to node $\alpha:
\unitsquare{none}\mapsto\unitsquare{none},
\unitsquare{none}\mapsto\dominoV{none}{none}{}$ (V);
[to-,very thick] (V) to node $\beta:
\unitsquare{none}\mapsto\unitsquare{none},
\unitsquare{none}\mapsto\dominoH{none}{none}{}$ (W);
[to-,very thick] (W) to node $\gamma:
\unitsquare{none}\mapsto\unitsquare{none}$ (U2);

A key result in this contribution is Theorem <ref> since
it is used twice to prove that we can desubstitute uniquely.  It can be seen as
a $2$-dimensional generalization to Wang subshifts of the notion of
derived sequences introduced in <cit.> for $1$-dimensional
substitutive sequences. Remark that another generalization of derived
sequences to tilings of $\R^2$ based on Voronoï tessellations is presented in
<cit.>. The advantage of markers and Theorem <ref> is
that the rectangular lattice structure of Wang tilings is preserved under each

The paper is structured as follows.
In Section <ref>, we present the necessary definitions and
notations on Wang tiles including self-similarity, recognizability and
In Section <ref>,
we present a sufficient condition for the existence of
a recognizable $2$-dimensional morphism allowing to desubstitute any tiling of
a Wang shift.
In Section <ref> and Section <ref>, we prove the existence of
tile sets $\V$ and $\W$ and $2$-dimensional morphisms
$\alpha:\Omega_\V\to\Omega_\U$ and
that are recognizable and surjective up to a shift.
In Section <ref>, we prove that $\U$ and $\W$ are
equivalent tile sets and we prove self-similarity, aperiodicity and minimality
of $\Omega_\U$.
In Section <ref>, we present a stone inflation version of
A minimal number of lemmas are proved using Sage
and their proofs are provided in Section <ref>.

§ PRELIMINARIES

In this section, we introduce
subshifts, shifts of finite type,
Wang tiles,
fusion of Wang tiles,
the transducer representation of Wang tiles,
$d$-dimensional words, morphisms and languages.
We recall the notions of
self-similarity and
recognizability for proving aperiodicity.

We denote by $\Z=\{\dots,-1,0,1,2,\dots\}$ the integers and
by $\N=\{0,1,2,\dots\}$ the nonnegative integers.
If $d\geq1$ is an integer and $1\leq k\leq d$, we denote by
$\be_k=(0,\dots,0,1,0,\dots,0)\in\Z^d$ the vector of the canonical
basis of $\Z^d$ with a $1$ as position $k$ and $0$ elsewhere.

§.§ Subshifts and shifts of finite type

We follow the notations of <cit.>.
Let $\A$ be a finite set, $d\geq 1$, and let $\A^{\Z^d}$ be the set of all maps
$x:\Z^d\to\A$, furnished with the compact product topology. We write a typical
point $x\in\A^{\Z^d}$ as $x=(x_\bm)=(x_\bm:\bm\in\Z^d)$, where $x_\bm\in\A$
denotes the value of $x$ at $\bm$. The shift action $\sigma:\bn\mapsto
\sigma^\bn$ of $\Z^d$ on $\A^{\Z^d}$ is defined by

\begin{equation}\label{eq:shift-action}
(\sigma^\bn(x))_\bm = x_{\bm+\bn}
\end{equation}

for every $x=(x_\bm)\in\A^{\Z^d}$ and $\bn\in\Z^d$. A subset $X\subset
\A^{\Z^d}$ is shift-invariant if $\sigma^\bn(X)=X$ for every
$\bn\in\Z^d$, and a closed, shift-invariant subset $X\subset\A^{\Z^d}$ is a
If $X\subset\A^{\Z^d}$ is a subshift we write
$\sigma=\sigma^X$ for the restriction of the shift-action
(<ref>) to $X$.
If $X\subset\A^{\Z^d}$ is a subshift it will sometimes be helpful to specify the
shift-action of $\Z^d$ explicitly and to write $(X,\sigma)$ instead of $X$.
A subshift $(X,\sigma)$ is called minimal if $X$ does not
contain any nonempty, proper, closed shift-invariant subset.

For any subset $S\subset\Z^d$ we denote by $\pi_S:\A^{\Z^d}\to\A^S$ the
projection map which restricts every $x\in\A^{\Z^d}$ to $S$.
A pattern is a function $p:S\to\A$ for some finite subset

A subshift $X\subset\A^{\Z^d}$ is a
shift of finite type (SFT) if there exists a finite set $\F$
of forbidden patterns such that

\begin{equation}\label{eq:SFT}
X = \{x\in\A^{\Z^d} \mid \pi_S\cdot\sigma^\bn(x)\notin\F
\text{ for every } \bn\in\Z^d \text{ and } S\subset\Z^d\}.
\end{equation}

In this case, we write $X=\SFT(\F)$.

§.§ Wang tiles

A Wang tile $\tau=\tile{$a$}{$b$}{$c$}{$d$}$ is a unit square with colored edges
formally represented as a tuple of four colors $(a,b,c,d)\in I\times J\times
I\times J$
where $I$, $J$ are
two finite sets (the vertical and horizontal colors respectively).
For each Wang tile $\tau=(a,b,c,d)$, we denote by
the colors of the right, top, left and bottom edges of $\tau$

Let $\T$ be a set of Wang tiles. A tiling of $\Z^2$ by $\T$ is an assignation $x$
of tiles to each position of $\Z^2$ so that contiguous edges have the same
color, that is, it is a function $x:\Z^2\to\T$ satisfying

\begin{align}
\scright\circ x(\bn)&=\scleft\circ x(\bn+\be_1)\label{eq:1}\\
\sctop\circ x(\bn)&=\scbottom\circ x(\bn+\be_2)\label{eq:2}
\end{align}

for every $\bn\in\Z^2$.
We denote by $\Omega_\T\subset\T^{\Z^2}$ the set of all Wang tilings of $\Z^2$
by $\T$ and we call it the Wang shift of $\T$. It is a SFT of
the form (<ref>).

A set of Wang tiles $\T$ tiles the plane if $\Omega_\T\neq\varnothing$
and does not tile the plane if $\Omega_\T=\varnothing$.
A tiling $x\in\Omega_\T$ is periodic if there is a nonzero period
$\bn\in\Z^2\setminus\{(0,0)\}$ such that $x=\sigma^\bn(x)$
and otherwise it is said nonperiodic.
A set of Wang tiles $\T$ is periodic if there is a tiling
$x\in\Omega_\T$ which is periodic. A Wang tile set $\T$ is aperiodic if
$\Omega_\T\neq\varnothing$ and every tiling $x\in\Omega_\T$ is nonperiodic.
As explained in the first page of <cit.>
(see also <cit.>),
if $\T$ is periodic, then there is a tiling $x$ by $\T$ with two linearly
independent translation vectors (in particular a tiling $x$ with vertical
and horizontal translation vectors).

We say that two Wang tile sets $\T$ and $\S$ are
equivalent if there exist two bijections $i:I\to I'$ $j:J\to J'$ such

\begin{equation*}
\S = \{(i(a),j(b),i(c),j(d)) \mid (a,b,c,d) \in \T\}.
\end{equation*}

If $\T$ is a set of Wang tiles, then we define the dual tile set $\T^*$
as its image under a reflection through the positive diagonal, i.e.,

\begin{equation*}
\T^* = \left\{(b,a,d,c)=\tile{$b$}{$a$}{$d$}{$c$}\,\middle|\,
\end{equation*}

§.§ Fusion of Wang tiles

Now, we introduce a fusion operation on Wang tiles that can be adjacent in a
$u=\tile{Y}{B}{X}{A}$ and
be two Wang tiles.
For $i\in\{1,2\}$,
we define a binary operation on Wang tiles denoted $\boxminus^i$ as

\begin{equation*}
u\boxminus^1 v=\tile{Z}{BD}{X}{AC}
\quad
\text{ if }
Y = W
\qquad
\text{ and }
\qquad
u\boxminus^2 v=
\raisebox{-3mm}{
\begin{tikzpicture}[scale=0.9]
% tile at position (x,y)=(0, 0)
\draw (0, 0) -- (1, 0);
\draw (0, 0) -- (0, 1);
\draw (1, 1) -- (1, 0);
\draw (1, 1) -- (0, 1);
\node[rotate=90,font=\footnotesize] at (0.8, 0.5) {YZ};
\node[rotate=0,font=\footnotesize] at (0.5, 0.8) {D};
\node[rotate=90,font=\footnotesize] at (0.2, 0.5) {XW};
\node[rotate=0,font=\footnotesize] at (0.5, 0.2) {A};
\end{tikzpicture}}
\quad \text{ if } B = C.
\end{equation*}

If $i=1$ and $Y\neq W$ or if
$i=2$ and $B\neq C$, we say that $u\boxminus^i v$ is not well-defined.
If $u\boxminus^i v$ is well-defined for some $i\in\{1,2\}$, it means that $u$
and $v$ can appear at position $\bn$ and $\bn+\be_i$ in a tiling for some
$\bn\in\Z^d$. When appropriate, we also use the following more visual notation
for denoting $u\boxminus^i v$:

\begin{equation*}
u\boxminus^1 v =
\begin{array}{|cc|}\hline u & v\\\hline\end{array}
\qquad
\text{ and }
\qquad
u\boxminus^2 v =
\begin{array}{|c|}
\hline
v \\
u \\
\hline
\end{array}.
\end{equation*}

For each $i\in\{1,2\}$, one can define a new tile set from
two Wang tile sets $\T$ and $\S$ as

\begin{equation*}
\T\boxminus^i\S = \{u\boxminus^i v \text{ well-defined }\mid
\end{equation*}

The fusion operation together with taking the dual of a tile set satisfy the
following equations:

\begin{equation*}
(\T\boxminus^1\S)^* = \T^*\boxminus^2\S^*
\qquad
\text{ and }
\qquad
(\T\boxminus^2\S)^* = \T^*\boxminus^1\S^*.
\end{equation*}

§.§ Transducer representation of Wang tiles

A transducer $M$ is a labeled directed graph whose nodes are called
states and edges are called transitions. The transitions are
labeled by pairs $a|b$ of letters. The first letter $a$ is the input symbol and
the second letter $b$ is the output symbol. There is no initial nor final state.
A transducer $M$ computes a relation $\rho(M)$ between bi-infinite sequences of

As observed in <cit.> and extensively used in
<cit.>, any finite set of Wang tiles may be interpreted
as a transducer. To a given tile set $\T$, the states of the corresponding
transducer $M_\T$ are the colors of the vertical edges. The colors of
horizontal edges are the input and output symbols. There is a transition from
state $s$ to state $t$ with label $a|b$ if and only if there is a tile
$(t,b,s,a)\in\T$ whose left, right, bottom and top edges are colored by $s$,
$t$, $a$ and $b$, respectively:

\begin{equation*}
M_\T = \left\{ s\xrightarrow{a|b} t :
\tile{$t$}{$b$}{$s$}{$a$}=(t,b,s,a) \in \T \right\}.
\end{equation*}

The transducer $M_\U$ for the tile set $\U$ is shown in Figure <ref>.

The transducer $M_\U$. Each tile of $\U$ corresponds to a transition.
For example, the first tile of $\U$ is associated to $J\xrightarrow{O|O}F$,

Sequences $x$ and $y$ are in the relation $\rho(M_\T)$ if and only
if there exists a row of tiles, with matching vertical edges, whose bottom edges
form sequence $x$ and top edges sequence $y$.
For example, the sequence of bottom colors seen on the
lowest row of the tiling shown at Figure <ref>
is $KOKPOKOKPOKPO$.
Starting in state $G$ and reading that word as input in the transducer
$M_\U$ we follow the transitions:

\[
\]

We finish in state $G$ and we get $PLKPLPLKPLPPL$ as output which corresponds
to the sequence of top colors of the lowest row of the tiling at
Figure <ref>.
Then, starting in state $F$ and reading the previously output word
$PLKPLPLKPLPPL$ as input we compute the second row of the tiling at
Figure <ref>, etc. In general, there is a
one-to-one correspondence between valid tilings of the plane, and
the iterated execution of the transducer.

Notice that the result of the usual composition of transducers
corresponds to the transducer of $\T\boxminus^2\S$:

\begin{equation}\label{eq:boxminus_with_transducer}
M_\T\circ M_{\S} = M_{\T\boxminus^2\S}.
\end{equation}

As done in <cit.>,
the result of the composition can be filtered by
recursively removing any source or sink state from the transducer
reducing the size of the tile set.
This is very helpful for doing computations
(see the proof Lemma <ref>).

§.§ $d$-dimensional word

In this section, we recall the definition of $d$-dimensional word that appeared
in <cit.> and we keep the notation $u\odot^i v$ they proposed
for the concatenation.

If $i\leq j$ are integers, then $\llbracket i, j\rrbracket$ denotes the interval of integers $\{i, i+1, \dots, j\}$.
Let $\bn=(n_1,\dots,n_d)\in\N^d$ and $\A$ be an alphabet.
We denote by $\A^{\bn}$ the set of functions

\begin{equation*}
\llbracket 0,n_1-1\rrbracket
\times
\cdots
\times
\llbracket 0,n_d-1\rrbracket
\to\A.
\end{equation*}

An element $u\in\A^\bn$ is called a
$d$-dimensional word $u$ of shape $\bn=(n_1,\dots,n_d)\in\N^d$
on the alphabet $\A$.
The set of all finite $d$-dimensional word is
A $d$-dimensional word of shape $\be_k+\sum_{i=1}^d\be_i$ is called a
domino in the direction $\be_k$.
When the context is clear, we write $\A$ instead of $\A^{(1,\dots,1)}$.
When $d=2$, we represent a $d$-dimensional word $u$ of shape $(n_1,n_2)$ as a
matrix with Cartesian coordinates:

\begin{equation*}
\left(\begin{array}{ccc}
u_{0,n_2-1} &\dots   & u_{n_1-1,n_2-1} \\
\dots   &\dots   & \dots \\
u_{0,0} &\dots   & u_{n_1-1,0}
\end{array}\right).
\end{equation*}

Let $\bn,\bm\in\N^d$ and $u\in\A^\bn$ and $v\in\A^\bm$.
If there exists an index $i$ such that the
shapes $\bn$ and $\bm$ are equal except at index $i$,
then the concatenation of $u$ and $v$ in the direction $\be_i$
is well-defined: it is
$d$-dimensional word $u\odot^i v$ of shape $(n_1,\dots,n_{i-1},n_i+m_i,n_{i+1},\dots,n_d)\in\N^d$
defined as

\begin{equation*}
(u\odot^i v) (\ba) =
\begin{cases}
u(\ba)          & \text{if}\quad 0 \leq a_i < n_i,\\
v(\ba-n_i\be_i) & \text{if}\quad n_i \leq a_i < n_i+m_i.
\end{cases}
\end{equation*}

If the shapes $\bn$ and $\bm$ are not equal except at
index $i$, we say that the concatenation of $u\in\A^\bn$ and $v\in\A^\bm$ in
the direction $\be_i$ is not well-defined.

Let $\bn,\bm\in\N^d$ and $u\in\A^\bn$ and $v\in\A^\bm$.
We say that $u$ occurs in $v$ at position $\bp\in\N^d$ if
$v$ is large enough, i.e., $\bm-\bp-\bn\in\N^d$ and

\[
v(\ba+\bp) = u(\ba)
\]

for all $\ba=(a_1,\dots,a_d)\in\N^d$ such that
$0\leq a_i<n_i$ with $1\leq i\leq d$.
If $u$ occurs in $v$ at some position, then we say that $u$ is a
$d$-dimensional subword or factor of $v$.

§.§ $d$-dimensional morphisms

In this section, we generalize the definition of $d$-dimensional morphisms
<cit.> to the case where the domain and codomain are different as for
$S$-adic systems.

Let $\A$ and $\B$ be two alphabets.
Let $X\subseteq\A^{*^d}$.
A function $\omega:X\to\B^{*^d}$ is a $d$-dimensional
morphism if for every
$i$ with $1\leq i\leq d$,
and every $u,v\in X$ such that $u\odot^i v\in X$ is well-defined
we have
that the concatenation $\omega(u)\odot^i \omega(v)$
in direction $\be_i$ is well-defined and

\begin{equation*}
\omega(u\odot^i v) = \omega(u)\odot^i \omega(v).
\end{equation*}

The next lemma can be deduced from the definition.
It says that when $d\geq 2$ every $d$-dimensional morphism
defined on the whole space $X=\A^{*^d}$ is uniform in the sense that it maps
every letter to a $d$-dimensional word of the same shape. These are called block-substitutions in <cit.>.

If $d\geq 2$ and $\omega:\A^{*^d}\to\B^{*^d}$ is a $d$-dimensional morphism,
then there exists a shape $\bn\in\N^d$ such that $\omega(a)\in\A^\bn$ for
every letter $a\in\A$.

Therefore, to consider non-uniform $d$-dimensional morphism when $d\geq 2$, we
need to restrict the domain to a strict subset $X\subsetneq\A^{*^d}$.
For example,
let $d=2$ and $\A=\{a,b,x,y\}$.
The map $\omega:\A\to\A^{*^2}$ defined by
$\omega: a\mapsto aaa, b\mapsto bbb, x\mapsto xx, y\mapsto yy$
is not a well-defined $2$-dimensional morphism $\A^{*^2} \to\A^{*^2}$,
it is a well-defined $2$-dimensional morphism $X\to\A^{*^2}$,
for the strict subset $X\subsetneq\A^{*^2}$ such that every column
of every $w\in X$ is over $\{a,b\}$ or $\{x,y\}$.

For instance, we have

\[
\omega:
\begin{array}{c|c|c|c}
x & a & b & y\\
y & a & a & y\\
x & b & a & x\\
y & b & b & y\\
y & b & a & x\\
x & a & b & x\\
\end{array}
\mapsto
\begin{array}{c|c|c|c}
xx & aaa & bbb & yy\\
yy & aaa & aaa & yy\\
xx & bbb & aaa & xx\\
yy & bbb & bbb & yy\\
yy & bbb & aaa & xx\\
xx & aaa & bbb & xx\\
\end{array}.
\]

A $d$-dimensional morphism
$\omega:X \to\B^{*^d}$
with $X\subseteq\A^{*^d}$
can be extended to a $d$-dimensional morphism
with $Y\subseteq\A^{\Z^d}$.

In <cit.> and <cit.>, they consider the case $\A=\B$
and they restrict the domain of $d$-dimensional morphisms to the language they

Suppose now that $\A=\B$.
We say that a $d$-dimensional morphism $\omega:\A\to\A^{*^d}$ is
if for every $a\in\A$ and $K\in\N$,
there exists $m\in\N$ such that
We say that $\omega$ is primitive
if there exists $m\in\N$ such that
for every $a,b\in\A$ the letter $b$ occurs in $\omega^m(a)$.

The definition of prolongable substitutions <cit.> can be adapted in the case of $d$-dimensional morphisms.
Let $d$-dimensional morphism $\omega:X \to\A^{*^d}$ with $X\subseteq\A^{*^d}$.
Let $s\in\{+1,-1\}^d$.
We say that $\omega$ is prolongable on letter $a\in\A$ in the
hyperoctant of sign $s$ if the letter $a$ appears in the appropriate corner of
its own image $\omega(a)$ more precisely at position
$p=(p_1,\dots,p_d)\in\N^d$ where

\[
p_i =
\begin{cases}
0       & \text{if}\quad s_i = +1,\\
n_i-1   & \text{if}\quad s_i = -1.
\end{cases}
\]

where $\bn=(n_1,\dots,n_d)\in\N^d$ is the shape of $\omega(a)$.
If $\omega$ is prolongable on letter $a\in\A$ in the hyperoctant of
sign $s$
and if
$\lim_{m\to\infty}\min(\shape(\omega^m(a)))=\infty$, then
$\lim_{m\to\infty}\omega^m(a)$ is a well-defined $d$-dimensional infinite word
$s_0\N\times\dots\times s_{d-1}\N\to\A$.

§.§ $d$-dimensional language

A subset $L\subseteq\A^{*^d}$ is called a $d$-dimensional language. The
factorial closure of a language $L$ is

\begin{equation*}
\overline{L}^{Fact}
= \{u\in\A^{*^d} \mid u\text{ is a $d$-dimensional subword of some }
v\in L\}.
\end{equation*}

A language $L$ is factorial if $\overline{L}^{Fact}=L$.
All languages considered in this contribution are factorial.
Given a tiling $x\in\A^{\Z^d}$, the language $\L(x)$ defined by $x$ is

\begin{equation*}
\L(x) = \{u\in\A^{*^d} \mid u\text{ is a $d$-dimensional subword of } x\}.
\end{equation*}

The language of a subshift $X\subseteq\A^{\Z^d}$ is
$\L_X = \cup_{x\in X} \L(x)$.
Conversely, given a factorial language $L\subseteq\A^{*^d}$ we define the subshift

\begin{equation*}
\X_L = \{x\in\A^{\Z^d}\mid \L(x)\subseteq L\}.
\end{equation*}

A language $L\subseteq\A^{*^d}$ is forbidden in a subshift
$X\subset\A^{\Z^d}$ if $L\cap\L_X=\varnothing$.
By extension, a $d$-dimensional subword $u\in\A^{*^d}$ is forbidden in a
subshift $X\subset\A^{\Z^d}$ if the singleton language $\{u\}$ is forbidden in

We say that a word $u\in\A^\bn$,
with $\bn=(n_1,\dots,n_d)\in\N^d$,
admits a surrounding of radius $r\in\N$
in a language $L\subseteq\A^{*^d}$ (resp. in a subshift $X\subset\A^{\Z^d}$)
if there exists $w\in\A^{\bn+2(r,\dots,r)}$
such that $w\in L$ (resp. $w\in\L_X$) and
$u$ occurs in $w$ at position $(r,\dots,r)$.

Now we consider notions of languages related to morphisms.
Given a $d$-dimensional morphism $\omega:\A \to\B^{*^d}$
and a language $L\subseteq\A^{*^d}$ of $d$-dimensional words, then
we define the image of the language $L$ under $\omega$ as
the language

\begin{equation*}
\overline{\omega(L)}^{Fact}
= \{u\in\B^{*^d} \mid u\text{ is a $d$-dimensional subword of }
\omega(v) \text{ with } v\in L\}
\subseteq \B^{*^d}
\end{equation*}

and the image of a subshift $X\subseteq\A^{\Z^d}$ under $\omega$
as the subshift

\begin{equation*}
\overline{\omega(X)}^{\sigma}
= \{\sigma^\bk\omega(x)\in\B^{\Z^d} \mid \bk\in\Z^d, x\in X\}
\subseteq \B^{\Z^d}.
\end{equation*}

The next lemma shows that the fact that a subshift is the image of another
subshift under a $d$-dimensional morphism can be restated equivalently in terms
of their languages.

Let $\omega:X\to Y$ be a $d$-dimensional morphism for some subshifts
$X\subseteq\A^{\Z^d}$ and $Y\subseteq\B^{\Z^d}$. The following conditions
are equivalent:

* $Y=\overline{\omega(X)}^{\sigma}$,

* $\L_Y=\overline{\omega(\L_X)}^{Fact}$.

(i) $\implies$ (ii)
By definition of $\omega$, we have $\omega(\L_X)\subseteq\L_Y$
and $\overline{\omega(\L_X)}^{Fact}\subseteq\L_Y$ since $\L_Y$ is a
factorial language.
Let $u\in\L_Y$, i.e.,
$u$ is a factor of some word $y\in Y$.
There exists $\bk\in\Z^d$ and $x\in X$ such that $y=\sigma^\bk\omega(x)$.
Therefore $u$ is a subword of $\omega(v)$ for some $v\in\L_X$
and we conclude $\L_Y \subseteq \overline{\omega(\L_X)}^{Fact}$.

(ii) $\implies$ (i)
We have $\omega(X)\subset Y$.
Since $Y$ is shift-invariant, we also have
$\overline{\omega(X)}^{\sigma}\subseteq Y$.
Let $y\in Y$. Thus $y$ is in the subshift generated by the language

Since $X$ is closed, there exists $x\in X$ and
$\bk\in\Z^d$ such that $y=\sigma^\bk\omega(x)$.

§.§ Self-similar subshifts

In this section we consider languages and subshifts defined from substitutions
leading to self-similar structures.
A subshift $X\subseteq\A^{\Z^d}$ (resp. a language $L\subseteq\A^{*^d}$)
is self-similar
if there exists an expansive
$d$-dimensional morphism $\omega:\A\to\A^{*^d}$ such that
(resp.  $L=\overline{\omega(L)}^{Fact}$).

Self-similar languages and subshifts can be constructed by iterative
application of the morphism $\omega$ starting with the letters.
The language $\L_\omega$ defined by an expansive $d$-dimensional
morphism $\omega:\A \to\A^{*^d}$ is

\begin{equation*}
\L_\omega = \{u\in\A^{*^d} \mid u\text{ is a $d$-dimensional subword of }
\omega^n(a) \text{ for some } a\in\A\text{ and } n\in\N \}.
\end{equation*}

It satisfies
and thus is self-similar.
The substitutive shift $\X_\omega=\X_{\L_\omega}$
defined from the language of $\omega$ is a self-similar subshift.
If $\omega$ is primitive then $\X_\omega$ is the smallest nonempty subshift
$X\subseteq\A^{\Z^d}$ satisfying $X=\overline{\omega(X)}^{\sigma}$.

In some references, the definition of self-similar is more restrictive.
For example, in <cit.>,
the definition of self-similarity for tilings of $\R^d$
would be restated in terms of tilings of $\Z^d$ as:
a subshift $X\subseteq\A^{\Z^d}$ is self-similar if there exists an
expansive $d$-dimensional morphism $\omega:\A\to\A^{*^d}$ such that $X =
\X_\omega$.
Observe that a nonempty subshift $X$ that satisfies
$X=\overline{\omega(X)}^{\sigma}$ for some expansive and primitive
$d$-dimensional morphism $\omega$ contains $\X_\omega$ but as illustrated
in the following example, it needs not be $\X_\omega$.

Consider the $1$-dimensional morphism $\mu:a\mapsto ca, b\mapsto bc, c\mapsto
cbac$ over the alphabet $\A=\{a,b,c\}$. It is expansive and primitive.
Consider the language

\[
L = \{u\in\A^{*^d} \mid u\text{ is a $d$-dimensional subword of }
\mu^n(ab) \text{ for some } n\in\N \}
\]

that satisfies $L\supseteq\L_\omega$ and
We have $ab\in L$ but $ab\notin\L_\omega$ thus $L\supsetneq\L_\omega$.

The next lemma shows that there is a unique language $L$ satisfying
and a unique subshift $X$ satisfying
whenever $\omega$ is primitive and
the words of shape $(2,\dots,2)$ of $L$
or of $\L_X$ are in $\L_\omega$.

Let $\omega:\A\to\A^{*^d}$ be an expansive and primitive $d$-dimensional
morphism. Let $L\subseteq\A^{*^d}$ be a $d$-dimensional language
such that $L=\overline{\omega(L)}^{Fact}$. Then $\L_\omega\subseteq L$ and
the following conditions are equivalent:

* $L=\L_\omega$,

* $\X_L$ is minimal,

* $\X_L=\X_\omega$,

* $L\cap\A^{(2,\dots,2)} = \L_\omega\cap\A^{(2,\dots,2)}$.

($\L_\omega\subseteq L$).
Notice that, recursively, $L=\overline{\omega^m(L)}^{Fact}$ for every $m\geq1$.  For every
$a\in\A$ and $m\geq1$, the $d$-dimensional word $\omega^m(a)$ is in the
language $L$.

(i) $\implies$ (ii).
We have that $\X_{\L_\omega}=\X_\omega$ is the substitutive shift of
$\omega$ which is minimal since $\omega$ is primitive.
(ii) $\implies$ (iii).
We know that $\L_\omega\subseteq L$.
Therefore $X_\omega\subseteq\X_L$.
Since $\X_L$ is minimal, we conclude that $X_\omega=\X_L$.
(iii) $\implies$ (iv).
If $X_\omega=\X_L$ then $L=\L_\omega$.
Therefore, $L\cap\A^{(2,\dots,2)} = \L_\omega\cap\A^{(2,\dots,2)}$.

(iv) $\implies$ (i).
Let $z\in L$. Since $\omega$ is expansive,
let $m\in\N$ such that the image of every letter
$a\in\A$ by $\omega^m$ is larger than $z$, that is,
$\shape(\omega^m(a))\geq\shape(z)$ for all $a\in\A$.
We have $z\in\overline{\omega^m(L)}^{Fact}$.
By the choice of $m$, $z$ can not overlap more than two block
$\omega^m(a)$ in the same direction. Then, there exists a word $u\in L$ of
shape $(2,\dots,2)$ such that $z$ is a subword of $\omega^m(u)$.
From the hypothesis, every word of shape $(2,\dots,2)$ that appear in $L$
also appear in $\L_\omega$. Therefore $u\in\L_\omega$.
Since $\omega$ is primitive, there exists $\ell$ such that every word $u$
of shape $(2,\dots,2)$ that appear in $\L_\omega$
is also a subword of $\omega^\ell(a)$ for every $a\in\A$.
Therefore, $z$ is a subword of $\omega^{m+\ell}(a)$ for every $a\in\A$.
Then $z\in\L_\omega$ and $L\subseteq\L_\omega$.

§.§ $d$-dimensional recognizability and aperiodicity

The definition of recognizability dates back to the work of Host, Quéffelec and
Mossé <cit.>. See also <cit.> who propose a
completion of the statement and proof for B. Mossé's unilateral recognizability
The definition introduced below is based on work of Berthé, Steiner and
Yassawi <cit.> on the recognizability in the case
of $S$-adic systems where more than one substitutions are involved.

Let $X\subseteq\A^{\Z^d}$ and
$\omega:X\to\B^{\Z^d}$ be a $d$-dimensional morphism.
If $y\in\overline{\omega(X)}^{\sigma}$, i.e.,
$y=\sigma^\bk\omega(x)$ for some $x\in X$ and $\bk\in\Z^d$, where $\sigma$ is
the $d$-dimensional shift map, we say that $(\bk,x)$ is a
$\omega$-representation of $y$. We say that it is centered if
$y_\zero$ lies inside of the image of $x_\zero$, i.e., if
$\zero\leq\bk<\shape(\omega(x_\zero))$ coordinate-wise.
We say that $\omega$ is recognizable in $X\subseteq\A^{\Z^d}$
if each $y\in\B^{\Z^d}$ has at most one centered $\omega$-representation
$(\bk,x)$ with $x\in X$.

The unique composition property and conditions <ref> and
<ref> can be stated in terms of subshifts, $d$-dimensional morphisms
and recognizability.

Let $\omega:\A\to\A^{*^d}$ be an expansive $d$-dimensional morphism.
Let $X\subseteq\A^{\Z^d}$ be a self-similar subshift such that
If $\omega$ is recognizable in $X$, then $X$ is aperiodic.

Suppose that there exists a periodic tiling $y\in X$ with
period $\bp\in\Z^d\setminus\{(0,0)\}$ satisfying $\sigma^\bp y=y$.
Since $\omega$ is expansive,
let $m\in\N$ such that the shape of the image of every letter
$a\in\A$ by $\omega^m$ is large enough, that is,
$\shape(\omega^m(a))\geq\bp$ for every
letter $a\in\A$.
By hypothesis,
every $y\in X$ has a $\omega$-representation.
Recursively, there
exists a $\omega^m$-representation $(\bk,x)$ of $y$ satisfying
We may assume that it is centered since $X$ is shift-invariant.
By definition of centered representation,
for every $\bu\in\Z^d$ such that $\zero\leq\bu<\shape(\omega^m(x_\zero))$,
$(\bu,x)$ is a centered $\omega^m$-representation of
By the choice of $m$, there exists $\bu\in\Z^d$ such that
$(\bu,x)$ is a centered $\omega^m$-representation of
$(\bu+\bp,x)$ is a centered $\omega^m$-representation of
=\sigma^{\bu-\bk}\sigma^\bp y
Therefore, $\omega^m$ is not recognizable
which implies that $\omega$ is not recognizable
which is a contradiction.
We conclude that there is no periodic tiling $y\in X$.

Note that the converse of
Proposition <ref> for tilings was proved
in <cit.> as a generalization of a result of Mossé <cit.>
who showed that recognizability and aperiodicity are equivalent for primitive
substitutive sequences.

Let $\omega:X\to Y$ be some $d$-dimensional morphism between two
subshifts $X$ and $Y$.

If $Y$ is aperiodic, then $X$ is aperiodic.

If $X$ contains a periodic tiling $x$, then
$\omega(x)\in Y$ is periodic.

§ A SUFFICIENT CONDITION FOR RECOGNIZABILITY AND SURJECTIVITY

The goal of this section is to show that under some hypothesis made on a Wang
tile set $\T$, namely the existence of markers, there exists another set $\S$
of Wang tiles and a nontrivial recognizable $2$-dimensional morphism
$\Omega_\S\to\Omega_\T$ that is onto up to a shift.  More precisely, every Wang
tiling by $\T$ is up to a shift the image under a nontrivial $2$-dimensional
morphism $\omega$ of a unique Wang tiling in $\Omega_\S$.

§.§ A sufficient condition for recognizability

The next lemma provides a sufficient condition for recognizability of
$d$-dimensional morphism. It is weak in the sense that it applies to morphism
whose images of letters are letters or a domino in a given direction, but it is
sufficient for our needs.

Let $d\geq1$ and $i$ such that $1\leq i\leq d$.
Let $X\subseteq\A^{\Z^d}$ and
$\omega:X\to\B^{\Z^d}$ be a $d$-dimensional morphism such that
the image of letters are letters or dominoes in the direction $\be_i$.
If $\omega|_\A$ is injective and there exists a subset $M\subset \B$ such that

\begin{equation}\label{eq:markers-on-right}
\omega(\A)
\subseteq (\B\setminus M)
\cup \left((\B\setminus M)\odot^i M\right),
\end{equation}

\begin{equation}\label{eq:markers-on-left}
\omega(\A)
\subseteq (\B\setminus M)
\cup \left(M\odot^i (\B\setminus M)\right),
\end{equation}

then $\omega$ is recognizable in $X$.

Informally, the letters $m\in M$ have the role of markers: when we see
them in the image under $\omega$, we know that they must appear as the left
(resp. right) part of a domino.
A formal definition of markers is given in the next section
(Definition <ref>).

Let $(\bk,x)$ and $(\bk',x')$ be two
centered $\omega$-representations of $y\in\B^{\Z^d}$ with
$\bk,\bk'\in\Z^d$ and $x,x'\in X$.
We want to show that they are equal.

Since the image of a letter under $\omega$ is a letter or a domino in the
direction $\be_i$, then $\bk,\bk'\in\{\zero,\be_i\}$.
If $y_\zero\in M$, then $y_\zero$ appears as the left or right part of a
domino and thus $\bk=\bk'=\be_i$
if Equation (<ref>) holds
or $\bk=\bk'=\zero$
if Equation (<ref>) holds.

Suppose now that $y_\zero\in \B\setminus M$.
If Equation (<ref>) holds,
then $\bk=\bk'=\zero$.
Suppose that Equation (<ref>) holds.
By contradiction, suppose that $\bk\neq\bk'$
and assume without lost of generality that
$\bk=\zero$ and $\bk'=\be_i$.
This means that $\omega(x'_\zero)=y_{-\be_i} \odot^i y_\zero$ is
a domino in the direction $\be_i$.
Since $y_\zero\in \B\setminus M$, we must have that $y_{-\be_i}\in M$
is a left marker.
This is impossible as
$\omega(x_{-\be_i})=y_{-\be_i}\in \B\setminus M$
$\omega(x_{-\be_i})=y_{-2\be_i} \odot^i y_{-\be_i}
\in M\odot^i (\B\setminus M)$.
Therefore, we must have $\bk=\bk'$ and

Suppose by contradiction that $x\neq x'$.
Let $\ba=(a_1,\dots,a_d)\in\Z^d$ be some minimal vector with respect to
$\Vert\ba\Vert_\infty$ such that $x_\ba\neq x'_\ba$.
Injectivity of $\omega$ implies that $\omega(x_\ba)$ and
$\omega(x'_\ba)$ must have different shapes.
Suppose without lost of generality that
$\omega(x_\ba)\in\B $ and
$\omega(x'_\ba)=b\odot^i c\in\B\odot^i\B$.
We need to consider two cases: $a_i\geq 0$ and $a_i<0$.

Suppose $a_i\geq 0$.
We must have that Equation (<ref>) holds.
We have $\omega(x_\ba)=b\in\B\setminus M$ and $c\in M$.
But then $\omega(x_{\ba+\be_i})=c$
or $\omega(x_{\ba+\be_i})=c\odot^i d$ for some
$c\in\B\setminus M$ and $d\in\B$ which is a contradiction.

Suppose $a_i<0$.
We must have that Equation (<ref>) holds.
We have $\omega(x_\ba)=c\in\B\setminus M$ and $b\in M$.
But then $\omega(x_{\ba-\be_i})=b$
or $\omega(x_{\ba+\be_i})=d\odot^i b$ for some
$b\in\B\setminus M$ and
$d\in\B$ which is a contradiction.
We conclude that $x=x'$.

§.§ A sufficient condition for surjectivity up to a shift

Theorem <ref> is the key result in this contribution
since it is used in Section <ref> to desubstitute tilings
in $\Omega_\U$
into tilings in $\Omega_\V$ for some Wang tile set $\V$
and in
Section <ref> to desubstitute tilings of $\Omega_\V$
into tilings in $\Omega_\W$ for some Wang tile set $\W$.
It can be seen as a $2$-dimensional generalization of the notion of derived
sequence introduced in <cit.> for the $1$-dimensional substitutive
case. While for the $1$-dimensional substitutive
case the derived sequence is obtained by
considering the return words to a single letter, here it gives sufficient
condition for the existence of a derived tiling by considering the return
words to a subset of letters $\T\setminus M$ for some

Let $\T$ be a Wang tile set
and let $\Omega_\T$ be its Wang shift.
A nonempty proper subset $M\subset\T$ is called markers in the
direction $\be_1$ if

\begin{equation}
M\odot^1 M, \qquad
M\odot^2 (\T\setminus M), \qquad
(\T\setminus M) \odot^2 M
\end{equation}

are forbidden in $\Omega_\T$.
It is called markers in the direction $\be_2$ if

\begin{equation}
M\odot^2 M, \qquad
M\odot^1 (\T\setminus M), \qquad
(\T\setminus M) \odot^1 M
\end{equation}

are forbidden in $\Omega_\T$.

The markers in the direction $\be_1$ (resp. $\be_2$) appear as nonadjacent
columns (resp. rows) of tiles in a tiling.
The existence of markers allows to desubstitute tilings uniquely by
$2$-dimensional morphism that are essentially $1$-dimensional.

Let $\T$ be a Wang tile set
and let $\Omega_\T$ be its Wang shift.
If there exists a subset
of markers in the direction
then there exists
a Wang tile set $\S$
and a $2$-dimensional morphism
such that

\begin{equation}
\omega(\S)\subseteq (\T\setminus M)\cup
\left((\T\setminus M)\odot^i M\right)
\end{equation}

which is recognizable in the Wang shift $\Omega_\S$
and surjective up to a shift, i.e.,

For every $r\in\N$, we define the set of dominoes in the direction
$\be_i$ that admits a surrounding of radius $r$ in $\Omega_\T$:

\[
= \left\{u\odot^i v \,\middle|\, u\odot^iv \text{ admits a surrounding
of radius $r$ in } \Omega_\T\right\}.
\]

Notice that since $M$ is a set of markers, there exists $r\in\N$ such that
$D_{\T,\be_i,r}\cap(M\odot^i M)=\varnothing$.
Now let $r\in\N$ be any nonnegative integer and
let $P_r$, $K_r$ be the following sets:

\begin{align*}
P_r &= \left\{u\boxminus^i v \,\middle|\,
u\in\T\setminus M, v\in M
\text{ and }
u\odot^i v \in D_{\T,\be_i,r}\right\},\\
K_r &= \left\{u\in\T\setminus M\,\middle|\, \text{ there exists }
M \text{ such that } u\odot^iv \in D_{\T,\be_i,r}\right\}.
\end{align*}

Let $\S=K_r\cup P_r$ be a Wang tile set
and $\Omega_\S$ be its Wang shift.
Let $\omega:\Omega_\S\to\Omega_\T$ be the $2$-dimensional morphism
defined by

\begin{equation}\label{eq:omegaStoT}
\omega:
\begin{cases}
u\boxminus^i v
\quad \mapsto \quad
u\odot^i v
& \text{ if }
u\boxminus^i v \in P_r,\\
u \quad \mapsto \quad
u & \text{ if } u \in K_r.
\end{cases}
\end{equation}

From now on, we suppose that the markers $M$ are in the direction
$\be_i=\be_1$, the argument being symmetric for $i=2$.
First we show that $\omega$ is well-defined.
Let $x\in\Omega_\S$ be a Wang tiling.
We show that $\omega(x)$ is a valid Wang tiling.
It is sufficient to prove it for all dominoes $p\odot^jq$ that appear in
$\omega(x)$ with $p,q\in\T$ and $j\in\{1,2\}$.
Any domino $p\odot^jq$ that appears in $\omega(x)$ appears in the
image under $\omega$ of a letter or
of a domino in $x$.
The first case can happen only if $j=1$ and
there exists $u\boxminus^1v\in P_r$ such that
$p\odot^1q=u\odot^1v=\omega(u\boxminus^1v)$, in which case
the right color of $p$ is equal to the left color of $q$ since
In the second case, $p$ and $q$ belong to the image of distinct letters.
The case $j=1$ (horizontal dominoes) is easy since
$\omega$ preserve the right and left colors of
tiles, i.e., $r(\omega(s))=r(s)$
and $\ell(\omega(s))=\ell(s)$ for all $s\in\S$
so that $r(p)=\ell(q)$.
Consider now $j=2$ (vertical dominoes).
Any vertical domino $p\odot^2q$ that appears in $\omega(x)$ appears in the
image under $\omega$ of a vertical domino $p'\odot^2q'$ in $x$.
There are two cases to consider.
If $p',q'\in K_r$, then
If $p',q'\in P_r$,
then there exists $a,b,c,d\in\T$ such that
$p\odot^2q$ appears in $(a\odot^1b)\odot^2(c\odot^1d)=\omega(p'\odot^2q')$.

\[
(t(a),t(b)) =
t(a\odot^1b) =
=(b(c), b(d)).
\]

Then $t(a)=b(c)$ and $t(b)=b(d)$
from which we conclude that $t(p)=b(q)$.
Therefore $\omega(x)$ is a valid Wang tiling of the plane and belongs to

Now we show that $\omega$ is surjective up to a shift.
Let $y\in\Omega_\T$ be a Wang tiling which can be seen as a function
Consider the set $y^{-1}(M)\subset\Z^2$ of positions of marker tiles
in $y$. From the definition of markers in the direction $\be_i=\be_1$,
markers appear in nonadjacent columns in a tiling.
Formally, there exists
a set $H\subset\Z$ such that $y^{-1}(M)=H\times\Z$ and
$1\notin H-H$.
Since $1\notin H-H$, there exists a strictly increasing sequence
$(a_k)_{k\in\Z}$ such that $\Z\setminus H=\{a_k\mid k\in\Z\}$.
We assume that $a_0=0$ if $0\in\Z\setminus H$ and $a_0=-1$ if $0\in H$
which makes the sequence $(a_k)_{k\in\Z}$ uniquely defined.

\begin{equation*}
\begin{array}{rccl}
x:&\Z^2 & \to & \S\\
&(k,\ell) & \mapsto &
\begin{cases}
y(a_k,\ell)                          & \text{ if } a_k+1\notin H,\\
y(a_k,\ell)\boxminus^1 y(a_k+1,\ell) & \text{ if } a_k+1\in H.
\end{cases}
\end{array}
\end{equation*}

The function $x$ is well-defined since $x(k,\ell)\in\S$ for all
Indeed, if $a_k+1\notin H$, then $x(k,\ell)= y(a_k,\ell)\in\T\setminus M$.
Also $y(a_k+1,\ell)\in\T\setminus M$.
Since $y$ is a valid Wang tiling $y(a_k,\ell)\odot^1 y(a_k+1,\ell)$ admits
arbitrarily large surrounding in $\Omega_\T$.
Therefore, $x(k,\ell)=y(a_k,\ell)\in K_\infty\subseteq K_r\subset\S$.
Suppose now that $a_k+1\in H$.
Then $x(k,\ell)=y(a_k,\ell)\boxminus^1 y(a_k+1,\ell)\in(\T\setminus
M)\boxminus^1 M$.
Since $y$ is a valid Wang tiling $x(k,\ell)\in P_\infty\subseteq
Moreover, we deduce that $x\in\Omega_\S$, that is it is a valid Wang tiling
of the plane, from the fact that $y\in\Omega_\T$ is a valid Wang tiling of
the plane.

We may now finish the proof of surjectivity.
If $0\notin H$,
then the tiling $y$ is exactly the image under $\omega$ of the tiling $x$ that
we constructed: $y=\omega(x)$.
If $0\in H$, then
the tiling $y$ is a shift of the image under $\omega$ of the tiling $x$:
Thus $\omega$ is surjective up to a shift.

The function $\omega$ is of the form

\begin{equation*}
\omega(\S)
\subseteq (\T\setminus M)
\cup \left((\T\setminus M)\odot^1 M\right)
\end{equation*}

and its restriction on $\S$ is injective by construction.
Therefore, we conclude from Lemma <ref> that
$\omega$ is recognizable in $\Omega_\S$.

In Equation (<ref>), given two Wang tiles $u$ and $v$ such that
$u\boxminus^i v$ is well-defined for $i\in\{1,2\}$, we consider a
$2$-dimensional morphism of the form

\begin{equation*}
u\boxminus^i v
\quad
\mapsto
\quad
u\odot^i v
\end{equation*}

which can be seen as

(0, 0) – (1, 0);
(0, 0) – (0, 1);
(1, 1) – (1, 0);
(1, 1) – (0, 1);
[rotate=0,font=] at (0.8, 0.5) Z;
[rotate=0,font=] at (0.5, 0.8) BD;
[rotate=0,font=] at (0.2, 0.5) X;
[rotate=0,font=] at (0.5, 0.2) AC;
at (1.5,.5) $\mapsto$;
at (3.0,0.5) [scale=0.900000000000000]

(0, 0) – (1, 0);
(0, 0) – (0, 1);
(1, 1) – (1, 0);
(1, 1) – (0, 1);
[rotate=0,font=] at (0.8, 0.5) Y;
[rotate=0,font=] at (0.5, 0.8) B;
[rotate=0,font=] at (0.2, 0.5) X;
[rotate=0,font=] at (0.5, 0.2) A;

(1, 0) – (2, 0);
(1, 0) – (1, 1);
(2, 1) – (2, 0);
(2, 1) – (1, 1);
[rotate=0,font=] at (1.8, 0.5) Z;
[rotate=0,font=] at (1.5, 0.8) D;
[rotate=0,font=] at (1.2, 0.5) Y;
[rotate=0,font=] at (1.5, 0.2) C;

5mm or

(0, 0) – (1, 0);
(0, 0) – (0, 1);
(1, 1) – (1, 0);
(1, 1) – (0, 1);
[rotate=90,font=] at (0.8, 0.5) YZ;
[rotate=0,font=] at (0.5, 0.8) D;
[rotate=90,font=] at (0.2, 0.5) XW;
[rotate=0,font=] at (0.5, 0.2) A;
at (1.5,.5) $\mapsto$;
at (2.5,0.5) [scale=0.900000000000000]

(0, 0) – (1, 0);
(0, 0) – (0, 1);
(1, 1) – (1, 0);
(1, 1) – (0, 1);
[rotate=0,font=] at (0.8, 0.5) Y;
[rotate=0,font=] at (0.5, 0.8) B;
[rotate=0,font=] at (0.2, 0.5) X;
[rotate=0,font=] at (0.5, 0.2) A;

(0, 1) – (1, 1);
(0, 1) – (0, 2);
(1, 2) – (1, 1);
(1, 2) – (0, 2);
[rotate=0,font=] at (0.8, 1.5) Z;
[rotate=0,font=] at (0.5, 1.8) D;
[rotate=0,font=] at (0.2, 1.5) W;
[rotate=0,font=] at (0.5, 1.2) B;

whether $i=1$ or $i=2$.

In Equation (<ref>), the set $P_r$
can be computed with the help of transducers since
the fusion operation $\boxminus^i$ on Wang tiles can be seen as the product of
transducers (see Equation (<ref>)).
The algorithmic aspects of Theorem <ref>
will be considered in a forthcoming work <cit.>.

The existence of a $2$-dimensional morphism $\omega:\Omega_\S\to\Omega_\T$
which is recognizable in the Wang shift $\Omega_\S$ and
surjective up to a shift implies the existence of a
homeomorphism between $\Omega_\S$ and $\Omega_\T$ where each tile
have specific real width and height and tilings are defined in $\R^2$
rather than in $\Z^2$.
We have chosen in this contribution the point of view of tilings of $\Z^2$
which makes some aspects look easier and other more intricate.

§ DESUBSTITUTION OF $\OMEGA_\U$

In this section, we prove that tilings in $\Omega_\U$ can be desubstituted
uniquely into tilings of $\Z^2$ over another set $\V$ of Wang tiles. The proof
follows from the computation of the set of vertical dominoes appearing in
$\Omega_\U$ (Lemma <ref>) whose proof is done with

The tile set $\U$ seen in Figure <ref> is defined over an
$\{A, B, C, D, E, F, G, H, I, J\}$
of 10 vertical colors
and an alphabet
$\{K, L, M, N, O, P\}$
of 6 horizontal colors.
We identify each tile $u_i$ in $\U$ with an index $i\in\{0,\dots,18\}$ in the
following way and we draw this index in the center of each tile to ease their

\begin{equation*}
\begin{array}{l}
\U= \left\{
\right.\\
\hspace{0mm}\left.
\right.\\
\hspace{5mm}\left.
\right\}.
\end{array}
\end{equation*}

The transducer representation of the tile set $\U$
was shown in Figure <ref>.

The set of dominoes in direction $\be_2$ allowing a surrounding of radius 2
in $\Omega_\U$ is

\begin{align*}
D_{\U,\be_2,2} &= \input{article1_U_dominoes_2_radius_2.tex}.
\end{align*}

The proof of Lemma <ref> is done with Sage
in Section <ref>.

The set
$R = \{u_0, u_1, u_2, u_3, u_4, u_5, u_6, u_7\}$
is a set of markers in the direction $\be_2$ for $\U$.

First we show that $R\odot^2 R$ is forbidden in $\Omega_\U$.
The language of dominoes in direction $\be_2$ in $\Omega_\U$ is a subset
of the set of dominoes in direction $\be_2$ allowing a surrounding of
radius 2 in $\Omega_\U$:

\[
\left\{(u,v)\in\U^2\mid u\odot^2v\in\L(\Omega_\U)\right\}
\subseteq D_{\U,\be_2,2}
\]

computed in Lemma <ref>.
Since $D_{\U,\be_2,2}\cap R^2=\varnothing$, we deduce that
$(R\odot^2 R)\cap\L(\Omega_\U)=\varnothing$, that is
$R\odot^2 R$ is forbidden in $\Omega_\U$.

Finally, we remark that

\begin{align*}
\scleft(\U\setminus R)&=\scright(\U\setminus R) = \{A,B,C,E,G,I\},\\
\scleft(R)&=\scright(R) = \{D,F,H,J\},
\end{align*}

which are disjoint.
$R\odot^1 (\U\setminus R)$ and
$(\U\setminus R)\odot^1 R$
are forbidden in $\Omega_\U$.
We conclude that $R$
is a set of markers in the direction $\be_2$ for $\U$.

The morphism $\alpha:\Omega_\V\to\Omega_\U$.

There exists a tile set $\V$ of cardinality 21 and
a $d$-dimensional morphism $\alpha:\Omega_\V\to\Omega_\U$
that is recognizable in $\Omega_\V$
and $\alpha(\Omega_\V)\cup\sigma^{\be_2}\alpha(\Omega_\V)=\Omega_\U$.

From Lemma <ref>,
$R = \{u_0, u_1, u_2, u_3, u_4, u_5, u_6, u_7\}$
is a set of markers in the direction $\be_2$ for $\U$.
Therefore, Theorem <ref> applies.
Let $P_2$ be the set

\begin{align*}
P_2 &= \left\{u\boxminus^2 v \,\middle|\,
u\in\U\setminus R, v\in R
\text{ and }
(u,v) \in D_{\U,\be_2,2}\right\}\\
&= \input{article1_set_P_for_tiles_U.tex}
\end{align*}

according to Lemma <ref>.
Let $K_2$ be the set

\begin{align*}
K_2 &= \left\{u\in\U\setminus R\,\middle|\, \text{ there exists }
R \text{ such that } (u,v) \in D_{\U,\be_2,2}\right\}\\
&= \{u_8, u_9, u_{11}, u_{13}, u_{14}, u_{15}, u_{16}, u_{17}\}.
\end{align*}

Let $\Omega_\V$ be the Wang shift of the Wang tile set $\V=K_2\cup
P_2$ of cardinality 21:

\begin{equation*}\label{eq:tilesV}
\begin{array}{c}
\V= \left\{
\right.\\
\hspace{1cm}\left.
\right.\\
\hspace{1cm}\left.
\right\}.
\end{array}
\end{equation*}

Let $\alpha:\Omega_\V\to\Omega_\U$ be the $2$-dimensional morphism
defined by

\begin{equation*}
\alpha:
\begin{cases}
u\boxminus^2 v
\quad \mapsto \quad
u\odot^2 v
& \text{ if }
u\boxminus^2 v \in P_2\\
k \quad \mapsto \quad
k & \text{ if } k \in K_2.
\end{cases}
\end{equation*}

Then $\alpha:\Omega_\V\to\Omega_\U$ is
recognizable in $\Omega_\V$
and $\alpha(\Omega_\V)\cup\sigma^{\be_2}\alpha(\Omega_\V)=\Omega_\U$.

The morphism $\alpha$ in terms of the
$\U=\{u_i\}_{0\leq i\leq 18}$ and $\V=\{v_i\}_{0\leq i\leq 20}$
is in Figure <ref>.
The tile set $\V$ uses the
following alphabet of 13 vertical colors:

\begin{equation*}
\{A, B, E, G, I, AF, BF, CH, EH, GF, ID, IH, IJ\}
\end{equation*}

and the following alphabet of 5 horizontal colors:

\begin{equation*}
\{K, L, M, O, P\}.
\end{equation*}

Notice that the set of vertical left and right colors has increased in size
compared to $\U$ and that the set of horizontal bottom and top colors
has decreased in size. Indeed, color N has disappeared.

§ DESUBSTITUTION OF $\OMEGA_\V$

In this section, we prove that tilings in $\Omega_\V$ can be desubstituted
uniquely into tilings of $\Z^2$ over another set $\W$ of Wang tiles. The proof
follows from the computation of the set of horizontal dominoes appearing in
$\Omega_\V$ (Lemma <ref>) whose proof is done with

The set of dominoes in direction $\be_1$ allowing a surrounding of radius 1
in $\Omega_\V$ is

\begin{align*}
D_{\V,\be_1,1} &= \input{article1_V_dominoes_1_radius_1.tex}.
\end{align*}

The proof of Lemma <ref> is done with Sage
in Section <ref>.

The set
$R = \{v_0, v_1, v_3, v_8, v_9, v_{14}, v_{15}\}$
is a set of markers in the direction $\be_1$ for $\V$.

First we show that $R\odot^1 R$ is forbidden in $\Omega_\V$.
The language of dominoes in direction $\be_1$ in $\Omega_\V$ is a subset
of the set of dominoes in direction $\be_1$ allowing a surrounding of
radius 1 in $\Omega_\V$:

\[
\left\{(u,v)\in\V^2\mid u\odot^1v\in\L(\Omega_\V)\right\}
\subseteq D_{\V,\be_1,1}
\]

computed in Lemma <ref>.
Since $D_{\V,\be_1,1}\cap R^2=\varnothing$, we deduce that
$(R\odot^1 R)\cap\L(\Omega_\V)=\varnothing$, that is
$R\odot^1 R$ is forbidden in $\Omega_\V$.

Finally, we remark that

\begin{align*}
\scbottom(\V\setminus R) &= \sctop(\V\setminus R) = \{K,M,P\},\\
\scbottom(R) &= \sctop(R) = \{L,O\},
\end{align*}

which are disjoint.
$R\odot^2 (\V\setminus R)$ and
$(\V\setminus R)\odot^2 R$
are forbidden in $\Omega_\V$.
We conclude that $R$
is a set of markers in the direction $\be_1$ for $\V$.

The morphism $\beta:\Omega_\W\to\Omega_\V$.

There exists a tile set $\W$ of cardinality 19 and
a $d$-dimensional morphism $\beta:\Omega_\W\to\Omega_\V$
that is recognizable in $\Omega_\W$
and $\beta(\Omega_\W)\cup\sigma^{\be_1}\beta(\Omega_\W)=\Omega_\V$.

From Lemma <ref>,
$R = \{v_0, v_1, v_3, v_8, v_9, v_{14}, v_{15}\}$
is a set of markers in the direction $\be_1$ for $\V$.
Therefore, Theorem <ref> applies.
Let $P_1$ be the set

\begin{align*}
P_1 &= \left\{u\boxminus^1 v \mid
u\in\V\setminus R, v\in R
\text{ and }
u\odot^1v \in D_{\V,\be_1,1}
\right\}\\
&=\left\{ \begin{array}{l}
\input{article1_set_P_for_tiles_V.tex}
\end{array} \right\}
\end{align*}

according to Lemma <ref>.
Let $K_1$ be the set

\begin{align*}
K_1 &= \left\{u\in\V\setminus R\mid \text{ there exists } v\in\V\setminus
R \text{ such that } (u,v) \in D_{\V,\be_1,1}\right\}\\
&= \{u_8, u_9, u_{11}, u_{13}, u_{14}, u_{15}, u_{16}, u_{17}\}.
\end{align*}

Let $\Omega_\W$ be the Wang shift of the Wang tile set $\W=K_1\cup P_1$
of cardinality 19:

\begin{equation*}\label{eq:tiles9}
\begin{array}{c}
\W= \left\{
\right.\\
\hspace{1cm}\left.
\right.\\
\hspace{1cm}\left.
\right\}.
\end{array}
\end{equation*}

Let $\beta:\Omega_\W\to\Omega_\V$ be the $2$-dimensional morphism
defined by

\begin{equation*}
\beta:
\begin{cases}
u\boxminus^1 v
\quad \mapsto \quad
u\odot^1 v
& \text{ if }
u\boxminus^1 v \in P_1\\
k \quad \mapsto \quad
k & \text{ if } k \in K_1.
\end{cases}
\end{equation*}

Then $\beta:\Omega_\W\to\Omega_\V$
is recognizable in $\Omega_\W$
and $\beta(\Omega_\W)\cup\sigma^{\be_1}\beta(\Omega_\W)=\Omega_\V$.

The morphism $\beta$ in terms of the
$\V=\{v_i\}_{0\leq i\leq 20}$ and $\W=\{w_i\}_{0\leq i\leq 18}$
is in Figure <ref>.
The tile set $\W$ uses the
following alphabet of 10 vertical colors:

\begin{equation*}
\{A, B, G, I, AF, BF, GF, ID, IH, IJ\}
\end{equation*}

and the following alphabet of 6 horizontal colors:

\begin{equation*}
\{K, M, KO, MO, PL, PO\}.
\end{equation*}

Notice that the set of horizontal left and right colors has increased in size
compared to $\V$ and that the set of vertical bottom and top colors
has decreased in size. Indeed, colors E, CH and EH have disappeared.

§ SELF-SIMILARITY AND APERIODICITY OF $\OMEGA_\U$

Let $\gamma:\U\to\W$ be the map defined
by the rule $u_i\mapsto w_i$ for every $i\in\{0,1,\dots,18\}$.
On tiles, the effect is shown below where the position of tile $u_i$ in the
table on the left is the same as the position of the tile $w_i$
in the table on the right:

\begin{equation*}
\gamma:
\left\{
\arraycolsep=.5pt
\begin{array}{ccccc}
\raisebox{-3mm}{\UTileO}
\\
\raisebox{-3mm}{\UTileV}
\\
\raisebox{-3mm}{\UTileX}
\\
\raisebox{-3mm}{\UTileXV}
\end{array}
\mapsto
\begin{array}{ccccc}
\raisebox{-3mm}{\WTileO}
\\
\raisebox{-3mm}{\WTileV}
\\
\raisebox{-3mm}{\WTileX}
\\
\raisebox{-3mm}{\WTileXV}
\end{array}
\right.
\end{equation*}

$\U$ and $\W$ are equivalent Wang tile sets.
The map $\gamma:\U\to\W$ defines a
$d$-dimensional morphism $\gamma:\Omega_\U\to\Omega_\W$
which is a bijection.

We consider the following bijection between the colors of $\U$
and the colors of $\W$:

\[
\left\{
\begin{array}{ll}
O\mapsto K& P\mapsto KO\\
L\mapsto M& N\mapsto MO\\
& M\mapsto PL\\
& K\mapsto PO\\
\end{array}\right.,
\qquad
\left\{
\begin{array}{ll}
J\mapsto A&E\mapsto AF\\
H\mapsto B&C\mapsto BF\\
D\mapsto G&I\mapsto GF\\
F\mapsto I&G\mapsto ID\\
&B\mapsto IH\\
&A\mapsto IJ\\
\end{array}\right.,
\]

where $h$ relabels the horizontal (bottom and top) colors
where $k$ relabels the vertical (left and right) colors.
For every $i$ in $\{0,1,\ldots, 18\}$, we observe
that the application of the map $h$
on the bottom and left colors
and $k$ on the left and right colors
transforms bijectively $u_i$ into $w_i$:

\[
\gamma(\U)
= \{(k(a),h(b),k(c),h(d))\mid(a,b,c,d)\in\U\}
= \W.
\]

Thus $\gamma$ is a bijection and $\U$ and $\W$ are equivalent Wang tile sets.

Consider the $d$-dimensional morphism
$\omega:\Omega_\U\to\Omega_\U$ defined as
$\omega=\alpha\circ\beta\circ\gamma$ shown in Figure <ref>.

The morphism $\omega:\Omega_\U\to\Omega_\U$.
The image of each tile $\omega(u_i)$ corresponds to the supertiles
shown in Figure <ref>.

The morphism $\omega$ is primitive.
The characteristic polynomial of its incidence matrix $M$ is

\[
\chi_M(x) = x^{3} \cdot (x - 1)^{4} \cdot (x + 1)^{4} \cdot (x^{2} - 3x +
1) \cdot (x^{2} + x - 1)^{3}.
\]

The dominant eigenvalue is
The associated positive right eigenvector is

\[
\left(1, 3\varphi^3, \varphi^2, \varphi^3, \varphi, \varphi^2, \varphi^4,
\varphi^3, \varphi^4, 2\varphi^3, \varphi^2, \varphi^3, \varphi,
\varphi^4, \varphi^4+\varphi^2, \varphi^3, \varphi^4, \varphi^3, \varphi^2
\right)^t
\]

and associated positive left eigenvector is

\[
\left(1, 1,
\varphi, \varphi, \varphi, \varphi, \varphi, \varphi, \varphi, \varphi, \varphi, \varphi,
\varphi^2, \varphi^2, \varphi^2, \varphi^2, \varphi^2, \varphi^2, \varphi^2\right).
\]

The incidence matrix $M$ of $\omega$ is

\begin{equation*}
\left(\begin{array}{rrrrrrrrrrrrrrrrrrr}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0
\end{array}\right)
\end{equation*}

whose $7$-th power $M^7$ is positive. Therefore $M$ is a primitive matrix
and the morphism is primitive.
The computation of characteristic polynomial, eigenvalues and eigenvectors of $M$ is done using Sage
in Section <ref>.

We now prove the main result using the composition-decomposition approach.
Informally, the morphism $\alpha\beta:\Omega_\W\to\Omega_\U$ allows to group
tiles in any tilings admitted by $\U$ in a unique way into supertiles of the
form $\alpha\beta(w_i)$ for $i\in\{0,1,\dots,18\}$, thus satisfying condition
The morphism $\gamma:\Omega_\U\to\Omega_\W$ implies that
the markings on the supertiles $\W$
imply a matching condition for the supertiles which is exactly equivalent to
that originally specified for the tiles $\U$, thus satisfying condition

The $d$-dimensional morphism
$\omega:\Omega_\U\to\Omega_\U$ defined as
$\omega=\alpha\circ\beta\circ\gamma$ is
expansive, recognizable in $\Omega_\U$
and satisfies

\begin{equation}\label{eq:omega-is-kinda-onto}
\Omega_\U = \omega(\Omega_\U)
\cup\sigma^{\be_1}\omega(\Omega_\U)
\cup\sigma^{\be_2}\omega(\Omega_\U)
\cup\sigma^{\be_1+\be_2}\omega(\Omega_\U).
\end{equation}

From Proposition <ref>,
Proposition <ref> and
Lemma <ref>,
we have the sequence of recognizable $2$-dimensional morphisms:

\[
\Omega_\U
\xleftarrow{\alpha}
\Omega_\V
\xleftarrow{\beta}
\Omega_\W
\xleftarrow{\gamma}
\Omega_\U.
\]

and the equations
Consider the $d$-dimensional morphism $\omega=\alpha\beta\gamma$ which
is recognizable in $\Omega_\U$.
Since $\alpha\sigma^{\be_1}= \sigma^{\be_1}\alpha$, we deduce Equation
As shown in  Lemma <ref>, $\omega$ is primitive
and sends at least one letter to a $2$-dimensional word of shape $(2,2)$.
Thus it is expansive.

We can now prove the aperiodicity of $\U$ from the
recognizability of $\omega$.

$\Omega_\U$ is self-similar and aperiodic.

From Proposition <ref>, $\omega$ is expansive and
recognizable in $\Omega_\U$.
By taking the closure under the shift $\sigma$ on both sides of
Equation (<ref>), we deduce that
Thus $\Omega_\U$ is self-similar.

We conclude aperiodicity of $\Omega_\U$ from
Proposition <ref>.

The next lemma shows that the subwords of shape $(2,2)$ in
$\Omega_\U$ and $\X_\omega$ are the same.

We have
$\L(\X_\omega)\cap \U^{(2,2)} = \L(\Omega_\U)\cap \U^{(2,2)}=S$
where $S$ is

\begin{equation*}\arraycolsep=1pt
\input{article1_all_2x2_factors.tex}
\end{equation*}

The proof of Lemma <ref> is done using Sage
in Section <ref>.

$\Omega_\U$ is minimal. More precisely,
$\Omega_\U=\X_\omega$ where $\omega=\alpha\beta\gamma$.

From Corollary <ref>,
we have
From Lemma <ref>,
this is equivalent to $\L(\Omega_\U) = \overline{\omega(\L(\Omega_\U))}^{Fact}$.
From Lemma <ref>
we have
$\L(\X_\omega)\cap \U^{(2,2)} = \L(\Omega_\U)\cap \U^{(2,2)} $.
From Lemma <ref>
and Proposition <ref>, $\omega$ is primitive and expansive.
From Lemma <ref>,
we conclude that $\L(\X_\omega) = \L(\Omega_\U)$,
$\X_\omega= \Omega_\U$
and $\Omega_\U$ is minimal.

It is proved that $\U$ is self-similar and aperiodic in
Corollary <ref> and
that $\Omega_\U$ is minimal in
Proposition <ref>.

We deduce also that $\V$ is aperiodic from
Lemma <ref> since $\alpha$ sends periodic
tilings onto periodic tilings.

The vector of frequency of the tiles $\{u_i\}_{0\leq i\leq 18}$ in
any tiling of plane by $\U$ is

\[
\frac{1}{2}
\left(
\frac{1}{\varphi^8},
\frac{3}{\varphi^5},
\frac{1}{\varphi^6},
\frac{1}{\varphi^5},
\frac{1}{\varphi^7},
\frac{1}{\varphi^6},
\frac{1}{\varphi^4},
\frac{1}{\varphi^5},
\frac{1}{\varphi^4},
\frac{2}{\varphi^5},
\frac{1}{\varphi^6},
\frac{1}{\varphi^5},
\frac{1}{\varphi^7},
\frac{1}{\varphi^4},
\frac{1}{\varphi^4}+\frac{1}{\varphi^6},
\frac{1}{\varphi^5},
\frac{1}{\varphi^4},
\frac{1}{\varphi^5},
\frac{1}{\varphi^6}\right)^t.
\]

\[
\frac{1}{2\varphi^4}\approx
\frac{1}{2\varphi^5}\approx
\frac{1}{2\varphi^6}\approx
\frac{1}{2\varphi^7}\approx
\frac{1}{2\varphi^8}\approx
\]

\[
\frac{2}{2\varphi^5}\approx
\frac{3}{2\varphi^5}\approx
\frac{1}{2\varphi^4}+\frac{1}{2\varphi^6}\approx
\]

The sum of the values of the right eigenvector given in Lemma <ref>
is $2\varphi^8=42\varphi+26$.
Therefore, the frequency vector is $\frac{1}{2\varphi^8}$ times the right eigenvector.

We remark that the morphism $\omega$ on $\U$ is not
prolongable on any Wang tile but its square $\omega^2$ is prolongable on
many of them (see Figure <ref>).

The gray background color identify tiles where the morphism
$\omega^2:\Omega_\U\to\Omega_\U$ is prolongable on the initial tile

§ A STONE INFLATION

In this short section, we illustrate how the substitution $\omega$ can be seen
as a stone inflation <cit.>.
We consider the following correspondence between colors of the tile set $\U$
and length of edges:

\begin{align*}
&\{A,B,C,E,G,I\} &\mapsto &&\text{ vertical edge of length } 1\\
&\{D,F,H,J\}     &\mapsto &&\text{ vertical edge of length } \varphi^{-1}\\
&\{K,M,N,P\} &\mapsto &&\text{ horizontal edge of length } 1\\
&\{L,O\}     &\mapsto &&\text{ horizontal edge of length }\varphi^{-1}
\end{align*}

To each tile in $\U$ we associate a rectangle $\subset\R^2$ according to the rule

\[
\textsc{rectangle}(u_i) =
\begin{cases}
[0,\varphi^{-1}]\times[0,\varphi^{-1}]  & \text{ if } i \in \{0,1\},\\
[0,1]\times[0,\varphi^{-1}]  & \text{ if } i \in \{2,3,4,5,6,7\},\\
[0,\varphi^{-1}]\times[0,1]  & \text{ if } i \in \{8,9,10,11\},\\
[0,1]\times[0,1]             & \text{ if } i \in \{12,13,14,15,16,17,18\}.\\
\end{cases}
\]

The relative area of each rectangle is proportional to the left eigenvector of the incidence matrix of $\omega$ (Lemma <ref>).
Then the substitution $\omega:\Omega_\U\to\Omega_\U$ defines a
stone inflation on the finite set of tiles $\{\textsc{rectangle}(u_i)\}_{0\leq
i\leq 18}$ with expansion factor $\varphi=(1+\sqrt{5})/2$
(see Figure <ref>).

The morphism $\omega$ seen as a stone inflation.

§ PROOFS OF LEMMAS BASED ON SAGE

This section gathers proofs
of Lemma <ref>,
Lemma <ref>,
Lemma <ref> and
Lemma <ref>
made using version 8.2 of Sage <cit.>
together with the optional Sage package
<cit.> which can be installed by running the command
The computations will be faster if the Gurobi linear program solver
<cit.> is installed and available in Sage.
First we import the necessary libraries from :

We create the tile set :

This allows to create the transducer graph of $\U$ shown at
Figure <ref>.

We compute the number of dominoes in the direction $\be_2$ allowing a
surrounding of radius $1,2,3$ in $\Omega_\U$. We obtain 35 dominoes in the
direction $\be_2$  allowing a surrounding of radius $2$ and $3$.

Now we create the tile set :

We compute the number of dominoes in the direction $\be_1$ allowing a
surrounding of radius $1,2$ in $\Omega_\V$. We obtain 30 dominoes in the
direction $\be_1$ allowing a surrounding of radius $1$ and $2$.

We create the matrix  in Sage.
The characteristic polynomial, the eigenvalues and the eigenvectors of
can be computed easily in Sage.
After changing the ring of the
matrix to the number field containing $\varphi$, we obtain the result stated in
the proposition.

First we create the substitution $\omega$:

Then we create its incidence matrix, we check it is primitive, we compute it
characteristic polynomial, its eigenvalues and left and right eigenvectors:

From Corollary <ref>,
we know that $\L(\Omega_\U) = \omega(\L(\Omega_\U))$.
Therefore from Lemma <ref>,
we have $\L_\omega\subseteq\L(\Omega_\U)$.

Now we show using Sage that $\L(\Omega_\U)\cap \U^{(2,2)}\subseteq S$.
First we compute $U\boxminus^1\U$. It contains 35 tiles (after recursively
removing any source or sink state).
Then we compute $(U\boxminus^1\U)\boxminus^2(U\boxminus^1\U)$ for which
the resulting transducer after recursively
removing any source or sink state contains 55
transitions (or tiles).
Among them, 5 can not be surrounded, that is, there is no valid tiling of a
$3\times 3$ rectangle with them in the middle.
For each tile $t$ of the remaining 50 tiles, we compute all valid ways
of writing $t=(u\boxminus^1 v)\boxminus^2(w\boxminus^1 z)$
with $u,v,w,z\in\U$. It turns out that there is a unique way in each case
leading to a set $S\subset\U^{(2,2)}$ of 50 subwords of shape $(2,2)$
satisfying $\L(\Omega_\U)\cap \U^{(2,2)}\subseteq S$.
The following takes 4s if using  <cit.>
and 4 min if using :

Now we show using Sage that $S\subseteq\L_\omega$.
We compute the set $\L_\omega\cap \U^{(2,2)}$ using Sage.

Thus we have shown
$S\subseteq\L_\omega\cap \U^{(2,2)}
\subseteq\L(\Omega_\U)\cap \U^{(2,2)}\subseteq S$.

§ PERSPECTIVES

In this contribution, we have chosen to study the substitutive structure
of $\Omega_\U$ as $\alpha\circ\beta\circ\gamma$ where $\alpha$ involves
vertical dominoes, $\beta$ involves horizontal dominoes and $\gamma$ is a
bijection. We could have done it the other way around as
$\alpha'\circ\beta'\circ\gamma'$ where $\alpha'$ involves horizontal dominoes,
$\beta'$ involves vertical dominoes and $\gamma'$ is some other bijection as
shown below. It would be interesting to investigate all of these possible sequences
of substitutions describing $\Omega_\U$.

(U) at (0,0) $\Omega_\U$;
(V) at (1,1) $\Omega_\V$;
(V2) at (1,-1) $\Omega_{\V'}$;
(W) at (2,1) $\Omega_\W$;
(W2) at (2,-1) $\Omega_{\W'}$;
(U2) at (3,0) $\Omega_\U$;
[to-,very thick] (U) to node $\alpha$ (V);
[to-,very thick] (V) to node $\beta$ (W);
[to-,very thick] (W) to node $\gamma$ (U2);
[to-,very thick] (U) to node[swap] $\alpha'$ (V2);
[to-,very thick] (V2) to node[swap] $\beta'$ (W2);
[to-,very thick] (W2) to node[swap] $\gamma'$ (U2);

In <cit.>, an aperiodic set of 16 Wang tiles is deduced from
the Ammann tiling A2 <cit.> without much details.
A substitution showing its self-similar structure is also given with a
structure very close to the $2$-dimensional morphism
$\omega:\Omega_\U\to\Omega_\U$. Is there a link between Ammann tilings A2 and
$\Omega_\U$? Can we find a concave hexagonal shape with decorations related
to $\Omega_\U$? Can we factor the substitution as product of morphisms sending letters to letters or dominoes? The previous question is
related to the notion of elementary substitutions in D0L systems.

Many one-dimensional properties of $\Omega_\U$ can be extracted from the
morphism $\omega$. For example, considering the tiles $u_1$, $u_5$ and $u_6$,
one can see that the effect of $\omega^2$ on the indices of tiles is

\[
1\mapsto \left(\begin{array}{rr}
5 & 1 \\
18 & 10
\end{array}\right),
5\mapsto \left(\begin{array}{rrr}
5 & 1 & 6 \\
18 & 10 & 14
\end{array}\right),
6\mapsto \left(\begin{array}{rrr}
6 & 1 & 6 \\
12 & 9 & 14
\end{array}\right)
\]

which contains the one-dimensional morphism:
$\mu:1 \mapsto 51,5 \mapsto 516,6 \mapsto 616$.
This can be used to show that there exist tilings in $\Omega_\U$ that contains
rows using only the tiles in the set $\{u_1, u_5, u_6\}$.

As we have seen $\omega^2$ is prolongable on many letters thus it admits many
fixed point $x\in\Omega_\U\subset\U^{\Z^2}$.  Such fixed point were called
shape-symmetric $d$-dimensional word by Arnaud Maes when the image of
every letter on the diagonal are squares.  In <cit.> (see also
<cit.>), it is proved that a multidimensional
infinite word $x:\N^d\to\A$ over a finite alphabet $\A$ is the image by a coding
of a shape-symmetric infinite word if and only if $x$ is $S$-automatic for some
abstract numeration system $S$ built on a regular language containing the empty
word. Recall that an infinite word is $S$-automatic if, for all $n\geq0$, its
$(n+1)$-th letter is the output of a deterministic automaton fed with the
representation of $n$ in the numeration system $S$. Can we find the numeration
system $S$ and the deterministic automaton associated to $\Omega_\U$?

As noticed by the anonymous referee, the factor complexity of the language of
$\Omega_\U$ is quadratic, the first values for the number of distinct
$2$-dimensional word of shape $(n,n)$ for $n\geq 1$ being: 19, 50, 94, 154,
229, 317, 420. Tilings generated by expansive and primitive are linearly
repetitive (which means that there is some $C>0$ for which every patch of
radius $r$ is found somewhere in every ball of radius $Cr$) and one can show
that a linearly repetitive tiling of $\R^d$ must have factor complexity bounded
by a constant times $r^d$.

§ ACKNOWLEDGEMENTS

I want to thank Michaël Rao for the talk he made (Combinatorics on words and
tilings, CRM, Montréal, April 2017) from which this work is originated.  I want
to thank Vincent Delecroix for many helpful discussions at LaBRI in Bordeaux
during the preparation of this article. I am also thankful to Jörg
Thuswaldner, Henk Bruin, for inviting me to present this work (Substitutions
and tiling spaces, University of Vienna, September 2017) and to Pierre Arnoux
and Shigeki Akiyama for the same reason (Tiling and Recurrence, CIRM,
Marseille, December 2017). I want to thank Michael Baake for very
helpful discussions on inflation rules and model sets and Shigeki Akiyama for
its enthusiasm toward this project.

The author is grateful to the comments of the referee which leaded to a great
improvement in the presentation while reducing its size and simplifying many
technical proofs into simpler ones. I also wish to thank David Renault for his
careful reading of a preliminary version and his valuable comments.

I acknowledge financial support from the Laboratoire International
Franco-Québécois de Recherche en Combinatoire (LIRCO), the Agence Nationale de
la Recherche “Dynamique des algorithmes du pgcd : une approche Algorithmique,
Analytique, Arithmétique et Symbolique (Dyna3S)” (ANR-13-BS02-0003) and the
Horizon  2020  European  Research  Infrastructure  project  OpenDreamKit

* test

* test

* test

\[
A =
\begin{cases}
0       & \text{if}\quad 0 \leq k < b_i,\\
\alpha  & \text{if}\quad b_i \leq k < \omega,
\end{cases}
\]

\[
\begin{array}{rcl}
M:\Delta & \to & GL(3,\ZZ)\\
\bx & \mapsto &
\begin{cases}
A_k    & \text{ if } \bx \in A_k\Delta,\\
P_{jk}  & \text{ else if } \bx \in P_{jk}H_{jk}\Delta.
\end{cases}
\end{array}
\]