\documentclass[dvips,10pt,b5paper]{book}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[dvips]{graphicx}

\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{multirow}
\usepackage{enumerate}

\usepackage{AlgofInfColor23January2011}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Automata
\usepackage{emlines,emlines2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Compilers
\usepackage[emtex,dvips,all]{xy} 
\usepackage{hhline} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Reliable
\usepackage{enumerate}
\usepackage{amsmath,amssymb}

\addtocounter{part}{0}
\addtocounter{chapter}{28}
\setcounter{page}{1451}
\setcounter{tocdepth}{2}

\topmargin -10mm
\oddsidemargin 0.0in
\evensidemargin 0.0in

\makeindex


\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Zset{\mathbb{Z}}


\begin{document}
\tableofcontents

\chapter{ Perfect Arrays}

\noindent An $(n,a,b)$-perfect double cube is a $b \times b \times b$ sized $n$-ary periodic array 
containing all possible $a \times a \times a$ sized $n$-ary array exactly once as subarray.
A growing cube is an array whose $c_j \times c_j \times c_j$ sized prefix is an
$(n_j,a,c_j)$-perfect double cube for $j = 1, 2, \ldots$, where $c_j = n_j^{v/3}, \ v = a^3$
and $ n_1 < n_2 < \cdots.$ We construct the smallest possible perfect double cube (a $256 \times 256 \times 256$
sized 8-ary array) and growing cubes for any $a$. 

\section{Basic concepts}
Cyclic sequences in which every possible sequence of a fixed length occurs exactly once have been studied 
for more than a hundred years. The same problem, which can be applied to position localization, 
was extended to arrays by Fan et al. in 1985.

Let $\Zset$ be the set of integers. For $u, \ v \in \Zset$ we
denote the set $\{j \in \Zset \ | \ u \leq j \leq v \}$ by
$[u..v]$ and the set $\{j \in \Zset \ | \ j \geq u\}$ by
$[u..\infty]$. Let $d \in [1..\infty]$ and $k, \ n \in
[2..\infty],$ $b_i, \ c_i, \ j_i \in [1..\infty]  \ (i \in
[1..d])$ and $a_i, \ k_i \in [2..\infty] \ (i \in [1..d]).$ Let
$\mathbf{a} = \langle a_1,a_2,\ldots,a_d\rangle,$ $\mathbf{b} =
\langle b_1,b_2,\ldots,b_d\rangle,$ $\mathbf{c} = \langle
c_1,c_2,\ldots,c_d \rangle, \ \mathbf{j} = \langle
j_1,j_2,\ldots,j_d \rangle$ and $\mathbf{k} = \langle
k_1,k_2,\ldots,k_d \rangle$ be vectors of length $d$, $\mathbf{n}
= \langle n_1,n_2,\ldots \rangle$ an infinite vector with $2 \leq n_1 <
n_2 < \cdots$.

A \ki{d-dimensional n-ary array A} is a mapping $A : [1..\infty]^d \rightarrow [0,n-1].$  

If there exist a vector $\mathbf{b}$ and an array $M$ such that
$$\forall \mathbf{j} \in [1..\infty]^d :
A[\mathbf{j}]=M[(j_1 \ \mathrm{mod} \ b_1)+1, (j_2 \ \mathrm{mod}
\ b_2)+1,\ldots,(j_d \ \mathrm{mod} \ b_d)+1],$$ 
then A is a \textbf{b}\ki{periodic array} and $M$ is a period of $A.$
 
 The \ki{$\mathbf{a}$-sized \textbf{subarrays} of $A$} are the
$\mathbf{a}$-periodic $n$-ary arrays.

Although our arrays are infinite we say that a \textbf{b}-periodic array is \textbf{b}\ki{-sized.}

\ki{Indexset $A_{\hbox{index}}$} of a $\mathbf{b}$-periodic array $A$ is the Cartesian product
$$A_{index} = \times_{i = 1}^{d} [1..b_i]\koz.$$

A $d$ dimensional $\mathbf{b}$-periodic $n$-ary array $A$ is called 
\ki{$(n,d,\mathbf{a},\mathbf{b})$-perfect,} if all possible $n$-ary arrays of size $\mathbf{a}$ appear in
$A$ exactly once as a subarray.

Here $n$ is the alphabet size, $d$ gives the number of dimensions
of the ``window'' and the perfect array $M,$ the vector $\mathbf{a}$
characterizes the size of the window,  and the vector $\mathbf{b}$
is the size of the perfect array $M.$

An $(n,d,\mathbf{a},\mathbf{b})$-perfect array $A$ is called \ki{$\mathbf{c}$-cellular,} 
if $c_i$ divides $b_i$ for $i \in [1..d]$. A cellular array
consists of $b_1/c_1 \times b_2/c_2 \times \cdots \times b_d/c_d$
disjoint subarrays of size $\mathbf{c},$ called \ki{cells.} In
each cell the element with smallest indices is called the
\ki{head} of the cell. The contents of the cell is called \ki{pattern.}

The product of the elements of a vector $\mathbf{a}$ is called the \ki{volume}
of the vector and is denoted by $|\mathbf{a}|.$ The number of elements of the 
perfect array $M$ is called the \ki{volume} of $M$ and is denoted by $|M|.$

If $b_1 = b_2 = \cdots = b_d,$ then the $(n,d,\mathbf{a},\mathbf{b})$-perfect
array $A$ is called \textbf{symmetric}. If $A$ is symmetric and
$a_1 = a_2 = \cdots = a_d,$ then $A$ is called \textbf{doubly
symmetric.} If $A$ is doubly symmetric and
\begin{enumerate}
\item $d = 1,$ then $A$ is called a \ki{double sequence;}
\item $d = 2,$ then $A$ is called a \ki{double square;} 
\item $d = 3,$ then $A$ is called a \ki{double cube.}
\end{enumerate}

According to this definition, all perfect sequences are doubly
symmetric. In the case of symmetric arrays we use the notion
$(n,d,\mathbf{a},b)$ and in the case of doubly symmetric arrays we
use $(n,d,a,b)$ instead of $(n,d,\mathbf{a},\mathbf{b}).$

The first known result originates from Flye-Sainte\nevindex{Flye-Sainte,T. Marie} who proved 
the existence of $(2,1,a,2^a)$-perfect sequences for all possible values of $a$ in 1894.

One dimensional perfect arrays are often called de Bruijn or Good sequences. 
Two dimensional perfect arrays are called also perfect maps or de Bruijn tori.

Even De Bruijn sequences---introduced by Antal Iv�nyi and Zolt�n T�th in 1988---are useful in construction 
of perfect arrays when the size of the alphabet is an even number and the
window size is $2 \times 2.$ Their definition is as follows.

If $n$ is an even integer then an $(n,1,2,n^2)$-perfect sequence
$M = (m_1,m_2,$ $\ldots,m_{n^2})$ is called \ki{even,} if 
$m_i = x, \ m_{i + 1} = y, \ x \neq y, m_j = y$ and $m_{j + 1} = x$ imply $j - i$ is even.

Iv�nyi and T�th in 1988 and later Hurlbert and Isaak in 1994  
provided a constructive proof of the existence of even sequences. The later algorithm is stronger 
since it constructs a universal infinite sequence whos prefixes are even sequences for the corresponding 
alphabet size.

\ki{Lexicographic indexing} of an array $M = [m_{j_1j_2\ldots j_d}] = [m_{\mathbf{j}}]$ $(1\leq$ \linebreak 
\noindent $j_i\leq b_i)$ for $i \in [1..d]$ means that the index $I(m_{\mathbf{j}})$ is defined as
$$I(m_{\mathbf{j}}) = j_1 - 1 + \sum_{i = 2}^d \left ((j_i - 1) \prod_{m=1}^{i-1} b_m \right ).$$

The concept of perfectness can be extended to infinite arrays in
various ways. In \ki{growing arrays} introduced by G. Hurlbert and G. isaak in 1994 
the window size is fixed, the alphabet size is increasing and the
prefixes grow in all $d$ directions.

Let $a$ and $d$ be positive integers with $a \geq 2$ and $\mathbf{n} = 
\langle n_1, n_2, \ldots \rangle$
be a strictly increasing sequence of positive integers. An array $M = [m_{i_1 i_2 \ldots i_d}]$ is called
\ki{$(\mathbf{n},d,a)$-growing,} if the following conditions hold:
\begin{enumerate}
\item $M = [m_{i_1 i_2 \ldots i_d}] \ (1 \leq i_j < \infty)$
for $j \in [1..d]$;
\item $m_{i_1 i_2 \ldots i_d} \in [0..n - 1]$;
\item the
prefix $M_k = [m_{i_1 i_2 \ldots i_d}] \ (1 \leq i_j \leq
n_k^{a^d/d} for \ j \in [1..d])$ of $M$ is
$(n_k,d,a,n_k^{a^d/d})$-perfect array for $k \in [0..\infty].$
\end{enumerate}

For the growing arrays we use the terms growing sequence, growing square and growing cube.

For $a, n \in [2..\infty]$ the \ki{new alphabet size} $N(n,a)$ is
\begin{equation}
N{(n,a)} = \left\{ \begin{array}{ll}
n,              & \ if \ any \ prime \ divisor \ of \ a \ divides \ n\koz, \\
nq,              & \ otherwise\koz,\label{eqn:new}
\end{array}
\right.
\end{equation}
where $q$ is the product of the prime divisors of $a$ not dividing $n.$

Note, that alphabet size $n$ and new alphabet size $N$ have the
property that $n \mid N,$ furthermore, $n = N$ holds in the most
interesting case $d = 3$ and $n = a_1 = a_2 = a_3 = 2.$

The aim of this chapter is to prove the existence of a double cube.
As a side-effect we show that there exist
$(\mathbf{n},d,a)$-growing arrays for any $n,$ $d$ and $a.$

\section{Necessary condition and earlier results}
Since in the period $M$ of a perfect array $A$ each element is the
head of a pattern, the volume of $M$ equals the number of the
possible patterns. Since each pattern -- among others the pattern
containing only zeros -- can appear only once, any size of $M$ is
greater then the corresponding size of the window. So we have the
following necessary condition due to Cook,\nevindex{Cock, J. C.} further 
Hurlbert\nevindex{Hurlbert, Glenn} and Isaak:\nevindex{Isaak, Garth} If
$M$ is an $(n,d,\mathbf{a},\mathbf{b})$-perfect array, then
\begin{equation}
|\mathbf{b}| = n^{|\mathbf{a}|} \label{eq-neclong1}
\end{equation}
and
\begin{equation}
b_i > a_i \ \mathrm{for} \ i \in [1..d]\koz.\label{eq-neclong2}
\end{equation}

Different construction algorithms and other results concerning one and two dimensional perfect arrays
can be found in the fourth volume of \textit{The Art of Computer Programming} written by D. E. Knuth
\cite{Knuth2011}. E.g. a (2,1,5,32)-perfect array \cite[page 22]{Knuth2011},
a 36-length even sequence whose 4-length and 16-length prefixes are also even sequences
\cite[page 62]{Knuth2011}, a (2,2,2,4)-perfect array
\cite[page 38]{Knuth2011} and a (4,2,2,16)-perfect array \cite[page 63]{Knuth2011}.

It is known \cite{Bruijn46,Knuth2011} that in the one-dimensional
case the necessary condition (\ref{eq:neclong}) is sufficient too.
There are many construction algorithms, like the ones of
 Cock \cite{Cock1988}, Fan, Fan, Ma and 
 Siu\nevindex{Siu, M. K.} \cite{FanFMS1985}, Martin \cite{Martin34}
 or any algorithm for constructing of directed Euler cycles \cite{Lovasz1979}.

Chung, Diaconis and Graham \cite{ChungGD1992} posed the problem to give a necessary and 
sufficient condition of the existence of $(n,2,\mathbf{a,b})$-perfect arrays.

The conditions (2) and (3) are sufficient for the existence of
(2,2,\textbf{a},\textbf{b})-perfect arrays \cite{FanFMS1985}
and (n,2,a,b)-perfect arrays \cite{Paterson1994}. Later Paterson in
\cite{Paterson1996I,Paterson1996II} supplied further sufficient conditions.

Hurlbert and Isaak \cite{HurlbertI1994}
gave a construction for one and two dimensional growing arrays.


\section{One-dimensional arrays\label{sectiononeinfinite}}
In the construction of one-dimensional perfect arrays we use the following algorithms.

Algorithm \textsc{Martin} generates one-dimensional perfect arrays.\index{one-dimensional perfect array}
Its inputs are the alphabet size $n$ and the window size $a.$ Its output
is an $n$-ary perfect sequence\index{nary perfect sequence@$n$-ary perfect sequence} 
of length $n^a.$ The output begins with
$a$ zeros and always continues with the maximal permitted element of the alphabet.

\subsection{Pseudocode of the algorithm \textsc{Quick-Martin}}\inddef{\textsc{Quick-Martin}}
A natural implementation of Martin's algorithm can be found in the chapter \textit{Complexity of words} 
of this book. The following effective implementation of \textsc{Martin} is due to M. Horv�th\nevindex{Horv�th, M�rk} 
and A. Iv�nyi.\nevindex{Iv�nyi, Antal Mikl�s}

\smallskip
\textsc{Quick-Martin($n,a$)}\inddef{\textsc{Quick-Martin}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \key{for} \= $i = 0$ \key{to} $n^{a - 1} - 1$ \\
2              \> $C[i] = n - 1$ \\
3 \key{for} \= $i = 1$ \key{to} $a$ \\
4              \> $w[i] = 0$ \\
5 \key{for} \= $i = a + 1$ \key{to} $n^a$ \\
6              \> $k = w[i - a + 1]$ \\
7              \> \key{for} \= $j = 1$ \key{to} $a - 1$ \\
8              \>              \> $k = k n + w[i - a + j]$ \\
9              \> $w[i] = C[k]$ \\
10             \> $C[k] = C[k] - 1$ \\
11 \key{return} $\mathbf{w}$
\end{tabbing}

This algorithm runs in $\Theta(an^a)$ time. The following implementation of Martin algorithm requires 
even smaller time.

\subsection{Pseudocode of the algorithm \textsc{Optimal-Martin}}\inddef{\textsc{Optimal-Martin}}
\smallskip
\textsc{Optimal-Martin($n,a$)}\inddef{\textsc{Optimal-Martin}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \key{for} \= $i = 0$ \key{to} $n^{a - 1} - 1$ \\
2              \> $C[i] = n - 1$ \\
3 \key{for} \= $i = 1$ \key{to} $a$ \\
4              \> $w[i] = 0$ \\
5 \key{for} \= $i = a + 1$ \key{to} $n^a$ \\
6              \> $k = w[i - a + 1]$ \\
7              \> \key{for} \= $j = 1$ \key{to} $a - 1$ \\
8              \>              \> $k = k n + w[i - a + j]$ \\
9              \> $w[i] = C[k]$ \\
10             \> $C[k] = C[k] - 1$ \\
11 \key{return} $\mathbf{w}$
\end{tabbing}

The running time of any algorithm which constructs a on??? perfect array is $\Omega(n^a),$ since 
the sequance contains $n^a$ elements. The running time of \textsc{Optimal-Martin} is $\Theta(n^a).$

\subsection{Pseudocode of the algorithm \textsc{Shift}}\inddef{\textsc{Shift}}
Algorithm \textsc{Shift} proposed by Cook in 1988 is a widely usable
algorithm to construct perfect arrays. We use it to transform cellular $(N,d,a,\mathbf{b})$-perfect arrays
into $(N,d + 1, a,\mathbf{c})$-perfect arrays.

\smallskip
\textsc{Shift}$(N,d,a,P_d,P_{d + 1})$\inddef{\textsc{Shift}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \textsc{Martin}$(N^{a^d},a - 1,\mathbf{w})$\\
2 \key{for} \= $j = 0$ \key{to} $N^{a^d - a^{d - 1}}- 1$ \\
3            \> transform $w_i$ to an $a^d$ digit $N$-ary number \\
4            \> produce the $(j+1)$-st layer of the output $P_{d + 1}$ by multiple shifting \\
             \> the $j$th layer of $P_d$ by the transformed number (the first $a$ digits \\
             \> give the shift size for the first direction, then the next $a^2-a$ digits \\
             \> in the second direction etc.) \\
5 \key{return} $P_{d + 1}$
\end{tabbing}

\subsection{Pseudocode of the algorithm \textsc{Even}}

If $N$ is even, then this algorithm generates the $N^2$-length prefix of an even
growing sequence \cite{HurlbertI1994}.

\smallskip
\textsc{Even($N,\mathbf{w}$)}\inddef{\textsc{Even}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \textbf{if} \= $N == 2$  \\
2             \> $w[1] = 0$ \\
3             \> $w[2] = 0$ \\
4             \> $w[3] = 1$ \\
5             \> $w[4] = 1$ \\
6             \> \key{return w} \\
7 \key{for} \= $i = 1$ \key{to} $N/2 - 1$ \\
8           \> \key{for} \= $j = 0$ \key{to} $2i - 1$ \\
9           \>           \> $w[4i^2 + 2j + 1] = j$ \\
10          \> \key{for} \= $j = 0$ \key{to} $i - 1$ \\
11          \>           \> $w[4i^2 + 2 + 4j] = 2i$ \\
12          \> \key{for} \= $j = 0$ \key{to} $i - 1$ \\
13          \>           \> $w[4i^2 + 4 + 4j] = 2i + 1$ \\
14          \> \key{for} \= $j = 0$ \key{to} $4i - 1$ \\
15          \>           \> $w[4i^2 + 4i + 1 + j] = w[4i^2 + 4i - j]$ \\
16          \> $w[4i^2 + 8i + 1] = 2i + 1$ \\
17          \> $w[4i^2 + 8i + 2] = 2i$ \\
18          \> $w[4i^2 + 8i + 3] = 2i$ \\
19          \> $w[4i^2 + 8i + 4] = 2i + 1$ \\
20 \key{return} $\mathbf{w}$
\end{tabbing}

Algorithm \textsc{Even} \cite{HurlbertI1994} produces even de Bruijn sequences.

\section{One dimensional words with fixed length\label{sectiononefixedlength}}

\section{Two-dimensional infinite arrays\label{sectiontwo}}
Chung, Diaconis and Graham posed the problem to give a necessary and sufficient condition of the
existence of $(n,2,\mathbf{a,b})$-perfect arrays.

As Fan, Fan and Siu\nevindex{Siu, M. K.} proved in 1985, the conditions (2) and (3) 
are sufficient for the existence of
(2,2,\textbf{a},\textbf{b})-perfect arrays. Paterson proved the same in 1994 for  
$(n,2,a,b)$-perfect arrays. leter Paterson supplied further sufficient conditions.

Hurlbert and Isaak in 1993 gave a construction for one and two dimensional growing arrays.

\subsection{Pseudocode of the algorithm \textsc{Mesh}}
The following implementation of \textsc{Mesh} is was proposed by Iv�nyi\nevindex{Iv�nyi, Antal Mikl�s} 
and T�th\nevindex{T�th, Zolt�n} in 1988.

\smallskip
\textsc{Mesh($N,\mathbf{w},S$)}\inddef{\textsc{Mesh}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \key{for} \= $i = 1$ \key{to} $N^2$ \\
2            \> \key{for} \= $j = 1$ \key{to} $N^2$ \\
3            \>           \> \key{if} \ \ \ \= $i + j$ is even \\
4            \>           \>               \> $S[i,j] = w[i]$ \\ 
5            \>           \> \key{else}    \> $S[i,j] = w[j]$ \\
6 \key{return} $S$
\end{tabbing}

\subsection{Pseudocode of the algorithm \textsc{Cellular}}
This is an extension and combination of the known algorithms \textsc{Shift, Martin, Even} and
\textsc{Mesh}.

\textsc{Cellular} results cellular perfect arrays.
Its input data are $n, \ d$ and $\mathbf{a}$, its output is an $(N,d,\mathbf{a},\mathbf{b})$-perfect array,
where $b_1 = N^{a_1}$ and $b_i = N^{a_1a_2\ldots a_i - a_1a_2\ldots a_{i-1}}$ for $i = 2, 3, \ldots, d.$
\textsc{Cellular} consists of five parts:
\begin{enumerate}
\item \textit{Calculation} (line 1 in the pseudocode) determining
the new alphabet size $N$ using formula (\ref{eqn:new});
\item
\textit{Walking} (lines 2--3) if $d = 1,$ then construction of a perfect symmetric sequence $S_1$ using algorithm
\textsc{Martin} (walking in a de Bruijn graph);
\item
\textit{Meshing} (lines 4--6) if $d = 2, \ N$ is even and $a = 2,$ then
first construct an $N$-ary even perfect sequence
$\mathbf{e} = \langle e_1,e_2,\ldots, e_{N^2} \rangle$ using \textsc{Even},
then construct an $N^2 \times N^2$ sized $N$-ary square $S_1$
using meshing
function (\ref{eqn:mesh});
\item
\textit{Shifting} (lines 7--12) if $d > 1$ and $(N  \ \mathrm{is \ odd \ or} \ a > 2),$ then use \textsc{Martin} once, then
use \textsc{Shift} $d - 1$ times, receiving a perfect array $P;$
\item
\textit{Combination} (lines 13--16) if $d > 2, \ N$ is even and $a = 2,$
then construct an even sequence with \textsc{Even,}
construct a perfect square by \textsc{Mesh} and finally use of
\textsc{Shift} $d - 2$ times, results a perfect array $P.$
\end{enumerate}

\smallskip
\textsc{Cellular($n,d,a,N,A$)}\inddef{\textsc{Cellular}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 $N = N(n,a)$ \\
2 \key{if} \= $d = 1$ \\ 
3          \> \textsc{Martin}$(N,d,a,A$) \\
4 \key{return} $A$ \\
5 \key{if} \= $d == 2$ and $a == 2$ and $N$ is even  \= \\
6          \> \textsc{Mesh}($N,a,A$) \\
7          \> \key{return} $A$ \\
8 \key{if} \= $N$ is odd or $a \neq 2$\\
9          \> \textsc{Martin$(N,a,P_1)$} \\
10         \> \key{for} \= $i = 1$ \key{to} $d - 1$ \\
11         \>           \> \textsc{Shift}$(N,i,P_i,P_{i+1})$ \\
12         \>            \> $A = P_1$ \\
13         \> \key{return} $A$ \\
14 \textsc{Mesh}$(N,a,P_1)$ \\
15 \key{for} \= $i = 2$ \key{to} $d - 1$ \\
16           \> \textsc{Shift}$(N,i,P_i,P_{i+1})$ \\
17 $A \leftarrow P_d$ \\
18 \key{return} $P_d$ \\
\end{tabbing}

\section{Three-dimensional infinite cubes\label{sectioncubes}} 

\subsection{Pseudocode of the algorithm \textsc{Colour}}
\textsc{Colour} transforms cellular perfect arrays into larger cellular perfect arrays.
Its input data are
\begin{itemize}
\item
$d \geq 1$ -- the number of dimensions;
\item
$N \geq 2$ -- the size of the alphabet;
\item
$ \mathbf{a}$ -- the window size;
\item
$ \mathbf{b}$ -- the size of the cellular perfect array $A$;
\item
$A$ -- a cellular $(N,d,\textbf{a},\textbf{b})$-perfect array.
\item
$k \geq 2$ -- the multiplication coefficient of the alphabet;
\item
$\langle k_1,k_2,\ldots,k_d \rangle$  --
the extension vector having the property $k^{|\mathbf{a}|} = k_1 \times k_2 \times \cdots \times k_d.$
\end{itemize}

The \textit{output} of \textsc{Colour} is
\begin{itemize}
\item
a $(kN)$-ary cellular perfect array $P$ of size  $\mathbf{b} =
\langle k_1 a_1,k_2 a_2,\ldots,k_d a_d \rangle.$
\end{itemize}

\textsc{Colour} consists of three steps:
\begin{enumerate}
\item
\textit{Blocking:} (line 1) arranging $k^{|\mathbf{a}|}$ copies (blocks) of a cellular perfect array
$A$ into a rectangular array $R$ of size $\mathbf{k} = k_1 \times k_2 \times \cdots \times k_d$ 
and indexing the blocks lexicographically (by $0, \ 1, \ldots, k^{|\mathbf{a}|}-1$);
\item
\textit{Indexing:} (line 2) the construction of a lexicographic indexing scheme $I$ containing the
elements $0, 1, \ldots k^{|a|} - 1$ and having the same structure as the array $R$, then construction of a
colouring matrix $C$, transforming the elements of $I$ into $k$-ary numbers consisting of $|\mathbf{a}|$
digits;
\item
\textit{Colouring:} (lines 3-4) colouring $R$ into a symmetric perfect array $P$ using the colouring array
$C$ that is adding the $N$-fold of the $j$-th element of $C$ to each
cell of the $j$-th block in $R$ (considering the
elements of the cell as lexicographically ordered digits of a number).
\end{enumerate}

The output $P$ consists of blocks, blocks consist of cells and cells consists of elements.
If $e = P[\mathbf{j}]$ is an element of $P,$ then the lexicographic index of the block containing
$e$ is called the \textbf{\textit{blockindex}} of $e,$ the lexicographic index of the cell containing $e$
is called the \textbf{\textit{cellindex}} and the lexicographic
index of $e$ in the cell is called
\textbf{\textit{elementindex}}.  E.g. the element $S_2[7,6] = 2$ in Table 3 has blockindex 5, cellindex 2
and elementindex 1.


Input parameters are $N, \ d, \ a, \ k, \ \mathbf{k},$ a cellular $(N,d,a,\mathbf{b})$-perfect array $A,$
the output is a $(kN,d,\mathbf{a},\mathbf{c})$-perfect array $P,$ where
$\mathbf{c} = \langle a_1k_1,a_2k_2, \ldots, a_dk_d \rangle.$

\smallskip
\textsc{Colour($N,d,\mathbf{a},k,\mathbf{k},A,P$)}\inddef{\textsc{Colour}}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \= arrange the copies of $P$ into an array $R$ of size \\
  \> $k_1 \times k_2 \times \cdots \times k_d$ blocks \\
2 \= construct a lexicographic indexing scheme $I$ containing the elements \\
  \> of $[0..k^{a^d}-1]$ and having the same structure as $R$ \\
3 \= construct an array $C$ transforming the elements of $I$ into $k$-ary \\
  \> numbers of $v$ digits and multiplying them by $N$ \\
4 \= produce the output $S$ adding the $j$-th $(j \in [0..k^{a^d}-1])$ element of $C$ \\
  \> to each cell of the $j$-th block in $R$ for each block of $R$\\
5 \key{return} $S$ \\
\end{tabbing}

\subsection{Pseudocode of the algorithm \textsc{Growing}}
Finally, algorithm \textsc{Growing} generates a prefix $S_r$ of a growing array $G.$
Its input data are $r,$ the number of required doubly perfect prefixes of the growing array $G$,
then $n, d$ and $\mathbf{a}.$
It consists of the following steps:

\begin{enumerate}
\item
\textit{Initialization}: construction of a cellular perfect array $P$ using \textsc{Cellular};
\item
\textit{Resizing:} if the result of the initialization is not doubly symmetric, then
construction of a symmetric perfect array $S_1$ using \textsc{Colour}, otherwise we take $P$ as $S_1$;
\item
\textit{Iteration}: construction of the further $r - 1$ prefixes of the growing array $G$
repeatedly, using \textsc{Colour}.
\end{enumerate}

Input parameters of \textsc{Growing} are $n, \ d, \ a$ and $r,$ the output is a doubly symmetric perfect
array $S_r,$ which is the $r$th prefix of an $(\mathbf{n},d,a)$-growing array.


\textsc{Growing($n,d,a,r,S_r$)}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \textsc{Cellular($n,d,a,N,P$)} \\
2 calculation of $N$ using formula (\ref{eqn:new}) \\
3 \key{if} \= $P$ is symmetric \\ 
4          \> $S_1 = P$ \\
5 \key{if} \= $P$ is not symmetric \\
6          \> $n_1 = N^{d/\mathrm{gcd}(d,a^d)}$ \\
7          \> $k = n_1/N$ \\
8          \> $k_1 = (n_1)^{a^d/3}/N^a$ \\
9          \> \key{for} \= $i = 2$ \key{to} $d$ \\
10         \>           \> $k_i = (n_1)^{a^d/d}/N^{a^i - a^{i-1}}$ \\
11         \>           \> \textsc{Colour($n_1,d,a,k,\mathbf{k},P,S_1$)} \\
12 $k = N^d/\mathrm{gcd}(d,a^d)$ \\
13 \key{for} \= $i = 1$ \key{to} $d$ \\
14           \> $k_i = (n_2)^{a^d/d}/N^{a^i - a^{i-1}}$ \\
15 \key{for} \= $i = 2$ \key{to} $r$ \\
16           \> $n_i = N^{di/\mathrm{gcd}(d,a^d)}$ \\
17           \> \textsc{Colour$(n_i,d,\mathbf{a},k,\mathbf{k},S_{i-1},S_i)$} \\
18 \key{return} $S_r$
\end{tabbing}

\section{Examples of constructing growing arrays using colouring}
In this section particular constructions are presented.

\subsection{Construction of growing sequences}
As the first example let $n = 2, \ a = 2$ and $r = 3.$
\textsc{Cellular} calculates $N = 2$
and \textsc{Martin} produces the cellular (2,1,2,4)-perfect
sequence $P = 0 0 | 1 1.$

Since $P$ is symmetric, $S_1 = P.$ Now \textsc{Growing} chooses  multiplication coefficient
$k = n_2/n_1 = 2,$ extension vector $\mathbf{k} = \langle 4 \rangle$ and uses \textsc{Colour}
to construct a 4-ary perfect sequence.

\textsc{Colour} arranges $k_1 = 4$ copies into a $4$ blocks sized arrray receiving
\begin{equation}
R = 0 0 | 1 1 \ || \  0  0 | 1  1 \ || \  0  0 | 1  1 \ || \  0  0 | 1  1.
\end{equation}

\textsc{Colouring} receives the indexing scheme $I = 0 \ 1 \ 2
\ 3,$ and
the colouring matrix $C$ transforming the elements of $I$ into $a$ digit length
$k$-ary numbers: $C = 0 0 \ || \ 0 1 \ || \ 1 0 \ || \ 1 1.$

Finally we colour the matrix $R$ using $C$ -- that is multiply the elements of $C$ by $n_1$
and adding the $j$-th $(j = 0, 1, 2, 3)$
block of $C_1 = n_1C$ to both cells of the $j$-th copy in $R$:

\begin{equation}
S_2 = 0 0 | 1 1 \ || \  0  2 | 1  3 \ || \  2  0 | 3  1 \ || \  2  2 | 3  3.
\end{equation}

Since $r = 3,$ we use \textsc{Colour} again with $k = n_3/n_2 = 2$
and get the (8,1,2,64)-perfect sequence $S_3$ repeating $S_2$ 4
times, using the same indexing array $I$ and colouring array $C' =
2C$.

Another example is $a = 2, \ n= 3$ and $r = 2.$ To guarantee the cellular property now
we need a new alphabet size $N = 6.$ Martin produces a (6,1,2,36)-perfect sequence $S_1,$
then \textsc{Colour} results a (12,1,2,144)-perfect sequence $S_2.$

\subsection{Construction of growing squares}
Let $n = a = 2$ and $r = 3.$ Then $N(2,2) = 2.$
We construct the even sequence $W_4 = e_1 e_2 e_3 e_4 = 0 \  0 \ 1 \ 1$ using
\textsc{Even} and the symmetric perfect array $A$ in Table \ref{tab:perf2244}.a
using the meshing function (\ref{eqn:mesh}). Since $A$ is symmetric, it can be used as
$S_1.$ Now the greatest common divisor of
$a$ and $a^d$ is 2, therefore indeed $n_1 = N^{2/2} = 2.$

\begin{table}
\caption{a) A (2,2,4,4)-square \hspace{24mm} b) Indexing scheme $I$ of size $4 \times 4$\label{tab:perf2244}\label{tab:ind16}}
\begin{tabular}{|c||c|c|c|c|||c||c|c|c|c|}  \hline
column/row & 1   &  2   &  3 & 4 & \hspace{1cm} column/row & 1   & 2   &  3 & 4 \\ \hline \hline
1          & 0   &  0   & 0 & 1  & \hspace{1cm} 1          & \ 0 & \ 1 &\ 2 &\ 3 \\ \hline
2          & 0   &  0  & 1  & 0  & \hspace{1cm} 2          &\ 4  &\ 5  & 6  & 7 \\ \hline
3          & 1   & 0   & 1  & 1  & \hspace{1cm} 3          & 8   & 9   & 10 & 11   \\ \hline
4          & 0   & 1   & 1  & 1  & \hspace{1cm} 4          & 12  & 13  & 14 & 15  \\ \hline
\end{tabular}
\end{table}


\textsc{Growing} chooses $k = n_1/N = 2$ and \textsc{Colour}
returns the array $R$ repeating the array $A$ $k^2 \times k^2 = 4
\times 4$ times.

\textsc{Colour} uses the indexing scheme $I$ containing $k^4$
indices in the same $4 \times 4$ arrangement as it was used in
$R$. Table \ref{tab:ind16}.b shows $I.$

Transformation of the elements of $I$ into 4-digit $k$-ary form
results the colouring matrix $C$ represented in Table \ref{tab:col16}.

\begin{table}
\caption{Binary colouring matrix $C$ of size $8 \times 8$} \label{tab:col16}
\begin{tabular}{|c||c c|c c|c c|c c|}  \hline \hline
column/row & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8   \\ \hline
1          & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  \\
2          & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline
3          & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
4          & 0 & 0 & 0 & 1 & 1 & 0 & 1  & 1 \\ \hline
5          & 1 & 0 & 1 & 0 & 1 & 0 & 1  & 0 \\
6          & 0 & 0 & 0 & 1 & 1 & 0 & 1  & 1  \\\hline
7          & 1 & 1 & 1 & 1 & 1 & 1 & 1  & 1  \\
8          & 0 & 0 & 0 & 1 & 1 & 0 & 1  & 1 \\ \hline
\end{tabular}
\end{table}

Colouring of array $R$ using the colouring array $2C$ results the (4,2,2,16)-square $S_2$ represented
in Table \ref{tab:perf16}.

In the next iteration \textsc{Colour} constructs an 8-ary square repeating
$S_2$ $4 \times 4$ times, using the same indexing scheme $I$ and
colouring by $4C.$ The result is $S_3,$ a $(8,2,2,64)$-perfect square.


\begin{table}
\caption{A (4,2,2,16)-square generated by colouring} \label{tab:perf16}
\begin{tabular}{|c||c|c|c|c||c|c|c|c||c|c|c|c||c|c|c|c|}  \hline
column/row & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline  \hline
1          & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 &  0  & 1  &  0 & 0  & 0  &  1  \\
2          & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 2 & 2 & 0 &  3  & 0  &  2 & 2  & 3  &  2   \\ \hline
3          & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 &  1  & 1  &  1 & 0  & 1  & 1   \\
4          & 0 & 1 & 1 & 1 & 0 & 3 & 1 & 3 & 2 & 1 &  3  & 1  &  2 & 3  & 3  & 3  \\ \hline \hline
5          & 0 & 2 & 0 & 3 & 0 & 2 & 0 & 3 & 0 & 2 &  0  & 3  &  0 & 2  & 0  &  3  \\
6          & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 2 & 2 & 0 &  3  & 0  &  2 & 2  & 3  &  2   \\ \hline
7          & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 3 & 1 & 2 &  1  & 3  &  1 & 2  & 1  & 3   \\
8          & 0 & 1 & 1 & 1 & 0 & 3 & 1 & 3 & 2 & 1 &  3  & 1  &  2 & 3  & 3  & 3  \\ \hline \hline
9          & 2 & 0 & 2 & 1 & 2 & 0 & 2 & 1 & 2 & 0 &  2  & 1  &  2 & 0  & 2  &  1  \\
10         & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 2 & 2 & 0 &  3  & 0  &  2 & 2  & 3  &  2   \\ \hline
11         & 3 & 0 & 3 & 1 & 3 & 0 & 3 & 1 & 3 & 0 &  3  & 1  &  3 & 0  & 3  & 1   \\
12         & 0 & 1 & 1 & 1 & 0 & 3 & 1 & 3 & 2 & 1 &  3  & 1  &  2 & 3  & 3  & 3  \\ \hline \hline
13         & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 &  2  & 3  &  2 & 2  & 2  &  3  \\
14         & 0 & 0 & 1 & 0 & 0 & 2 & 1 & 2 & 2 & 0 &  3  & 0  &  2 & 2  & 3  &  2   \\ \hline
15         & 3 & 2 & 3 & 3 & 3 & 2 & 3 & 3 & 3 & 2 &  3  & 3  &  3 & 2  & 3  & 3   \\
16         & 0 & 1 & 1 & 1 & 0 & 3 & 1 & 3 & 2 & 1 &  3  & 1  &  2 & 3  & 3  & 3  \\ \hline \hline
\end{tabular}
\end{table}

\subsection{Construction of growing cubes}
If $d = 3,$ then the necessary condition (2) is $b^3 = (n)^{a^3}$
for double cubes, implying $n$ is a cube number or $a$ is a
multiple of 3. Therefore, either $n \geq 8$ and then $b \geq 256,$
or $a \geq 3$ and so $b \geq 512,$ that is, the smallest possible
perfect double cube is the (8, 3, 2, 256)-cube.

As an example, let $n = 2, \ a=2$ and $r = 2.$ \textsc{Cellular}
computes $N = 2,$ \textsc{Mesh} constructs the $(2,2,2,4)$-perfect
square in Table \ref{tab:perf2244}.a, then \textsc{Shift} uses
\textsc{Martin} with $N = 16$ and $a = 1$ to get the shift sizes
for the layers of the $(2,3,2,\mathbf{b})$-perfect output $P$ of
\textsc{Cellular}, where $\mathbf{b} = \langle 4,4,16 \rangle.$
\textsc{Shift} uses $P$ as zeroth layer and the $j$th $(j \in
[1:15])$ layer is generated by cyclic shifting of the previous
layer downwards by $w_i$ (div 4) and right by $w_i$ (mod 4), where
$\mathbf{w} = \langle 0$ 15  14  13  12  11  10 9 8  7 6 5 4 3 2
1$\rangle.$ 8 layers of $P$ are shown in Table \ref{tab:perf4416}.

\begin{table}
\caption{8 layers of a (2,3,2,16)-perfect
array}\label{tab:perf4416}
\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline \hline
Layer 0 & Layer 1 & Layer 2& Layer 3& Layer 4 & Layer 5 & Layer 6
& Layer 7 \\ \hline 0 0 0 1 & 0 0 0 1 &1 0 1 1 & 1 0 1 1 &1 0 1 1
& 1 0 1 1 & 1 0 1 1 & 1 0 1 1 \\ \hline 0 0 1 0 & 0 0 1 0 & 0 0 0
1 & 0 0 0 1 & 0 1 1 1 & 0 1 1 1& 0 1 1 1& 0 1 1 1 \\ \hline 1 0 1
1 & 1 0 1 1 & 1 0 1 1 & 1 0 1 1 &1 0 1 1 & 1 0 1 1 &1 0 1 1 & 1 0
1 1  \\ \hline 0 1 1 1 & 0 1 1 1 &1 0 1 1 & 1 0 1 1 &1 0 1 1 & 1 0
1 1 & 1 0 1 1 & 0 1 1 1\\ \hline
\end{tabular}
\end{table}

Let $A_3$ be a $4 \times 4 \times 16$ sized perfect, rectangular
matrix, whose 0. layer is the matrix represented in Table
\ref{tab:perf2244}, and the $(2,3,\mathrm{a},\mathrm{b})$-perfect
array $P$ in Table \ref{tab:perf4416}, where $\mathrm{a} =
(2,2,2)$ and $\mathrm{b} = (4,4,8).$

\textsc{Growing} uses \textsc{Colour} to retrieve a doubly
symmetric cube. $n_1 = 8,$ thus $b = 256, \ k = n_1/N = 4$ and
$\mathbf{k} = \langle 256/4,256/4,256/64 \rangle,$ that is we
construct the matrix $R$ repeating $P$ $64 \times 64 \times 16$
times.

$I$ has the size $64 \times 64 \times 16$ and $I[i_1,i_2,i_3] =
64^2 (i_1 - 1)  + 64 (i_2 - 1) + i_3 - 1$. \textsc{Colour} gets
the colouring matrix $C$ by transforming the elements of $I$ into
8-digit $4$-ary numbers -- and arrange the elements into $2 \times
2 \times 2$ sized cubes in lexicographic order -- that is in order
(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0),
(1,1,1). Finally colouring results a double cube $S_1$.

$S_1$ contains $2^{24}$ elements therefore it is presented only in electronic form (on the homepage of the
corresponding author).

If we repeat the colouring again with $k = 2,$ then we
get a 64-ary $65536 \times 64536 \times 64536$ sized double cube $S_2$.

\section{Proof of the main result}
The main result of this paper can be formulated as follows.
\begin{tetel} If $n \geq 2, \ d \geq 1, \ a \geq 2, \ n_j = N^{dj/\mathrm{gcd}(d,a^d)}$ with 
$N = N(n,a)$ given by (1) 
for $j \in [0..\infty],$ then there exists an $(\mathbf{n},d,a)$-growing array.
\end{tetel}

The proof is based on the following lemmas.
\begin{lemma} $(\mathrm{Cellular \ lemma})$ If $n \geq 2, \ d \geq 1$ and $a \geq 2,$ then algorithm
\textsc{Cellular} produces a cellular $(N,d,a,\mathbf{b})$-perfect
array $A$, where $N$ is determined by formula (\ref{eqn:new}), $b_1 = N^{a}$ and
$b_i = N^{a^i - a^{i - 1}} \ (i \in [2..d]).$
\end{lemma}
\begin{biz} It is known that algorithms $\textsc{Even} + \textsc{Mesh}$ and
$\textsc{Martin} + \textsc{Shift}$ result perfect outputs.

Since \textsc{Mesh} is used only for even alphabet size and for $2 \times 2$ sized window, the sizes of
the constructed array are even numbers and so the output array is cellular.

In the case of \textsc{Shift} we exploit that all prime divisors of $a$ divide the new alphabet
size $N,$ and $b_i = N^{(a-1)(a^{i-1})}$ and $(a-1)(a^{i-1}) \geq 1.$
\end{biz}

\begin{lemma} $(\mathrm{Indexing \ lemma})$ If $n \geq 2, \ d \geq 2, \ k \geq 2, \ C$ is a $d$ dimensional
$\mathbf{a}$-cellular array with $|\mathbf{b}| = k^{|\mathbf{a}|}$ cells and
each cell of $C$ contains the corresponding cellindex as an $|\mathbf{a}|$ digit $k$-ary number,
then any two elements of $C$ having the same elementindex and different cellindex
are heads of different patterns.
\end{lemma}
\begin{biz} Let $P_1$ and $P_2$ be two such patterns and let us suppose they are identical. Let
the head of $P_1$ in the cell have cellindex $g$ and head of $P_2$
in the cell have cellindex $h$ (both cells are in array $C$). Let
$g - h = u.$

We show that $u = 0 \ (\mathrm{mod} \ k^{|b|}).$ For example in Table 2 let the
head of $P_1$ be $(2,2)$ and the head of $P_2$ be $(2,6).$ Then these
heads are in cells with cellindex 0 and 2 so here $u = 2.$

In both cells, let us consider the position containing the values
having local value 1 of some number (in our example they are the
elements (3,2) and (3,6) of $C.$) Since these elements are
identical, then $k | u.$ Then let us consider the positions with
local values $k$ (in our example they are (3,1) and (3,5).) Since
these elements are also identical so $k^2|u.$ We continue this way
up to the elements having local value $k^{|b|}$ and get $k^{|b|} |
u$, implying $u = 0.$

This contradicts to the conditon that the patterns are in different cells.
\end{biz}

\begin{lemma} $(\mathrm{Colouring \ lemma})$ If $k \geq 2,$ $k_i \in [2..\infty] \ (i \in [1..d]),$ $A$
is a cellular $(n,d,\mathbf{a},\mathbf{b})$-perfect array, then algorithm
\textsc{Colour}$(N,d,\mathbf{a},k,\mathbf{k},A,S)$
produces a cellular $(kN,d,\mathbf{a},\mathbf{c})$-perfect array $P,$ where $\mathbf{c} = \langle k_1a_1,k_2a_2,
\ldots,k_da_d \rangle.$
\end{lemma}
\begin{biz} The input array $A$ is $N$-ary, therefore $R$ is also $N$-ary.
The colouring array $C$ contains the elements of $[0..N(k - 1)],$ so elements of $P$
are in $[0 .. kN-1]$.

The number of dimensions of $S$ equals to the number of dimensions
of $P$ that is, $d.$

Since $A$ is cellular and $c_i$ is a multiple of $b_i \ (i \in [1..d]), \ P$ is cellular.

All that has to be shown is that the patterns in $P$ are
different.


Let's consider two elements of $P$ as heads of two windows and their contents -- patterns
$p$ and $q.$ If these heads have different cellindex, then
the considered patterns are different due to the periodicity of $R.$
E.g. in Table \ref{tab:perf16} $P[11,9]$ has cellindex 8,
the pattern headed by $P[9,11]$ has cellindex 2, therefore they are different (see parity of the elements).


If two heads have identical cellindex but different blockindex, then the indexing lemma can be applied.
\end{biz}

\begin{biz} \textcolor{magenta}{\textbf{of the main theorem.}}
Lemma 18 implies that the first call of \textsc{Colour} in line 10 of \textsc{Growing} results a doubly
symmetric perfect output $S_1$. In every iteration step (in lines 14--16 of \textsc{Growing}) the zeroth block
of $S_i$ is the same as $S_{i-1},$ since the zeroth cell of the colouring
array is filled up with zeros.

Thus $S_1$ is transformed into a doubly symmetric perfect output
$S_r$ having the required prefixes $S_1, \ S_2, \ \ldots,
S_{r-1}$. 
\end{biz}

\section{Multi-dimensional infinite arrays\label{sectionmulti}}


\begin{fejmegj} 
Cyclic sequences in which every possible sequence of a fixed length occurs exactly once have been studied 
for more than a hundred years. The first proof of the existence of $(2,1,a,2^a)$-perfect sequences was 
published by Flye-Sainte\nevindex{Flye-Sainte, T. Marie} \cite{Flye1894} in 1894. The problem was extended 
to arrays by Fan, Fan, Ma, and 
Siu\nevindex{Siu, M. K.}\nevindex{Fan, C. T.}\nevindex{Fan, S. M.}\nevindex{Ma, S. L}\nevindex{Siu, M. K.}  
in 1985 \cite{FanFMS1985}.  

One dimensional perfect arrays are often called de Bruijn or Good sequences, since the papers of 
De Bruijn\nevindex{De Bruijn, Nicolaas Govert} \cite{Bruijn46} and Good\nevindex{Good, I. J.} 
\cite{Good1946} make these sequences popular. Two dimensional perfect arrays were called  
perfect maps by Reed\nevindex{Reed, I. S.} and Stewart\nevindex{Stewart, R. M.} in 1962 \cite{ReedS1962} 
and  by Paterson\nevindex{Paterson, Kenneth G.} in 1996 \cite{Paterson1996I}, 
or de Bruijn tori by Hurlbert\nevindex{Hurlbert, Glenn} and Isaak\nevindex{Isaak, Garth} and 
Mitchell\nevindex{Mitchell, Chris J.} in 1993 and later \cite{HurlbertI1993,HurlbertI1994,HurlbertMP1996}.

The even De Bruijn sequences were introduced by A. Iv�nyi\nevindex{Iv�nyi, Antal Mikl�s} and 
Z. T�th\nevindex{T�th, Zolt�n} in 1988 \cite{IvanyiT1988,Knuth2011}. 
They proposed an algorithm constructing even sequences 
for arbitrary alphabet size. Later Hurlbert\nevindex{Hurlbert, Glenn} and Isaak\nevindex{Isaak, Garth} 
\cite{HurlbertI1994} provided an universal algorithm which constructs an infinite sequence whose prefixes are 
even for the corresponding alphabet size. 

The concept of \ki{growing sequences}\inddef{growing sequence} was introduced by 
G. Hurlbert\nevindex{Hurlbert, Glenn} and G. Isaak\nevindex{Isaak, Garth} \cite{HurlbertI1994}.

The necessary conditions \ref{eq-neclong1} and \ref{eq-neclong2} were formulated at first in papers of    
Cock\nevindex{Cock, J. C.} in 1988 \cite{Cock1988}, and in 1994 of Hurlbert\nevindex{Hurlbert, Glenn} and 
Isaak \cite{HurlbertI2004}.\nevindex{Isaak, Garth} 

For Section \ref{sectiononefixedlength}:

For Section \ref{sectiontwo}:

For Section \ref{sectioncubes}:

\cite{Arazi84} \cite{ChungGD1992} \cite{Cock1988}

\cite{CormenLRS2009} \cite{CummingsW1986}

\cite{Bruijn46} \cite{DenesKeedwell1988} \cite{Flye1894} \cite{Good1946} \cite{HorvathI2008}

\cite{HurlbertI1993} \cite{HurlbertI1994} \cite{HurlbertI1995} \cite{HurlbertI1997}
 
\cite{HurlbertMP1996} \cite{Isaak2002}  

\cite{Ivanyi1987} \cite{Ivanyi1988} \cite{Ivanyi1990} \cite{IvanyiT1988} \cite{Knuth2011} 

\cite{Lovasz1979} \cite{Martin34} \cite{Mitchell1995} \cite{Paterson1994}

\cite{Paterson1996I} \cite{Paterson1996II} \cite{Petriou1989} \cite{Petriou1990}

\cite{ReedS1962} \cite{Voros84}

For Section \ref{sectionmulti}:
\end{fejmegj}

\bibliography{AlgofInf3-7March}
This bibliography is made by HBib\TeX. First key of the sorting is the name of 
the authors (first author, second author etc.), second key is the year of publication, 
third key is the title of the document.

Underlying shows that the electronic version of the bibliography on the homepage of the book 
contains a link to the corresponding address.
\bibliographystyle{algofinf}

\begin{printindex}
This index uses the following conventions. Numbers are alphabetised as if spelled out; for example, 
``2-3-4-tree" is indexed as if were ``two-three-four-tree". 
When an entry refers to a place other than the main text, the page number is followed by a tag: 
\textit{exe} for exercise, \textit{exa} for example, \textit{fig} for figure, \textit{pr} 
for problem and \textit{fn} for footnote.

The numbers of pages containing a definition are printed in \textit{italic} font, e.g. \\

time complexity, \underline{\textit{583}}.  
\end{printindex}

\begin{printnevindex}
This index uses the following conventions. If we know the full name of a cited person, then 
we print it. If the cited person is not living, and we know the correct data, then we print also the 
year of her/his birth and death.
\end{printnevindex}
\end{document}
