11institutetext: Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400,
Talence, France
22institutetext: FNSPE, CTU in Prague, Trojanova 13, 120 00 Praha, Czech
Republic
22email<EMAIL_ADDRESS>22email<EMAIL_ADDRESS>
# A Numeration System for Fibonacci-like
Wang Shifts

Sébastien Labbé 11 Jana Lepšová 1122

###### Abstract

Motivated by the study of Fibonacci-like Wang shifts, we define a numeration
system for $\mathbb{Z}$ and $\mathbb{Z}^{2}$ based on the binary alphabet
$\\{0,1\\}$. We introduce a set of 16 Wang tiles that admits a valid tiling of
the plane described by a deterministic finite automaton taking as input the
representation of a position $(m,n)\in\mathbb{Z}^{2}$ and outputting a Wang
tile.

##  1 Introduction

A theorem of Cobham (1972) says that a sequence $u=(u_{n})_{n\geq 0}$ is
$k$-automatic with $k\geq 2$ if and only if it is the image, under a coding,
of a fixed point of a $k$-uniform morphism [AS03, Theorem 6.3.2]. This result
was extended to non-uniform morphisms [RM02], see also [BR10, Theorem 3.4.1],
by replacing the usual base-$k$ expansion of nonnegative integers by an
abstract numeration system and a regular language [LR01]. It was later
extended to configurations $x:\mathbb{N}^{d}\to\Sigma$ in dimension $d\geq 1$
based on the notion of shape-symmetric morphic words [CKR10], see also [BR10,
Theorem 3.4.26] and [AA20, § 5].

In this article, we explore an extension of Cobham’s result beyond the
nonnegative octant $\mathbb{N}^{d}$ to include configurations
$x:\mathbb{Z}^{d}\to\Sigma$ defined on the whole lattice $\mathbb{Z}^{d}$. We
concentrate on one example in dimension $d=2$. The example is motivated by the
study of Wang tilings of the plane. Given an alphabet $\mathcal{C}$ of colors,
a Wang tile is a 4-tuple $(a,b,c,d)\in\mathcal{C}^{4}$ that represents the
labeling of the edges of a unit square, by convention, in the order
corresponding to a positive rotation on the complex plane, i.e., $a$ is the
east edge label, $b$ is the north edge label, $c$ is the west edge label and
$d$ is the south edge label.

Figure 1: The set $\mathcal{Z}=\\{z_{0},\dots,z_{15}\\}$ of 16 Wang tiles. The
index $i$ of the tile $z_{i}$ is written in the center of each tile.

We introduce a set $\mathcal{Z}=\\{z_{0},\dots,z_{15}\\}$ of 16 Wang tiles
shown in Figure 1. The set $\mathcal{Z}$ is a simplification of an existing
aperiodic set of 19 Wang tiles [Lab19] after identification of few colors,
which was shown to be related [Lab21] to the smallest set of aperiodic Wang
tiles found by Jeandel and Rao [JR21].

A valid configuration over the set of Wang tiles $\mathcal{Z}$ is a function
$f:\mathbb{Z}^{2}\to\\{0,\dots,15\\}$ such that adjacent tiles have the same
label on their common edge, i.e., for every $n\in\mathbb{Z}^{2}$, the east
label of the tile $z_{f(n)}$ is equal to the west label of the tile
$z_{f(n+e_{1})}$ and the north label of the tile $z_{f(n)}$ is equal to the
south label of the tile $z_{f(n+e_{2})}$. A partial valid configuration is
shown in Figure 2. It is this particular configuration that is linked with a
numeration system in Theorem 1. The set $\Omega_{\mathcal{Z}}$ of valid
configurations $f:\mathbb{Z}^{2}\to\\{0,\dots,15\\}$ is called the Wang shift
associated to the set of Wang tiles $\mathcal{Z}$.

Figure 2: A partial valid configuration $[-5,8[^{2}\to\\{0,\dots,15\\}$ with
the set $\mathcal{Z}$ of Wang tiles.

We show the following result which states a link between a specific
configuration over the set $\mathcal{Z}$ of Wang tiles shown in Figure 1, a
numeration system for $\mathbb{Z}^{2}$ and a deterministic finite automaton
with output (DFAO). Definition of DFAO is recalled in Section 3 and
corresponds to the classic definition [AS03].

###### Theorem 1.1

Let $\mathcal{Z}$ be the set of 16 Wang tiles shown in Figure 1. There exist a
valid Wang configuration $x\in\Omega_{\mathcal{Z}}$ and a DFAO $\mathcal{A}$
and a numeration system $\mathcal{F}$ for $\mathbb{Z}^{2}$ with a
representation function
$\operatorname{rep}_{\mathcal{F}}:\mathbb{Z}^{2}\to\\{\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}0\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
1\end{smallmatrix}\right)\\}^{*}$ such that the tile at position
${\boldsymbol{n}}\in\mathbb{Z}^{2}$ in $x$ is
$x_{\boldsymbol{n}}=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}}))$.

In fact, the Wang shift $\Omega_{\mathcal{Z}}$ is self-similar, minimal and
aperiodic. Moreover, it is topologically conjugate to the Wang shift
$\Omega_{\mathcal{U}}$ generated by the set $\mathcal{U}$ of 19 Wang tiles
introduced in [Lab19]. These results are not shown here due to lack of space
and will be part of an extended version of this article.

The article is structured as follows. In Section 2, we introduce a Fibonacci
numeration system for $\mathbb{Z}$ and $\mathbb{Z}^{2}$. In Section 3, we
illustrate how to change the usual automaton in Cobham’s theorem for
$\mathbb{N}$ so that it can read the representation of integers including the
negative ones. In Section 4, we recall the definitions and notations for two-
dimensional words, languages and morphisms. The self-similarity of the Wang
shift $\Omega_{\mathcal{Z}}$ is stated in Section 5 (the proof is available in
the appendix of the preprint version) from which the automaton of Theorem 1.1
is deduced, see Figure 5. The proof of Theorem 1.1 is done in Section 6.

Acknowledgements. This work was supported by the Agence Nationale de la
Recherche through the project Codys (ANR-18-CE40-0007).

##  2 A Fibonacci Numeration System for $\mathbb{Z}$ and $\mathbb{Z}^{2}$

Let $(F_{n})_{n\geq 1}$ be the Fibonacci sequence defined with the reccurent
relation

$F_{0}=1,F_{1}=1,F_{2}=2,F_{n+2}=F_{n+1}+F_{n}\ \ \text{ for all }n\geq 1.$

By the Zeckendorf theorem [Zec72] every nonnegative integer $n$ can be
represented as a unique sum of nonconsecutive Fibonacci numbers
$n=\sum_{i=1}^{\ell}w_{i}F_{i},$ where
$\ell=\max\left\\{i\in\mathbb{N}_{0}:F_{i}\leq n\right\\}$,
$w_{i}\in\left\\{0,1\right\\}$ and $w_{i}w_{i+1}=0,\text{ for all
}i\in\left\\{1,2,...,\ell-1\right\\}$.

Inspired by the Two’s complement, “ _the most common method of representing
signed integers on computers_
”,111https://en.wikipedia.org/wiki/Two’s_complement we introduce a numeration
system $\mathcal{F}$ which extends the Fibonacci numeration system to all
$n\in\mathbb{Z}$ as follows. For each binary word $w=w_{2k+1}w_{2k}\cdots
w_{1}\in\Sigma^{2k+1}$ of odd length over the alphabet $\Sigma=\\{0,1\\}$, we
define

$\operatorname{val}_{\mathcal{F}}(w)=\sum_{i=1}^{2k}w_{i}F_{i}-w_{2k+1}F_{2k}.$

The following lemma is an exercise based on the Fibonacci recurrence.

###### Lemma 1

Let $k\in\mathbb{N}$ and $w\in\Sigma^{2k}\setminus\Sigma^{*}11\Sigma^{*}$. We
have

  1. 1.

$\operatorname{val}_{\mathcal{F}}(0w)=\operatorname{val}_{\mathcal{F}}(000w)=\operatorname{val}_{\mathcal{F}}(110w)$,

  2. 2.

$\operatorname{val}_{\mathcal{F}}(1w)=\operatorname{val}_{\mathcal{F}}(101w)$,

  3. 3.

$\operatorname{val}_{\mathcal{F}}(100w)=\operatorname{val}_{\mathcal{F}}(000w)-F_{2k+2}$,

  4. 4.

$0\leq\operatorname{val}_{\mathcal{F}}(0w)<F_{2k+1}$,

  5. 5.

$-F_{2k+2}\leq\operatorname{val}_{\mathcal{F}}(100w)<0$.∎

Thus, the first digit of $w\in\Sigma^{2k+1}\setminus\Sigma^{*}11\Sigma^{*}$
gives the sign (nonnegative or negative) of the value
$\operatorname{val}_{\mathcal{F}}(w)$. We can show the following.

###### Proposition 1

For every $n\in\mathbb{Z}$ there exists a unique odd-length word

$w\in\Sigma(\Sigma\Sigma)^{*}\setminus\left(\Sigma^{*}11\Sigma^{*}\cup
000\Sigma^{*}\cup 101\Sigma^{*}\right)$

such that $n=\operatorname{val}_{\mathcal{F}}(w)$.

###### Proof

(Unicity). Let
$w,w^{\prime}\in\Sigma(\Sigma\Sigma)^{*}\setminus\left(\Sigma^{*}11\Sigma^{*}\cup
000\Sigma^{*}\cup 101\Sigma^{*}\right)$ of minimal length such that
$\operatorname{val}_{\mathcal{F}}(w)=\operatorname{val}_{\mathcal{F}}(w^{\prime})$.
If $w\in 1\Sigma^{*}$, then
$\operatorname{val}_{\mathcal{F}}(w)=\operatorname{val}_{\mathcal{F}}(w^{\prime})<0$
and $w^{\prime}\in 1\Sigma^{*}$ as well. In fact, we must have
$w,w^{\prime}\in 100\Sigma^{*}$. Thus $w=10u$ and $w=10u^{\prime}$ for some
words $u,u^{\prime}$ such that
$\operatorname{val}_{\mathcal{F}}(u)=\operatorname{val}_{\mathcal{F}}(u^{\prime})$.
This contradicts the minimality of the lengths of $w$ and $w^{\prime}$. If
$w\in 0\Sigma^{*}$, then
$\operatorname{val}_{\mathcal{F}}(w)=\operatorname{val}_{\mathcal{F}}(w^{\prime})\geq
0$ and $w^{\prime}\in 0\Sigma^{*}$ as well. But $w,w^{\prime}\notin
000\Sigma^{*}$, thus $w\in\\{01,001\\}u$ and
$w^{\prime}\in\\{01,001\\}u^{\prime}$ for some $u,u^{\prime}\in\Sigma^{*}$.
From Zeckendorf’s theorem applied to $1u$ and $1u^{\prime}$, we conclude that
$u=u^{\prime}$.

(Existence). If $n=0$, then $n=0=\operatorname{rep}_{\mathcal{F}}(0)$. Assume
that $n>0$. From Zeckendorf’s theorem, there exists a unique $u\in
1\Sigma^{*}\setminus\Sigma^{*}11\Sigma^{*}$ such that
$n=\operatorname{val}_{F}(u)$. If $u$ has odd-length, then
$n=\operatorname{val}_{\mathcal{F}}(00u)$. If $u$ has even-length, then
$n=\operatorname{val}_{\mathcal{F}}(0u)$. Now assume that $n<0$. Let
$k\in\mathbb{N}$ be such that $-F_{2k}\leq n<-F_{2k-2}$. We have $0\leq
n+F_{2k}<F_{2k}-F_{2k-2}=F_{2k-1}$. Let
$w\in\Sigma^{2k-2}\setminus\Sigma^{*}11\Sigma^{*}$ such that
$\operatorname{val}_{\mathcal{F}}(000w)=n+F_{2k}$. We thus have
$n=\operatorname{val}_{\mathcal{F}}(100w)$. ∎

######  Definition 1 (Numeration system $\mathcal{F}$ for $\mathbb{Z}$)

For each $n\in\mathbb{Z}$, we denote by $\operatorname{rep}_{\mathcal{F}}(n)$
the unique word satisfying the proposition.

The numeration system $\mathcal{F}$ is illustrated in Figure 3.

start0-112-234567-3-4-5891011121314151617181920-6-7-8-9-10-11-12-130001011001001001000100100100100100010010010001001001001001000100100100 $n$ | $\operatorname{rep}_{\mathcal{F}}(n)$
---|---
7 | 01010
6 | 01001
5 | 01000
4 | 00101
3 | 00100
2 | 010
1 | 001
0 | 0
-1 | 1
-2 | 100
-3 | 10010
-4 | 10001
-5 | 10000
$n$ | $\operatorname{rep}_{\mathcal{F}}(n)$
---|---
20 | 0101010
19 | 0101001
18 | 0101000
17 | 0100101
16 | 0100100
15 | 0100010
14 | 0100001
13 | 0100000
12 | 0010101
11 | 0010100
10 | 0010010
9 | 0010001
8 | 0010000
-6 | 1001010
-7 | 1001001
-8 | 1001000
-9 | 1000101
-10 | 1000100
-11 | 1000010
-12 | 1000001
-13 | 1000000
Figure 3: Representations in the numeration system $\mathcal{F}$ of
$n\in[-13,21[$.

We now extend that numeration system to $\mathbb{Z}^{2}$. If
${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{Z}^{2}$ is such that
$|n_{1}|>>|n_{2}|$, then the word representing $n_{2}$ is smaller than the
word representing $n_{1}$. We handle this issue by padding the smaller word so
that it becomes of the same length as the longer one. The padding is done
differently according to the sign of the number involved: nonnegative numbers
are padded with $00$, while negative numbers are padded with $10$. This is
consistent with the numeration system $\mathcal{F}$, refer also to the two
loops in Figure 3.

######  Definition 2 (Numeration system $\mathcal{F}$ for $\mathbb{Z}^{2}$)

Let ${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{Z}^{2}$. We define

$\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})=\left(\begin{array}[]{c}\operatorname{pad}_{t}(\operatorname{rep}_{\mathcal{F}}(n_{1}))\\\
\operatorname{pad}_{t}(\operatorname{rep}_{\mathcal{F}}(n_{2}))\end{array}\right)$

where
$t=\max\\{|\operatorname{rep}_{\mathcal{F}}(n_{1})|,|\operatorname{rep}_{\mathcal{F}}(n_{2})|\\}$
and

$\operatorname{pad}_{t}(w)=\begin{cases}(00)^{\frac{1}{2}(t-|w|)}w&\text{ if
}w\in 0\Sigma^{*},\\\ (10)^{\frac{1}{2}(t-|w|)}w&\text{ if }w\in
1\Sigma^{*}.\end{cases}$

The set of all canonical representations
$\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})$ for
${\boldsymbol{n}}\in\mathbb{Z}^{2}$ are words in
$\left\\{\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}0\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
1\end{smallmatrix}\right)\right\\}^{*}$ of odd length such that there are no
consecutive one’s in each row. E.g.
$\operatorname{rep}_{\mathcal{F}}(-2,9)=\left(\begin{smallmatrix}1010{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}100}\\\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0010001}\end{smallmatrix}\right),\operatorname{rep}_{\mathcal{F}}(14,2)=\left(\begin{smallmatrix}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0100001}\\\
0000{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}010}\end{smallmatrix}\right)$.
The length of the representation splits $\mathbb{Z}$ and $\mathbb{Z}^{2}$ into
levels.

###### Lemma 2

For every $k\in\mathbb{N}$, we have

$\displaystyle\\{n\in\mathbb{Z}\colon|\operatorname{rep}_{\mathcal{F}}(n)|=2k+1\\}=I_{k}\setminus
I_{k-1},$
$\displaystyle\\{{\boldsymbol{n}}\in\mathbb{Z}^{2}\colon|\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})|=2k+1\\}=I_{k}^{2}\setminus
I_{k-1}^{2}$

where $I_{k}=\\{i\in\mathbb{Z}\mid-F_{2k}\leq i<F_{2k+1}\\}$ for $k\geq 0$ and
$I_{-1}=\varnothing$.

###### Proof

The first equality follows from the fact that
$I_{k}=\\{n\in\mathbb{Z}\colon|\operatorname{rep}_{\mathcal{F}}(n)|\leq
2k+1\\}$ where the minimal value $-F_{2k}$ is attained by the word $1(00)^{k}$
and the maximal value $F_{2k+1}-1$ is attained by the word $0(10)^{k}$. The
second equality follows from the fact that
$I_{k}^{2}=\\{{\boldsymbol{n}}\in\mathbb{Z}^{2}\colon|\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})|\leq
2k+1\\}$. ∎

In Figure 2, the levels $I_{0}^{2}\setminus I_{-1}^{2}$, $I_{1}^{2}\setminus
I_{0}^{2}$ and $I_{2}^{2}\setminus I_{1}^{2}$ are shown in yellow, green and
blue respectively.

##  3 An Automaton not only for Nonnegative Integers

We introduce the terms based on [BR10] to be used in this section. Let
$\sigma:A\mapsto A^{*}$ be a non-erasing morphism prolongable on the letter
$a\in A$ such that $x=(x_{n})_{n\geq 0}=\sigma^{\omega}(a)$ is infinite. Let
$C=\left\\{0,...,\max_{b\in A}|\sigma(b)|-1\right\\}$ be an alphabet. The
deterministic finite automaton with output (DFAO) associated to the morphism
$\sigma$ and letter $a$ is the 5-tuple,222In contrast to [BR10] we omit the
coding as it is the identity map. $\mathcal{A}_{\sigma,a}=(A,C,\delta,a,A),$
where $\delta:A\times C\rightarrow A$ is a partial function such that
$\delta(b,i)=c$ if and only if $c=u_{i}$ and $\sigma(b)=u_{0}\dots
u_{|\sigma(b)|-1}$. Let $L$ be the language accepted by
$\mathcal{A}_{\sigma,a}$. Then the triple $\mathcal{S}$ = ($L\setminus
0C^{*}$, $C$, $<$) is an abstract numeration system, where $(C,<)$ is the
totally ordered alphabet with the natural order on $\mathbb{N}$ and the
language $L\setminus 0C^{*}$ is radix ordered. Radix order $<_{rad}$ is
defined for words $u,v\in L\setminus 0C^{*}$ as follows: $u<_{rad}v$ if and
only if $|u|<|v|$ or $|u|=|v|$ and $u<_{lex}v$. The map
$\operatorname{rep}_{\mathcal{S}}:\mathbb{N}\rightarrow L\setminus 0C^{*}$
maps $n\in\mathbb{N}$ to the $(n+1)^{th}$ word in the language $L\setminus
0C^{*}$ and the map $\operatorname{val}_{\mathcal{S}}:L\rightarrow\mathbb{N}$
maps a word $w$ to the number $n$ such that
$\operatorname{rep}_{\mathcal{S}}(n)=w^{\prime}$, where $w=0^{p}w^{\prime}$
for a $p\geq 0.$ For some state $r\in A$ and word $w\in C^{*}$, we denote by
$\mathcal{A}_{\sigma,a}(r,w)$ the state reached by the automaton after
following the path labeled by $w$ from the state $r$. We denote it by
$\mathcal{A}_{\sigma,a}(w)$ when $r$ is the initial state. The following is
essentially a reformulation of [BR10, Corollary 3.4.14].

###### Proposition 2

For every integer $n>0$, there exist integers $m\in\mathbb{N}$ and $\ell\in C$
such that $x_{n}=\sigma(x_{m})[\ell]$ and
$\operatorname{rep}_{\mathcal{S}}(n)=\operatorname{rep}_{\mathcal{S}}(m)\cdot\ell$.
Moreover, for any $i\in\mathbb{N}$, $|\operatorname{rep}_{\mathcal{S}}(n)|=i$
if and only if $|\sigma^{i-1}(a)|\leq n<|\sigma^{i}(a)|$.

###### Proof

Let $n\in\mathbb{N}$. Let $u\in L\setminus 0C^{*}$ such that
$\operatorname{rep}_{\mathcal{S}}(n)=u$. Let $w\in C^{*}$ and $\ell\in C$ such
that $u=w\ell$. We have $\operatorname{val}_{\mathcal{S}}(w\ell)=n$. Let
$m=\operatorname{val}_{\mathcal{S}}(w)$. Since $w\in L\setminus 0C^{*}$, then
$\operatorname{rep}_{\mathcal{S}}(m)=w$. From [BR10, Corollary 3.4.14], we
have

$\displaystyle\sigma(x_{\operatorname{val}_{\mathcal{S}}(w)})=x_{\operatorname{val}_{\mathcal{S}}(w0)}x_{\operatorname{val}_{\mathcal{S}}(w1)}\cdots
x_{\operatorname{val}_{\mathcal{S}}(w\ell)}\cdots
x_{\operatorname{val}_{\mathcal{S}}(w\cdot(K-1))}$

where $K=|\sigma(x_{\operatorname{val}_{\mathcal{S}}(w)})|$. Thus
$x_{n}=x_{\operatorname{val}_{\mathcal{S}}(w\ell)}=\sigma(x_{\operatorname{val}_{\mathcal{S}}(w)})[\ell]=\sigma(x_{m})[\ell]$.
The other statement follows from the equation [BR10, (3.12)]. ∎

Let $\varphi$ be the morphism $\varphi:a\mapsto ab,b\mapsto a$. The automaton
$\mathcal{A}_{\varphi^{2},a}$ associated to the right-infinite fixed point of
$\varphi^{2}$ starting with letter $a$ is shown in Figure 4. We construct
another automaton $\mathcal{A}_{\varphi^{2},s}$ associated to the bi-infinite
fixed point of $\varphi^{2}$ defined from the seed $s=b.a$, see Figure 4. The
bi-infinite Fibonacci word is $x=\lim_{k\rightarrow+\infty}\varphi^{2k}(b.a)$,
where the dot represents the origin between positions $-1$ and $0$. When
referring to $\varphi^{2k}(b.)$ we mean the finite word
$\varphi^{2k}(b)=x_{-\mid\varphi^{2k}(b)\mid}\dots x_{-2}x_{-1}$.

$a$$b$$1$$0$$0,2$$1$START$a$$b$$01$$00$$0$$1$$00,10$$01$START$a$$b$$1$$0$$0$$1$$0$
Figure 4: Automata $\mathcal{A}_{\varphi^{2},a}$,
$\mathcal{A}_{\varphi^{2},s}$ and $\mathcal{A}_{\varphi,s}$ with seed $s=b.a$.

###### Lemma 3

Let $x=\lim_{k\rightarrow+\infty}\varphi^{2k}(b.a)$ and let
$n\in\mathbb{Z}\setminus I_{0}$. Then there exist integers $m\in\mathbb{Z}$
and $0\leq\ell<3$ such that

$x[n]=\varphi^{2}(x[m])[\ell],\text{ with
}\operatorname{rep}_{\mathcal{F}}(n)=\operatorname{rep}_{\mathcal{F}}(m)h(\ell),$

where $h$ is the morphism
$h:\left\\{0,1,2\right\\}^{*}\rightarrow\left\\{0,1\right\\}^{*}$ defined as
$h:0\mapsto 00,1\mapsto 01,2\mapsto 10$. Moreover, if $n\in I_{i}\setminus
I_{i-1}$ for some $1\leq i\leq k,$ then $m\in I_{i-1}\setminus I_{i-2}.$

###### Proof

First assume that $n>0$. Let $\mathcal{A}_{\varphi^{2},a}$ and
$\mathcal{G}=(L\setminus 0C^{*},C,<)$. Then
$x=\lim_{k\rightarrow+\infty}\varphi^{2k}(a)$ is $\mathcal{G}$-automatic,
i.e., for any $n\in\mathbb{N},$ we have
$x_{n}=\mathcal{A}_{\varphi^{2},a}(\operatorname{rep}_{\mathcal{G}}(n)),$
where
$\operatorname{rep}_{\mathcal{G}}(n)\in\\{\varepsilon,1,2,10,11,20,21,22,100,101,\dots\\}$.
From the definition of $\mathcal{A}_{\varphi^{2},s}$ in Figure 4, we have
$x_{n}=\mathcal{A}_{\varphi^{2},s}(0h(\operatorname{rep}_{\mathcal{G}}(n)))$.
Moreover, from Proposition 2, for $n>0$ there exist integers $m\in\mathbb{N}$
and $\ell$ such that
$h(\operatorname{rep}_{\mathcal{G}}(n))=h(\operatorname{rep}_{\mathcal{G}}(m))h(l).$
On the other hand,
$0h(\operatorname{rep}_{\mathcal{G}}(n))=\operatorname{rep}_{\mathcal{F}}(n)$
for all $n\in\mathbb{N}.$ This follows from the following reasons. Applying
Proposition 2, we obtain that
$|0h(\operatorname{rep}_{\mathcal{G}}(n))|=2i+1\text{ if and only if
}n\in(I_{i}\setminus I_{i-1})\cap\mathbb{N}$. The alphabet $h(C)$ has the same
ordering as the alphabet $C$. Finally, a word $12$ is not accepted by the
automaton $\mathcal{A}_{\varphi^{2},a}$ and therefore a word $11$ is forbidden
in $0h(L)$. Moreover, as $|h(\ell)|=2$, we observe
$|\operatorname{rep}_{\mathcal{F}}(m)|=|\operatorname{rep}_{\mathcal{F}}(n)|-2$,
thus $m\in I_{i-1}\setminus I_{i-2}.$

If $n=-2,$ then we denote $\ell=0,m=-1.$ Let $n<-2$ and let $k\geq 2$ be such
that $n\in I_{k}\setminus I_{k-1}.$ We have

$\varphi^{2k}(b.)[n]=\varphi^{2k-1}(a)[n+|\varphi^{2k}(b)|],$ (1)

where $|\varphi^{2k}(b)|=F_{2k}.$ As $\varphi^{2k-1}(a)$ is a prefix of
$\varphi^{2k}(a),$ we can write

$\varphi^{2k-1}(a)[n+F_{2k}]=\varphi^{2k}(a)[n+F_{2k}].$

Then $0\leq n+F_{2k}<F_{2k-1}$ and we denote $0\leq i\leq k-1$ such that
$n+F_{2k}\in I_{i}\setminus I_{i-1}.$ In case that $i>0$, we use the previous
paragraph for positive $n>0$ on a long enough prefix $z$ of $x$
($z=\varphi^{2k-2}(a)$, therefore $n+F_{2k}<|z|=F_{2k-1}$) and we find
$m_{P}\in I_{i-1}\setminus I_{i-2}$ and $\ell$ such that
$\operatorname{rep}_{\mathcal{F}}(n+F_{2k})=\operatorname{rep}_{\mathcal{F}}(m_{P})h(\ell)$
and

$\varphi^{2}(\varphi^{2k-2}(a))[n+F_{2k}]=\varphi^{2}(\varphi^{2k-2}(a)[m_{P}])[\ell].$

As $0\leq m_{P}<F_{2k-3}<F_{2k-1}=|\varphi^{2k-2}(a)|$, we restrict the last
relation just to a prefix $\varphi^{2k-3}(a)$ and use the relation (1) again
to get $m=m_{P}-F_{2k-2}<0$

$\varphi^{2k}(b.)[n]=\varphi^{2}(\varphi^{2k-3}(a)[m_{P}])[\ell]=\varphi^{2}(\varphi^{2k-2}(b.)[m_{P}-F_{2k-2}])[\ell].$

The representation $\operatorname{rep}_{\mathcal{F}}(n)=10w$ has the first
digit corresponding to $-F_{2k}.$ Then
$(00)^{k-i}\operatorname{rep}_{\mathcal{F}}(n+F_{2k})=00w.$ As $m_{P}\in
I_{i-1}\setminus I_{i-2}$, then $m_{P}-F_{2k-2}\in I_{k-1}\setminus I_{k-2}$
and
$\operatorname{rep}_{\mathcal{F}}(m_{P}-F_{2k-2})=10(00)^{k-i-1}\operatorname{rep}_{\mathcal{F}}(m_{P})$.
As a whole,

$\operatorname{rep}_{\mathcal{F}}(n)=10(00)^{k-i-1}\operatorname{rep}_{\mathcal{F}}(m_{P})h(\ell)=\operatorname{rep}_{\mathcal{F}}(m_{P}-F_{2k-2})h(\ell)=\operatorname{rep}_{\mathcal{F}}(m)h(\ell).$

If $i=0,$ then we denote $\ell=0,m=-F_{2k-2}$ and the statement holds true. ∎

We show the following result.

###### Proposition 3

The DFAO $\mathcal{A}_{\varphi,s}$ associated to the seed $s=b.a$ satisfies

$x_{n}=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(n))\text{ for
all }n\in\mathbb{Z}.$

###### Proof

Let $\mathcal{A}_{\varphi,s}$ be the automaton shown in Figure 4, i.e., the
DFAO
$\mathcal{A}_{\varphi,s}=(\left\\{a,b\right\\}\cup\left\\{\textsc{start}\right\\},\left\\{0,1\right\\},\delta,\textsc{start},\left\\{a,b\right\\})$
with the partial function $\delta$ such that

  * •

$\delta(\textsc{start},\operatorname{rep}_{\mathcal{F}}(n))=s_{n}$ for every
$n\in I_{0}=\\{-1,0\\}$, where $s_{-1}=b$, $s_{0}=a,$

  * •

$\delta(c,i)=d$ for any $c,d\in\\{a,b\\}$ if and only if $\varphi(c)=u$ and
$u_{i}=d.$

Assume $n\in I_{0}$. If $n=0$, then we have
$x_{0}=a=\mathcal{A}_{\varphi,s}(0)=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(0))$.
If $n=-1$, then
$x_{-1}=b=\mathcal{A}_{\varphi,s}(1)=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(-1))$.
Induction hypothesis: we assume for some $k\in\mathbb{N}$ that
$x_{m}=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(m))$ for all
$m\in I_{k}\setminus I_{k-1}$. Let $n\in I_{k+1}\setminus I_{k}$. Then from
Lemma 3 there exist $m\in I_{k}\setminus I_{k-1}$ and $\ell\in\\{0,1,2\\}$
such that $x_{n}=\varphi^{2}(x_{m})[\ell]$ and
$\operatorname{rep}_{\mathcal{F}}(n)=\operatorname{rep}_{\mathcal{F}}(m)\cdot
h(\ell)$, where $h(\ell)=\ell_{0}\cdot\ell_{1}$ for some
$\ell_{0},\ell_{1}\in\\{0,1\\}$. From the induction hypothesis, we have

$\displaystyle x_{n}$
$\displaystyle=\varphi^{2}(x_{m})[\ell]=\varphi^{2}(\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(m)))[\ell]=\varphi(\varphi(\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(m)))[\ell_{0}])[\ell_{1}]$
$\displaystyle=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(m)\cdot\ell_{0}\cdot\ell_{1})=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(m)h(\ell))=\mathcal{A}_{\varphi,s}(\operatorname{rep}_{\mathcal{F}}(n)).\qquad\squareforqed$

##  4 Two-dimensional Words, Languages and Morphisms

In this section, we introduce 2-dimensional words, languages and morphisms
following the notations of [CKR10, Lab21]. Let $k\in\mathbb{N}$ and
$\mathcal{A}=\\{0,1,\dots,k\\}$ be a finite alphabet and let
$u:\left\\{0,\dots,n_{1}-1\right\\}\times\left\\{0,\dots,n_{2}-1\right\\}\to\mathcal{A}$
be a 2-dimensional word of shape
${\boldsymbol{n}}=(n_{1},n_{2})\in\mathbb{N}^{2}.$ Let
$\mathcal{A}^{\boldsymbol{n}}$ denote the set of all 2-dimensional words of
shape ${\boldsymbol{n}}$. We refer to the words of shape (1,2), (2,1) as to
the vertical, horizontal dominoes, respectively. We represent a
$2$-dimensional word $u$ of shape $(n_{1},n_{2})\in\mathbb{N}^{2}$ as a matrix
with Cartesian coordinates:

$u=\begin{pmatrix}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{pmatrix}.$

Let
${\mathcal{A}^{*}}^{2}=\bigcup_{\textbf{n}\in\mathbb{N}^{2}}\mathcal{A}^{\textbf{n}}$
the set of all 2-dimensional words. Let $u$, $v\in{\mathcal{A}^{*}}^{2}$ be of
shape $(n_{1},n_{2})$, $(\tilde{n}_{1},\tilde{n}_{2})$, respectively. If
$n_{2}=\tilde{n}_{2}$, the concatenation in direction ${\boldsymbol{e}}_{1}$
is defined as a 2-dimensional word $u\odot^{1}v$ of shape
$(n_{1}+\tilde{n}_{1},n_{2})$ given as

$u\odot^{1}v=\begin{pmatrix}u_{0,n_{2}-1}&\dots&u_{n_{1}-1,n_{2}-1}&v_{0,n_{2}-1}&\dots\dots&v_{\tilde{n_{1}}-1,n_{2}-1}\\\
\dots&\dots&\dots&\dots&\dots&\dots\\\
u_{0,0}&\dots&u_{n_{1}-1,0}&v_{0,0}&\dots\dots&v_{\tilde{n}_{1}-1,0}\end{pmatrix}.$

If $n_{1}=\tilde{n}_{1}$, the concatenation in direction
${\boldsymbol{e}}_{2}$ is defined analogically. A word
$v\in{\mathcal{A}^{*}}^{2}$ is a _subword_ of a word
$u\in{\mathcal{A}^{*}}^{2}$ if there exist words
$u_{1},u_{2},u_{3},u_{4}\in{\mathcal{A}^{*}}^{2}$ such that
$u=u_{3}\odot^{2}(u_{1}\odot^{1}v\odot^{1}u_{2})\odot^{2}u_{4}$.

A subset $L\subseteq{\mathcal{A}^{*}}^{2}$ is called a 2-dimensional
_factorial_ language if $u\in L$ implies that $v\in L$ for all $2$-dimensional
subwords $v$ of $u$.

Let $\mathcal{A}$ and $\mathcal{B}$ be two alphabets. Let
$L\subseteq\mathcal{A}^{*^{2}}$ be a factorial language. A function
$\omega:L\to\mathcal{B}^{*^{2}}$ is a _$2$ -dimensional morphism_ if for every
$i$ with $1\leq i\leq 2$, and every $u,v\in L$ such that $u\odot^{i}v$ is
defined and $u\odot^{i}v\in L$, we have that the concatenation
$\omega(u)\odot^{i}\omega(v)$ in direction ${\boldsymbol{e}}_{i}$ is defined
and

$\omega(u\odot^{i}v)=\omega(u)\odot^{i}\omega(v).$

A $2$-dimensional morphism $L\to\mathcal{B}^{*^{2}}$ is thus completely
defined from the image of the letters in $\mathcal{A}$ and can be denoted as a
rule $\mathcal{A}\to\mathcal{B}^{*^{2}}.$

A subset $X\subseteq\mathcal{A}^{\mathbb{Z}^{2}}$ is called a _subshift_ if it
is closed under the shift333Note that from now on, $\sigma$ denotes the shift
action and not a morphism. $\sigma$ and closed with respect to compact product
topology. Let $L\subseteq\mathcal{A}^{*^{2}}$ be a factorial language and
$\mathcal{L}(x)$ be the factorial language containing all subwords of the
configuration $x\in\mathcal{A}^{\mathbb{Z}^{2}}$. Then,
$\mathcal{X}_{L}=\\{x\in\mathcal{A}^{\mathbb{Z}^{2}}\mid\mathcal{L}(x)\subset
L\\}$ is a subshift generated by $L$. A $2$-dimensional morphism
$\omega:L\to\mathcal{B}^{*^{2}}$ can be extended to a continuous map
$\omega:\mathcal{X}_{L}\to\mathcal{B}^{\mathbb{Z}^{2}}$ in such a way that the
origin of $\omega(x)$ is at zero position in the word $\omega(x_{(0,0)})$ for
all $x\in\mathcal{X}_{L}$.

In general, the closure under the shift of the image of a subshift
$X\subseteq\mathcal{A}^{\mathbb{Z}^{2}}$ under $\omega$ is the subshift
$\overline{\omega(X)}^{\sigma}=\\{\sigma^{\boldsymbol{k}}\omega(x)\in\mathcal{B}^{\mathbb{Z}^{2}}\mid{\boldsymbol{k}}\in\mathbb{Z}^{2},x\in
X\\}\subseteq\mathcal{B}^{\mathbb{Z}^{2}}$.

A 2-dimensional morphism $\omega:\mathcal{A}\to\mathcal{A}^{*^{2}}$ is said
_expansive_ if the width and height of $\omega^{k}(a)$ goes to $\infty$ for
all letters $a\in\mathcal{A}$. A subshift
$X\subset\mathcal{A}^{\mathbb{Z}^{2}}$ is _self-similar_ if there exists an
expansive 2-dimensional morphism $\mathcal{A}\to\mathcal{A}^{*^{2}}$ such that
$X=\overline{\omega(X)}^{\sigma}$.

##  5 Self-similarity of the Wang Shift $\Omega_{\mathcal{Z}}$

###### Proposition 4

The Wang shift $\Omega_{\mathcal{Z}}$ is self-similar satisfying
$\overline{\phi(\Omega_{\mathcal{Z}})}^{\sigma}=\Omega_{\mathcal{Z}}$ where
$\phi$ is the 2-dimensional morphism over the alphabet
$\mathcal{H}=\\{0,\dots,15\\}$

$\begin{array}[]{ll}\phi:&\mathcal{H}\to\mathcal{H}^{*^{2}}\\\\[5.69054pt]
&\left\\{\scriptsize\begin{array}[]{llll}0\mapsto\left(14\right),&1\mapsto\left(13\right),&2\mapsto\left(12,\,10\right),&3\mapsto\left(11,\,8\right),\\\
4\mapsto\left(14,\,7\right),&5\mapsto\left(13,\,7\right),&6\mapsto\left(12,\,7\right),&7\mapsto\left(\begin{array}[]{r}6\\\
12\end{array}\right),\\\ 8\mapsto\left(\begin{array}[]{r}3\\\
14\end{array}\right),&9\mapsto\left(\begin{array}[]{r}3\\\
13\end{array}\right),&10\mapsto\left(\begin{array}[]{r}2\\\
12\end{array}\right),&11\mapsto\left(\begin{array}[]{rr}6&1\\\
12&10\end{array}\right),\\\ 12\mapsto\left(\begin{array}[]{rr}6&1\\\
11&8\end{array}\right),&13\mapsto\left(\begin{array}[]{rr}5&1\\\
15&9\end{array}\right),&14\mapsto\left(\begin{array}[]{rr}4&1\\\
11&8\end{array}\right),&15\mapsto\left(\begin{array}[]{rr}2&0\\\
12&7\end{array}\right).\end{array}\right.\end{array}$ (2)

The proof of Proposition 4 is done in the appendix. It is using algorithms to
desubstitute Wang shifts based on the notion of marker tiles [Lab21].

Similarly to the 1-dimensional case, we can build an automaton associated to a
fixed point of the 2-dimensional morphism $\phi$ defined in Equation (2). Let
$s=\left(\begin{smallmatrix}8&12\\\
1&6\end{smallmatrix}\right)\in\mathcal{H}^{(2,2)}$ be the seed associating one
letter to each quadrant. We observe that $\phi^{2}(s)$ prolongates $s$ at the
origin. Therefore, $\lim_{k\to\infty}\phi^{2k}(s)$ defines a configuration in
$\mathcal{H}^{\mathbb{Z}^{2}}$ which is a fixed point of $\phi^{2}$.

Associated to the morphism $\phi$ and to the seed
$s=\left(\begin{smallmatrix}s_{(-1,0)}&s_{(0,0)}\\\
s_{(-1,-1)}&s_{(0,-1)}\end{smallmatrix}\right)\in\mathcal{H}^{(2,2)}$, we
construct a DFAO
$\mathcal{A}_{\phi,s}=(\mathcal{H}\cup\\{\textsc{start}\\},\Sigma,\delta,I,\mathcal{H})$
such that $\Sigma=\left\\{\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}0\\\
1\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
0\end{smallmatrix}\right),\left(\begin{smallmatrix}1\\\
1\end{smallmatrix}\right)\right\\}$, $I=\left\\{\textsc{start}\right\\}$ and
$\delta:Q\times\Sigma\rightarrow Q$ is a partial function such that

  * •

$\delta(\textsc{start},\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}}))=s_{\boldsymbol{n}}$
for every ${\boldsymbol{n}}\in I_{0}^{2}=\\{(0,0),(-1,0),(0,-1),(-1,-1)\\}$,

  * •

$\delta(a,e)=b$ for any $a,b\in\mathcal{H}$ and $e\in\Sigma$ if and only if
$b$ is in $\phi(a)$ at position $e$.

The automaton $\mathcal{A}_{\phi,s}$ associated to the morphism $\phi$ and
seed $s=\left(\begin{smallmatrix}8&12\\\ 1&6\end{smallmatrix}\right)$ is shown
in Figure 5.

Figure 5: The automaton $\mathcal{A}_{\phi,s}$ associated to the 2-dimensional
morphism $\phi$ and seed $s=\left(\begin{smallmatrix}8&12\\\
1&6\end{smallmatrix}\right)$.

##  6 Proof of Main Results

In this section, we prove Theorem 1.1. The strategy is to extract the
horizontal and vertical structure (expressed as 1-dimensional morphisms) of a
2-dimensional morphism and exploit results proved for the 1-dimensional case
in Section 3, in particular Lemma 3.

Let $\omega$ be a 2-dimensional morphism on the alphabet $\mathcal{Q}$ and
$\mathcal{X}_{\omega}$ be the associated substitutive subshift. Since
$\omega:\mathcal{X}_{\omega}\to\mathcal{X}_{\omega}$ is well-defined, it
imposes that the horizontal width of $\omega(a)$ equals the horizontal width
of $\omega(b)$ for every pair of letters $a,b\in\mathcal{Q}$ appearing in the
same column. This holds also for the height of the images of letters appearing
in the same row. However, more can be said.

We define $\sim_{\rm col}$ the equivalence relation as the reflexive,
symmetric and transitive closure of the relation
$\\{(a,b)\mid\left(\begin{smallmatrix}b\\\
a\end{smallmatrix}\right)\in\mathcal{L}_{\omega}\\}$ made of the vertical
dominoes in the language. We define $\sim_{\rm row}$ the equivalence relation
as the reflexive, symmetric and transitive closure of the relation
$\\{(a,b)\mid\left(\begin{smallmatrix}a&b\end{smallmatrix}\right)\in\mathcal{L}_{\omega}\\}$
made of the horizontal dominoes in the language. We have that $a\sim_{\rm
col}b$ if and only if letters $a$ and $b$ appear in the same column in some
configuration of $\mathcal{X}_{\omega}$. Let $\pi_{\rm
col}:\mathcal{Q}\rightarrow\mathcal{Q}|_{\sim_{\rm col}}$ and $\pi_{\rm
row}:\mathcal{Q}\rightarrow\mathcal{Q}|_{\sim_{\rm row}}$ be the maps defined
as $\pi_{\rm col}:a\mapsto[a]_{\sim_{\rm col}}$, and $\pi_{\rm
row}:a\mapsto[a]_{\sim_{\rm row}}$ mapping a letter $a\in\mathcal{Q}$ to its
equivalence class.

We define the horizontal and vertical structure of $\omega$ resp. as the
1-dimensional morphisms $\omega_{\textsc{horiz}}:\mathcal{Q}|_{\sim_{\rm
col}}^{*}\to\mathcal{Q}|_{\sim_{\rm col}}^{*}$ and
$\omega_{\textsc{vert}}:\mathcal{Q}|_{\sim_{\rm
row}}^{*}\to\mathcal{Q}|_{\sim_{\rm row}}^{*}$ by

$\omega_{\textsc{horiz}}([a]_{\sim_{\rm col}})=[w_{0,0}]_{\sim_{\rm
col}}\cdots[w_{m-1,0}]_{\sim_{\rm col}},$
$\omega_{\textsc{vert}}([a]_{\sim_{\rm row}})=[w_{0,0}]_{\sim_{\rm
row}}\cdots[w_{0,n-1}]_{\sim_{\rm row}}$

where $w=\omega(a)\in\mathcal{Q}^{(m,n)}$.

###### Lemma 4

Let $\phi$ be the 2-dimensional morphism from Proposition 4 and $x$ the point
fixed by $\phi^{2},$ $x=\lim_{k\rightarrow+\infty}\phi^{2k}(s)$ for the seed
$s=\left(\begin{smallmatrix}8&12\\\ 1&6\end{smallmatrix}\right)$. Let
${\boldsymbol{n}}\in\mathbb{Z}^{2}\setminus I_{0}^{2}$. Then, there exist
vectors ${\boldsymbol{m}}\in\mathbb{Z}^{2}$ and
${\boldsymbol{\ell}}\in\left\\{0,1,2\right\\}^{2}$ such that

$x_{{\boldsymbol{n}}}=\phi^{2}(x_{{\boldsymbol{m}}})[{\boldsymbol{\ell}}]\text{,
where
}\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})=\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})\cdot
h({\boldsymbol{\ell}}).$

###### Proof

Let ${\boldsymbol{n}}\in\mathbb{Z}^{2}\setminus I_{0}^{2}$. The powers
$\phi^{2k}(s)$ are defined such that they grow in all four quadrants. The
vertical and horizontal structure of $\phi$ are respectively
$\phi_{\textsc{vert}}=\phi_{\textsc{horiz}}=\left\\{\begin{array}[]{l}a\mapsto
ab\\\ b\mapsto a\end{array}\right.$ satisfying

$\displaystyle\operatorname{width}(\phi(w))$
$\displaystyle=|\phi_{\textsc{horiz}}\circ\pi_{col}(w_{0,0}\cdots w_{m-1,0})|$
$\displaystyle\operatorname{height}(\phi(w))$
$\displaystyle=|\phi_{\textsc{vert}}\circ\pi_{row}(w_{0,0}\cdots w_{0,n-1})|$

for all 2-dimensional words $w\in\mathcal{L}_{\phi}$ of shape $(m,n)$.
Therefore, the vectors ${\boldsymbol{m}}$ and ${\boldsymbol{\ell}}$ we are
searching for can be found coordinate by coordinate.

Let
$y=\lim_{k\to\infty}\phi_{\textsc{horiz}}^{2k}(b.a)=\lim_{k\to\infty}\phi_{\textsc{vert}}^{2k}(b.a)$.
From Lemma 3, there exist integers $m_{1},m_{2}\in\mathbb{Z}$ and
$0\leq\ell_{1},\ell_{2}<3$ such that

$y[n_{1}]=\phi_{\textsc{horiz}}^{2}(y[m_{1}])[\ell_{1}]\qquad\text{ and
}\qquad y[n_{2}]=\phi_{\textsc{vert}}^{2}(y[m_{2}])[\ell_{2}],$

where
$\operatorname{rep}_{\mathcal{F}}(n_{1})=\operatorname{rep}_{\mathcal{F}}(m_{1})\cdot
h(\ell_{1})$ and
$\operatorname{rep}_{\mathcal{F}}(n_{2})=\operatorname{rep}_{\mathcal{F}}(m_{2})\cdot
h(\ell_{2})$. Moreover, it satisfies
$x_{(n_{1},n_{2})}=\phi^{2}(x_{(m_{1},m_{2})})[(\ell_{1},\ell_{2})]$. We
conclude

$\operatorname{rep}_{\mathcal{G}}({\boldsymbol{n}})=\left(\begin{array}[]{l}\operatorname{pad}_{t}(\operatorname{rep}_{\mathcal{F}}(n_{1}))\\\
\operatorname{pad}_{t}(\operatorname{rep}_{\mathcal{F}}(n_{2}))\end{array}\right)=\left(\begin{array}[]{l}\operatorname{pad}_{t-2}(\operatorname{rep}_{\mathcal{F}}(m_{1})\cdot
h(\ell_{1})\\\
\operatorname{pad}_{t-2}(\operatorname{rep}_{\mathcal{F}}(m_{2})\cdot
h(\ell_{2})\end{array}\right)=\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})\cdot
h({\boldsymbol{\ell}}).$

where
$t=\max\\{|\operatorname{rep}_{\mathcal{F}}(n_{1})|,|\operatorname{rep}_{\mathcal{F}}(n_{2})|\\}$.∎

###### Lemma 5

For any state $r\in Q\setminus\\{\textsc{start}\\}$ in the automaton
$\mathcal{A}_{\phi,s}$ and any
${\boldsymbol{\ell}}\in\left\\{0,...,\operatorname{width}(\phi^{2}(r))-1\right\\}\times\left\\{0,...,\operatorname{height}(\phi^{2}(r))-1\right\\}$
we have

$\mathcal{A}_{\phi,s}(r,h({\boldsymbol{\ell}}))=\phi^{2}(r)[{\boldsymbol{\ell}}].$

###### Proof

Let $r$ and ${\boldsymbol{\ell}}$ be according to the assumptions. Therefore,
${\boldsymbol{\ell}}\in\left\\{0,1,2\right\\}^{2}.$ Then, there exist unique
vectors
${\boldsymbol{\ell}}_{0},{\boldsymbol{\ell}}_{1}\in\left\\{0,1\right\\}^{2}$
such that
$\phi^{2}(s)[{\boldsymbol{\ell}}]=\phi(\phi(s)[{\boldsymbol{\ell}}_{0}])[{\boldsymbol{\ell}}_{1}].$
As
${\boldsymbol{\ell}}_{0},{\boldsymbol{\ell}}_{1}\in\left\\{0,1\right\\}^{2}$,
they belong to the set of edges $\Sigma$ of the automaton
$\mathcal{A}_{\phi,s}$. Then, using the general properties of an automaton we
have

$\displaystyle\phi^{2}(r)[{\boldsymbol{\ell}}]$
$\displaystyle=\phi(\phi(r)[{\boldsymbol{\ell}}_{0}])[{\boldsymbol{\ell}}_{1}]=\phi(\mathcal{A}_{\phi,s}(r,{\boldsymbol{\ell}}_{0}))[{\boldsymbol{\ell}}_{1}]$
$\displaystyle=\mathcal{A}_{\phi,s}(\mathcal{A}_{\phi,s}(r,{\boldsymbol{\ell}}_{0}),{\boldsymbol{\ell}}_{1})=\mathcal{A}_{\phi,s}(r,{\boldsymbol{\ell}}_{0}{\boldsymbol{\ell}}_{1})=\mathcal{A}_{\phi,s}(r,h({\boldsymbol{\ell}})),$

where the last equation holds for the following reasons.

I) If
${\boldsymbol{\ell}}\in\left\\{0,1\right\\}^{2},\left(\begin{smallmatrix}i\\\
j\end{smallmatrix}\right)={\boldsymbol{\ell}},$ then
$h({\boldsymbol{\ell}})=\left(\begin{smallmatrix}0&i\\\
0&j\end{smallmatrix}\right).$ Also,
${\boldsymbol{\ell}}_{0}=\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right)$ and
${\boldsymbol{\ell}}_{1}=\left(\begin{smallmatrix}i\\\
j\end{smallmatrix}\right).$

II) If
$\ell\in\left\\{2\right\\}\times\left\\{0,1\right\\},\left(\begin{smallmatrix}2\\\
j\end{smallmatrix}\right)={\boldsymbol{\ell}},$ then
$h({\boldsymbol{\ell}})=\left(\begin{smallmatrix}1&0\\\
0&j\end{smallmatrix}\right).$ On the other hand,
${\boldsymbol{\ell}}_{0}=\left(\begin{smallmatrix}1\\\
0\end{smallmatrix}\right)$ and
${\boldsymbol{\ell}}_{1}=\left(\begin{smallmatrix}0\\\
j\end{smallmatrix}\right).$ The case
${\boldsymbol{\ell}}\in\left\\{0,1\right\\}\times\left\\{2\right\\}$ is
analogical.

III) If ${\boldsymbol{\ell}}\in\left\\{2\right\\}^{2},$ then
$h({\boldsymbol{\ell}})=\left(\begin{smallmatrix}1&0\\\
1&0\end{smallmatrix}\right).$ Also,
${\boldsymbol{\ell}}_{0}=\left(\begin{smallmatrix}1\\\
1\end{smallmatrix}\right)$ and
${\boldsymbol{\ell}}_{1}=\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right).$ ∎

###### Theorem 6.1

Let $\phi$ be a 2-dimensional morphism and $x$ the point fixed by $\phi^{2}$,
$x=\lim_{k\rightarrow+\infty}\phi^{2k}(s)$ for a seed
$s=\left(\begin{smallmatrix}8&12\\\ 1&6\end{smallmatrix}\right)$. Then, there
exists an automaton $\mathcal{A}$ such that
$x_{{\boldsymbol{n}}}=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}}))$.

###### Proof

Let $\mathcal{A}=\mathcal{A}_{\phi,s}$ the automaton associated to the
morphism $\phi$ and seed $s=\left(\begin{smallmatrix}8&12\\\
1&6\end{smallmatrix}\right)$. If ${\boldsymbol{n}}\in
I_{0}^{2}=\left\\{(0,0),(-1,0),(-1,-1),(0,-1)\right\\},$ then
$x_{{\boldsymbol{n}}}=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}}))$.
Induction hypothesis: we assume for some $k\in\mathbb{N}$ that
$x_{{\boldsymbol{m}}}=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}}))$
for all ${\boldsymbol{m}}\in I_{k}^{2}\setminus I_{k-1}^{2}$. Let
${\boldsymbol{n}}\in I_{k+1}^{2}\setminus I_{k}^{2}.$ Then, from Lemma 4 there
exist ${\boldsymbol{m}}\in\mathbb{Z}^{2}$ and
${\boldsymbol{\ell}}\in\\{0,1,2\\}^{2}$ such that
$x_{{\boldsymbol{n}}}=\phi^{2}(x_{{\boldsymbol{m}}})[{\boldsymbol{\ell}}]$
where
$\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})=\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})\cdot
h({\boldsymbol{\ell}})$.

This implies
$|\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})|=|\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})|-2,$
and therefore by Lemma 2, ${\boldsymbol{m}}\in I_{k}^{2}\setminus
I_{k-1}^{2}.$ From the induction hypothesis,
$x_{{\boldsymbol{m}}}=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}}))$.
Then, from the induction hypothesis and Lemma 5, we have

$\displaystyle x_{{\boldsymbol{n}}}$
$\displaystyle=\phi^{2}(x_{{\boldsymbol{m}}})[{\boldsymbol{\ell}}]=\phi^{2}(\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})))[{\boldsymbol{\ell}}]$
$\displaystyle=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{m}})h({\boldsymbol{\ell}}))=\mathcal{A}(\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})).\qquad\squareforqed$

######  Proof (of Theorem 1.1)

Let $\phi$ be the 2-dimensional morphism from Proposition 4 and let
$x=\phi^{2}(x)$ be the point fixed by $\phi^{2},$ where
$x=\lim_{k\rightarrow+\infty}\phi^{2k}(s)$ of the seed
$s=\left(\begin{smallmatrix}8&12\\\ 1&6\end{smallmatrix}\right)$. Let
$\mathcal{A}=\mathcal{A}_{\phi,s}$ (see Figure 5). The conclusion follows from
Theorem 6.1. ∎

###### Example 1

Let ${\boldsymbol{n}}=(-1,6)\in\mathbb{Z}^{2}$. Then,
$\operatorname{rep}_{\mathcal{F}}({\boldsymbol{n}})=\left(\begin{smallmatrix}10101\\\
01001\end{smallmatrix}\right)$ and $\mathcal{A}_{\phi,s}$ gives

$\textsc{start}\xrightarrow{(1,0)}8\xrightarrow{(0,1)}3\xrightarrow{(1,0)}8\xrightarrow{(0,0)}14\xrightarrow{(1,1)}1.$

The tile at position ${\boldsymbol{n}}$ in the tiling $x$ in Figure 2 is
indeed $x_{\boldsymbol{n}}=1$.

Since $\Omega_{\mathcal{Z}}$ is minimal, we believe that Theorem 1.1 can be
extended to all configurations in $\Omega_{\mathcal{Z}}$ provided an
additional input is given. Moreover, we believe that Theorem 1.1 holds for a
large family of self-similar subshifts and not only for Fibonacci-like
examples, thus extending Cobham’s theorem to $\mathbb{Z}^{2}$ and
$\mathbb{Z}^{d}$. This asks for further research and is part of an ongoing
work.

## References

  * [AA20] Shigeki Akiyama and Pierre Arnoux, editors.  Substitution and tiling dynamics: introduction to self-inducing structures. CIRM Jean-Morlet Chair, Marseille, France, Fall 2017, volume 2273\.  Cham: Springer, 2020.
  * [AS03] Jean-Paul Allouche and Jeffrey Shallit.  Automatic sequences.  Cambridge University Press, Cambridge, 2003.  Theory, applications, generalizations.
  * [BR10] Valérie Berthé and Michel Rigo, editors.  Combinatorics, automata, and number theory, volume 135.  Cambridge: Cambridge University Press, 2010.
  * [CKR10] Emilie Charlier, Tomi Kärki, and Michel Rigo.  Multidimensional generalized automatic sequences and shape-symmetric morphic words.  Discrete Math., 310(6-7):1238–1252, 2010.
  * [JR21] Emmanuel Jeandel and Michaël Rao.  An aperiodic set of 11 Wang tiles.  Advances in Combinatorics, January 2021.
  * [Lab19] Sébastien Labbé.  A self-similar aperiodic set of 19 Wang tiles.  Geom. Dedicata, 201:81–109, 2019.
  * [Lab20a] Sébastien Labbé.  Optional SageMath Package slabbe (Version 0.6.2).  https://pypi.python.org/pypi/slabbe/, 2020.
  * [Lab20b] Sébastien Labbé.  Three characterizations of a self-similar aperiodic 2-dimensional subshift.  December 2020.  arXiv:2012.03892.
  * [Lab21] Sébastien Labbé.  Substitutive Structure of Jeandel-Rao Aperiodic Tilings.  Discrete Comput. Geom., 65(3):800–855, 2021.
  * [LR01] P. B. A. Lecomte and M. Rigo.  Numeration systems on a regular language.  Theory Comput. Syst., 34(1):27–44, 2001.
  * [RM02] Michel Rigo and Arnaud Maes.  More on generalized automatic sequences.  J. Autom. Lang. Comb., 7(3):351–376, 2002.
  * [Zec72] E. Zeckendorf.  Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas.  Bull. Soc. Roy. Sci. Liège, 41:179–182, 1972.

##  7 Appendix

We now define the notion of markers for subshifts
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$. Their existence allows to desubstitute
uniquely the configurations in $X$ using a $d$-dimensional morphism.
Originally, those results were proved for $d=2$ in order to desubstitute
configurations from Wang shifts, see [Lab19] and [Lab21]. It turns out that
the notion of markers is more general and the results holds in general
subshifts $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ [Lab20b].

Recall that if $w:\mathbb{Z}^{d}\to\mathcal{A}$ is a configuration and
$a\in\mathcal{A}$ is a letter, then $w^{-1}(a)\subset\mathbb{Z}^{d}$ is the
set of positions where the letter $a$ appears in $w$.

###### Definition 3

Let $\mathcal{A}$ be an alphabet and $X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ be
a subshift. A nonempty subset $M\subset\mathcal{A}$ is called _markers in the
direction ${\boldsymbol{e}}_{i}$_, with $i\in\\{1,\dots,d\\}$, if positions of
the letters of $M$ in any configuration are nonadjacent $(d-1)$-dimensional
layers orthogonal to ${\boldsymbol{e}}_{i}$, that is, for all configurations
$w\in X$ there exists $P\subset\mathbb{Z}$ such that the positions of the
markers satisfy

$w^{-1}(M)=P{\boldsymbol{e}}_{i}+\sum_{k\neq
i}\mathbb{Z}{\boldsymbol{e}}_{k}\quad\text{ with }\quad 1\notin P-P$

where $P-P=\\{b-a\mid a\in P,b\in P\\}$ is the set of differences between
elements of $P$.

Note that it follows from the definition that a subset of markers is a proper
subset of $\mathcal{A}$ as the case $M=\mathcal{A}$ is impossible.

The presence of markers allows to desubstitute uniquely the configurations of
a subshift. There is even a choice to be made in the construction of the
substitution. We may construct the substitution in such a way that the markers
are on the left or on the right in the image of letters that are dominoes in
the direction ${\boldsymbol{e}}_{k}$. We make this distinction in the
statement of the following result which was stated in the context of Wang
shifts in [Lab19, Lab21] and extended to $\mathbb{Z}^{d}$ in [Lab20b].

###### Theorem 7.1

[Lab20b] Let $\mathcal{A}$ be an alphabet and
$X\subset\mathcal{A}^{\mathbb{Z}^{d}}$ be a subshift. If there exists a subset
$M\subset\mathcal{A}$ of markers in the direction
${\boldsymbol{e}}_{i}\in\\{{\boldsymbol{e}}_{1},\dots,{\boldsymbol{e}}_{d}\\}$,
then

  1. (i)

(markers on the right) there exists an alphabet $\mathcal{B}_{R}$, a subshift
$Y\subset\mathcal{B}_{R}^{\mathbb{Z}^{d}}$ and a $2$-dimensional morphism
$\omega_{R}:Y\to X$ such that

$\omega_{R}(\mathcal{B}_{R})\subseteq(\mathcal{A}\setminus
M)\cup\left((\mathcal{A}\setminus M)\odot^{i}M\right)$

which is recognizable and onto up to a shift and

  2. (ii)

(markers on the left) there exists an alphabet $\mathcal{B}_{L}$, a subshift
$Y\subset\mathcal{B}_{L}^{\mathbb{Z}^{d}}$ and a $2$-dimensional morphism
$\omega_{L}:Y\to X$ such that

$\omega_{L}(\mathcal{B}_{L})\subseteq(\mathcal{A}\setminus
M)\cup\left(M\odot^{i}(\mathcal{A}\setminus M)\right)$

which is recognizable and onto up to a shift.

The morphisms provided in Theorem 7.1 can be computed with an algorithm taking
as input the subset of marker tiles. Those algorithms are available in [Lab21,
Lab20b] and are implemented in the slabbe optional package [Lab20a] of
SageMath. The algorithms are used in the proof below.

In the following proof, we use the notation $\llbracket
m,n\rrbracket=\\{k\in\mathbb{Z}\mid m\leq k\leq n\\}$, where
$m,n\in\mathbb{Z}$, to denote interval of integers.

######  Proof (of Proposition 4)

We use the algorithms to desubstitute Wang shifts based on the notion of
marker tiles [Lab21, Theorem 3.6]. We construct the set $\mathcal{Z}$ of 16
Wang tiles:

    sage: from slabbe import WangTileSet
    sage: tiles = ["DOJO", "DOHL", "JMDP", "DMDK", "HPJP", "HPHN", "HKDP", "BOIO",
    ....:          "ILEO", "ILCL", "ALIO", "EPIP", "IPIK", "IKBM", "IKAK", "CNIP"]
    sage: Z = WangTileSet([tuple(tile) for tile in tiles]); Z
    Wang tile set of cardinality 16

We compute a subset of markers $M\subset\mathcal{Z}$ for the direction
${\boldsymbol{e}}_{2}$ and we use them to desubstitute the Wang shift
$\Omega_{\mathcal{Z}}$:

    sage: Z.find_markers(i=2, radius=2, solver="dancing_links")
    [[0, 1, 2, 3, 4, 5, 6]]
    sage: M = [0, 1, 2, 3, 4, 5, 6]
    sage: Z1,gamma0 = Z.find_substitution(M, i=2, radius=2,
    ....:            side="right", solver="dancing_links")

We obtain the morphism
$\gamma_{0}:\Omega_{\mathcal{Z}_{1}}\to\Omega_{\mathcal{Z}}$ given as a rule
of the form

$\begin{array}[]{ll}\gamma_{0}:&\llbracket 0,17\rrbracket\to\llbracket
0,15\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\scriptsize\begin{array}[]{llll}0\mapsto\left(7\right),&1\mapsto\left(8\right),&2\mapsto\left(10\right),&3\mapsto\left(11\right),\\\
4\mapsto\left(12\right),&5\mapsto\left(13\right),&6\mapsto\left(14\right),&7\mapsto\left(\begin{array}[]{r}0\\\
7\end{array}\right),\\\ 8\mapsto\left(\begin{array}[]{r}1\\\
8\end{array}\right),&9\mapsto\left(\begin{array}[]{r}1\\\
9\end{array}\right),&10\mapsto\left(\begin{array}[]{r}1\\\
10\end{array}\right),&11\mapsto\left(\begin{array}[]{r}4\\\
11\end{array}\right),\\\ 12\mapsto\left(\begin{array}[]{r}6\\\
11\end{array}\right),&13\mapsto\left(\begin{array}[]{r}2\\\
12\end{array}\right),&14\mapsto\left(\begin{array}[]{r}6\\\
12\end{array}\right),&15\mapsto\left(\begin{array}[]{r}3\\\
13\end{array}\right),\\\ 16\mapsto\left(\begin{array}[]{r}3\\\
14\end{array}\right),&17\mapsto\left(\begin{array}[]{r}5\\\
15\end{array}\right).\end{array}\right.\end{array}$

and the set $\mathcal{Z}_{1}$ of 18 Wang tiles

$\mathcal{Z}_{1}=\left\\{\raisebox{-18.49428pt}{\includegraphics[width=238.49231pt]{SAGEOUTPUTS/Z1-tiles.pdf}}\right\\}.$

We compute a subset of markers $M_{1}\subset\mathcal{Z}_{1}$ for the direction
${\boldsymbol{e}}_{1}$ and we use them to desubstitute the Wang shift
$\Omega_{\mathcal{Z}_{1}}$:

    sage: Z1.find_markers(i=1, radius=1,solver="dancing_links")
    [[0, 1, 2, 7, 8, 9, 10]]
    sage: M = [0,1,2,7,8,9,10]
    sage: Z2,gamma1 = Z1.find_substitution(M, i=1, radius=1,
    ....:             side="right", solver="dancing_links")

We obtain the morphism
$\gamma_{1}:\Omega_{\mathcal{Z}_{2}}\to\Omega_{\mathcal{Z}_{1}}$ given as a
rule of the form

$\begin{array}[]{ll}\gamma_{1}:&\llbracket 0,15\rrbracket\to\llbracket
0,17\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\scriptsize\begin{array}[]{llll}0\mapsto\left(5\right),&1\mapsto\left(6\right),&2\mapsto\left(13\right),&3\mapsto\left(14\right),\\\
4\mapsto\left(15\right),&5\mapsto\left(16\right),&6\mapsto\left(3,\,1\right),&7\mapsto\left(4,\,0\right),\\\
8\mapsto\left(4,\,2\right),&9\mapsto\left(5,\,0\right),&10\mapsto\left(6,\,0\right),&11\mapsto\left(11,\,8\right),\\\
12\mapsto\left(12,\,8\right),&13\mapsto\left(13,\,7\right),&14\mapsto\left(14,\,10\right),&15\mapsto\left(17,\,9\right).\end{array}\right.\end{array}$

and the set $\mathcal{Z}_{2}$ of 16 Wang tiles

$\mathcal{Z}_{2}=\left\\{\raisebox{-18.49428pt}{\includegraphics[width=238.49231pt]{SAGEOUTPUTS/Z2-tiles.pdf}}\right\\}.$

It turns out that $\mathcal{Z}$ and $\mathcal{Z}_{2}$ are equivalent. The
proof can be done using graph isomorphisms:

    sage: Z2.is_equivalent(Z)
    True

The bijection vert between the vertical colors, the bijection horiz between
the horizontal colors and bijection $\gamma_{2}$ from $\mathcal{Z}_{2}$ to
$\mathcal{Z}$ is computed as follows:

    sage: _,vert,horiz,gamma2 = Z.is_equivalent(Z2, certificate=True)

We obtain the morphism
$\gamma_{2}:\Omega_{\mathcal{Z}}\to\Omega_{\mathcal{Z}_{2}}$ given as a rule
of the form

$\begin{array}[]{ll}\gamma_{2}:&\llbracket 0,15\rrbracket\to\llbracket
0,15\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\scriptsize\begin{array}[]{llll}0\mapsto\left(1\right),&1\mapsto\left(0\right),&2\mapsto\left(8\right),&3\mapsto\left(6\right),\\\
4\mapsto\left(10\right),&5\mapsto\left(9\right),&6\mapsto\left(7\right),&7\mapsto\left(3\right),\\\
8\mapsto\left(5\right),&9\mapsto\left(4\right),&10\mapsto\left(2\right),&11\mapsto\left(14\right),\\\
12\mapsto\left(12\right),&13\mapsto\left(15\right),&14\mapsto\left(11\right),&15\mapsto\left(13\right).\end{array}\right.\end{array}$

and we have

$\begin{array}[]{ll}\gamma_{0}\gamma_{1}\gamma_{2}:&\llbracket
0,15\rrbracket\to\llbracket 0,15\rrbracket^{*^{2}}\\\\[5.69054pt]
&\left\\{\scriptsize\begin{array}[]{llll}0\mapsto\left(14\right),&1\mapsto\left(13\right),&2\mapsto\left(12,\,10\right),&3\mapsto\left(11,\,8\right),\\\
4\mapsto\left(14,\,7\right),&5\mapsto\left(13,\,7\right),&6\mapsto\left(12,\,7\right),&7\mapsto\left(\begin{array}[]{r}6\\\
12\end{array}\right),\\\ 8\mapsto\left(\begin{array}[]{r}3\\\
14\end{array}\right),&9\mapsto\left(\begin{array}[]{r}3\\\
13\end{array}\right),&10\mapsto\left(\begin{array}[]{r}2\\\
12\end{array}\right),&11\mapsto\left(\begin{array}[]{rr}6&1\\\
12&10\end{array}\right),\\\ 12\mapsto\left(\begin{array}[]{rr}6&1\\\
11&8\end{array}\right),&13\mapsto\left(\begin{array}[]{rr}5&1\\\
15&9\end{array}\right),&14\mapsto\left(\begin{array}[]{rr}4&1\\\
11&8\end{array}\right),&15\mapsto\left(\begin{array}[]{rr}2&0\\\
12&7\end{array}\right).\end{array}\right.\end{array}$

We conclude that
$\Omega_{\mathcal{Z}}=\overline{\gamma_{0}(\Omega_{\mathcal{Z}_{1}})}^{\sigma}=\overline{\gamma_{0}\gamma_{1}(\Omega_{\mathcal{Z}_{2}})}^{\sigma}=\overline{\gamma_{0}\gamma_{1}\gamma_{2}(\Omega_{\mathcal{Z}})}^{\sigma}=\overline{\phi(\Omega_{\mathcal{Z}})}^{\sigma}$.
∎

###### Theorem 7.2

The Wang shift $\Omega_{\mathcal{Z}}$ generated by the tiles $\mathcal{Z}$ is
self-similar, minimal and aperiodic.

######  Proof (of Theorem 7.2)

From Proposition 4 we obtain that $\Omega_{\mathcal{Z}}$ is self-similar
satisfying
$\overline{\phi(\Omega_{\mathcal{Z}})}^{\sigma}=\Omega_{\mathcal{Z}}$. Since
$\phi$ is expansive and recognizable, the Wang shift $\Omega_{\mathcal{Z}}$ is
aperiodic [Lab19, Proposition 6].

We compute the set of $2\times 2$ words for which the morphism $\phi$ is
prolongable for some power of $\phi$ in each of the four quadrants:

    sage: gamma012 = gamma0 * gamma1 * gamma2
    sage: seeds = flatten(gamma012.prolongable_seeds_list())
    sage: seeds
    [
    [ 8 12]  [14 11]  [ 8 12]  [14 11]  [ 9 11]  [13 12]  [ 9 12]  [13 11]
    [ 1  6], [13 12], [ 7 13], [ 6  5], [ 8 12], [ 3  6], [10 14], [ 2  4]
    ]

We check whether these $2\times 2$ factors belong to the language
$\mathcal{L}_{\phi}$ generated from the application of the morphism on the
letters:

    sage: seeds = [[list(reversed(col)) for col in seed.columns()] for seed in seeds]
    sage: F = gamma012.list_2x2_factors()
    sage: all(seed in F for seed in seeds)
    True

Thus the substitutive subshift $\mathcal{X}_{\phi}$ is the unique self-similar
subshift $X\subset\llbracket 0,15\rrbracket^{\mathbb{Z}^{2}}$ satisfying
$\overline{\phi(X)}^{\sigma}=X$ [Lab20b, Lemma 3.9]. Thus
$\mathcal{X}_{\phi}=\Omega_{\mathcal{Z}}$. Moreover $\mathcal{X}_{\phi}$ is
minimal since $\phi$ is primitive and expansive. ∎