# Enumerating and Locating the Subwords of the Two-dimensional Infinite
Fibonacci Word

Sivasankar M1 Corresponding Author Rama R1  Department of Mathematics, Indian
Institute of Technology Madras, Chennai, India

###### Abstract

Given an infinite word, enumerating its subwords is an important exercise for
understanding the structure of the word. The process of finding all the
subwords is quite tricky for two-dimensional words. In this paper we enumerate
the subwords of the two-dimensional infinite Fibonacci word,
$f_{\infty,\infty}$, in a few possible ways. In addition, we extend a method
for locating the subwords of the one-dimensional infinite Fibonacci word
$f_{\infty}$ to locate the positions of the subwords of $f_{\infty,\infty}$.

###### keywords:

Fibonacci Words, Fibonacci Arrays, Tandems, Two-dimensional Factor Complexity,
Two-dimensional Morphic Words

###### keywords:

Two-dimensional Fibonacci words, Subwords, Conjugates of two-dimensional
words, Directed acyclic word graph.

##  1 Introduction

Let $w$ be finite/infinite word over an alphabet $\Sigma$. The details about
the subwords (otherwise called, the factors) of $w$ would be of considerable
use for a better understanding of the structure and characteristics of $w$.
The number of factors and the periodic/primitive nature of the word $w$ are
closely related and are in general analysed simultaneously. Any additional
information about the factors of $w$ can help in the
factorization/decomposition of $w$. In turn, factorizations like Lyndon,
Ziv–Lempel and Crochemore are used in text compression algorithms [6, 16].

Fibonacci words (more generally Sturmian words) are simple morphic words. By
simple, we mean that the morphisms defining these words are short and are
easily conceivable. Also, it is known that, for infinite words $w$, which are
not ultimately periodic, $p_{n}(w)\geq n+1$, where $p_{n}(w)$ is the number of
factors of length $n$ of $w$ [4]. It is interesting to note that Sturmian
words are a class of aperiodic infinite words that achieve the least possible
$p_{n}$ value, namely $n+1$ [21].

Generating the Fibonacci words over $\\{0,1\\}$ can be systematically achieved
either by the famous Fibonacci morphism, $\phi(1)=10$, $\phi(0)=1$ [21] or by
recursive constructions like $f_{0}=0,f_{1}=1,f_{n}=f_{n-1}f_{n-2},n\geq 2$
[8, 9, 10]. Infinite iterations of the Fibonacci morphism or the recursion,
generates the infinite Fibonacci word $f_{\infty}=10110101\ldots$. Some
remarkable properties of $f_{n}$ and $f_{\infty}$ are: (i) $f_{\infty}$
contains no fourth power, (ii) if a word $u^{2}$ is a factor of $f_{\infty}$,
then $u$ is a conjugate of some finite Fibonacci word, (iii) The finite
Fibonacci words are primitive [4, 1].

With a minimum number of subwords of any particular length, it is no wonder
that the subwords repeat more often in $f_{\infty}$ [11, 31, 24]. There are a
few interesting systematic ways to list these subwords. In [4], subwords of
length $k$ are used to list the subwords of length $k+1$. In [26], a directed
acyclic word graph ($DAWG$) is used to analyse the subwords. In [11], the
suffixes of the conjugates of a specific conjugate of a finite Fibonacci word
is used to find all the factors of a given length.

As a natural extension to the one-dimensional words, two-dimensional words are
studied [14, 25, 27]. (We will interchangeably use $1D$ for one-dimensional
and $2D$ for two-dimensional, hereafter in this article.) Two-dimensional
words finding some useful applications in image processing, data compression
and crystallography is another push for exploring two-dimensional words. In
[3], $2D$ Fibonacci words, $f_{m,n},m,n\geq 0$, are introduced to show that
they attain the general upper bound for the number of occurrences of a
particular type of tandem. In [19, 22], a few combinatorial and palindromic
properties of $f_{m,n}$ are studied. In [28], the authors obtain
$f_{\infty,\infty}$, the $2D$ infinite Fibonacci word, using a $2D$ morphism.
Further, they count the number of tandems occurring in it.

In this paper, we list all the subwords of a given size $(k,l),k,l\geq 1$ of
the $2D$ infinite Fibonacci word $f_{\infty,\infty}$. We systematically extend
the methods used in [26, 4, 11] for finding the subwords of $f_{\infty}$, to
$f_{\infty,\infty}$. The remaining of the paper is organized as follows. In
section 2, all the required definitions and notions are elaborated. In section
3, a $DAWG$ for $f_{\infty,\infty}$ is constructed and the subwords of
$f_{\infty,\infty}$ are enumerated. The method explained in section 4, uses
the subwords of size $(k,l)$ to find the subwords of size $(k+1,l+1)$. In
section 5, given a $k\geq 2$ and a $l\geq 2$, to list all the subwords of size
$(k,l)$, conjugates of a special conjugate of $f_{m,n}$ ($m,n$ depend on
$k,l$) are used. Section 7 has concluding remarks and a few future directions.

##  2 Preliminaries

###  2.1 One-dimensional Words

In formal language theory, $\Sigma$, an alphabet is a finite set of symbols
and $\Sigma^{*}$ is the free monoid generated by $\Sigma$. The elements of
$\Sigma^{*}$ are called words and are obtained by concatenating symbols from
$\Sigma$. The neutral element of $\Sigma^{*}$ is the empty word (denoted by
$\lambda$) and we have $\Sigma^{+}=\Sigma^{*}-\\{\lambda\\}$. For a word
$u\in\Sigma^{*}$, $|u|$ called the length of the word is the number of letters
occurring in $u$. By definition, $|\lambda|=0$. Given a word $w\in\Sigma^{*}$,
$u\in\Sigma^{*}$ is a prefix (suffix, respectively) of $w$, if $w=uv$ ($w=vu$,
respectively) for some $v\in\Sigma^{*}$. The reversal of a word
$u=a_{1}a_{2}\cdots a_{n}$, $a_{i}\in\Sigma$, for $1\leq i\leq n$, is the word
$u^{R}=a_{n}\cdots a_{2}a_{1}$. A word $u$ is said to be a palindrome (or a
one-dimensional palindrome) if $u=u^{R}$.

A word $w$ is said to be primitive if $w=u^{n}$ implies $n=1$ and $w=u$. Note
that a power of a word is nothing but repeated concatenation of the word with
itself. That is $u^{n}$ is obtained by concatenating $u$ with itself $n$
number of times. For a detailed study of formal language theory and
combinatorics on words, the reader is referred to [20].

###  2.2 Two-dimensional Words

The concepts of formal language theory can be obviously extended to two
dimensions [14]. A two-dimensional word is called a picture or array and is a
rectangular array of symbols taken from $\Sigma$.

######  Definition 1.

[19] A $2D$ word $u=[u_{i,j}]_{1\leq i\leq m,1\leq j\leq n}$ of size $(m,n)$
over $\Sigma$ is a two-dimensional rectangular finite arrangement of letters:

$u=\begin{matrix}u_{1,1}&u_{1,2}&\cdots&u_{1,n-1}&u_{1,n}\\\
u_{2,1}&u_{2,2}&\cdots&u_{2,n-1}&u_{2,n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
u_{m-1,1}&u_{m-1,2}&\cdots&u_{m-1,n-1}&u_{m-1,n}\\\
u_{m,1}&u_{m,2}&\cdots&u_{m,n-1}&u_{m,n}\\\ \end{matrix}$

We denote the number of rows and columns of $u$ by $|u|_{\text{row}}$ and
$|u|_{\text{col}}$, respectively. An empty array, denoted by $\Lambda$ is an
array of size $(0,0)$. Note that the arrays of size $(m,0)$ and $(0,m)$ for
$m>0$ are not defined. The set of all arrays over $\Sigma$ including
$\Lambda$, is denoted by $\Sigma^{**}$ and $\Sigma^{++}$ will denote the set
of all non-empty arrays over $\Sigma$. Any subset of $\Sigma^{**}$ is called a
picture language.

To locate any position or region in an array, we require a reference system
[2]. Given an array $u$, the set of coordinates
$\\{1,2,\ldots,|u|_{\text{row}}\\}\times\\{1,2,\ldots,|u|_{\text{col}}\\}$ is
referred to as the domain of $u$. A subdomain or subarray of an array $u$
(that is, a factor of the $2D$ word $u$), denoted by
$u[(i,j),(i^{\prime},j^{\prime})]$, is the portion of $u$ located in the
region $\\{i,i+1,\ldots,i^{\prime}\\}\times\\{j,j+1,\ldots,j^{\prime}\\}$,
where $1\leq i\leq|u|_{\text{row}},1\leq j\leq|u|_{\text{col}}$.

Similar to the concatenation operation in one dimension, the column
concatenation and the row concatenation operations between two arrays are as
follows.

######  Definition 2.

[14] Let $u,v$ be arrays of sizes $(m_{1},n_{1})$ and $(m_{2},n_{2})$,
respectively with $m_{1},n_{1},m_{2},n_{2}>0$, over $\Sigma$. Then, the column
concatenation of $u$ and $v$, denoted by $\obar$, is a partial operation,
defined if $m_{1}=m_{2}=m$, and is given by

$u\obar
v=\begin{matrix}u_{1,1}&\cdots&u_{1,n_{1}}&v_{1,1}&\cdots&v_{1,n_{2}}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
u_{m,1}&\cdots&u_{m,n_{1}}&v_{m,1}&\cdots&v_{m,n_{2}}\end{matrix}.$

Similarly, the row concatenation of $u$ and $v$, denoted by $\ominus$, is
another partial operation, defined if $n_{1}=n_{2}=n$, and is given by

$u\ominus v=\begin{matrix}u_{1,1}&\cdots&u_{1,n}\\\ \vdots&&\vdots\\\
u_{m_{1},1}&\cdots&u_{m_{1},n}\\\ v_{1,1}&\cdots&v_{1,n}\\\ \vdots&&\vdots\\\
v_{m_{2},1}&\cdots&v_{m_{2},n}\end{matrix}.$

The column and row concatenation of $u$ and the empty array $\Lambda$ are
always defined and $\Lambda$ is a neutral element for both the operations.

For a $u\in\Sigma^{**}$, an array $v\in\Sigma^{**}$ is said to be a prefix of
$u$ $($suffix of $u$, respectively$)$, if $u=(v\ominus x)\obar y$
$(u=y\obar(x\ominus v)$, respectively$)$ for some $x,y\in\Sigma^{**}$. If
$x\in\Sigma^{++}$, then by $(x^{k_{1}\obar})^{k_{2}\ominus}$ we mean that the
array is constructed by repeating $x$, $k_{1}$ times column-wise and
$x^{k_{1}\obar}$, $k_{2}$ times row-wise. An array $w\in\Sigma^{++}$ is said
to be 2D primitive if $w=(x^{k_{1}\obar})^{k_{2}\ominus}$ implies that
$k_{1}k_{2}=1$ and $w=x$ [13].

###  2.3 Fibonacci Words

Fibonacci words are closely related with the Fibonacci numbers. Recall the
recursive definition of the Fibonacci numerical sequence: $F(0)=1$, $F(1)=1$,
$F(n)=F(n-1)+F(n-2)$ for $n\geq 2$. Likewise, for $\Sigma=\\{a,b\\}$, the
sequence $\\{f_{n}\\}_{n\geq 0}$ of Fibonacci words, is defined recursively by
$f_{0}=a$, $f_{1}=b$, $f_{n}=f_{n-1}f_{n-2}$ for $n\geq 2$. First few words of
this sequence are: $f_{0}=a,f_{1}=b,f_{2}=ba,f_{3}=bab,f_{4}=babba$. Note that
$|f_{n}|=F(n)$ for $n\geq 0$. The sequence of Fibonacci words can be obtained
by iterating the Fibonacci morphism $\phi:\Sigma^{*}\rightarrow\Sigma^{*}$
defined by $\phi(a)=b,\phi(b)=ba$. Infinite number of iterations of $\phi$
produces the $1D$ infinite Fibonacci word $f_{\infty}$. That is,

$\lim_{n\to\infty}\phi^{n}(b)=f_{\infty}=babbabab\ldots.$

Through out this paper, we use $f_{\infty}^{s_{1},s_{2}}$ to denote the $1D$
infinite Fibonacci word $s_{1}s_{2}s_{1}s_{1}s_{2}\ldots$ over the alphabet
$\\{s_{1},s_{2}\\}$. Similarly, $f_{n}^{s_{1},s_{2}}$ denotes the $1D$ finite
Fibonacci word $s_{1}s_{2}s_{1}s_{1}s_{2}\ldots s_{1}s_{2}$ or
$s_{1}s_{2}s_{1}s_{1}s_{2}\ldots s_{2}s_{1}$ accordingly $n$ is even or odd.

The extension of $1D$ Fibonacci words to $2D$ Fibonacci words is presented in
[3].

######  Definition 3.

[3] Let $\Sigma=\\{a,b,c,d\\}$. The sequence of Fibonacci arrays,
$\\{f_{m,n}\\}$ where $m,n\geq 0$, is defined as:

  1. 1.

$f_{0,0}=\beta,f_{0,1}=\gamma,f_{1,0}=\delta,f_{1,1}=\alpha$ where
$\alpha,\beta,\gamma$ and $\delta$ are symbols from $\Sigma$ with some but not
all, among $\alpha,\beta,\gamma$ and $\delta$ might be identical.

  2. 2.

For $k\geq 0$ and $m,n\geq 1$,

$f_{k,n+1}=f_{k,n}\obar f_{k,n-1},\hskip 5.69046ptf_{m+1,k}=f_{m,k}\ominus
f_{m-1,k}.$

For convenience, let us fix $f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$, where
some but not all of $a,b,c$ and $d$ might be identical. For example, let us
derive the $2D$ Fibonacci word $f_{2,2}$ [19].

$f_{2,2}=f_{1,2}\ominus f_{0,2}=(f_{1,1}\obar f_{1,0})\ominus(f_{0,1}\obar
f_{0,0}).$

It can also be obtained by column-wise expansion,

$f_{2,2}=f_{2,1}\obar f_{2,0}=(f_{1,1}\ominus f_{0,1})\obar(f_{1,0}\ominus
f_{0,0}).$

Using the $f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$, $f_{2,2}$ is given by

$f_{2,2}=\>\begin{matrix}f_{1,1}&f_{1,0}\\\
f_{0,1}&f_{0,0}\end{matrix}\>=\>\begin{matrix}d&c\\\ b&a\end{matrix}.$

We state here some properties of $f_{m,n}$ which we would use later in our
proofs.

######  Lemma 1.

[19] Let $f_{m,n},(m,n=0,1,2,\dotsc)$ be the sequence of $2D$ Fibonacci arrays
over $\Sigma=\\{a,b,c,d\\}$, with $f_{0,0}=a,f_{0,1}=b,f_{1,0}=c,f_{1,1}=d$.
Also let $\Sigma_{1}=\\{a,b\\}$, $\Sigma_{2}=\\{c,d\\}$,
$\Sigma_{1}^{\prime}=\\{a,c\\}$ and $\Sigma_{2}^{\prime}=\\{b,d\\}$ such that
$\Sigma=\Sigma_{1}\cup\Sigma_{2}=\Sigma_{1}^{\prime}\cup\Sigma_{2}^{\prime}$.
Then,

  * a.

any row of $f_{m,n}$ is a $1D$ Fibonacci word over either $\Sigma_{1}$ or
$\Sigma_{2}$.

  * b.

if $\Sigma_{1}\neq\Sigma_{2}$ then all the rows of $f_{m,n}$, over
$\Sigma_{1}$ are identical and all the rows of $f_{m,n}$, over $\Sigma_{2}$
are identical.

  * c.

any column of $f_{m,n}$ is a $1D$ Fibonacci word over either
$\Sigma_{1}^{\prime}$ or $\Sigma_{2}^{\prime}$.

  * d.

if $\Sigma_{1}^{\prime}\neq\Sigma_{2}^{\prime}$ then all the columns of
$f_{m,n}$, over $\Sigma_{1}^{\prime}$ are identical and all the columns of
$f_{m,n}$, over $\Sigma_{2}^{\prime}$ are identical.

  * e.

if $\Sigma_{1}=\Sigma_{2}(\Sigma_{1}^{\prime}=\Sigma_{2}^{\prime})$, then
either all the rows$($columns$)$ of $f_{m,n}$ are identical or a set of rows
are identical and are complementary to the set of remaining rows $($columns,
respectively$)$ which are identical.

###  2.4 The $2D$ Infinite Fibonacci Word, $f_{\infty,\infty}$

The sequence of $2D$ finite Fibonacci words, $\\{f_{m,n}\\}_{m,n\geq 0}$, in a
sense, has the $2D$ infinite Fibonacci word, $f_{\infty,\infty}$, as its
limit. This can be perceived by extending each row, column of any $f_{m,n}$,
$m,n\geq 2$, to the $1D$ infinite Fibonacci word over the alphabet of the word
present in that row, column. But this outlook is informal. Formally, in [28],
the authors have defined the $2D$ infinite Fibonacci word through the $2D$
morphism,

$\mu:~{}~{}d\rightarrow\begin{matrix}d&c\\\
b&a\end{matrix},~{}~{}c\rightarrow\begin{matrix}d\\\
b\end{matrix},~{}~{}b\rightarrow\begin{matrix}d&c\end{matrix},~{}~{}~{}a\rightarrow
d.$ (1)

For a detailed study of multidimensional morphisms, [7] can be referred.

Observe that the morphism defined by (1) is prolongable on $d$ and infinite
number of iterations of $\mu$ on $d$ produces $f_{\infty,\infty}$ [28]. That
is to say, $f_{\infty,\infty}$ is the fixed point of the morphism $\mu$. That
is,

$f_{\infty,\infty}=\lim_{n\rightarrow+\infty}\mu^{n}(d)=\mu^{\omega}(d).$

First few iterations of $\mu$ on $d$ are shown below.

$d\rightarrow\begin{matrix}d&c\\\
b&a\end{matrix}\rightarrow\begin{matrix}d&c&d\\\ b&a&b\\\
d&c&d\end{matrix}\rightarrow\begin{matrix}d&c&d&d&c\\\ b&a&b&b&a\\\
d&c&d&d&c\\\ d&c&d&d&c\\\ b&a&b&b&a\\\
\end{matrix}\rightarrow\cdots\rightarrow\begin{matrix}d&c&d&d&c&d&c&d&\cdots\\\
b&a&b&b&a&b&a&b&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\
b&a&b&b&a&b&a&b&\cdots\\\ d&c&d&d&c&d&c&d&\cdots\\\ b&a&b&b&a&b&a&b&\cdots\\\
d&c&d&d&c&d&c&d&\cdots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{matrix}$

As $f_{\infty,\infty}$ is the limit of $\\{f_{m,n}\\}_{m,n\geq 0}$, all the
properties listed in Lemma 1, hold true for $f_{\infty,\infty}$ also.

##  3 Enumeration Using Subword Graphs

In [26] the authors have given a way to identify the subwords of $f_{\infty}$
using a directed acyclic graph.

The directed acyclic word graph of a word $w$, $DAWG(w)$, is the smallest
finite state automaton that recognizes all the suffixes of the word [5].
$CDAWG(w)$, a space efficient variant of $DAWG(w)$, is obtained by compacting
$DAWG(w)$ [12].

In [26], the subwords of $f_{\infty}$ are analysed through the graph
$\mathcal{G}_{\infty}$, which is, in a certain sense, a $DAWG$ of
$f_{\infty}=abaababb\ldots=f_{\infty}(1,2,3,\ldots)$. The $DAWG$ is
constructed as below:

Let $F(0)=1,F(1)=2,F(n)=F(n-1)+F(n-2)$, for $n\geq 2$, be the Fibonacci
sequence. The nodes of $\mathcal{G}_{\infty}$ are all non-negative integers.
For $i>0$, with $F(i)$ being the $i^{th}$ Fibonacci number, the labelled edges
of $\mathcal{G}_{\infty}$ are

$\displaystyle(i-1)\xrightarrow[]{f_{\infty}(i)}i,\quad
F(i)-2\;\xrightarrow[]{\;s\;}\;F(i+1)-1$

where $s=a$ whenever $i$ is even and $s=b$ whenever $i$ is odd (Refer Fig. 1).

Figure 1: DAWG, $\mathcal{G}_{\infty}$ of $f_{\infty}^{a,b}$

###  3.1 Cross Product of $DAWG$s

As the $2D$ finite Fibonacci words, $f_{m,n}$, can be obtained by the
Cartesian product of Fibonacci reduced representation of the integers $m,n$
[19], a natural extension of $\mathcal{G}_{\infty}$ for the $2D$ infinite
Fibonacci word will be the Cartesian product of $\mathcal{G}_{\infty}$ with
itself.

######  Definition 4.

[32] The Cartesian product of G and H, written $G\,\square\,H$, is the graph
with vertex set $V(G)\times V(H)$ specified by putting $(u,v)$ adjacent to
$(u^{\prime},v^{\prime})$ if and only if $(1)u=u^{\prime}$ and $vv^{\prime}\in
E(H)$, or $(2)v=v^{\prime}$ and $uu^{\prime}\in E(G)$.

Since $f_{\infty,\infty}$ has two distinct rows (one over $\\{d,c\\}$ and one
over $\\{b,a\\}$) [22], to obtain a $DAWG$ of $f_{\infty,\infty}$, we slightly
modify the labels of $\mathcal{G}_{\infty}$. Note that, all the rows of
$f_{\infty,\infty}$ are $f_{\infty}$ only. In fact the rows over $\\{d,c\\}$
would be $dcddcdcd\ldots$ and the rows over $\\{b,a\\}$ would be
$babbabab\ldots$. In order to simultaneously control these two categories of
rows/words, we will use a single $DAWG$, the $DAWG$ of the Fibonacci word
$DCDDCDCD\ldots$, with $D=\\{d,b\\}$ and $C=\\{c,a\\}$. With this adaptation,
$D$ is allowed to assume either $d$ or $b$ and $C$ is allowed to assume either
$c$ or $a$. As the rows of $f_{\infty,\infty}$ are words over a binary
alphabet, we also impose an additional condition that, if $D$ assumes $d$ then
$C$ would assume $c$ and if $D$ assumes $b$ then $C$ would assume $a$. This
$DAWG$, say "$\mathcal{G}_{\infty}$ for rows", is depicted at the top, in Fig.
2. In the graph, for convenience, we have written $D=\\{d,b\\}$ and
$C=\\{c,a\\}$ as ‘$d,b$’and ‘$c,a$’, respectively.

Figure 2: The Cartesian product of $\mathcal{G}_{\infty}$ for columns and
$\mathcal{G}_{\infty}$ for rows

Similarly, since $f_{\infty,\infty}$ has two distinct columns (one over
$\\{d,b\\}$ and one over $\\{c,a\\}$) [22], to manage both the type of columns
through a single $DAWG$, we consider the $DAWG$ of the Fibonacci word
$D^{\prime}BD^{\prime}D^{\prime}BD^{\prime}BD^{\prime}\ldots$, where
$D^{\prime}=\\{d,c\\}$ and $B=\\{b,a\\}$, implying $D^{\prime}$ can be either
$d$ or $c$, and $B$ can be either $b$ or $a$, with an additional condition
that, if $D^{\prime}$ is $d$ then $B$ would be $b$ and if $D^{\prime}$ is $c$
then $B$ would be $a$. Again, in the graph, for convenience we write only
‘$d,c$’ and ‘$b,a$’ (without the curly braces). This $DAWG$, say
"$\mathcal{G}_{\infty}$ for columns", is depicted at the left, in Fig. 2.

Now we obtain the Cartesian product of "$\mathcal{G}_{\infty}$ for columns"
and "$\mathcal{G}_{\infty}$ for rows". Note that, when $G$ and $H$ are
labelled, the labels are carried over to the edges of the Cartesian product
appropriately. The resulting graph is given in Fig. 2.

Since $1D$ words have only one direction, one can get all the letters of a
subword by traversing along a directed path (starting at the root) of their
$DAWG$s. But in the $DAWG$s of $2D$ words (if they exist), to get all the
letters in a subword, all the edges that lie between the root and any node
that lie in a different column/row may have to be traversed. Clearly, this is
not possible as the intended $DAWG$ (that is, the Cartesian product) is
acyclic and also prevents any back-and-forth traversals.

But the structure of $2D$ Fibonacci words is such that, for a subword $u$ of
$f_{\infty,\infty}$, the knowledge of any one row and any one column of $u$ is
enough to write down the entire $u$. Due to this, the Cartesian product will
serve as the $DAWG$ of $f_{\infty,\infty}$. Further, since it is enough to
know just a row and a column of $u$, even the Cartesian product is redundant
and we need only the "rooted product" of "$\mathcal{G}_{\infty}$ for rows" and
"$\mathcal{G}_{\infty}$ for columns".

###  3.2 Rooted Product of $DAWG$s

######  Definition 5.

[18] The rooted product of a graph $G$ and a rooted graph $H$, denoted by
$G\circ H$, is defined as follows$:$ take $|V(G)|$ copies of $H$, and for
every vertex $v_{i}$ of $G$, identify $v_{i}$ with the root vertex of the
$i^{th}$ copy of $H$.

In other words if the vertex set of $G$ is $\\{g_{1},\ldots,g_{n}\\}$ and the
vertex set of $H$ is $\\{h_{1},\ldots,h_{m}\\}$ with $h_{1}$ as its root, then
the vertex set, $V$ and the edge set, $E$ of $G\circ H$ will be as below.

$\displaystyle V$ $\displaystyle=\\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq
m\\}$ $\displaystyle E$ $\displaystyle=E_{1}\cup E_{2}\quad\text{where,}$
$\displaystyle E_{1}$
$\displaystyle=\\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\in E(G)\\},$
$\displaystyle E_{2}$
$\displaystyle=\bigcup_{i=1}^{n}\\{((g_{i},h_{j}),(g_{i},h_{k})):(h_{j},h_{k})\in
E(H)\\}$

In fact, it is easy to see that, $G\circ H$ is a subgraph of $G\square H$.

Now, we take the "rooted product" of "$\mathcal{G}_{\infty}$ for rows" and
"$\mathcal{G}_{\infty}$ for columns" (Refer Fig. 3) to get the $DAWG$ of
$f_{\infty,\infty}$ and denote it by $\mathcal{G}_{\infty,\infty}$. From
$\mathcal{G}_{\infty,\infty}$, we can obtain the first row and the last column
of any subword of $f_{\infty,\infty}$. We designate the node $(0,0)$ as the
root node of $\mathcal{G}_{\infty,\infty}$.

Figure 3: DAWG, $\mathcal{G}_{\infty,\infty}$ of $f_{\infty,\infty}$:
($\mathcal{G}_{\infty}$ for rows) $\circ$ ($\mathcal{G}_{\infty}$ for columns)

###  3.3 Enumerating the subwords: The $DAWG$ way

In this subsection, we prove that the number of finite paths in
$\mathcal{G}_{\infty,\infty}$, starting at its root node, equals the number of
subwords of $f_{\infty,\infty}$. In particular, we prove that, for $k,l\geq
1$, a path of length $k+l$ , comprising of a horizontal path of length $k$ and
a vertical path of length $l$, will lead to subword of $f_{\infty,\infty}$ of
size $(k,l)$. Note that by a horizontal path (a vertical path, respectively),
we mean a path whose adjacent vertices are in $\mathcal{G}_{\infty}$ for rows
($\mathcal{G}_{\infty}$ for columns, respectively).

######  Theorem 1.

Let $k,l\in\mathbb{N}$ be given. Then, from a path of length $k+l$ (starting
at the root) in $\mathcal{G}_{\infty,\infty}$, comprising of a horizontal path
of length $l$ and a vertical path of length $k$, we can construct a subword of
$f_{\infty,\infty}$ of size $(k,l)$.

###### Proof.

Due to the construction of $\mathcal{G}_{\infty,\infty}$, when we start at the
root and traverse a horizontal path of length $l\geq 1$, we get a subword of
the $1D$ Fibonacci infinite word $DCDDCDCD\ldots$. In fact, we can obtain two
horizontal subwords of length $l$, one over $\\{d,c\\}$ (obtained by taking
$d$ for $D$ and $c$ for $C$) and one over $\\{b,a\\}$ (obtained by taking $b$
for $D$ and $a$ for $C$). The former subword occurs in any row of
$f_{\infty,\infty}$ which is over $\\{d,c\\}$, and the later occurs in any row
of $f_{\infty,\infty}$ which is over $\\{b,a\\}$.

Now, starting from the last node of this horizontal path, we traverse a
vertical path of length $k$. Note that, the rooted product guarantees such a
path. Similar to the earlier argument, here we obtain a vertical path of
length $k\geq 1$, which corresponds to a subword of length $k$ of the $1D$
Fibonacci infinite word
$D^{\prime}BD^{\prime}D^{\prime}BD^{\prime}BD^{\prime}\ldots$. Here also we
can obtain two vertical subwords of length $k$, one over $\\{d,b\\}$ (obtained
by taking $d$ for $D^{\prime}$ and $b$ for $B$) and one over $\\{c,a\\}$
(obtained by taking $c$ for $D^{\prime}$ and $a$ for $B$). The former subword
occurs in any column of $f_{\infty,\infty}$ which is over $\\{d,b\\}$, and the
later occurs in any column of $f_{\infty,\infty}$ which is over $\\{c,a\\}$.

To prove that these two paths can produce a unique subword of size $(k,l)$ of
$f_{\infty,\infty}$, we use the fact that ‘the last letter in the first row
and the first letter in the last column of a $2D$ word are the same’. Hence,
while constructing the subword, the last letter (say "$s_{joint}$") in the
horizontal path has to be the first letter in the vertical path. For example,
out of the two available subwords of length $l$, suppose we select the subword
over $\\{d,c\\}$, say $H$, and if $s_{joint}$ $=d$ ($s_{joint}$ $=c$,
respectively), then we will(have to) select the vertical subword , say $V$,
over $\\{d,b\\}$ ($\\{c,a\\}$, respectively). Now, by taking $H$ and $V$ as
the first row and the last column, respectively, in a $2D$ word of size
$(k,l)$, we will obtain the entire subword. Again note that, this is not
possible for all $2D$ words, but for $f_{\infty,\infty}$, due to its
structure.

As any row of $f_{\infty,\infty}$ is either over $\Sigma_{1}=\\{a,b\\}$ or
$\Sigma_{2}=\\{c,d\\}$, $s_{joint}$ has to be either in $\Sigma_{1}$ or in
$\Sigma_{2}$. As any column of $f_{\infty,\infty}$ is either over
$\Sigma_{1}^{\prime}=\\{a,c\\}$ or $\Sigma_{2}^{\prime}=\\{b,d\\}$, $V$ has to
be either in $\Sigma_{1}^{\prime}$ or in $\Sigma_{2}^{\prime}$. Hence the
following four cases only arise.

Case (i) | : |  $s_{joint}$ $=a$ (then, $V$ will be over $\\{a,c\\}$)
---|---|---
Case (ii) | : |  $s_{joint}$ $=b$ (then, $V$ will be over $\\{b,d\\}$)
Case (iii) | : |  $s_{joint}$ $=c$ (then, $V$ will be over $\\{a,c\\}$)
Case (iv) | : |  $s_{joint}$ $=d$ (then, $V$ will be over $\\{b,d\\}$)

To find the letters occurring at the other positions of $u$ we define two
substitutions. If $H$ is over $\\{a,b\\}$, we create a $1D$ word $H^{\prime}$
from $H$ using the substitution $\theta_{1}:\theta_{1}(a)=c,\theta_{1}(b)=d$.
If $H$ is over $\\{c,d\\}$, we create a $1D$ word $H^{\prime\prime}$ from $H$
using the substitution $\theta_{2}:\theta_{2}(c)=a,\theta_{2}(d)=b$. These
words $H^{\prime}$ and $H^{\prime\prime}$ will be used to fill up/find the
other rows of the subword we are constructing. These substitutions are
motivated by the fact that, a row of $f_{\infty,\infty}$ over $\\{a,b\\}$ can
be obtained from a row of $f_{\infty,\infty}$ over $\\{c,d\\}$ and vice-versa
through simple substitutions.

Let $R_{1},R_{2},R_{3},\ldots,R_{k}$ be the $k$ rows of the subword being
constructed. Note that $R_{1}=H$. Now, for $2\leq j\leq k$,

Case(i): $s_{joint}$ $=a$ (and hence $H$ is over $\\{a,b\\}$)

If the letter in the $j^{th}$ row of $V$ is $s_{joint}$, then $R_{j}=H$ else
$R_{j}=H^{\prime}$.

Case(ii): $s_{joint}$ $=b$ (and hence $H$ is over $\\{a,b\\}$)

If the letter in the $j^{th}$ row of $V$ is $s_{joint}$, then $R_{j}=H$ else
$R_{j}=H^{\prime}$.

Case(iii): $s_{joint}$ $=c$ (and hence $H$ is over $\\{c,d\\}$)

If the letter in the $j^{th}$ row of $V$ is $s_{joint}$, then $R_{j}=H$ else
$R_{j}=H^{\prime\prime}$.

Case(iv): $s_{joint}$$=d$ (and hence $H$ is over $\\{c,d\\}$)

If the letter in the $j^{th}$ row of $V$ is $s_{joint}$, then $R_{j}=H$ else
$R_{j}=H^{\prime\prime}$.

Note that while constructing the subword, the alphabet of each row and the
order in which the two distinct rows ($H$ and $H^{\prime}$ (or) $H$ and
$H^{\prime\prime}$) of the subword are getting arranged are decided/guided by
$V$. Since $V$ is a subword of length $l$ of some column of
$f_{\infty,\infty}$, the obtained $2D$ word is a subword of
$f_{\infty,\infty}$ of size $(k,l)$. ∎

######  Remark 1.

Theorem 1 can be proved by taking "rooted product" of "$\mathcal{G}_{\infty}$
for columns" and "$\mathcal{G}_{\infty}$ for rows". In that case, first we
have to traverse a vertical path of length $k$, then a horizontal path of
length $l$ to obtain the first column and the last row of the subword in that
order. Finding the other rows can be done similar to the process explained in
the proof.

######  Remark 2.

Since we constructed $\mathcal{G}_{\infty,\infty}$ as the "rooted product" of
"$\mathcal{G}_{\infty}$ for rows" by "$\mathcal{G}_{\infty}$ for columns", we
will always use a horizontal edge (an edge of $\mathcal{G}_{\infty}$ for rows)
at first. Also, as $l\geq 1$, we will never use the copy of
$\mathcal{G}_{\infty}$ for columns rooted at $(0,0)$. Hence we can remove this
redundant copy from $\mathcal{G}_{\infty,\infty}$ and can still entitle the
new graph $\mathcal{G}_{\infty,\infty}$.

######  Remark 3.

The $DAWG$ also can be constructed by a similar methodology as given in [26].
Let

$f_{row,\infty}=DCDDCDCD\ldots=f_{row,\infty}(1,2,3,\ldots),$
$f_{col,\infty}=D^{\prime}BD^{\prime}D^{\prime}BD^{\prime}BD^{\prime}\ldots=f_{col,\infty}(1,2,3,\ldots)$

where $D,C,D^{\prime}$ and $B$ are as defined earlier. The nodes of
$\mathcal{G}_{\infty,\infty}$ are all non-negative integer pairs,
$(i,j),i,j\geq 0$.

For $j>0$, with $F(j)$ being the $j^{th}$ Fibonacci number, the labelled edges
of $\mathcal{G}_{\infty,\infty}$ are

$\displaystyle(0,j-1)\xrightarrow[]{f_{row,\infty}(j)}(0,j),\quad(0,F(j)-2)\;\xrightarrow[]{\;s\;}\;(0,F(j+1)-1)$

where $s=D$ whenever $j$ is even and $s=C$ whenever $j$ is odd, and

for each $j\geq 0$ ($j\geq 1$ is suffice; refer Remark 2) and $i>0$,

$\displaystyle(i-1,j)\xrightarrow[]{f_{col,\infty}(i)}(i,j),\quad(F(i)-2,j)\;\xrightarrow[]{\;s\;}\;(F(i+1)-1,j)$

where $s=D^{\prime}$ whenever $i$ is even and $s=B$ whenever $i$ is odd.

######  Corollary 1.

For $k,l\geq 1$, there are $(k+1)(l+1)$ subwords of size $(k,l)$ in
$f_{\infty,\infty}$.

###### Proof.

As the graph "$\mathcal{G}_{\infty}$ for rows" is the $DAWG$ of the $1D$
Fibonacci word $DCDDC\ldots$, there are $(l+1)$ number of horizontal paths in
"$\mathcal{G}_{\infty,\infty}$ for rows" [26]. Since the graph
"$\mathcal{G}_{\infty}$ for columns" is the $DAWG$ of the $1D$ Fibonacci word
$D^{\prime}BD^{\prime}D^{\prime}B\ldots$, from the last node of every
horizontal path, there are $(k+1)$ number of vertical paths available for
traversing. Note that, though paths with labels from $\\{D,C\\}$ and
$\\{D^{\prime},B\\}$ have two possibilities, due to the condition on
$s_{joint}$ (as explained in the proof of Theorem 1), only one path with
labels $\\{a,b,c,d\\}$ will materialize. Thus, there are $(k+1)(l+1)$ number
of paths of length $k+l$, comprising of a horizontal path of length $l$ and a
vertical path of length $k$. Now, by Theorem 1, a path of length $k+l$ in
$\mathcal{G}_{\infty,\infty}$, comprising of a horizontal path of length $l$
and a vertical path of length $k$, uniquely corresponds to a subword of size
$(k,l)$ of $f_{\infty,\infty}$. Hence the corollary. ∎

The following example will explain the construction used in the proof of
Theorem 1.

######  Example 1.

Let $k=2$ and $l=2$ so that all the subwords of size $(2,2)$ will be obtained.
By corollary 1, there will be $9$ subwords of this size. Construction of one
of these 9 subwords is explained here.

The horizontal paths of length $2$ in $DCDDC\ldots$ are $DC,DD$ and $CD$.
Suppose we select $d$ for $D$. Then $H$ can be any one of $\\{dc,dd,cd\\}$.
Let us choose $H$ as $cd$.

Now the vertical paths of length $2$ in
$D^{\prime}BD^{\prime}D^{\prime}B\ldots$ are $\begin{matrix}D^{\prime}\\\
B\end{matrix},\;\begin{matrix}D^{\prime}\\\ D^{\prime}\end{matrix}$ and
$\begin{matrix}B\\\ D^{\prime}\end{matrix}$. Since $s_{joint}$ = $d$, to have
a subword of $f_{\infty,\infty}$, the vertical path of length 2 should start
with $d$. By selecting $d$ for $D^{\prime}$ we have the three vertical paths
$\left\\{\begin{matrix}d\\\ b\end{matrix},\begin{matrix}d\\\
d\end{matrix},\begin{matrix}b\\\ d\end{matrix}\right\\}$.

Let us take $V=\begin{matrix}d\\\ b\end{matrix}$. Then the first column and
the last row of the subword are fixed. The incomplete subword is,
$\begin{matrix}c&d\\\ *&b\end{matrix}$, where the symbol ’$*$’ denotes the
entry therein is unknown yet.

Since $s_{joint}=d$ and the letter in the second row of $V$ is not a $d$, we
fill the second row with $H^{\prime\prime}=ab$. Hence the subword
corresponding to this path is $\begin{matrix}c&d\\\ a&b\end{matrix}$.

All the possible 9 cases of $H$, $V$ and their corresponding subwords are
listed in Tab. 1 .

Table 1: All the factors of size $(2,2)$ of $f_{\infty,\infty}$

H $dc$ $dc$ $dd$ $dd$ $cd$ $cd$ $ba$ $bb$ $ab$ V $\begin{matrix}c\\\
a\end{matrix}$ $\begin{matrix}c\\\ c\end{matrix}$ $\begin{matrix}d\\\
b\end{matrix}$ $\begin{matrix}d\\\ d\end{matrix}$ $\begin{matrix}d\\\
b\end{matrix}$ $\begin{matrix}d\\\ d\end{matrix}$ $\begin{matrix}a\\\
c\end{matrix}$ $\begin{matrix}b\\\ d\end{matrix}$ $\begin{matrix}b\\\
d\end{matrix}$ Incomplete $\begin{matrix}d&c\\\ *&a\end{matrix}$
$\begin{matrix}d&c\\\ *&c\end{matrix}$ $\begin{matrix}d&d\\\ *&b\end{matrix}$
$\begin{matrix}d&d\\\ *&d\end{matrix}$ $\begin{matrix}c&d\\\ *&b\end{matrix}$
$\begin{matrix}c&d\\\ *&d\end{matrix}$ $\begin{matrix}b&a\\\ *&c\end{matrix}$
$\begin{matrix}b&b\\\ *&d\end{matrix}$ $\begin{matrix}a&b\\\ *&d\end{matrix}$
Subword Complete $\begin{matrix}d&c\\\ b&a\end{matrix}$ $\begin{matrix}d&c\\\
d&c\end{matrix}$ $\begin{matrix}d&d\\\ b&b\end{matrix}$ $\begin{matrix}d&d\\\
d&d\end{matrix}$ $\begin{matrix}c&d\\\ a&b\end{matrix}$ $\begin{matrix}c&d\\\
c&d\end{matrix}$ $\begin{matrix}b&a\\\ d&c\end{matrix}$ $\begin{matrix}b&b\\\
d&d\end{matrix}$ $\begin{matrix}a&b\\\ c&d\end{matrix}$ Subword

##  4 Enumeration by Extension

In this section the basic methodology discussed in [4] for enumerating the
subwords of $1D$ infinite Fibonacci word is extended to $2D$ infinite
Fibonacci word. In [4], all the subwords of length $k$ of $f_{\infty}$ were
obtained from the subwords of length $(k-1)$ by properly extending them to the
right by one symbol (Refer Fig. 4). In $1D$, each subword of length $(k-1)$ ,
except one, will extend to one subword of length $k$. The exceptional subword
of length $(k-1)$ which produces two subwords of length $k$ is called
"special". In $2D$ also we will encounter a similar word.

######  Definition 6.

Let $f_{\infty}=abaab\ldots$ be the $1D$ Fibonacci word over $\\{a,b\\}$. A
factor $w$ of $f_{\infty}$ is called special if both $wa$ and $wb$ are factors
of $f_{\infty}$.

Figure 4: Extending subwords to the right (Special subwords are underlined)

Before constructing the subwords of $f_{\infty,\infty}$, let us define a
structure called "FRAME".

######  Definition 7.

Let $w$ be a $2D$ word. The structure obtained by considering only the first
row, the first column, the last row and the last column of $w$ is called the
FRAME of $w$. In particular, the first row (first column, last row, and last
column, respectively) is called $FRAME_{T}$ ($FRAME_{L}$, $FRAME_{B}$, and
$FRAME_{R}$, respectively).

Extending Definition 7, we can have the substructures $FRAME_{TL}$ (which
consists of $FRAME_{T}$ and $FRAME_{L}$), $FRAME_{TR}$, $FRAME_{LB}$ and
$FRAME_{RB}$. We will be predominantly using $FRAME_{TL}$ only. Note that
$FRAME_{T}$ and $FRAME_{L}$ share a common prefix of length one. We call this
common symbol $s_{joint,TL}$. Similarly $s_{joint,TR}$ is defined (Refer Fig.
5).

(a) $FRAME_{TL}$

(b) $FRAME_{TR}$

Figure 5: Two of the four substructures of $FRAME$

The following Lemma is inspired by the properties listed in Lemma 1. Note that
there are only two distinct rows in $f_{\infty,\infty}$. These distinct rows
also are one and the same words except that their respective alphabets are
different. Hence, given the entire first row and any one letter of another
row, say $R$, $R$ can be written down with ease using a substitution rule.

######  Lemma 2.

Given $FRAME_{TL}$ of a subword of $f_{\infty,\infty}$ with its $FRAME_{T}$
being a subword of length $l$ of $f_{\infty}^{a,b}$ or $f_{\infty}^{c,d}$ and
$FRAME_{L}$ being a subword of length $k$ of $f_{\infty}^{a,c}$ or
$f_{\infty}^{b,d}$, we can construct a subword of size $(k,l)$ of
$f_{\infty,\infty}$.

###### Proof.

Let $u$ be the $2D$ word whose $FRAME_{TL}$ is given. We will make use of the
two substitution rules defined in the proof of Theorem 1 to get the
corresponding subword of $f_{\infty,\infty}$.

If $FRAME_{T}$ is over $\\{a,b\\}$, then define
$\theta_{1}:\theta_{1}(a)=c,\theta_{1}(b)=d$. Now, for any row $i$, $2\leq
i\leq k$, of $FRAME_{L}$, if the letter present therein is $s_{joint,TL}$, the
$i^{th}$ row of $u$ is $FRAME_{T}$ itself; else, the $i^{th}$ row of $u$ is
$\theta_{1}(\textit{$FRAME_{T}$})$.

If $FRAME_{T}$ is over $\\{c,d\\}$, then define
$\theta_{2}:\theta_{2}(c)=a,\theta_{2}(d)=b$. Now, for any row $i$, $2\leq
i\leq k$, of $FRAME_{L}$, if the letter present therein is $s_{joint,TL}$, the
$i^{th}$ row of $u$ is $FRAME_{T}$ itself; else, the $i^{th}$ row of $u$ is
$\theta_{2}(\textit{$FRAME_{T}$})$.

As mentioned in the proof of Theorem 1, the rows other than $FRAME_{T}$ are
constructed using $FRAME_{L}$. That is the alphabet of a particular row and
the order in which the two distinct rows of the subword are arranged are
decided by $FRAME_{L}$. Since $FRAME_{L}$ is a subword of length $l$ of some
column of $f_{\infty,\infty}$, the obtained $2D$ word is a subword of
$f_{\infty,\infty}$ of size $(k,l)$.

∎

######  Remark 4.

In Lemma 2, we have constructed the entire subword from $FRAME_{TL}$.
Similarly, with appropriate conditions on $FRAME_{L}$, $FRAME_{T}$,
$FRAME_{R}$, $FRAME_{B}$, one can construct the entire subword from any of
$FRAME_{LB}$,$FRAME_{TR}$ and $FRAME_{RB}$ also.

######  Remark 5.

Given a $FRAME_{TL}$ such that its $FRAME_{L}$ and $FRAME_{T}$ are vertical
and horizontal subwords of length $k$ and $l$ respectively of
$f_{\infty,\infty}$ and if $s_{joint,{TL}}$ (and hence $FRAME_{TL}$) is
positioned at the position $(1,1)$ of $f_{\infty,\infty}$, then the subword
constructed from $FRAME_{TL}$ will be a prefix of size $(k,l)$ of
$f_{\infty,\infty}$.

We know that there are $(k+1)(l+1)$ subwords of size $(k,l)$ in
$f_{\infty,\infty}$ (Refer Preprint or previous section). In the following
theorem, we prove that given the $(k+1)(l+1)$ subwords of size $(k,l)$ of
$f_{\infty,\infty}$, we can extend them to get the $(k+2)(l+2)$ subwords of
size $(k+1,l+1)$.

######  Theorem 2.

Given the $(k+1)(l+1)$ subwords of size $(k,l)$ of $f_{\infty,\infty}$, by
appropriately extending each subword’s $FRAME_{T}$ to the right and
$FRAME_{L}$ to the bottom, we can obtain all the $(k+2)(l+2)$ subwords of size
$(k+1,l+1)$ of $f_{\infty,\infty}$.

###### Proof.

Let $u$ be a subword of size $(k,l)$ of $f_{\infty,\infty}$.

Since $f_{\infty,\infty}$ has only two distinct rows (refer Lemma 1),
$FRAME_{T}$ of $u$ will be either over $\\{a,b\\}$ or over $\\{c,d\\}$. Also,
a row of $f_{\infty,\infty}$ which is over $\\{a,b\\}$ ($\\{c,d\\}$,
respectively), is nothing but the $1D$ Fibonacci word generated by the
morphism $b\rightarrow ba,a\rightarrow b$ ($d\rightarrow dc,c\rightarrow d$,
respectively). Thus, if $FRAME_{T}$ of $u$ is over $\\{a,b\\}$ ($\\{c,d\\}$,
respectively), the first row of $u$ is nothing but a factor of length $l$ of
the infinite Fibonacci word, $f_{\infty}^{b,a}=babba\ldots$
($f_{\infty}^{d,c}=dcddc\ldots$, respectively). So, $FRAME_{T}\in H$, where
$H$ is the union of the $l+1$ subwords of length $l$ of
$f_{\infty}^{b,a}$(with one out of them being special) and the $l+1$ subwords
of length $l$ of $f_{\infty}^{d,c}$ (with one out of them being special). Note
that, $|H|=2(l+1)$.

Similarly, a column of $f_{\infty,\infty}$ which is over $\\{b,d\\}$
($\\{a,c\\}$, respectively), can be perceived as a $1D$ Fibonacci word
generated by the morphism $d\rightarrow db,b\rightarrow d$ ($c\rightarrow
ca,a\rightarrow c$, respectively). Thus, if $FRAME_{L}$ of $u$ is over
$\\{b,d\\}$ ($\\{a,c\\}$, respectively), the first column of $u$ is nothing
but a factor of length $k$ of the infinite Fibonacci word,
$f_{\infty}^{d,b}=dbddb\ldots$ ($f_{\infty}^{c,a}=cacca\ldots$, respectively).
So, $FRAME_{L}\in V$, where $V$ is the union of the $k+1$ subwords of length
$k$ of $f_{\infty}^{d,b}$(with one out of them being special) and the $k+1$
subwords of length $k$ of $f_{\infty}^{c,a}$ (with one out of them being
special). Note that, $|V|=2(k+1)$.

Now let us construct a subword of size $(k+1,l+1)$ from $u$. Consider
$FRAME_{TL}$ of $u$. We encounter the following four types of $FRAME_{TL}$s.

$Type(i)$ | : | The word in $FRAME_{T}$ and the word in $FRAME_{L}$ both are not special
---|---|---
$Type(ii)$ | : | The word in $FRAME_{T}$ is not special and the word in $FRAME_{L}$ is special
$Type(iii)$ | : | The word in $FRAME_{T}$ is special and the word in $FRAME_{L}$ is not special
$Type(iv)$ | : | The word in $FRAME_{T}$ and the word in $FRAME_{L}$ both are special

Let _$Alph_{T}$_ $=$ Alphabet of $FRAME_{T}$ and let _$Alph_{L}$_ $=$ Alphabet
of $FRAME_{L}$.

In $Type(i)$, we can extend $FRAME_{T}$ to the right by appending one
appropriate letter from _$Alph_{T}$_ and can extend $FRAME_{L}$ to the bottom
by appending one appropriate letter from _$Alph_{L}$_. Thus we get
$FRAME_{TL}^{new}$ with a new $FRAME_{L}$, say $FRAME_{L}^{new}$, with $(k+1)$
rows, and a new $FRAME_{T}$, say $FRAME_{T}^{new}$, with $(l+1)$ columns. Note
that, by the way $FRAME_{TL}$ is extended to $FRAME_{TL}^{new}$,
$FRAME_{TL}^{new}$ will be $FRAME_{TL}$ of a subword of size $(k+1,l+1)$ of
$f_{\infty,\infty}$. Now by Lemma 2, we can construct the subword of size
$(k+1)(l+1)$ corresponding to this $FRAME_{TL}^{new}$.

In $Type(ii)$, we can extend $FRAME_{T}$ to the right by appending one
appropriate letter from _$Alph_{T}$_. But, $FRAME_{L}$ being special, will
produce two $FRAME_{L}^{new}$s. Thus we get $FRAME_{TL}^{new1}$ consisting of
$FRAME_{L}^{new1}$ with $FRAME_{T}^{new}$ and $FRAME_{TL}^{new2}$ consisting
of $FRAME_{L}^{new2}$ with $FRAME_{T}^{new}$. Each one will be $FRAME_{TL}$ of
a subword of size $(k+1,l+1)$ of $f_{\infty,\infty}$. Again by Lemma 2, we can
construct two distinct subwords of size $(k+1)(l+1)$ from this type of
$FRAME_{TL}$.

Similarly, a $FRAME_{TL}$ of $Type(iii)$ will produce two distinct subwords of
size $(k+1)(l+1)$ and a $FRAME_{TL}$ of $Type(iv)$ will produce four distinct
subwords of size $(k+1)(l+1)$.

We now prove that exactly $(k+2)(l+2)$ subwords only are produced by this
method.

Towards that, let us analyse the $FRAME_{TL}$s of the $(k+1)(l+1)$ factors of
size $(k,l)$ which are being extended. Let us recall how these factors of size
$(k,l)$ are created (preprint). We know that, in the $2(k+1)$ vertical factors
of size $k$, available in the columns of $f_{\infty,\infty}$, $k+1$ are over
$\\{a,c\\}$ and $k+1$ are over $\\{b,d\\}$. Let us name the factors over
$\\{a,c\\}$ as $V_{1}^{a,c},V_{2}^{a,c},\ldots,V_{k}^{a,c},V_{k+1}^{a,c}$,
with the last one being the special factor over $\\{a,c\\}$. As the two
distinct columns occurring in $f_{\infty,\infty}$ are structurally the same,
the other $(k+1)$ factors over $\\{b,d\\}$, namely,
$V_{1}^{b,d},V_{2}^{b,d},\ldots,V_{k}^{b,d},V_{k+1}^{b,d}$, are obtained by
the simple substitution $s(a)=b,s(c)=d$ so that $V_{1}^{b,d}=s(V_{1}^{a,c})$,
$V_{2}^{b,d}=s(V_{2}^{a,c})$, $\ldots$, $V_{k+1}^{b,d}=s(V_{k+1}^{a,c})$, with
the last one being the special factor over $\\{b,d\\}$. Then the $(k+1)$ pairs
$V_{i}=\\{V_{i}^{a,c},V_{i}^{b,d}\\}$, $1\leq i\leq(k+1)$ are created.
Similarly the $(l+1)$ pairs $H_{j}=\\{H_{j}^{a,b},H_{j}^{c,d}\\}$, $1\leq
j\leq(l+1)$ are created. Here $H_{j}^{a,b}$, $1\leq j\leq(l+1)$ are the $l+1$
horizontal factors over $\\{a,b\\}$ with the last one being the special factor
over $\\{a,b\\}$ and $H_{j}^{c,d}$, $1\leq j\leq(l+1)$ are the $l+1$
horizontal factors over $\\{c,d\\}$ with the last one being the special factor
over $\\{c,d\\}$.

The nature of $FRAME_{TL}$s and hence the type of each of the $(k+1)(l+1)$
subwords depends on the possible ways the factors from $V_{i}$s and $H_{j}$s
occupy $FRAME_{L}$ and $FRAME_{T}$ of the subwords. These features are listed
in Tab. 2. In the table, the cell at the intersection of $V_{i}$, $1\leq i\leq
k+1$ and $H_{j}$, $1\leq j\leq l+1$ corresponds to the subword having
$FRAME_{L}\in V_{i}$ and $FRAME_{T}\in H_{j}$. Also, $F_{L}$ means $FRAME_{L}$
is special and $\neg F_{L}$ means $FRAME_{L}$ is not special. $F_{T}$ and
$\neg F_{T}$ have similar meanings.

Table 2: Distribution of the Types of $FRAME_{TL}$ in the subwords of size
$(k,l)$

$H_{i}\rightarrow$ $H_{1}$ $H_{2}$ $\ldots$ $H_{l}$ $H_{l+1}$
$V_{i}\downarrow$ $V_{1}$ $\neg F_{L}$ and $\neg F_{T}$ $\neg F_{L}$ and $\neg
F_{T}$ $\ldots$ $\neg F_{L}$ and $\neg F_{T}$ $\neg F_{L}$ and $F_{T}$ Type
(i) Type (i) … Type (i) Type (iii) $V_{2}$ $\neg F_{L}$ and $\neg F_{T}$ $\neg
F_{L}$ and $\neg F_{T}$ $\ldots$ $\neg F_{L}$ and $\neg F_{T}$ $\neg F_{L}$
and $F_{T}$ Type (i) Type (i) … Type (i) Type (iii) $\vdots$ $\vdots$ $\vdots$
$\quad\ddots\quad$ $\vdots$ $\vdots$ $V_{k}$ $\neg F_{L}$ and $\neg F_{T}$
$\neg F_{L}$ and $\neg F_{T}$ $\ldots$ $\neg F_{L}$ and $\neg F_{T}$ $\neg
F_{L}$ and $F_{T}$ Type (i) Type (i) … Type (i) Type (iii) $V_{k+1}$ $F_{L}$
and $\neg F_{T}$ $F_{L}$ and $\neg F_{T}$ $\ldots$ $F_{L}$ and $\neg F_{T}$
$F_{L}$ and $F_{T}$ Type (ii) Type (ii) … Type (ii) Type (iv)

From the table, it is clear that, by extending their $FRAME_{TL}$, each of the
$kl$ number of subwords of size $(k,l)$ produce $1$ subword of size
$(k+1,l+1)$, each of the $k+l$ number of subwords of size $(k,l)$ produce $2$
subwords of size $(k+1,l+1)$ and one subword of size $(k,l)$ produces $4$
subwords of size $(k+1,l+1)$. Therefore, $kl+2(k+l)+4=(k+2)(l+2)$ subwords of
size $(k+1,l+1)$ will be produced. ∎

######  Example 2.

Consider all the 9 subwords of size $(2,2)$ of $f_{\infty,\infty}$ listed in
Table 1. We will extend each of them to get the 16 subwords of size $(3,3)$ of
$f_{\infty,\infty}$. The 16 subwords are listed in Tab. 3.

Table 3: Obtaining the factors by Extension Subword of | Type | Extended | Subword of
---|---|---|---
Size (2,2) |  | $FRAME_{TL}^{new}$ | Size (3,3)
$\begin{matrix}d&c\\\ b&a\end{matrix}$ | (i) | $\begin{matrix}d&c&d\\\ b&*&*\\\ d&*&*\end{matrix}$ | $\begin{matrix}d&c&d\\\ b&a&b\\\ d&c&d\end{matrix}$
$\begin{matrix}d&c\\\ d&c\end{matrix}$ | (i) | $\begin{matrix}d&c&d\\\ d&*&*\\\ b&*&*\end{matrix}$ | $\begin{matrix}d&c&d\\\ d&c&d\\\ b&a&b\end{matrix}$
$\begin{matrix}d&d\\\ b&b\end{matrix}$ | (i) | $\begin{matrix}d&d&c\\\ b&*&*\\\ d&*&*\end{matrix}$ | $\begin{matrix}d&d&c\\\ b&b&a\\\ d&d&c\end{matrix}$
$\begin{matrix}d&d\\\ d&d\end{matrix}$ | (i) | $\begin{matrix}d&d&c\\\ d&*&*\\\ b&*&*\end{matrix}$ | $\begin{matrix}d&d&c\\\ d&d&c\\\ b&b&a\end{matrix}$
$\begin{matrix}c&d\\\ a&b\end{matrix}$ | (iii) |  $\begin{matrix}c&d&c\\\ a&*&*\\\ c&*&*\end{matrix}$ , $\begin{matrix}c&d&d\\\ a&*&*\\\ c&*&*\end{matrix}\quad$ |  $\begin{matrix}c&d&c\\\ a&b&a\\\ c&d&c\end{matrix}$ , $\begin{matrix}c&d&d\\\ a&b&b\\\ c&d&d\end{matrix}\quad$
$\begin{matrix}c&d\\\ c&d\end{matrix}$ | (iii) |  $\begin{matrix}c&d&c\\\ c&*&*\\\ a&*&*\end{matrix}$ , $\begin{matrix}c&d&d\\\ c&*&*\\\ a&*&*\end{matrix}\quad$ |  $\begin{matrix}c&d&c\\\ c&d&c\\\ a&b&a\end{matrix}$ , $\begin{matrix}c&d&d\\\ c&d&d\\\ \ a&b&b\end{matrix}\quad$
$\begin{matrix}b&a\\\ d&c\end{matrix}$ | (ii) |  $\begin{matrix}b&a&b\\\ d&*&*\\\ b&*&*\end{matrix}$ , $\begin{matrix}b&a&b\\\ d&*&*\\\ d&*&*\end{matrix}\quad$ |  $\begin{matrix}b&a&b\\\ d&c&d\\\ b&a&b\end{matrix}$ , $\begin{matrix}b&a&b\\\ d&c&d\\\ d&c&d\end{matrix}\quad$
$\begin{matrix}b&b\\\ d&d\end{matrix}$ | (ii) |  $\begin{matrix}b&b&a\\\ d&*&*\\\ b&*&*\end{matrix}$ , $\begin{matrix}b&b&a\\\ d&*&*\\\ d&*&*\end{matrix}\quad$ |  $\begin{matrix}b&b&a\\\ d&d&c\\\ b&b&a\end{matrix}$ , $\begin{matrix}b&b&a\\\ d&d&c\\\ d&d&c\end{matrix}\quad$
$\begin{matrix}a&b\\\ c&d\end{matrix}$ | (iv) |  $\begin{matrix}a&b&a\\\ c&*&*\\\ a&*&*\end{matrix}$ , $\begin{matrix}a&b&a\\\ c&*&*\\\ c&*&*\end{matrix}\quad$ |  $\begin{matrix}a&b&a\\\ c&d&c\\\ a&b&a\end{matrix}$ , $\begin{matrix}a&b&a\\\ c&d&c\\\ c&d&c\end{matrix}\quad$
|  |  $\begin{matrix}a&b&b\\\ c&*&*\\\ a&*&*\end{matrix}$ , $\begin{matrix}a&b&b\\\ c&*&*\\\ c&*&*\end{matrix}\quad$ |  $\begin{matrix}a&b&b\\\ c&d&d\\\ a&b&b\end{matrix}$ , $\begin{matrix}a&b&b\\\ c&d&d\\\ c&d&d\end{matrix}\quad$

##  5 Enumeration by Conjugation

For a given $k$, let $n$ be such that $1\leq k<F(n)$, where $F(n)$ is the
$n^{th}$ Fibonacci number. In this section we use the method described in
[11], wherein it is proved that the prefixes of length $k$ of the conjugates
of a "special" conjugate of $f_{n}$ are the subwords of length $k$ of
$f_{\infty}$. The Lemma is recalled here.

With $\Sigma$, an alphabet, define the operator $T$ on $\Sigma^{+}$ as
follows. For a word $w=a_{1}a_{2}\ldots a_{n}\in\Sigma^{+}$,
$T(a_{1}a_{2}\ldots a_{n-1}a_{n})=a_{2}\ldots a_{n-1}a_{n}a_{1}$ and
$T^{-1}(a_{1}a_{2}\ldots a_{n-1}a_{n})=a_{n}a_{1}a_{2}\ldots a_{n-1}$. Higher
powers of $T$ are defined iteratively. That is, $T^{p}(w)=T(T^{p-1}(w))$ and
$T^{-p}(w)=T^{-1}(T^{-(p-1)}(w))$.

######  Lemma 3.

[11] Let $f_{0}=a,f_{1}=b,f_{n}=f_{n-1}f_{n-2},n\geq 2$ be the sequence of
Fibonacci words. Let $F(n)=|f_{n}|$ and let

$q_{n}=\begin{cases}T^{F(n)-1}(f_{n})&\text{if n is even}\\\
T^{F(n-1)-1}(f_{n})&\text{if n is odd}.\end{cases}$

Then for each $k$ with $1\leq k<F(n)$, the $k+1$ prefixes of
$T^{0}(q_{n}),T^{-1}(q_{n}),\ldots,T^{-k}(q_{n})$ having length $k$ are the
$k+1$ distinct factors of $f_{\infty}$ of length $k$.

######  Example 3.

Let $f_{\infty}=abaab\ldots$. For $k=4$, $n$ will be $4$, as $4<F(4)$. So,
$f_{n}=f_{4}=abaab$. With $F(4)=5,F(3)=3$, we have $q_{4}=T^{4}(abaab)=babaa$,
is the special conjugate of $f_{4}$.

Now, $T^{0}(q_{4}),T^{-1}(q_{4}),T^{-2}(q_{4}),T^{-3}(q_{4}),T^{-4}(q_{4})$
are $babaa$, $ababa$, $aabab$, $baaba$, $abaab$ respectively and the subwords
of $f_{\infty}$ of length 4 are $baba,abab,aaba,baab,abaa$.

Similar to the operators $T$ and $T^{-1}$, we define four operators on $2D$
words.

######  Definition 8.

Let $r_{1},r_{2},\cdots,r_{m}$ and $c_{1},c_{2},\cdots,c_{n}$ be the $m$ rows
and the $n$ columns of a $2D$ word $w$ of size $(m,n)$. Then the operations
$T_{col}(w)$, $T^{-1}_{col}(w)$, $T_{row}(w)$ and $T^{-1}_{row}(w)$ are
defined as below.

$\displaystyle T_{col}(w)$ $\displaystyle=c_{2}\obar c_{3}\obar\cdots\obar
c_{n}\obar c_{1}$ $\displaystyle T^{-1}_{col}(w)$ $\displaystyle=c_{n}\obar
c_{1}\obar c_{2}\obar\cdots\obar c_{n-2}\obar c_{n-1}$ $\displaystyle
T_{row}(w)$ $\displaystyle=r_{2}\ominus r_{3}\ominus\cdots\ominus r_{m}\ominus
r_{1}$ $\displaystyle T^{-1}_{row}(w)$ $\displaystyle=r_{n}\ominus
r_{1}\ominus r_{2}\ominus\cdots\ominus r_{n-2}\ominus r_{n-1}.$

Higher powers of $T_{col}(w)$, $T^{-1}_{col}(w)$, $T_{row}(w)$ and
$T^{-1}_{row}(w)$ are defined iteratively. For example, with $s\geq 1$,
$T^{s}_{col}(w)=T_{col}(T^{s-1}_{col}(w))$.

Through these operators we define the conjucacy class of a $2D$ word $w$.

######  Definition 9.

Let $w$ be a $2D$ word of size $(m,n)$. Then

$\displaystyle Conj(w)$ $\displaystyle=\left\\{T_{row}^{i}T_{col}^{j}(w),0\leq
i\leq m-1,0\leq j\leq n-1\right\\}$
$\displaystyle=\left\\{T_{col}^{j}T_{row}^{i}(w),0\leq j\leq n-1,0\leq i\leq
m-1\right\\}$

is called the Conjugacy Class of $w$.

Since $0\leq i\leq m-1$ and $0\leq j\leq n-1$, it is easy to see that the
number of conjugates of $w$ can be at the maximum $mn$. Note that, if $w$ is
primitive then the maximum possible value of $mn$ will be achieved by
$|Conj(w)|$.

Now, we will enumerate the subwords of size $(k,l)$ of $f_{\infty,\infty}$
using the conjugates of a "special" conjugate of $f_{m,n}$ ($m,n\geq 3$ and
depend on $k,l$).

######  Theorem 3.

Let $F(0)=F(1)=1,F(2)=2,F(3)=3,F(4)=5,\ldots$ be the sequence of Fibonacci
numbers. For a given $k,l\geq 1$, consider the $2D$ finite Fibonacci word
$f_{m,n}$, where $m$, $n$ are such that $k<F(m)$ and $l<F(n)$. Let

$q_{m,n}=\begin{cases}T_{row}^{F(m)-1}\left(T_{col}^{F(n)-1}(f_{m,n})\right)&\text{if
m is even and n is even}\\\
T_{row}^{F(m)-1}\left(T_{col}^{F(n-1)-1}(f_{m,n})\right)&\text{if m is even
and n is odd}\\\
T_{row}^{F(m-1)-1}\left(T_{col}^{F(n)-1}(f_{m,n})\right)&\text{if m is odd and
n is even}\\\
T_{row}^{F(m-1)-1}\left(T_{col}^{F(n-1)-1}(f_{m,n})\right)&\text{if m is odd
and n is odd}\end{cases}$

Then for each $k$ with $1\leq k<F(m)$ and for each $l$ with $1\leq l<F(n)$,
the $(k+1)(l+1)$ prefixes of

$T^{0}_{row}T^{0}_{col}(q_{m,n}),T^{0}_{row}T^{-1}_{col}(q_{m,n}),\ldots\>\dots,\>T^{0}_{row}T^{-l}_{col}(q_{m,n})$,
---
$T^{-1}_{row}T^{0}_{col}(q_{m,n}),T^{-1}_{row}T^{-1}_{col}(q_{m,n}),\ldots\>\dots,\>T^{-1}_{row}T^{-l}_{col}(q_{m,n})$,
$\cdots\quad\cdots\quad\cdots$
$\cdots\quad\cdots\quad\cdots$
$T^{-k}_{row}T^{0}_{col}(q_{m,n}),T^{-k}_{row}T^{-1}_{col}(q_{m,n}),\ldots\>\ldots,\>T^{-k}_{row}T^{-l}_{col}(q_{m,n})$

having size $(k,l)$ are the $(k+1)(l+1)$ distinct factors of
$f_{\infty,\infty}$ of size $(k,l)$.

###### Proof.

Suppose that we want to find all the subwords of $f_{\infty,\infty}$ of size
$(k,l)$. Let $F(0)=F(1)=1,F(2)=2,F(3)=3,F(4)=5,\ldots$ be the sequence of
Fibonacci numbers. Consider the $2D$ finite Fibonacci word $f_{m,n}$ where $m$
and $n$ are such that $k<F(m)$ and $l<F(n)$. Note that $f_{m,n}$ will be of
size ($F(m),F(n)$) [22].

We prove the theorem for the case where both $m$ and $n$ are even. The proofs
of other cases are similar.

Denote the columns of $f_{m,n}$ by $C_{1},C_{2},\ldots,C_{F(n)}$. Since there
are only two distinct columns (refer Lemma 1), let us symbolize the columns
over $\\{b,d\\}$ by $D$ and the columns over $\\{a,c\\}$ by $C$. As every row
of $f_{m,n}$ is a Fibonacci word of size $F(n)$, the two distinct columns are
indeed arranged in a Fibonacci pattern in $f_{m,n}$. That is, the symbolized
word for $f_{m,n}=C_{1}\obar C_{2}\obar\ldots\obar C_{F(n)}=DCDDC\ldots
DC=H_{n}$, say, is a Fibonacci word of size $F(n)$. Since $n$ is even, the
suffix of length 2 of $H_{n}$ will be $DC$. Now by Lemma 3, the prefixes of
length $l$ of the conjugates of $T^{F(n)-1}(H_{n})=q_{n}^{\prime}$ (say), are
the subwords of length $l$ of $H_{n}$. We now replace the symbols $D$ and $C$
occurring in $q_{n}^{\prime}$ by the original columns to get the $2D$ word
$q_{n}$. What we have proved is that, we can arrange the columns of $f_{m,n}$
in a way that we can obtain all the subwords of length $l$ of the infinite
Fibonacci words occupying the rows of $f_{m,n}$ through the conjugates of
$q_{n}$.

Now, let us denote the rows of $q_{n}$ by $R_{1},R_{2},\ldots,R_{F(m)}$. By
symbolizing the rows over $\\{d,c\\}$ as $D^{\prime}$ and $\\{a,b\\}$ as $B$,
we get $V_{m}$, the symbolized word of $q_{n}$ over $\\{D^{\prime},B\\}$ as
$V_{m}=R_{1}\ominus R_{2}\ominus\ldots\ominus
R_{F(m)}=D^{\prime}BD^{\prime}D^{\prime}B\ldots D^{\prime}B$. Following a
similar argument as above, we get a word $q_{m}^{\prime}=T^{F(m)-1}(V_{m})$
over $\\{D^{\prime},B\\}$. We can now replace the symbols occurring in
$q_{m}^{\prime}$ to get the $2D$ word $q_{m,n}$. What we have proved is that,
we can arrange the rows of $q_{n}$ in a way that we can get all the subwords
of length $k$ of the infinite Fibonacci words occupying the columns of
$f_{m,n}$ through the conjugates of $q_{m,n}$.

Note that $q_{m,n}$ is a conjugate of $f_{m,n}$. In fact, by the two stage
process, what we have obtained as $q_{m,n}$ is nothing but
$T_{row}^{F(m)-1}\left(T_{col}^{F(n)-1}(f_{m,n})\right)$. As assured by Lemma
3, the rows and columns of $q_{m,n}$ are arranged in such a way that, for each
$0\leq i\leq k$, $0\leq j\leq l$, the prefixes of length $k$ of the first
columns and the prefixes of length $l$ of the first rows of
$T^{i}_{row}T^{j}_{col}(q_{m,n})$, produces $(k+1)(l+1)$ distinct
$FRAME_{TL}$s. We can call $q_{m,n}$ a "special" conjugate of $f_{m,n}$, in
this context. Since in each of these $FRAME_{TL}$s, $FRAME_{L}$s are subwords
of $f_{\infty}^{d,b}$ or $f_{\infty}^{c,a}$, and $FRAME_{T}$s are subwords of
$f_{\infty}^{d,c}$ or $f_{\infty}^{b,a}$, by Lemma 2 we get $(k+1)(l+1)$
distinct subwords of $f_{\infty,\infty}$. ∎

Let us understand the enumeration of the subwords through an example.

######  Example 4.

Let $k=2$, $l=2$. That is, we wish to find all the $(2,2)$-subwords of
$f_{\infty,\infty}$. As $k$ and $l$ are less than $F(3)=3$, $m=n=3$ and we
consider

$\displaystyle f_{3,3}=\begin{matrix}d&c&d\\\ b&a&b\\\ d&c&d\end{matrix}.$

Then, as both $m$ and $n$ are odd,
$q_{3,3}=T_{row}^{2-1}\left(T_{col}^{2-1}(f_{3,3})\right)=f_{3,3}=\begin{matrix}a&b&b\\\
c&d&d\\\ c&d&d\end{matrix}.$

As mentioned earlier $q_{3,3}$ is a "special" conjugate of $f_{3,3}$. Since
$f_{m,n},m,n\geq 0$ are primitive, $q_{3,3}$ is primitive and has 9
conjugates. All the 9 conjugates and the corresponding subword of size $(2,2)$
of $f_{\infty,\infty}$ are listed in Table 4.

Table 4: Conjugates of $q_{3,3}$ and the subwords of size $(2,2)$ of
$f_{\infty,\infty}$

$T_{row}^{i}(T_{col}^{j}(q_{3,3}))$ Conjugate of $q_{3,3}$ Subword
$T_{row}^{0}(T_{col}^{0}(q_{3,3}))$ $\begin{matrix}a&b&b\\\ c&d&d\\\
c&d&d\end{matrix}$ $\begin{matrix}a&b\\\ c&d\end{matrix}$
$T_{row}^{0}(T_{col}^{-1}(q_{3,3}))$ $\begin{matrix}b&a&b\\\ d&c&d\\\
d&c&d\end{matrix}$ $\begin{matrix}b&a\\\ d&c\end{matrix}$
$T_{row}^{0}(T_{col}^{-2}(q_{3,3}))$ $\begin{matrix}b&b&a\\\ d&d&c\\\
d&d&c\end{matrix}$ $\begin{matrix}b&b\\\ d&d\end{matrix}$
$T_{row}^{-1}(T_{col}^{0}(q_{3,3}))$ $\begin{matrix}c&d&d\\\ a&b&b\\\
c&d&d\end{matrix}$ $\begin{matrix}c&d\\\ a&b\end{matrix}$
$T_{row}^{-1}(T_{col}^{-1}(q_{3,3}))$ $\begin{matrix}d&c&d\\\ b&a&b\\\
d&c&d\end{matrix}$ $\begin{matrix}d&c\\\ b&a\end{matrix}$
$T_{row}^{-1}(T_{col}^{-2}(q_{3,3}))$ $\begin{matrix}d&d&c\\\ b&b&a\\\
d&d&c\par\end{matrix}$ $\begin{matrix}d&d\\\ b&b\end{matrix}$
$T_{row}^{-2}(T_{col}^{0}(q_{3,3}))$ $\begin{matrix}c&d&d\\\ c&d&d\\\
a&b&b\par\end{matrix}$ $\begin{matrix}c&d\\\ c&d\end{matrix}$
$T_{row}^{-2}(T_{col}^{-1}(q_{3,3}))$ $\begin{matrix}d&c&d\\\ d&c&d\\\
b&a&b\par\end{matrix}$ $\begin{matrix}d&c\\\ d&c\end{matrix}$
$T_{row}^{-2}(T_{col}^{-2}(q_{3,3}))$ $\begin{matrix}d&d&c\\\ d&d&c\\\
b&b&a\end{matrix}$ $\begin{matrix}d&d\\\ d&d\end{matrix}$

In [11], apart from the sophisticated way of obtaining the subwords of
$f_{\infty}$, described in Lemma 3, the author provides another simple way of
obtaining the subwords of length $k$.

######  Proposition 1.

[11] Let $n\geq 2$ and $F(n)\leq k<F(n+1)$. Then the $k+1$ prefixes of
$T^{i}(f_{n+1})$ of length $k$, where
$i\in\\{0,1,\ldots,F(n)-1\\}\cup\\{F(n+2)-k-1,F(n+2)-k,\ldots,F(n+1)-1\\}$,
are the $k+1$ distinct factors of $f_{\infty}$ of length $k$.

Proposition 1 is extended to $f_{\infty,\infty}$ as below.

######  Proposition 2.

Let $m,n\geq 2$ and $F(m)\leq k<F(m+1)$, $F(n)\leq l<F(n+1)$. Then the
$(k+1)(l+1)$ prefixes of $T_{row}^{i}(T_{col}^{j}(f_{m+1,n+1}))$ of size
$(k,l)$, where
$i\in\\{0,1,\ldots,F(m)-1\\}\cup\\{F(m+2)-k-1,F(m+2)-k,\ldots,F(m+1)-1\\}$,
$j\in\\{0,1,\ldots,F(n)-1\\}\cup\\{F(n+2)-l-1,F(n+2)-l,\ldots,F(n+1)-1\\}$,
are the $(k+1)(l+1)$ distinct factors of $f_{\infty,\infty}$ of size $(k,l)$.

###### Proof.

For $m,n\geq 2$, consider the $2D$ finite Fibonacci word $f_{m+1,n+1}$. Recall
that the columns and rows of $f_{m+1,n+1}$ are $1D$ finite Fibonacci words (in
fact, they are $f_{m+1}^{d,b}$ or $f_{m+1}^{c,a}$, and $f_{n+1}^{d,c}$ or
$f_{n+1}^{b,a}$). Hence, the $FRAME_{L}$s and $FRAME_{T}$s of the $(k+1)(l+1)$
number of $FRAME_{TL}$s obtained from the conjugates
$T_{row}^{i}(T_{col}^{j}(f_{m+1,n+1}))$,
$i\in\\{0,1,\ldots,F(m)-1\\}\cup\\{F(m+2)-k-1,F(m+2)-k,\ldots,F(m+1)-1\\}$,
$j\in\\{0,1,\ldots,F(n)-1\\}\cup\\{F(n+2)-l-1,F(n+2)-l,\ldots,F(n+1)-1\\}$ are
nothing but the $(k+1)(l+1)$ appropriate combinations of vertical factors of
length $k$ and horizontal factors of length $l$ of the infinite Fibonacci
words occurring in the columns and in the rows of $f_{\infty,\infty}$. Since
all these $FRAME_{TL}$s are taken from the prefixes of $f_{\infty,\infty}$,
the subword constructed from these $FRAME_{TL}$s (refer Lemma 2) will be
obviously prefixes of $f_{\infty,\infty}$. Hence, the prefixes of size $(k,l)$
of $T_{row}^{i}(T_{col}^{j}(f_{m+1,n+1}))$ for the stated values of $i,j$ are
the factors of $f_{\infty,\infty}$ of size $(k,l)$. ∎

##  6 Locating the Factors of $f_{\infty,\infty}$

In the previous sections, we developed a few methods for listing all the
$(k+1)(l+1)$ factors of size $(k,l)$ of $f_{\infty,\infty}$. In this section
we will locate (find the exact positions $\\{(i,j),i,j\geq 1\\}$ of) these
factors in the domain of $f_{\infty,\infty}$. We know that since there are
only $k+1$ factors of length $k$ in $f_{\infty}$, there are many repetitions
of every factor in $f_{\infty}$ [4]. As the rows and columns of
$f_{\infty,\infty}$ are composed of $f_{\infty}$, the same thing happens in
$f_{\infty,\infty}$ also.

For locating the factors of $f_{\infty}$, the reader may either refer [11] or
[26]. We recall some terminologies from [26] for our use.

Let $f_{0}=a,f_{1}=ab$ and for $n\geq 1,f_{n+1}=f_{n}f_{n-1}$ so that
$f_{\infty}=abaababaabaab\ldots\ldots=f_{\infty}(1,2,3,\ldots)$. Also, for
$n\geq 0$ let $F(n)=|f_{n}|$ be the $n^{th}$ Fibonacci number. For $n\geq 2$,
let $g_{n}$ be the $n^{th}$ truncated Fibonacci word, the word obtained from
$f_{n}$ by removing its last two letters.

Let $u$ be a subword of $f_{\infty}$. By an occurrence of $u$ we mean a $i\geq
0$ such that $f_{\infty}(i+1)f_{\infty}(i+2)\dots f_{\infty}(i+|u|)=u$. By
first-occ($u$) we mean the least value of occurrence of $u$ and by occ($u$) we
mean the set of all occurrences of $u$ in $f_{\infty}$. Now, for a set of
integers $X$ and for a $j\geq 0$, define the operator $\boxplus$ as,
$X\boxplus j=\\{x+j:x\in X\\}$.

Recall that the Fibonacci number system represents a number as a sum of
Fibonacci numbers such that no two consecutive Fibonacci numbers are used.
Also, the sum of zero number of integers equals zero. This representation of
any nonnegative integer $n$, in the Fibonacci number system is called the
Fibonacci representation of $n$. For $n\geq 1$, let $\mathcal{Z}_{n}$ be the
set of nonnegative integers which do not use Fibonacci numbers
$F(0),F(1),F(2),\ldots,F(n-1)$ in their Fibonacci representation. For example
$\mathcal{Z}_{1}=\\{0,2,3,5,\ldots\\}$ and
$\mathcal{Z}_{2}=\\{0,3,5,8,11,\ldots\\}$. Then, it is proved in [26] that,

$\textit{occ}(u)=occ(g_{n})\boxplus\textit{first-occ}(u),$

where $n$ is such that $g_{n}$ is the shortest truncated Fibonacci word
containing $u$. Since for $n\geq 2$, occ($g_{n+1}$) = occ($f_{n}$) =
$\mathcal{Z}_{n}$ we have,

$\textit{occ}(u)=\mathcal{Z}_{n-1}\boxplus\textit{first-occ}(u).$

We also have that occ($f_{1}$) = occ($f_{2}$) and
occ($f_{0}$)$=\mathcal{Z}_{1}$.

######  Example 5.

Let us locate the positions of the factor $u=abab$ in $f_{\infty}^{a,b}$. We
have first-occ($u$) = $3$. Since $u$ occurs for the first time in $g_{5}$, we
get $n=5$ and hence occ($abab$) = $\mathcal{Z}_{4}\boxplus
3=\\{0,8,13,21,29,\ldots\\}\boxplus 3=\\{3,11,16,24,32,\ldots\\}$.

We are now ready to locate any factor of $f_{\infty,\infty}$. Let $w$ be a
subword of $f_{\infty,\infty}$. Let the size of $w$ be $(k,l)$. Note that,
because $w$ is a $2D$ word, first-occ($w$) is a pair $(i,j)$ such that $u$
occurs in the domain $\\{i+1,i+2,\ldots,i+k\\}\times\\{j+1,j+2,\dots,j+l\\}$
of $f_{\infty,\infty}$. The definition of occ($w$) is similar to its $1D$
counterpart. Since a subword of $f_{\infty,\infty}$ is uniquely determined by
its $FRAME_{TL}$, its first occurrence and hence its all other occurrences
will be determined by the first occurrences of its $FRAME_{T}$ and
$FRAME_{L}$. With $FRAME_{T}$ and $FRAME_{L}$ both being $1D$ Fibonacci words
we have the following Proposition.

######  Proposition 3.

Let $w$ be a subword of $f_{\infty,\infty}$. Let $FRAME_{T}$ and $FRAME_{L}$
denote its first row and first column respectively. Then,

$\displaystyle\textit{first-
occ($w$)}=\begin{cases}(fo_{L}^{d,b},fo_{T}^{d,c})&\quad\text{if $FRAME_{L}$
is over $\\{d,b\\}$ and $FRAME_{T}$ is over $\\{d,c\\}$}\\\
(fo_{L}^{d,b},fo_{T}^{b,a})&\quad\text{if $FRAME_{L}$ is over $\\{d,b\\}$ and
$FRAME_{T}$ is over $\\{b,a\\}$}\\\ (fo_{L}^{c,a},fo_{T}^{d,c})&\quad\text{if
$FRAME_{L}$ is over $\\{c,a\\}$ and $FRAME_{T}$ is over $\\{d,c\\}$}\\\
(fo_{L}^{c,a},fo_{T}^{b,a})&\quad\text{if $FRAME_{L}$ is over $\\{c,a\\}$ and
$FRAME_{T}$ is over $\\{b,a\\}$}\\\ \end{cases}$

where $fo_{L}^{d,b}$ is the first-occ($FRAME_{L}$) in $f_{\infty}^{d,b}$,
$fo_{L}^{c,a}$ is the first-occ($FRAME_{L}$) in $f_{\infty}^{c,a}$,
$fo_{T}^{d,c}$ is the first-occ($FRAME_{T}$) in $f_{\infty}^{d,c}$ and
$fo_{T}^{b,a}$ is the first-occ($FRAME_{T}$) in $f_{\infty}^{b,a}$.

###### Proof.

We discuss the proof for the case in which $FRAME_{L}$ is over $\\{d,b\\}$ and
$FRAME_{T}$ is over $\\{d,c\\}$. Proofs of the other cases are similar.

Since $w$ can occur in $f_{\infty,\infty}$, only when $FRAME_{TL}$ of $w$
occurs in $f_{\infty,\infty}$, it is clear that first-occ($w$) is decided by
first-occ($FRAME_{L}$) in $f_{\infty}^{d,b}$ and first-occ($FRAME_{T}$) in
$f_{\infty}^{d,c}$. Let $fo_{L}^{d,b}\geq 0$, be first-occ($FRAME_{L}$) in
$f_{\infty}^{d,b}$. Let $fo_{T}^{d,c}\geq 0$ be first-occ($FRAME_{T}$) in
$f_{\infty}^{d,c}$. Since all the columns of $f_{\infty,\infty}$ over
$\\{d,b\\}$ are identical $fo_{L}^{d,b}$ value will be the same in all the
columns which are over $\\{d,b\\}$. So in the ${fo_{T}^{d,c}}^{\>th}$ column
(where $FRAME_{T}(w)$ occurs for the first time) also, $fo_{L}^{d,b}$ will be
the same. Similarly, since all the rows of $f_{\infty,\infty}$ over
$\\{d,c\\}$ are identical $fo_{T}^{d,c}$ value will be the same in all the
rows which are over $\\{d,c\\}$.

Now, first-occ($FRAME_{TL}(w)$) can be $(i,j)$, say, only when both first-
occ($FRAME_{L}(w)$) and first-occ($FRAME_{T}(w)$) are $(i,j)$. Hence first-
occ($w$) = first-occ($FRAME_{TL}(w)$) = ($fo_{L}^{d,b}$, $fo_{T}^{d,c}$), if
$FRAME_{L}$ is over $\\{d,b\\}$ and $FRAME_{T}$ is over $\\{d,c\\}$. ∎

######  Corollary 2.

Let $w$ be a subword of $f_{\infty,\infty}$. Let first-occ($w$) be given by
Proposition 3. Let $FRAME_{L}(w)$ be over $\\{s_{1},s_{2}\\}$ and
$FRAME_{T}(w)$ be over $\\{s^{\prime}_{1},s^{\prime}_{2}\\}$. Then, occ($w$) =
$X\times Y$, where $X=\mathcal{Z}_{m-1}\boxplus fo_{L}^{s_{1},s_{2}}$ and
$Y=\mathcal{Z}_{n-1}\boxplus fo_{T}^{s^{\prime}_{1},s^{\prime}_{2}}$.

###### Proof.

In all the columns of $f_{\infty,\infty}$ which are over $\\{s_{1},s_{2}\\}$,
occ($FRAME_{L}$) = $\mathcal{Z}_{m-1}\boxplus fo_{L}^{s_{1},s_{2}}$, where $m$
is such that $g_{m}$ is the shortest truncated Fibonacci word over
$\\{s_{1},s_{2}\\}$ containing $FRAME_{L}$. Similarly, in all the rows of
$f_{\infty,\infty}$ which are over $\\{s_{1}^{\prime},s_{2}^{\prime}\\}$,
occ($FRAME_{T}$) = $\mathcal{Z}_{n-1}\boxplus
fo_{T}^{s_{1}^{\prime},s_{2}^{\prime}}$, where $n$ is such that $g_{n}$ is the
shortest truncated Fibonacci word over $\\{s_{1}^{\prime},s_{2}^{\prime}\\}$
containing $FRAME_{T}$. Therefore, occ($FRAME_{TL}(w)$) =
(occ($FRAME_{L}(w)$), occ($FRAME_{T}(w)$)) =
$\\{(x,y):x\in\mathcal{Z}_{m-1}\boxplus
fo_{L}^{s_{1},s_{2}},y\in\mathcal{Z}_{n-1}\boxplus
fo_{T}^{s_{1}^{\prime},s_{2}^{\prime}}\\}=X\times Y$ where
$X=\mathcal{Z}_{m-1}\boxplus fo_{L}^{s_{1},s_{2}}$ and
$Y=\mathcal{Z}_{n-1}\boxplus fo_{T}^{s^{\prime}_{1},s^{\prime}_{2}}$. Since
occ($w$) = occ($FRAME_{TL}(w)$), the result follows. ∎

######  Example 6.

Let us find the occ($w$) where $w=\begin{matrix}d&d&c\\\ d&d&c\\\
b&b&a\end{matrix}$.

Note that, $FRAME_{L}$ of $w$ is $\begin{matrix}d\\\ d\\\ b\end{matrix}$ and
first-occ($FRAME_{L}$ ) in $f_{\infty}^{d,b}$ is $2$. That is
$fo_{L}^{d,b}=2$. Also the value of $m$ such that $g_{m}^{d,b}$ contains
$FRAME_{L}$ is $4$. Similarly, $FRAME_{T}$ of $w$ is
"$\begin{matrix}d&d&c\end{matrix}$" and first-occ($FRAME_{T}$) in
$f_{\infty}^{d,c}$ is $fo_{T}^{d,c}=2$. The value of $n$ such that
$g_{n}^{d,c}$ contains $FRAME_{T}$ is $4$.

Therefore, first-occ($w$) = $(2,2)$. And, occ($w$) = $X\times Y$, where where
$X=\mathcal{Z}_{3}\boxplus 2$ and $Y=\mathcal{Z}_{3}\boxplus 2$. With
$\mathcal{Z}_{3}=\\{0,5,8,13,18,\ldots\\}$, we have
$X=\\{2,7,10,15,20,\ldots\\}$ and $Y=\\{2,7,10,15,20,\ldots\\}$. Hence
occ($w$) = $\\{(2,2),(2,7),(2,10),\ldots,(7,2),(7,7),(7,10),\ldots\\}$.

##  7 Concluding Remarks

The knowledge of all the subwords of an infinite word would be very useful to
analyse the characteristics of the word. Though any sort of analysis like
periodicity, factor complexity is tricky in $2D$ words, $2D$ Fibonacci words
with their simple and elegant structure are pliable for exploring their
properties. In this paper we have enumerated the subwords of the $2D$ infinite
Fibonacci word, $f_{\infty,\infty}$, in a few possible ways. The location of
the occurrences of these subwords are also found out.

Suffix tree is an important tool used for pattern matching and dictionary
searching [23, 29]. Again, there are some limitations while extending this
tool for $2D$ words [15]. But the relatively simpler structure of
$f_{\infty,\infty}$ may help us to develop one for $2D$ words of similar type.
Also, variations attempted in the generation of the Fibonacci sequence [30]
lead to variants of $1D$ / $2D$ Fibonacci words [17]. We might start exploring
these directions.

## References

  * [1] Aldo de Luca: A combinatorial property of the Fibonacci words. Information Processing Letters 12(4), 193–195 (1981)
  * [2] Anselmo, M., Giammarresi, D., Madonia, M.: Prefix picture codes: a decidable class of two-dimensional codes. International Journal of Foundations of Computer Science 25(08), 1017–1031 (2014)
  * [3] Apostolico, A., Brimkov, V.E.: Fibonacci arrays and their two-dimensional repetitions. Theoretical Computer Science 237(1-2), 263–273 (2000)
  * [4] Berstel, J.: Fibonacci words - a survey. In: Rozenberg, G., Salomaa, A. (eds.) The book of L, pp. 13–27. Springer-Verlag (1986)
  * [5] Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M., Seiferas, J.: The smallest automation recognizing the subwords of a text. Theoretical Computer Science 40, 31–55 (1985)
  * [6] Burcroff, A., Winsor, E.: Generalized Lyndon factorizations of infinite words. Theoretical Computer Science 809, 30–38 (2020)
  * [7] Charlier, E., Kärki, T., Rigo, M.: Multidimensional generalized automatic sequences and shape-symmetric morphic words. Discrete Mathematics 310(6), 1238–1252 (2010)
  * [8] Chuan, W.F.: Fibonacci words. Fibonacci Quarterly 30(1), 68–76 (1992)
  * [9] Chuan, W.F.: Symmetric Fibonacci words. Fibonacci Quarterly 31(3), 251–255 (1993)
  * [10] Chuan, W.F.: Generating Fibonacci words. Fibonacci Quarterly 33(2), 104 – 112 (1995)
  * [11] Chuan, W.F., Ho, H.L.: Locating factors of the infinite Fibonacci word. Theoretical Computer Science 349(3), 429–442 (2005)
  * [12] Crochemore, M., Vérin, R.: Direct construction of compact directed acyclic word graphs. In: Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching. pp. 116–129. CPM ’97, Springer-Verlag (1997)
  * [13] Gamard, G., Richomme, G., Shallit, J., Smith, T.: Periodicity in rectangular arrays. Information Processing Letters 118, 58–63 (2017)
  * [14] Giammarresi, D., Restivo, A.: Two-dimensional languages. In: G. Rozenberg, A. Salomaa (eds), Handbook of Formal Languages, Vol. 3. Springer-Verlag (1997)
  * [15] Giancarlo, R., Guaiana, D.: On-line construction of two-dimensional suffix trees. Journal of Complexity 15(1), 72–127 (1999)
  * [16] Jahannia, M., Mohammad-noori, M., Rampersad, N., Stipulanti, M.: Palindromic Ziv–Lempel and Crochemore factorizations of m-bonacci infinite words. Theoretical Computer Science 790, 16–40 (2019)
  * [17] Jishe, F.: Some new remarks about the dying rabbit problem. Fibonacci Quarterly 49(2), 171–176 (2011)
  * [18] Kitaev, S., Lozin, V.: Words and Graphs. Springer Cham (2015)
  * [19] Kulkarni, M.S., Mahalingam, K., Sivasankar, M.: Combinatorial properties of Fibonacci arrays. In: Gopal, T., Watada, J. (eds.) Theory and Applications of Models of Computation. pp. 448–466. Springer International Publishing (2019)
  * [20] Lothaire, M.: Combinatorics on words. Cambridge University Press (1997)
  * [21] Lothaire, M.: Algebraic combinatorics on words. Cambridge University Press (2002)
  * [22] Mahalingam, K., Sivasankar, M., Krithivasan, K.: Palindromic properties of two dimensional Fibonacci words. The Romanian Journal of Information Science and Technology 21(3), 256 – 266 (2018)
  * [23] Maxime, C., Christophe, H., Thierry, L.: Algorithms on Strings. Cambridge University Press (2007)
  * [24] Mignosi, F., Pirillo, G.: Repetitions in the Fibonacci infinite word. RAIRO Theoretical Informatics and Applications 26(3), 199 – 204 (1992)
  * [25] Rosenfeld, A.: Picture languages: Formal models of picture recognition. Academic Press (1979)
  * [26] Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words. Theoretical Computer Science 363(2), 211–223 (2006)
  * [27] Siromoney, G., Siromoney, R., Krithivasan, K.: Picture languages with array rewriting rules. Information and Control 22, 447–470 (1973)
  * [28] Sivasankar, M., Rama, R.: Two-dimensional Fibonacci words: Tandem repeats and factor complexity. Preprint (2022)
  * [29] Smyth, B., Smyth, W.: Computing Patterns in Strings. Pearson Education (2003)
  * [30] Swain, Gordon, A.: Exploring sequences through variations on fibonacci. Ohio Journal of School Mathematics 77(1), 29–33 (2017)
  * [31] Walczak, B.: A simple representation of subwords of the Fibonacci word. Information Processing Letters 110(21), 956–960 (2010)
  * [32] West, D.B.: Introduction to Graph Theory. Pearson Education, 2nd edn. (2001)