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

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

\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{multirow}
\usepackage{enumerate}

\usepackage{AlgofInfColor19March2011}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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\label{ch-perfect}}

\noindent Sequences of elements of given sets of symbols have a great importance in 
different branches of natural sciences. For example in biology the 4-letter 
set $\{A,C,G,T \}$ containing the nucleotides (adenine, cytosine, 
guanine and thymine) and the 20-letter set $\{ a,c,d,e,f,g,h,i,k,l,m,$ 
$n,p,q,r,s,t,v, w, z\}$ containing the amino-acids (alanine, cysteine, asparagin-acid, glutamine-acid, 
phenyl, glycine, histidine, isoleucine, lysine, leucine, methionine, 
asparagine, proline, glutamine, arginine, serine, threonine, valine, 
triptophan, tyrosine) play leading role \cite{Ivanyi1987}.\nevindex{Iv�nyi, Antal Mikl�s} Mathematics uses 
the 10-letter set $\{0,1,\ldots,9\},$ while computer science prefer the binary set $\{0,1\}.$

Arrays with elements from given sets of symbols have various applications, e.g. D�nes and Keedwell
\cite{DenesK1988}\nevindex{D�nes, J�zsef}\nevindex{Keedwell, A. Donald} reported on application 
in frequency allocation of multibeam satellites, Harvit \cite{Harvit1971}\nevindex{Harvit, M.} in designing
mask configuration for spectrometers, Mitchell and Paterson \cite{MitchellP1994} in cryptography, 
Ma \cite{Ma1984}\nevindex{Ma, S. L.} in picture coding and processing, Arazi \cite{Arazi84} in position recovery of 
cars.

Complexity is a basic characteristic of arrays of symbols, since affects 
the cost of storage and reproduction, and the quantity of information stored 
in the arrays. The usual complexity measures are 
based on the time (or memory) needed for generating or recognizing them.

Cyclic sequences in which every possible sequence of a fixed length occurs exactly once have been studied 
for more than a hundred years \cite{Flye1894}. This mathematical problem was extended 
to two-dimensional arrays by Reed and Stewart \cite{ReedS1962}\nevindex{Reed, I. S.}\nevindex{Stewart, R. M.} 
who gave an example of $4 \times 4$ sized 
\textit{perfect map}.\index{perfect map} Fan et al. in 1985 \cite{FanFMS1985}\nevindex{Fan, C. T.}
\nevindex{Fan, S. M.}\nevindex{Ma, S. L.}\nevindex{Siu, M.-K.} proved the existence of binary perfect maps 
for larger sizes.

In the first seven sections of this chapter we deal with the existence and construction of perfect 
arrays.\index{perfect array} The last three sections superperfect sequences, the subword complexity 
and its extension, the $d$-complexity, are analysed.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic concepts\label{sec-basic}}
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}\inddef{ddimensionalnary@@$d$-dimensional $n$-ary array} 
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}\inddef{bperiodicarray@\textbf{b}-periodic array} and $M$ is 
a \ki{period}\inddef{period} of $A.$
 
The \ki{$\mathbf{a}$-sized subarrays}\inddef{asizedsubarrays@\textbf{a}-sized subarray} 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} = [1..b_1] \times [1..b_2] \times \cdots \times [1..b_d] \koz.$$

A $d$ dimensional $\mathbf{b}$-periodic $n$-ary array $A$ is called 
\ki{$(n,d,\mathbf{a},\mathbf{b})$-perfect,}\inddef{ndabperfectarray@$(n,d,\mathbf{a,b})$-perfect array} 
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,}\inddef{cellular array} 
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.}\inddef{cell} In
each cell the element with smallest indices is called the
\ki{head}\inddef{head of a cell} of the cell. The contents of the cell is called \ki{pattern.}\inddef{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}\inddef{volume of an array} 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}.\inddef{symmetric array} If $A$ is symmetric and
$a_1 = a_2 = \cdots = a_d,$ then $A$ is called \textbf{doubly symmetric.}\inddef{doubly symmetric array} 
If $A$ is doubly symmetric and
\begin{enumerate}
\item $d = 1,$ then $A$ is called a \ki{double sequence;}\inddef{double sequence}
\item $d = 2,$ then $A$ is called a \ki{double square;}\inddef{double square} 
\item $d = 3,$ then $A$ is called a \ki{double cube.}\inddef{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\index{de Bruijn sequence}\nevindex{Bruijn, Nicolaas Govert, de} or 
Good sequences.\index{Good-sequence}\nevindex{Good, I. J.} Two-dimensional perfect arrays are called also 
perfect maps\index{perfect map} 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,}\inddef{even sequence} 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\nevindex{Iv�nyi, Antal Mikl�s} and T�th\nevindex{T�th, Zolt�n} in 1988 and later 
Hurlbert\nevindex{Hurlbert, Glenn} and Isaak\nevindex{Isaak, Garth} in 1994  
provided a constructive proof of the existence of even sequences. The later algorithm is stronger 
since it constructs a universal infinite sequence whose prefixes are even sequences for the corresponding 
alphabet size.

\ki{Lexicographic indexing}\inddef{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
\begin{equation}
I(m_{\mathbf{j}}) = j_1 - 1 + \sum_{i = 2}^d \left ((j_i - 1) \prod_{m=1}^{i-1} b_m \right )\koz.\label{eq-indexing}
\end{equation}

The concept of perfectness can be extended to infinite arrays in various ways. In 
\ki{growing arrays}\inddef{growing arrays} introduced by Hurlbert and 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,}\inddef{ndagrowing@(\textbf{n,}$d,a)$} 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}\inddef{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{eq-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.$

Another possibility for the extension of concept of perfectness is to increase the window size. Then we get 
\ki{supercomplex arrays}\inddef{superperfect array} studied in Section \ref{sec-super}. 

\begin{gyak}
\ujgyak
Gather one-dimensional examples of the applications of perfect arrays.
\ujgyak
Gather two- and three-dimensional examples of the application of perfect arrays.
\ujgyak
\end{gyak}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 Cock,\nevindex{Cock, John 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-neclong1}) 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{Lovasz2007}.

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 (qref{eq-neclong1}) and (\ref{eq-neclong2} 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 perfect arrays\label{sec-one}}
In the construction of one-dimensional perfect arrays we use the following algorithms.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Pseudocode of the algorithm \textsc{Quick-Martin}}\index{\textsc{Quick-Martin}}
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.

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 \cite{HorvathI2008}.\nevindex{Iv�nyi, Antal Mikl�s}
\bigskip
\noindent \textsc{Quick-Martin($n,a$)}\inddef{\textsc{Quick-Martin}}
\vspace{-2mm}
\begin{tabbing}
\quad \= \quad \= \quad          \kill
01 \key{for} \= $i = 0$ \key{to} $n^{a - 1} - 1$ \\
02              \> $C[i] = n - 1$ \\
03 \key{for} \= $i = 1$ \key{to} $a$ \\
04              \> $w[i] = 0$ \\
05 \key{for} \= $i = a + 1$ \key{to} $n^a$ \\
06              \> $k = w[i - a + 1]$ \\
07              \> \key{for} \= $j = 1$ \key{to} $a - 1$ \\
08              \>              \> $k = k n + w[i - a + j]$ \\
09              \> $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. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Pseudocode of the algorithm \textsc{Optimal-Martin}}\inddef{\textsc{Optimal-Martin}}
The following implementation of Martin algorithm requires even smaller running time than \textsc{Quick-Martin}.
\bigskip
\noindent \textsc{Optimal-Martin($n,a$)}\inddef{\textsc{Optimal-Martin}}
\vspace{-2mm}
\begin{tabbing}
\quad \= \quad \= \quad          \kill
01 \key{for} \= $i = 0$ \key{to} $n^{a - 1} - 1$ \\
02              \> $C[i] = n - 1$ \\
03 \key{for} \= $i = 1$ \key{to} $a$ \\
04              \> $w[i] = 0$ \\
05 $k = 0$ \\
06 \key{for} \= $i = a + 1$ \key{to} $n^a$ \\
07           \> $k = k -w[i - a]n^{a - 1} + w[i - 1]$ \\
08 $w[i] = C[k]$ \\
09 $C[k] = C[k] - 1$ \\
10 \key{return} $\mathbf{w}$
\end{tabbing}

The running time of any algorithm which constructs a one-dimensional perfect array is $\Omega(n^a),$ since 
the sequence 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 Cock\nevindex{Cock, John C.} in 1988 \cite{Cock1988} 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.
\bigskip
\noindent \textsc{Shift}$(N,d,a,P_d)$\inddef{\textsc{Shift}}
\vspace{-2mm}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 \textsc{Optimal-Martin}$(N^(a^d),a - 1)$\\
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}

The running time of \textsc{Shift} is $\Theta(dN^(a^d)).$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}.\nevindex{Hurlbert, Glenn}\nevindex{Isaak, Garth}
\bigskip
\noindent \textsc{Even($N$)}\inddef{\textsc{Even}}
\vspace{-2mm}
\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}

The running time of algorithm \textsc{Even} \cite{HurlbertI1994} is $\Theta(N^2).$

\begin{gyak}
\ujgyak Solve the \ki{telex problem}, that is construct a $(2,1,5,32)$-perfect array 
(using \textsc{}).\inddef{telex problem}
\end{gyak}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Two-dimensional perfect 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 \cite{Paterson1994} for $(n,2,a,b)$-perfect arrays. Later Paterson 
\cite{Paterson1996I,Paterson1996II}\nevindex{Paterson, Kenneth G.} 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} was proposed by Iv�nyi\nevindex{Iv�nyi, Antal Mikl�s} 
and T�th\nevindex{T�th, Zolt�n} in 1988. The input of \textsc{Mesh} is the alphabet size $N$ and 
an even sequence \textbf{w}. The output is an $(N,2,2,N^2$-perfect array. It uses the following 
meshing function \cite{IvanyiT1988}:
\begin{equation}
P_{i,j} = \left\{ \begin{array}{ll}
e_j,              & \ \mbox{if} \ i + j \ \mbox{is even,} \\ 
e_i,              & \ \mbox{if} \ i + j \ \mbox{is odd}, \label{eqn-mesh}
\end{array}
\right.
\end{equation}
\bigskip
\noindent \textsc{Mesh($N,\mathbf{w},S$)}\inddef{\textsc{Mesh}}
\vspace{-2mm}
\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}}
Algorithm \textsc{Cellular}\index{Cellular@\textsc{Cellular}} is an extension and combination 
of the known algorithms \textsc{Shift, Optimal-Martin, Even} and \textsc{Mesh}.

\textsc{Cellular} results a cellular perfect array $A$.
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 six parts:
\begin{enumerate}
\item \textit{Calculation} (line 1 in the pseudocode): determines
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{Optimal-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.$
\item
\textit{Report} (line 17): returns the output $A$.
\end{enumerate}
\bigskip
\textsc{Cellular($n,d,a,N$)}\inddef{\textsc{Cellular}}
\vspace{-2mm}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
1 $N = N(n,a)$ \\
2 \key{if} \= $d = 1$ \\ 
3          \> \textsc{Optimal-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{Optimal-Martin$(N,a)$} \\
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)$ \\
17 $A = P_d$ \\
18 \key{return} $A$ \\
\end{tabbing}

\begin{gyak}
\ujgyak Construct a $(4,2,2,16)$-perfect array (a binary double square for window size $2 \times 2$.
\end{gyak}

\section{Three-dimensional perfect arrays\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
$(k_1,k_2,\ldots,k_d)$  --
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} =
(k_1 a_1,k_2 a_2,\ldots,k_d a_d).$
\end{itemize}

\textsc{Colour} consists of four 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).
\item
\textit{Report} (line 5): returns the output $A.$
\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} = (a_1k_1,a_2k_2, \ldots, a_dk_d).$
\bigskip
\noindent \textsc{Colour($N,d,\mathbf{a},k,\mathbf{k},A$)}\inddef{\textsc{Colour}}
\vspace{-2mm}
\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 $P$ 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} $P$
\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} (line 01): construction of a cellular perfect array $P$ using \textsc{Cellular};
\item
\textit{Resizing} (lines 02--14): 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} (lines 15--17): construction of the further $r - 1$ prefixes of the growing array $G$
repeatedly, using \textsc{Colour}.
\item
\textit{Report} (line 18): returns the output $S_r.$
\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.
\bigskip
\textsc{Growing($n,d,a,r,S_r$)}\inddef{\textsc{Growing}}
\vspace{-2mm}
\begin{tabbing}
\quad \=\quad\=\quad          \kill
01 \textsc{Cellular($n,d,a,N,P$)} \\
02 calculation of $N$ using formula (\ref{eqn-new}) \\
03 \key{if} \= $P$ is symmetric \\ 
04          \> $S_1 = P$ \\
05 \key{if} \= $P$ is not symmetric \\
06          \> $n_1 = N^{d/\mathrm{gcd}(d,a^d)}$ \\
07          \> $k = n_1/N$ \\
08          \> $k_1 = (n_1)^{a^d/3}/N^a$ \\
09          \> \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$)} \\
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})$} \\
18 \key{return} $S_r$
\end{tabbing}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Construction of 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} = (4)$ and uses \textsc{Colour}
to construct a 4-ary perfect sequence.

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

\textsc{Colour} 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 add 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}
As the first example 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 Figure \ref{fig-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{figure}[!t]
\begin{center}
\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}
\caption{a) A (2,2,4,4)-square; \hspace{8mm} b) Indexing scheme $I$ of size 
$4 \times 4$\label{fig-perf2244}}

\end{center}
\end{figure}


\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$. Figure \ref{fig-perf2244}.b shows $I.$

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

\begin{figure}[!t]
\begin{center}
\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}
\caption{Binary colouring matrix $C$ of size $8 \times 8$} \label{fig-col16}
\end{center}
\end{figure}

Colouring of array $R$ using the colouring array $2C$ results the (4,2,2,16)-square $S_2$ represented
in Figure \ref{fig-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{figure}
\begin{center}
\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}
\caption{A (4,2,2,16)-square generated by colouring} \label{fig-perf16}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Construction of growing cubes}
If $d = 3,$ then the necessary condition (\ref{eq-neclong2}) 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 Figure \ref{fig-perf2244}.a, then \textsc{Shift} uses
\textsc{Optimal-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} = (0,15,14,\ldots,2,1).$ 
16 layers of $P$ are shown in Figure \ref{fig-perf4416}.

Let $A_3$ be a $4 \times 4 \times 16$ sized perfect, rectangular
matrix, whose 0th layer is the matrix represented in Figure 
\ref{fig-perf2244}, and the $(2,3,\mathrm{a},\mathrm{b})$-perfect
array $P$ in Figure \ref{fig-perf4416}, where $\mathbf{a} =
(2,2,2)$ and $\mathbf{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 home page of the first 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$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Construction of a four-dimensional double hypercube}  
In 4 dimensions the smallest $b$'s satisfying (\ref{eq-neclong1}) are $b = 16$ and 
$b = 81$. But we do not know algorithm which can construct $(2,4,2,16)$-perfect or 
$(3,4,2,81)$-perfect hypercube. The third chance is the $(4,4,2,256)$-perfect hypercube. 
Let $n = 2$ and $a = 2$. \textsc{Cellular} calculates $N = 2$, then calls 
\textsc{Optimal-Martin} receiving the cellular $(2,1,2,4)$-perfect sequence $0 0 | 1 1.$ 
Then \textsc{Cellular} calls \textsc{Mesh} which constructs the cellular 
$(2,2,2,4)$-perfect square shown in Figure \ref{fig-perf2244}.

\begin{figure}[!t] 
\begin{center}
\begin{tabular}{|c||c|c|c|c|}  \hline
column/row & 1   &  2   &  3 & 4  \\ \hline \hline
1          & 0   &  0   & 0 & 1    \\ \hline
2          & 0   &  0  & 1  & 0    \\ \hline
3          & 1   & 0   & 1  & 1      \\ \hline
4          & 0   & 1   & 1  & 1   \\ \hline
\end{tabular}
\caption{A (2,2,4,4)-square\label{fig-perf2244}}
\end{center}
\end{figure}

Now \textsc{Shift} calls \textsc{Optimal-Martin} with $n = 1$ 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 layer 
is generated by cyclic shifting of the previous layer downwards 
by $w_i$ (div 4) and right by $w_i$ (mod 4), where \textbf{w} = $\langle 0 \ 15 \ 14 \ 13 \ 12 11 \ 10 \ 9 \ 8 \ 7 
\ 6 \ 5 \ 4 \ 3 \ 2 \ 1 \rangle$. The layers of the $(2,3,2,16)$-perfect array are shown 
in Figure \ref{fig-4416}. 

\begin{figure}[!t]
\begin{center}
\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 & 0 1 0 0 & 1 1 0 1 & 1 1 0 1 & 0 1 0 0 & 1 1 0 1 & 0 0 1 0 \\ \hline 
0 0 1 0 & 0 0 1 0 & 0 1 1 1 & 1 0 1 1 & 0 1 0 0 & 1 0 0 0 & 1 0 1 1 & 0 1 0 0 \\ \hline 
1 0 1 1 & 1 0 1 1 & 1 1 1 0 & 1 0 0 0 & 1 0 0 0 & 1 1 1 0 & 1 0 0 0 & 0 1 1 1 \\ \hline 
0 1 1 1 & 0 1 1 1 & 0 0 1 0 & 0 0 0 1 & 1 1 1 0 & 1 1 0 1 & 0 0 0 1 & 1 1 1 0\\ \hline
Layer 8 & Layer 9 & Layer 10& Layer 11& Layer 12 & Layer 13 & Layer 14 & Layer 15 \\ \hline 
1 0 1 1 & 0 0 0 1 & 1 1 1 0 & 1 1 0 1 & 1 0 0 0 & 0 1 0 0 & 1 0 0 0 & 0 0 1 0 \\ \hline 
0 1 1 1 & 0 0 1 0 & 0 0 1 0 & 1 0 1 1 & 1 1 1 0 & 1 0 0 0 & 0 0 0 1 & 0 1 0 0 \\ \hline 
0 0 0 1 & 1 0 1 1 & 0 1 0 0 & 1 0 0 0 & 1 1 0 1 & 1 1 1 0 & 1 1 0 1 & 0 1 1 1  \\ \hline 
0 0 1 0 & 0 1 1 1 & 0 1 1 1 & 0 0 0 1 & 0 1 0 0 & 1 1 0 1 & 1 0 1 1 & 1 1 1 0\\ \hline
\end{tabular}
\caption{Sixteen layers of the $(2,3,2,16)$-perfect output of \textsc{Shift}}\label{fig-4416}
\end{center}
\end{figure}

Up to this point the construction is the same as in \cite{HorvathI2008}, but now $d = 4$, therefore we use 
\textsc{Shift} again to get a $(2,4,2,256)$-perfect prism, then we fill an empty 
$256 \times 256 \times 256 \times 256$ cube with $4 \times 4 \times 16 \times 256$-sized prisms and 
finally colouring results the required 4-dimensional hypercube. 

\begin{gyak}
\ujgyak
Explain the construction of Figure \ref{fig-4416}.
\end{gyak}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The existence theorem of perfect arrays}
The main result of this chapter can be formulated as follows.

In the section---using the algorithms \textsc{Cellular}, \textsc{Optimal-Martin}, \textsc{Even}, \textsc{Mesh}, 
\textsc{Shift}, \textsc{Colour}  \cite{HorvathI2008,Ivanyi1990,IvanyiM2011ENDM,IvanyiT1988,Knuth2011}---we 
prove the following theorem and illustrate it  by the construction of a hypercube.
\begin{tetel} If\label{thm:main} $n \geq 2$, $d \geq 1$, $a \geq 2$, and $b \geq 2$ satisfy \ref{eq-neclong1} and

a) $d \ | \ a^d$ and $(un)^{a^d/d}\geq n^{a^d} - a^{d - 1}$, then there exists 
a $(un,d,a,(un)^{a^d/d})$-perfect array;

b) $(vn)^{a^d} \geq n^{a^d - a^{d - 1}}$, then there exists a 
$\left ( (vn)^d,d,a,(vn)^{a^d}\right )$-perfect array,where 
$u$ and $v$ are suitable positive integers. 
\end{tetel} 

The proof is based on the algorithms \textsc{Cellular}, \textsc{Optimal-Martin}, \textsc{Even}, \textsc{Mesh}, 
\textsc{Shift}, \textsc{Colour} \cite{HorvathI2008,Ivanyi1990,IvanyiM2011ENDM,IvanyiT1988,Knuth2011} and on the 
following two lemmas.

\begin{lemma} \emph{(Cellular lemma, Horv�th, Iv�nyi \cite{HorvathI2008,IvanyiM2011ENDM})} 
If\label{lemma-cel} $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{eq-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{Optimal-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} \emph{(Indexing lemma, Horv�th, Iv�nyi \cite{HorvathI2008,IvanyiM2011ENDM})} 
If\label{lemma-ind} $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 Fig. \ref{fig-col16} 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 condition that the patterns are in different cells.
\end{biz}

\begin{lemma} $(\mathrm{Colouring \ lemma})$ If\label{lemma-col} $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 us 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 Figure \ref{fig-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 \ref{lemma-cel} 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{ Superperfect arrays\label{sec-sup}}
This section deals with the construction of infinite De Bruijn arrays (superperfect arrays).

\begin{defi} Let $k \geq 2,$ $m, \ n, \ M, \ N$ be positive integers ($m \leq M, \ n \leq N, \ MN = k^{mn}$), 
$X = 0, 1, \ldots, k - 1.$ A $(k,m,n,M,N)$-array (or De Bruijn array) is a periodic 
$M \times N$ array with elements from $X$, in which all of the different $k$-ary  $m \times n$ arrays 
appear exactly ones.
\end{defi}

\begin{defi} Let $k \geq 2,$ $m$ and $M$ be positive integers, $X = \{0, 1, \ldots, k -1\}$. A $(k,m,M)$-array 
(or infinite De Bruijn array) is a $k$-ary infinite $m \times \infty$ array with elements from $X$ whose 
beginning parts of length $k^{mn}/M$ as periodic arrays are $(k,m,n,M,k^{mn}/M)$-arrays for $n =1, \ 2, \ldots \ .$ 
\end{defi}

The following theorems \cite{Ivanyi1988} give construction results.

\begin{tetel} \emph{Iv�nyi \cite{Ivanyi1988}} For any $k \geq 2,$ $m \geq 1$ and $n \geq 1$ there are $M$ and 
$N$ such that $(k,m,n,M,N)$-array $P$ exists.\nevindex{Iv�nyi, Antal Mikl�s}
\end{tetel}
\begin{biz} See \cite{Ivanyi1988}.
\end{biz}
\begin{tetel} \emph{Iv�nyi \cite{Ivanyi1988}} For\label{theorem-Bruijn2} any odd  $k \geq 3$ and $m \geq 1$ and 
also for any even $k \geq 2$ and $m \geq 3$ there is an $M$ such that a $(k,m,M)$-array $S$ exists.
\end{tetel}
\begin{biz}
See \cite{Ivanyi1988}.
\end{biz}

Theorem \ref{theorem-Bruijn2} does not cover the case when $k$ is even and $m \leq 2.$ No $(2,1,m)$-
 and $(2,2,M)$-arrays exist \cite{Ivanyi1987}.\nevindex{Iv�nyi, Antal Mikl�s}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ $d$-complexity of one-dimensional arrays\label{sec-dcomplexity}}
In this section a new complexity measure, $d$-complexity is studied. This 
measure is intended to express the total quantity of information included in a 
sequence counting the different $d$-subsequences (belonging to the given set 
of sequences) of the investigated sequence. The background of the new 
complexity measure lies in biology and chemistry. Some natural sequences, as 
amino-acid sequences in proteins or nucleotid sequences in DNA-molecules have 
a winding structure \cite{DassowMS2002,EbelingF1990} and some bends can be cut forming new
sequences. The distance parameter $d$ is the bound for the length of bends.

We use the basic concepts and notations of the theory of algorithms \cite{CormenLRS2009}, 
formal languages \cite{RozenbergS1997} and graphs \cite{Berge1976}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Definitions}
Let $n$ and $q$ be positive integers, $\mathcal{A}=\{a_1,a_2,\ldots,a_q \}$ 
be an alphabet, $\mathcal{A}^n$ the set 
of $n$-length words, $\mathcal{A}^*$ the set of finite words and 
$\mathcal{A}^+$ the set of finite nonempty words over $\mathcal{A}$. The 
length of a word $w$ is denoted by $\lambda (w)$. 

Let $m_1,\ m_2,\ \ldots,\ m_q$ be nonnegative integers. Then the 
multialphabet $\mathcal{M} = (\mathcal{A},m_1,m_2,\ldots,m_q)$ 
is the multiset $\{a_1^{m_1},a_2^{m_2},\ldots,a_p^{m_q})$, $\mathcal{M}^n$ 
the set of words $w \in \mathcal{A}^n$ and containing $a_i \in 
\mathcal{A}$ at most $m_i$ times $(i=1,2,\ldots,q)$, 
$\mathcal{M}^+$ the set of words $w \in \mathcal{M}^n$ containing $a_i \in 
\mathcal{A}^+$ at most $m_i$ times $(i=1,2,\ldots,q)$. Alphabets can be 
considered as special multialphabets with infinite multiplicityes of the 
letters. 

Nonempty sets of words --- e.g. $\mathcal{A}^n, \ \mathcal{A}^+, \ 
\mathcal{M}^n, \ \mathcal{M}^+$ --- are called languages. 
Set of $i$-length elements of a language $L$ is denoted by $L(i)$.

\begin{defi} Let $d, \ r$ and $s$ be positive integers, $u$ and $w$ 
words such that $u = u_1 u_2 \ldots u_r$ and $w=w_1 w_2 \ldots w_s$. 
If $r \geq 2$, then $u$ is a \textbf{\textit{d}-subword} of $w \ (u \subset _d 
w)$,  if and only if  there exists a sequence $i_1, \ i_2, \ \ldots, \ i_r$ with $1 \le 
i_1, i_r \le s, \ 1 \le i_{j + 1} - i_j \le d \ (j=1,\ldots,r-1)$ such that 
$u_j = w_{i_j} \ (j=1,2,\ldots,r)$. If $r = 1$, then $u$ is a $d$-subword of 
$w$, if and only if  there exists a sequence $i$ with $1 \le i \leq s$ such that $u_1 = w_i$.
If for given $u, \ w$ and $d$ there exist several such sequences (or indices), 
then the sequence belonging to $u, \ w$ and $d$ is the lexicographically 
minimal of them. The differences $i_{j+1}-i_j$ are called jumps. 1-length words 
contain a jump of size zero.
\end{defi}

According to this definition only nonempty words can be $d$-subwords.

Now we classify the $d$-subwords of a given word $w$ according to their 
length, position of their last letter and the length of their longest jump.

\begin{defi} Let $d$ and $n$ be positive integers, $\mathcal{M}$ 
 a multialphabet, $L \subseteq \mathcal{M}^+$ a multilanguage, $w=(w_1  w_2 
 \ldots w_n) \in \mathcal{M}^n$ a word, $D(w,L,i,d)$ denote the $i$-length 
 subwords of $w$ belonging to $L$, $P(L,w,i,d)$ denote the $d$-subwords of 
 $w$ for which the first appearance ends with $w_i$, $U(w,L,i,d)$ the set of 
subwords of $w$ for which the largest jump in its first occurrence in $w$ 
equals to $i$ (everywhere $0 \leq i \leq n)$. The 
$d$\ki{-complexity function}\inddef{dcomplexity function@$d$-complexity function} $C(w,L,i,d)$ of $w$ is 
\begin{equation}
C(w,L,i,d)=|D(w,L,i,d)| \ \ \ \ (i=1,2,\ldots,n),
\end{equation}
the $d$\ki{-characteristic function}\inddef{dcharacteristic function@$d$-characteristic function} 
$H_d(w, L, i, d)$ of $w$ is
\begin{equation}
H(w,L,i,d) = |P(w,L,i,d)| \ \ \ (i=1,2,\ldots,n).
\end{equation}
the $d$\ki{jump function}\inddef{djump function@$d$-jump function} $J(w,L,i,d)$ of $w$ is
\begin{equation}
J(w,L,i,d) = |U(w,L,i,d)| \ \ \ (i=0,1,\ldots,n-1),
\end{equation}
the \ki{total} $d$\ki{-complexity}\inddef{totaldcomplexity@total $d$-complexity} $T(w,L,d)$ of $w$ is
\begin{equation}
T(w,L,d) = \sum_{i=1}^n C(w,L,i,d)=\sum_{i=1}^n H(w,L,i,d)= 
\sum_{i=0}^{n-1} J(w,L,i,d). 
\end{equation}
\end{defi}

The special case $d=1, \ L=\mathcal{A}^+$ of $C(w,L,i,d)$ was introduced by 
M. Heinz \cite{Heinz1977}\nevindex{Heinz, Michael} in 1977 and studied later by many authors (see e.g.  
the papers \cite{Anisiu2002,Ferenczi99,Shallit93}. The special case $L = \mathcal{A}^+$ of $C(w,L,i,d)$ 
was introduced in 1984 \cite{HunyadvariI1984} and studied later e.g. in \cite{Ivanyi1988,Kasa1998}. 

\begin{pelda} Let $\mathcal{A}=\{A,E,L,T\}$ be an alphabet, 
$L=\mathcal{A}^+, \ w = (ELTE).$ \linebreak 
Classification according to the length of 
the subwords results $D(w,L,1,1) = $ $D(w,L,1,2)=D(w,L,1,3)= 
\{ E,L,T \}, \ D(w,L,2,1)=\{ EL,LT,TE \}, \ D(w,L,2,2)=\{ EL,ET,LT,LE,TE\}, 
\ D(w,L,2,3)=\{EL,ET,EE,LT,LE,TE\}, \ D(w,L,3,1)= \{ELT$, $LTE\}, D(w,L,3,2) 
= D(w,L,3,3)=\{ELT$, $ELE,ETE,LTE \}, \ D(w,L,4,1)= D(w,L,4,2)= D(w,L,4,3) =
\{ELTE\}$ and so $T(w,L,1)=3+3+2+1=9, \ T(w,L,2)=3+5+4+1=13, \ T(w,L,3)=3+ 
6+4+1=14$.

Classification according to the last letter gives $P(w,L,1,2)=\{E\}, \ 
P(w,L,2,2)=\{ EL,L \}, \ P(w$, $L,3,2)= \ \{ 
ELT,ET,LT,T \}$ and $P(w,L,4,2)= \{ELTE,ELE,ETE,LE,LTE,TE \}$ and so 
$T(w,L,2)=1+2+4+6=13$.

Classification according to the largest jumps results $U(w,\mathcal{A}^+,3,3)= 
\{ EE \}, \ U(w,\mathcal{A}^+,2,3)= \{ ELE,ET,ETE,LE \}, \ 
U(w,\mathcal{A}^+,1,3) = \{E,EL,ELT,ELTE,L,LT,LTE, T,TE \}$ and so 
$T(w,L$, $3)=1+4+9=14$.

Let $\mathcal{M} = (\mathcal{A},1,1,\ldots,1), \ N = \mathcal{M}^+$. The 
multisubwords can contain at most one $E$ and so $T(w,N,3) = 3+5+2+0 < 
T(w,L,3)=14$. Decreasing of some complexity values is natural since 
bounded multiplicityes exclude some subwords.
\end{pelda}

\begin{defi} Let $L$ be a finite language over $\mathcal{A}=\{ 0, 
1, \ldots, q-1 \}$ and $w \in \mathcal{A}^+$ be a word. $w$ is a 
$d$\ki{-covering word}\inddef{dcoveringword@$d$-covering word} 
of $L$ if and only if  $w$ contains all elements of $L$ as a \textit{d}-subword. The 
length of the shortest $d$-covering word of $L$ is denoted by $\gamma(L, \ 
d)$. Such words are called \ki{minimal}.\inddef{minimal word} If $L=\mathcal{A}^n$, then we 
use $g(q,n,d)$ instead of $\gamma(L,d).$
\end{defi} 
 
The special case $d = 1$ is well-known and widely studied as superstring 
problem \cite{YZ}.

\begin{defi} Let $d, \ q$ and $n$ be positive integers, $\mathcal{A} 
= \{0,1,\ldots,q-1\}$ be an alphabet and $L$ be a language over $\mathcal{A}$. 
The maximum of the $d$-complexities of the elements of $L$ is denoted by $\mu 
(L,d)$. Words having complexity $\mu (L,d)$ are called \textbf{maximal}. If
$L=\mathcal{A}^n$, then we use $f(q,n,d)$ instead of $\mu (L,d)$. Minimal and 
maximal words are called \ki{extremal}.\inddef{extremal word}
\end{defi}

\begin{defi} Let $\mathcal{F}(\mathcal{M}) = \{ L_1, \ L_2, \ 
\ldots \}$ be a sequence of languages over some alphabet multialphabet 
$\mathcal{M}$ with the property $L_i \subseteq \mathcal{M}^i \ (i=1, \ 2, \ \ 
\ldots)$. Such sequences of languages are called 
\ki{family.}\inddef{family of languages}
\end{defi}

\begin{defi} Let $d, \ n$ and $q$ be positive integers, 
$\mathcal{A} = \{0,1,\ldots,q-1\}$ an alphabet, 
$\mathcal{F}=\{L_1,L_2,\ldots\}$ a family of languages and 
$w=(x_1x_2\ldots)$ be a word over $\mathcal{A}$. $w$ is a 
\textit{d}\textbf{-superminimal word of the family} $\mathcal{F}$ if and only if  
the word $(x_1 x_2 \ldots x_{\gamma(L_k,d)})$ is a $d$-covering word of 
$L_n$ for $n = 1, \ 2, \ \ldots \ .$
\end{defi}

\begin{defi} Let $q$ be a positive integer, $\mathcal{A} = (0, 1, 
\ldots, q-1)$ be an alphabet, $d$ be a positive integer and $w=(x_1 \ x_2 \ 
\ldots)$ be a word over $\mathcal{A}$. $w$ is 
$d$\ki{-supermaximal word}\inddef{dsupermaximalword@$d$-supermaximal word} of the alphabet $\mathcal{A}$ 
if and only if  the word $x_1 x_2 \ldots x_n$ 
is a $d$-maximal word for $n=1,2, \ldots$ \koz.
\end{defi}

\begin{defi} The words consisting of identical letters are called 
\ki{homogeneous,}\inddef{homogeneous word} the words consisting of different letters are called 
\ki{rainbow}\inddef{rainbow word} and the words consisting of copies of a given rainbow word 
(the last copy can be only a prefix) are called \ki{cyclical.}\inddef{cyclical word} 
\end{defi}
 
\subsection{ Bounds of complexity measures}
In this section we formulate some simple properties of the investigated 
complexity measures. 

Lemmas \ref{lemma-m1}, \ref{lemma-m2}, \ref{lemma-m3} and \ref{lemma-m4} characterize 
the monotonity properties of the functions $C$ and $H$. 

Lemmas \ref{lemma-f1}, \ref{lemma-f2}, \ref{lemma-f3} and \ref{lemma-Heinz} give some bounds 
of the functions $C, H$ and $J$. 

\begin{lemma} If\label{lemma-m1} $d$ is a positive integer, $L$ is a language and 
$w$ is a word, then the $d$-complexity function $C(w,L,i,d)$ is a monotone 
nondecreasing function of the distance $d$, that is 
\begin{equation}
C(w,L,i,d+1) \ge C(w,L,i,d) \ \ \ (i=1,2,\ldots,\lambda(w))\label{eq-mon1}
\end{equation}
and in some cases the equality holds.
\end{lemma}
\begin{biz} $D(w,L,i,d) \subseteq D(w,L,i,d+1)$ implies the relation. E.g. 
if $\lambda(w) \ge 3$ and the first, second and last letters of a word $w$ 
are identical, then $D(w,L,2,\lambda(w)-2)=D(w,L,2,\lambda(w)-1)$ and 
generally if $d \ge \lambda(w)-1$, then in (\ref{eq-mon1}) equality holds for any $i$. 
\end{biz}

\begin{lemma} If\label{lemma-m2} $d$ and $q$ are positive integers and $\mathcal{A}=\{0,1, 
\ldots,q-1\}$, then $C(w,\mathcal{A}^+,i,d)$ is 
a trapezoidal function of $i$, that is there exist a positive integer $j \ (1 
\le j \le \lambda(w))$ and a nonnegative integer $m$ such that
\begin{equation} 
C(w,\mathcal{A}^+,i,d) < C(w,\mathcal{A}^+,i+1,d) \ \ (i=1,2,\ldots,j-1),
\end{equation}
\begin{equation}
C(w,\mathcal{A}^+,j,d)=C(w,\mathcal{A}^+,j+p,d) \ \ (p=0,1,\ldots,m)
\end{equation}
and
\begin{equation}  
C(w,\mathcal{A}^+,i,d) > C(w,\mathcal{A}^+,i+1,d) \ \ (i=j+m,j+m+1,\ldots,
\lambda(w)-1). 
\end{equation}
\end{lemma}


Special case $d = 1$ of this assertion was recently proved by de Luca [Lu]. 
Since only words belonging to $L$ are counted as $d$-subwords, the function 
$C$ is not always trapezoidal. E.g. if $\mathcal{A} = \{0,1,\ldots,q-1\}$ 
an alphabet, $m$ is a nonnegative integer, $L=\mathcal{A}^1 \cup 
\mathcal{A}^3 \cup \ \ldots \cup \mathcal{A}^{2m+1}$ and $w$ a covering word 
of $\mathcal{A}^{2m+1}$, then the function $C(w,L,i,\infty)$ has $k$ local 
maxima, since now $C(w,L,i,\infty)$ equals to $q^i$ for $i=1, \ 3, \ \ldots, \ 
2m+1$ and equals zero otherwise.

\begin{lemma} If\label{lemma-m3} $L$ is a language, then the $d$-characteristic 
function $H(w,L,i,d)$ is a nondecreasing function $d$ that is
\begin{equation}
H(w,L,i,d) \le H(w,L,i,d+1) \ \ \ (i=1, \ 2, \ \ldots,\ \lambda(w))
\end{equation}
and if $L = \mathcal{A^+}$ for some finite alphabet $\mathcal{A}$, then the 
$d$-characteristic function $H$ is an increasing function of $i$ that is
\begin{equation}
H(w,\mathcal{A}^+,i,d) \le H(w,\mathcal{A}^+,i+1,d) 
\ \ (i=1, \ 2, \ \ldots,\ \lambda(w)-1).
\end{equation}
\end{lemma}

\begin{lemma} If\label{lemma-m4} $d$ is a positive integer, $\mathcal{A}$ is an alphabet and 
$L=\mathcal{A}^+$ is a language, then the cumulated values of 
the functions $C$ and $H$ are increasing functions of $i$ that is
\begin{equation}
\sum_{j=1}^{i} \ C(w,\mathcal{A}^+,j,d) < \sum_{j=1}^{i+1} \
C(w,\mathcal{A}^+,j,d)   \ \ (i=1, \ 2, \ \ldots, \ \lambda(w)-1),
\end{equation}
\begin{equation}
\sum_{j=1}^{i} H(w,\mathcal{A}^+,j,d) < \sum_{j=1}^{i+1} 
H(w,\mathcal{A}^+,j,d)   \ \ (i=1, \ 2, \ \ldots, \ \lambda(w)-1).
\end{equation}
\end{lemma}
\begin{biz} The corresponding $D$ and $P$ are nonempty sets.
\end{biz}

E.g. if $L(\lambda(w))$ is empty, then the functions $C$ and $H$ are only nondecreasing ones. 

\begin{lemma} Let\label{lemma-f1} $\mathcal{A} = \{0, 1, \ldots, q-1 \}, \ w \in 
\ \mathcal{A}^+$ and $L \subseteq \mathcal{A}^+$, then
\begin{equation}
0 \leq C(w, L, i, d) \leq \min \ \left( L(i), \binom{n}{i} \right ) 
\ \ \ (i=1,2,\ldots,n)
\end{equation}
and if $w \in \mathcal{A}^n, \ L = \mathcal{A}^n$ and $d \ge n$, then
\begin{equation} \label{equation:min}
1 \leq C(w, \mathcal{A}^+,i,d) \leq \min \left( q^i,\binom{n}{i} \right )
\ \ \ (i=1,2,\ldots,n).
\end{equation}
The lower bounds are sharp. The upper bound is sharp if and only if  $q \ge n-1$.
\end{lemma}

\begin{lemma} Let\label{lemma-f2} $\mathcal{A} = \{0, 1, \ldots, q-1 \}, \ w \in 
\ \mathcal{A}^+$ and $L \subseteq \mathcal{A}^+$, then
\begin{equation}
0 \leq H(w, L, i, d) \leq 2^{i-1} \ \ \ (i=1,2,\ldots,n)
\end{equation}
and if $w \in \mathcal{A}^n, \ L = \mathcal{A}^n$ and $d \ge n$, then
\begin{equation}
1 \leq H(w, \mathcal{A}^+,i,d) \leq 2^{i-1} \ \ \ (i=1,2,\ldots,n).
\end{equation}
The lower bounds are sharp. The upper bound is sharp if and only if  $q \ge n-1$.
\end{lemma}

\begin{lemma} Let\label{lemma-f3} $\mathcal{A} = \{0, 1, \ldots, q-1 \}, \ w \in 
\ \mathcal{A}^+$ and $L \subseteq \mathcal{A}^+$, then
\begin{equation}
0 \leq C(w, L, i, d) \leq \min |(L(i)|, n-i-1) \ \ \ (i=1,2,\ldots,n)
\end{equation}
\end{lemma}

\begin{lemma} \label{lemma-Heinz} If $q$ is a positive integer and $\mathcal{A} = \{0, 1, \ldots, 
q-1 \}, \ w \in \ \mathcal{A}^n$, then
\begin{equation} \label{equation:min1}
1 \leq C(w, \mathcal{A}^+,i,1) \leq \min(q^i, n-i-1) \ \ \ (i=1,2,\ldots,n).
\end{equation}
The lower bound is sharp if and only if $w$ is homogeneous. The upper bound is sharp.
\end{lemma}

The first proof of Lemma \ref{lemma-Heinz} is due to Heinz 
\cite{Heinz1977}.\nevindex{Heinz, Michael} Shallit\nevindex{Shallit, O. Jeffrey} \cite{Shallit93} 
has proved that in the case $q = 2$ the upper bound can be achieved. M.-C. Anisiu 
\cite{Anisiu2002} proposed an algorithm constructing for any positive $n$ an $n$-length binary word 
$w$ with the following property: if $2^k + k - 1 \leq n \leq 2^{k + 1} + k$, then $w$ 
either contains all $k$-length binary words as subword or all of its $(k + 1)$-length 
subwords are different. 

The jump function characterizes the decreasing of the complexity due to 
the decreasing of $d$.

\begin{lemma} \label{lemma:jump} Let $q, \ n$ and $d$ be positive integers, $\mathcal{A} = 
\{0, 1, \ldots, q-1 \}, \ w \in \ \mathcal{A}^n, \ L = \mathcal{A}^+$. Then
\begin{equation}
\hspace{-3mm}J(w, L, i, \infty) \left \{ \begin{array}{llll} \leq (n-i)2^{n-i-1} & \mbox{if 
     $n/2 \leq i \leq n-1,$} \\ 
      \leq (n-i)2^{n-i-1} - 1, & \mbox{if $n/3 \leq i < n/2$ and $n=2i+1$} \\
     \leq (n-i)2^{n-i-1}-7, & \mbox{if $n/3 \leq i \leq n/2$ and $n=2i+2$}, \\
     \leq (n-i)2^{n-i-1}-14, & \mbox{if $n/3 \leq i \leq n/2$ and $n=2i+3$}.
         \end{array} \right.
\end{equation}
The bounds are sharp if and only if  $w$ is a rainbow word.
\end{lemma}
\begin{biz}
If $n/2 \leq i \leq n-1$, then at most one jump of length $i$ is possible. We 
have $n - i$ positions to start the jump and can choose or not the remaining 
$(n-i-1)$ letters.

If $n = 2i+1$, then we have either two jumps of length $i (w_1 - w_i, w_i-w_{2i+1})$ or one 
$(w_j-w_{j+i})$. Due to the second jump we loss a further subword comparing with the previous case.

If  $n = 2i+2$, then we have place also for one or two $i$-length jumps. The exponential part of the 
formula counts 2 subwords containing jumps of length $i$ and $i+1$ and counts twice 5 subwords 
containing two jumps of length $i$ so we loss 7 subwords. 

If  $n = 2i+3$, then also one or two jumps of length at most $i$ are permitted. 
We loss 2 subwords containing jumps of length $i$ and $i+2$, 6 subwords 
containing jumps of length $i$ and $i+1$ and all together 6 subwords containing 
two jumps both of length $i$. 
\end{biz}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Recurrence relations\label{subsec-reccurrence}}
The following recurrence properties of the complexity functions $H$ and $J$ 
are useful in the later analysis. In this section always $A = \{ 0,1,\ldots, 
q-1 \}, \ L=\mathcal{A}^n, \ w=w_1 w_2 \ldots w_n$ and $d \ge 1$, therefore 
the parameters $w, L$ and $d$ are omitted.

\begin{lemma} If  $1 \le i \le n$, then
\begin{equation}
H(i) \ge \delta(i) + \sum_{j=z}^{i-1} \ H(j) \koz .
\end{equation} 
where $z= \min (0, i-d, k)$, $k = \max (0, \ p | w_p = w_i$ and $1 \leq p 
   \leq i-1)$ and
\begin{equation}
\delta(i) = \left \{ \begin{array}{ll} 1, & \mbox{if $ \ \ \exists j 
    \ \ (1 \leq j < i)$ with $w_j = w_i $} \\
0, & \mbox{if $ \ \ \nexists j \ \ (1 \leq j < i)$ with $\ \ w_j = w_i $}\koz . 
            \end{array} \right.
\end{equation}
\end{lemma}

\begin{kov} If $w=(0 \ 1 \ldots \ )$ is a crossbow word and $i \geq 1$, then 
\begin{equation}
H(i)=\left \{ \begin{array}{ll} 1+ \sum_{j=1}^{i-1} \ H(j), & 
        \mbox{if $i>d \koz,$} \\
      i, & \mbox{if $1 \leq i \leq d$} \koz. 
          \end{array} \right. 
\end{equation}
\end{kov}

\begin{kov} If $w=(0 \ 1 \ldots \ q-1)^*$ is an infinite cyclical word and 
$d \ge q$, then
\begin{equation}
H(i) = \left \{ \begin{array}{ll} \sum_{j=1}^{i-1} \ H(j), & 
        \mbox{if $q>d,$} \\
      2^i, & \mbox{if $1 \leq i \leq d$}.
           \end{array} \right. 
\end{equation}
\end{kov}

The next three lemmas contain useful results of the theory of linear 
recurrence equations. The first one \cite{KnuthGP1997} gives the solution of the 
$d$-order inhomogeneous recurrence relation, the second one \cite{Ivanyi1987} 
characterizes the roots of the corresponding characteristic equations and 
the third one \cite{Ivanyi1987} sums the values of the solution function.
   
\begin{lemma} If $d$ is a positive integer, then the solution of the 
inhomogeneous linear recurrence equation
\begin{equation}
f(n) = \left \{ \begin{array}{ll} a + \sum_{i=1}^d \ f(n-d), & \mbox{if $n 
     > d$,} \\
     b(n), & \mbox{if $1 \leq n \leq d$}
     \end{array} \right.
\end{equation}
is
\begin{equation}
f(n) =  k_1 n + k_2 + \sum_{i=1}^{d} \ c_{i,d} r_{i,d}^i \koz, \label{eq:Recsol}
\end{equation}
where the constants $k_1, k_2, c_{1,d}, c_{2,d}, \ldots, c_{d,d}$ can be 
computed using the given initial values $b(n)$ and the values $r_{i,d}$ can 
be estimated using the next lemma.
\end{lemma}
 
\begin{lemma} If $d \ge 2$, then let $r_{1,d}, \ r_{2,d}, \ \ldots, \ r_{d,d}$ 
be the roots of the $d$-order algebraic equation 
\begin{equation}
z^d - z^{d-1} - \ldots - z - 1 = 0
\end{equation}
in decreasing order of their absolute values. Then
\begin{equation}
2 - \frac{1}{2^{d-1}} < r_{1,d} < 2 - \frac{1}{2^d}
\end{equation}
and
\begin{equation}
| r_{i,d} | < 1 \ \ \ (i = 2, \ 3, \ \ldots \koz, \ d).
\end{equation}
\end{lemma}
 
\begin{lemma} If 
\begin{equation}
f(n) =  k_1  + k_2 n + \sum_{i=1}^{d} \ c_{i,d} r_{i,d}^i \koz,
\end{equation}
then 
$$ \sum_{i=1}^{n} f(i) = \frac{c_{1,d} r_{1,d}}{r_{1,d} - 
1} r_{1,d}^n + k_1 n + \frac{k_2 n (n + 1)}{2} + $$
$$\sum_{i=1}^d \frac{c_{i,d} r_{i,d}}{1-r_{i,d}} + \sum_{j=2}^d 
\frac{c_{j,d} r_{j,d}}{r_{j,d}-1} r_{j,d}^n = \Theta(r_{1,d}^n) + O(n^2) \koz.
$$
\end{lemma}



\subsection{Pseudocode of the algorithm \textsc{Quick-Martin}}\index{\textsc{Quick-Martin}}
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.

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 \cite{HorvathI2008}.\nevindex{Iv�nyi, Antal Mikl�s}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Pseudocode of algorithm $d$-\textsc{Complexity}}
At first we present an algorithm $d$\textsc{Complexity} which estimates the $d$-complexity of words. 

\textit{Input:} $q$ the size of the alphabet, \\
$d$ the distance parameter, \\
$n$ the length of the investigated word, \\
$w[1], w[2], \ldots, w[n]$ the letters of the investigated word.

\textit{Output:} $I[n]$ the $d$-complexity of the investigated word.

\textit{Working variables:} $U[0], \ U[1], \ \ldots, \ U[q-1]$ position of 
the last occurrence of letters $0, \ 1, \ \ldots, \ q - 1$. \\
$z$ starting index of the summing. \\ 

\bigskip
\noindent \textsc{Complexity$(q,d,n,\mathbf{w})$}\inddef{\textsc{Complexity}}
\vspace{-2mm}
\begin{tabbing}
\quad \= \quad \= \quad          \kill
01 \textbf{for} \= $i = 0$ \textbf{to} $q-1$ \\
02              \>$U[i] = 0$ \\
03 $U[w[1]] = 1$  \\
04 $I[0] = 0$ \\
05 \textbf{for} \= $i = 1$ \textbf{to} $n$ \\
06              \= $H[i] = 0$ \\
07              \= $z = \max(0, U[w[i]], \ i + 1 - d)$ \\
08              \= \textbf{for} \= $j = z$ \textbf{to} $i$ \\
09              \=              \>  $H[i] = H[i] + H[j]$ \\
10              \>              \> \textbf{if} \= $U[w[i] == 0$ \\ 
11              \>              \>             \> $H[i] = H[i] + 1$ \\
12              \> $I[i] = I[i-1] + H[i]$ \\
13 \textbf{return} $I$
\end{tabbing}

The $d$-complexity of the investigated word is greater or equal to the output 
of this algorithm. If all letters of $w$ are different or if $w$ is a 
1-subword of the word $(0 \ 1 \ \ldots \ q - 1)^*$ or $d \ge n - 1$, then the 
output $I[n]$ of the algorithm is the exact complexity of $w$.

The running time of this algorithm is $O(qn)$. \\


\subsection{ Pseudocode of algorithm \textsc{Super}}  
The following algorithm produces a superperfect word \cite{Ivanyi1987,Ivanyi1988,Voros84}.\nevindex{V�r�s, N�ra}

\textit{Input}: $n_{max}$ the size of the alphabet, \\
$a$ the length of the window.
 
\textit{Output}: an infinite superperfect word \textbf{w} = $(w_1, \ w_2, \ \ldots)$. 

\bigskip
\noindent \textsc{Super$(a,n_{max})$}\inddef{\textsc{Super}}
\vspace{-2mm}
\begin{tabbing}
\quad \= \quad \= \quad          \kill
1 $n = 1$ \\
2 $\mathbf{w} = (0,1,\ldots,n-1)$ \\
3 \textbf{while} \= $n \leq n_{max}$ \\
4                \> Continue \textbf{w} to get an Eulerian circuit of De Bruijn graph $B(n,a)$ \\
5                $n = n + 1$ \\
6 \textbf{return} \textbf{w} 
\end{tabbing}

In line 4 of \textsc{Complex} we use algorithm \textsc{Bruijn} \cite{Ivanyi1988}. 


\subsection{ Pseudocode of algorithm \textsc{MaxSub}}
Algorithm \textsc{MaxSub} generates a word of given length having maximal subwordcomplexity.

\textit{Input:} $n$ the length of the word to be generated;\\
$q$: the size of the alphabet.

\textit{Output:} $m_1, \ m_2, \ldots \ m_n$: the letters of a maximal word $M(q,n)$. \\

\textit{Working variables:} $C[0], C[1], \ldots, C[q^n-1]$ counters of 
the vertices of de Bruijn graph $B(q,n)$. 

\bigskip
\noindent \textsc{MaxSub$(a,n_{max})$}\inddef{\textsc{MaxSub}}
\vspace{-2mm}
\begin{tabbing}
\quad \= \quad \= \quad          \kill
01 $k = \lfloor \log _q n \rfloor$ \\
02 \textbf{if} \= $n \leq q^k + k - 1$ \\ 
03             \> $k = k - 1$ \\
04 \textsc{Optimal-Martin}$(q,k)$ \\
05 \textbf{if} \= $n == q^k + k - 1$ \\ 
06             \> \textbf{return} $M(q,n)$  \\
07 Add 0 to the Martin-word and according to the new word draw a path in the De Bruijn graph $B(q,k+1)$ \\
08 Construct cycles in $B(q,k+1)$ using the remaining edges following Martin principle \\
09 Order these cycles in decreasing order of length. Let $|C_1| \geq |C_2| \geq \ldots \geq |C_m|$. \\
10 Transform \= $M(q,k)$ at first into a cyclical De Bruijn word, then back into 
             \> a De Bruijn word $L$ ending at the starting vertex of $C_1$.  \\
11 Add $C_1$ to $L$ receiving the letters $m_{q^k + k + 2} m_{q^k + k + 3} \ldots m_{q^k + k + 1 + |C_1|}$  \\
12 \textbf{if} \= the length of the new word is greater or equal to $n$ \\ 
13             \> \textbf{return} \\
14 \textbf{for} \= $i = 2$ \textbf{to} $m$ \\
15              \> Insert $C_i$ in the constructed word \\
16              \> \textbf{if} \= the length of the new word is greater or equal to $n$ \\ 
17              \>             \> \textbf{return} $M(q,n)$
\end{tabbing}

The running time of \textsc{MaxSub} is $O(a^{n_max})$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Construction and complexity of extremal words}
Due to the finiteness of the corresponding sets $d$-extremal 
words of languages exist in all cases. Similar assertion does not hold for maximal 
and minimal words of families of languages.

Theorem \ref{theorem-ex1} and \ref{theorem-ex3} contain general bounds of $d$-complexity, resp. 1-complexity. 
Theorem \ref{theorem-ex4} characterizes the maximal $d$-complexity for medium distance and implies 
the surprising corollary that binary alphabet is sufficient to get the same order
 of maximal subword complexity what can be achieved using an infinite alphabet.

Theorem \ref{theorem-ex6} and \ref{theorem-ex7} give the maximal complexity for different values of the parameters. 
Theorem \ref{theorem-ex8} contains the condition of the existence of $1$-superminimal words. 
Theorem \ref{theorem-ex9} gives the complexity of cyclical words and together with Theorem \ref{theorem-ex6} has the 
corollary that $f(q,n,d)$ and $f(d,n,q)$ have the same order of growth. Theorem \ref{theoremex10} 
gives the that the $n$-length words can be covered using only 
letters needed to cover the words $(0^n) \ (1)^n \ \ldots \ (q - 1)^n)$ 
and so illustrates the decreasing of the length of minimal $d$-covering 
words due to the permitted jumps in the construction.

\begin{tetel} \emph{Iv�nyi \cite{Ivanyi1987}} \label{theorem-ex1} If $d, \ n$ and $q$ are positive 
integers, $\mathcal{A} = \{ 0,1,\ldots,q-1 \} $ is an alphabet and $w \in \mathcal{A}^n$, then
\begin{equation}
n \leq T(w,\mathcal{A}^+,d) \le 2^n - 1 \koz.
\end{equation}
The lower bound is tight if and only if  $w$ is homogeneous. The upper bound is sharp 
if and only if  $w$ is a rainbow word and $d \ge n-1$.
\end{tetel}
\begin{biz} Since $w_1 w_2 \ldots w_i \in D(w,\mathcal{A}^+,i,d)$ holds for 
$i=1, 2, \ldots, n$, the lower bound is correct and for $w=0^n$ the equality 
holds. The upper bound can be proved using equation \ref{equation:min} and 
inequality $\min(q^i, \binom{n}{i}) \leq \binom{n}{2}$ or directly exploiting 
that an $n$-element set has $2^n - 1$ nonempty subsets. If $q \ge n$ and 
$d \ge n-1$, then $w=0 \ 1 \ \ldots \ n-1$ belongs to $\mathcal{A}^+$ and 
contains $2^n - 1$ different elements of $\mathcal{A}^n$ as a $d$-subword so 
the upper bound is also tight. From the other side if $n<k$, then $w$ contains 
repeated letters and so $C(w,\mathcal{A}^+,1,d)<n$, and if $d<n-1$, then the 
first and last letters of $w$ do not form $d$-subsequence and so 
$C(w,\mathcal{A}^+,2,d)<\textbinom{n}{2}$. 
\end{biz}

\begin{kov} If $d, \ n$ and $q$ are positive integers, then
\begin{equation}
f(1,n,d) = n
\end{equation}
and if $d \geq n - 1$, then 
\begin{equation}
f(n, n, d) = f(n, n, n - 1) = 2^n - 1 \koz.
\end{equation}
\end{kov}

\begin{tetel} \label{theorem-ex2} If $q$ and $n$ are positive integers, 
$\mathcal{A}=\{0,1,\ldots,q-1\}$ is an alphabet and $w \in 
\mathcal{A}^{\lambda(w)}$, then
\begin{equation}
n \leq T(w,\mathcal{A}^+,1) \le \frac{n(n+1)}{2} \koz.
\end{equation}
The lower bound is sharp if $w$ is homogeneous. The upper bound is sharp if and only if  
$w$ is a rainbow word. 
\end{tetel}
\begin{biz} We have $n + 1$ places for the 2 delimiters determining a 
1-subword of $w$. If $q \ge n$, then all 1-subwords of the word 
$u=0 \ 1 \ \ldots \ \lambda(w) - 1$ are different. From the other side if $q < 
n$, then $w$ has to contain repeated letters not representing different 
1-subwords. 
\end{biz}

\begin{tetel} If\label{theorem-ex3} $n$ and $q$ are positive integers and $1 < q < n - 1$, then
\begin{equation}
f(q,n,1) = \frac{n(n+1)}{2} - nk + \frac{k^2 - k}{2} + 
\frac{q^{k + 1} -q}{q-1} \koz,
\end{equation}
where $k$ is the unique integer satisfying $q^k + k - 1 \leq n < q^{k + 1} +k$ and so 
$k - 1 < \log_q n < k + 1$.
\end{tetel}
\begin{biz}
Summing the inequalities (\ref{equation-min1}) for $i = 1, 2, \ldots, n$ results
\begin{equation}
T(w,\mathcal{A}^+,1) \leq \sum_{i=1}^n \ \min(q^i, n - i + 1) \koz.
\end{equation}
In the sum for small values of $i$ the exponential part, for large values of $i$ the 
second part gives the minimum. Therefore concrete calculations result the formula of 
the theorem as a bound. Algorithm \textsc{MaxSb} produces a suitable word for any possible 
pair of $q-n$ achieving this bound.
\end{biz}

In the binary case Shallit\nevindex{Shallit, O. Jeffrey} \cite{Shallit93} has proved the existence of words with such 
complexity. Using alphabet containing $q \geq 3$ letters and algorithm \textsc{Super} we 
constructed \cite{Ivanyi1987}\nevindex{Iv�nyi, Antal Mikl�s} infinite words $w=w_1 w_2 \ldots$ 
with $T(w_1 w_2 \ldots w_n) = f(q,n,1)$.

\begin{kov} If $q \geq 2$, then
\begin{equation}
f(\infty,n,1) = \Theta(f(q,n,1)) = \frac{n(n + 1)}{2} + n \lg n + O(qn) \koz.
\end{equation}
\end{kov}


\begin{tetel} \label{theorem-ex4} If $d, \ q$ and $n$ are positive integers, $1 <d < n-1$ 
and $q \geq n$, then
\begin{equation}
f(q,n,d) = k_1(q,d) n + k_2(q,d) + \sum_{i = 1}^d c_{i,d} r_{i,d}^n \koz.
\end{equation}
\end{tetel}

If $d \leq 4$, then computation of the constants in Theorem \ref{theorem-ex4} requires 
only technical steps, otherwise there are algebraic difficulties. Z. K�sa \cite{Kasa1998} has 
found another recurrence relation and gave explicit formulas for $d \geq n/2$. Using the 
jump function we reprove his result and extend it for some smaller values of $d$.
 
\begin{tetel} \emph{K�sa \cite{Kasa1998}} If\label{theorem-ex5} $d, \ q$ and $n$ are 
positive integers and $q \geq n-1$, then
\begin{eqnarray*}
f(q,n,d) = \left \{ \begin{array}{lllllll} c_{1,2}r_{1,2}^n +
      c_{2,2}r_{2,2}^n - n - 3,  & \mbox{if $d=2$} \\
c_{1,3}r_{1,3}^n + c_{2,3}r_{2,2}^n + c_{3,3}r_{3,3}^n - n/2 - 3/2,  
       & \mbox{if $d = 3$} \\
c_{1,4}r_{1,4}^n + c_{2,4}r_{2,4}^n + c_{3,4}r_{3,4}^n + c_{4,4}r_{1,4}^n 
       - n/3 - 1, & \mbox{if $d = 4$}, \\
2^n-(n-2-d)2^{n-1-d}-2 & \mbox{if  $\frac{5}{2} \leq \frac{n}{2} \leq d 
    \leq n-2$}, \\
2^n-(n-2-d)2^{n-d-1} - 1, & \mbox{if $3 \leq n=2d+1$}, \\
2^n- (n-2-d)2^{n-d-1} + 5, & \mbox{if $4 \leq n=2d+2$}, \\
2^n- (n-2-d)2^{n-d-1} + 14, & \mbox{if $5 \leq n=2d+3$}.
     \end{array} \right.
\end{eqnarray*}
where $c_{1,2}=(3/2+0,7\sqrt{5}), \ c_{2,2}=(3/2-0,7\sqrt{5}), \ 
r_{1,2}=(1+\sqrt{5})/2, \ r_{1,2}=(1+\sqrt{5})/2$ and so
\begin{eqnarray*}
\begin{array}{lll}
f(n-1,n,2) \approx 3,065247.1,618034^n - 0,065247(-0,618034)^n - n - 3, \\
f(n-1,n,3) \approx 1,614776.1,839287^n - n/2 - 3/2 \ + \\
0,737353^n.[0,061034 \cos (2,176234(n+1)) - 0,052411 \sin (2,176234(n+1))]. \\
\end{array} 
\end{eqnarray*}
\end{tetel}
\begin{biz} The formulas for $d = 2$ and $d = 3$ appeared in \cite{Ivanyi1987}, the 
case $d = 4$ is a special case of Theorem \ref{theorem-ex4}.

If $n/2 \leq d \leq n - 2$, then according to Lemma \ref{lemma:jump} the sum of the 
jumping values $J(w,L,i,\infty)$ of a rainbow word $w$ for $i = n - 1, \ n - 2, 
\ \ldots, \ d + 1$ results our formula.

The last 3 formulas also can be derived using Lemma \ref{lemma-jump}.
\end{biz}

Figure \ref{fig-jump} shows the values of the jump function for rainbow words. The 
first and second columns are computed using the formulas $J(1)=n$ and $J(2)= 
n(n-1)/2$, the last columns using the formulas for $f(q,n,d)$ and the medium 
values (printed by bold digits) using the recurrence relation. These data 
support the conjecture that the jump function is trapezoidal.

\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}  \hline
$n/i$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & $2^n - 1$   \\ \hline
1 & 1 &   &  &  & &  &  & & &  & 1  \\ \hline
2 & 2 &  1 &  &   & &  &  & & & & 3 \\ \hline
3 &  3 &  3 & 1 &   & &  &  & & &  & 7 \\ \hline
4 & 4 & 6 & 4 & 1 & &  &  & &   & &  15 \\ \hline
5 & 5 & 10 & 12 & 4 & 1 &  &  & & & & 31  \\ \hline
6 &  6 & 15 & 25 & 12  &  4 & 1 & &  & &  & 63 \\ \hline
7 &7 & 21 &  \textbf{51} & 31 & 12  & 4 & 1  & & &  & 127 \\ \hline
8 & 8 & 28 &  \textbf{97} & 73 & 32 & 12 & 4 & 1 &  & &  255 \\ \hline
9 &  9 &  36 & \textbf{176} & 185 & 79 &  32 &  12 & 4 & 1 & & 511 \\ \hline
10&  10&  45 & \textbf{??} & \textbf{??}  & 191 &  90 & 32  & 12 & 4  & 1 & 1023 \\ \hline
\end{tabular}
\end{center}
\caption{Values of jumping function of rainbow words of length 1, 2, $\ldots, 10.$\label{fig-jump}} 
\end{figure}

\begin{tetel} If\label{theorem-ex6} $q$ is a positive integer, $\mathcal{A} = 
\{0,1,\ldots,q-1 \}$ is an alphabet, $L_n = \mathcal{A}^n$ for 
$n=1,2,\ldots$ and $\mathcal{F}= \{L_1,L_2,\ldots\} $, then $\mathcal{F}$ 
has a 1-superminimal word if and only if $n \neq 2$.
\end{tetel}  

The next theorem shows that the maximal $d$-complexity is exponential 
even over a binary alphabet and $d = 2.$ 

\begin{tetel} Let\label{theorem-ex7} $q \ge 2$ and $d\ge 2$ be positive integers and 
$w=w_1w_2\ldots= 0 \ 1 \ \ldots q-1  \ 0 \ 1 \ldots q-1 \ldots $ be an 
infinite cyclical word over the alphabet $\mathcal{A}=\{0,1,\ldots,q-1 \}$ 
and $p_n=w_1 w_2 \ldots$ . Then
\begin{equation}
T(p_n,\mathcal{A}^+,d) = \Theta(r_{1,d}^n) + O(n),
\end{equation}
If $q=2$, then
\begin{equation}
T(p_n,\mathcal{A}^+,d) = \frac{5 + 2 \sqrt{5}}{2} \left 
( \frac{1 + \sqrt{5}}{2} \right )^n + \frac{5 - 2 \sqrt{5}}{2} \left ( 
 \frac{1 - \sqrt{5}}{2} \right )^n - 2,
\end{equation}
and so
\begin{equation}
T ( p_n,\mathcal{A}^+,2 )=\Theta \left ( \left ( 
\frac{1 + \sqrt{5}}{2} \right )^n \right ).
\end{equation}
\end{tetel}
\begin{biz} In this case for the $d$-characteristic function we get a 
Fibonacci-type recursion $H(w,\mathcal{A}^+,$ $i+2,d)=H(w,\mathcal{A}^+, 
i,d)+H(w,\mathcal{A}^+,i+1,d)$ with initial  
values $H(w,\mathcal{A}^+,1,d)=1$ and $H(w,\mathcal{A}^+,2,d)=2$. The sum 
of the corresponding characteristic values gives the total complexity.
\end{biz}   

\begin{kov} If $q, n$ and $d$ are positive integers, $q \geq 2$ and 
$d \geq 2$, then
\begin{equation}
\Theta(f(q,n,d)) = \Theta(f(d,n,q)) = \Theta(r_{1,d}^n). 
\end{equation}
\end{kov}

\begin{tetel} If\label{theorem-ex8} $q, \ n$ and $d$ are positive integers, $d \geq q, \ \mathcal{A} 
=\{0,1,,\ldots,q-1)$ and $L=\mathcal{A}^n$, then 
\begin{equation}
g(q,n,d)=qn
\end{equation} 
and $w=(0 \ 1 \ \ldots \ q-1)^n$ is a minimal $q$-covering word of $L$.
\end{tetel}
  
\begin{kov} If $n$ and $q$ are positive integers, $\mathcal{A}=\{0,1, 
\ldots,q-1\}, \ \mathcal{M}=(\mathcal{A},n,n,\ldots,n)$ 
and $L = \mathcal{M}^n$, then $\gamma(L,n) = qn$ and $w=(1 \ 2 \ \ldots \ q)^n$
is a minimal $q$-covering word of $L$.   
\end{kov}

\begin{gyak}
\ujgyak 
Construct a superperfect word with maximal window size 4 for the alphabet $\{0, 1, 2\}$.
\end{gyak}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Finite two-dimensional arrays with maximal complexity}
The section starts with definitions, then bounds and several further properties of the complexity functions are given.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Definitions}
Let $q \geq 2 $ be a positive integer and $X=\{0,1,\ldots,q-1\}$ an alphabet. Let
$X^{M\times N}$ denote the set of $q$-ary $M\times N$ arrays ($M$, $N \geq 1$
positive integers), and $X^{\ast\ast}=\cup _{M,N \geq 1}X^{M\times N}$ the set of
finite $q$-ary two-dimensional arrays.
\begin{defi}
\label{d1} Let $m$ and $n$ be positive integers with $1\leq m\leq M$ and $1 \leq n\leq N$. 
A $q$-ary $m\times n$ array $\mathcal{B}=[b_{ij}]_{m\times n}$ is a \textbf{subarray} of the 
$q$-ary $M\times N$ array
$\mathcal{A}=[a_{kl}]_{M\times N}$ if there exist indices $r,\ s$ such that
$r+m-1\leq M$, $s+n-1\leq N$ and $\mathcal{B}=[a_{uv}]_{r\leq u\leq
r+m-1,s\leq v\leq s+n-1}.$
\end{defi}

According to this definition only nonempty arrays can be $(m,n)$-subarrays.

We remark that we are dealing with \emph{aperiodic}\index{aperiodic array} $q$-ary $M\times
N$\ arrays (written on a planar surface, with all the subarrays situated
completely within the borders of the array). Another point of view is to
consider the given array wrapped round on itself (written on a torus), hence a
\emph{periodic} array. Existence results for periodic and aperiodic arrays
which contain every rectangular subarray of given sizes precisely once are
given by Paterson \cite{Paterson1994}, respectively Mitchell \cite{Mitchell1995}.

Notions of complexity similar to those for words can be introduced for arrays.

\begin{def}
\textbf{\label{d2}} Let $\mathcal{A}\in X^{M\times N}$ be a
$q$-ary array and$\ m$, $n$ positive integers with $1\leq m\leq M$ and $1\leq
n\leq N$. Let $D_{\mathcal{A}}(m,n)$ denote the set of different $m\times n$
subarrays of $\mathcal{A}$. The \textbf{subarray complexity function}, or,
simply, the \ki{complexity function}\inddef{complexity function} $C_{\mathcal{A}}:\left\{
1,2,\ldots,M\right\}  \times\left\{  1,2,\ldots,N\right\}  \rightarrow
\mathbb{N}$ of $\mathcal{A}$ is
\begin{equation}
C_{\mathcal{A}}(m,n)=|D_{\mathcal{A}}(m,n)|,\ \ \ \ m=1,2,\ldots
,M,\ n=1,2,\ldots,N, \label{f1}%
\end{equation}
and the \textbf{total complexity function} $T_{\mathcal{A}}$ of $\mathcal{A}$
is
\begin{equation}
T_{\mathcal{A}}=\sum_{m=1}^{M}\sum_{n=1}^{N}\ C_{\mathcal{A}}(m,n) \koz.
\label{f2}%
\end{equation}
\end{def}

The one-dimensional complexity and total complexity functions were introduced
by M. Heinz \cite{Heinz1977}\nevindex{Heinz, Michael} in 1977, and studied later by many authors (see e.g.
recent papers \cite{Anisiu2002,AnisiuBK02,BlazsikK2002,AnisiuC2004,CarpiL2001,Ferenczi99,Luca1999,Shallit93}).

\begin{pelda}
\label{e1}Let $X=\{0,1,2,3,4,5\}$ be an alphabet and
\[
\mathcal{A}_{1}=\left(
\begin{array}
[c]{c}%
0\ 0\ 0\\
0\ 0\ 0
\end{array}
\right)  ,\ \ \ \ \mathcal{A}_{2}=\left(
\begin{array}
[c]{c}%
0\ 1\ 0\\
0\ 0\ 2
\end{array}
\right)  ,\ \ \ \ \mathcal{A}_{3}=\left(
\begin{array}
[c]{c}%
0\ 1\ 2\\
3\ 4\ 5
\end{array}
\right)  .
\]
Then $T_{\mathcal{A}_{1}}=6,\ T_{\mathcal{A}_{2}}=15,$ and $T_{\mathcal{A} _{3}}=18.$
\end{pelda}

\begin{def}
\label{d3}The $q$-ary $M\times N$ array $\mathcal{A}$ is $(q,m,n)$%
-\textbf{extremal} if
\begin{equation}
{\normalsize C_{\mathcal{A}}(m,n)=\max\limits_{\mathcal{B}\in X^{M\times N}%
}C_{\mathcal{B}}(m,n) \koz. } \label{f3}
\end{equation}
\end{def}

\begin{def}
\label{d4}The $q$-ary $M\times N$ array $\mathcal{A}$ is $(q,m,n)$%
-\textbf{perfect} if it contains each of the $q^{mn}$\ possible $m\times
n\ q$-ary arrays as a subarray exactly once.
\end{def}

\begin{def}
\label{d8}The arrays consisting of identical letters are called
\textbf{homogeneous} arrays, the arrays consisting of different letters are
called \textbf{rainbow} arrays.
\end{def}

We mention that a $q$-ary $M\times N$ rainbow array\ exists if and only if
$q\geq MN$. It is obvious that $(q,m,n)$-extremal arrays always exist in
$X^{M\times N}$ for arbitrary values of $M$, $N$, while $(q,m,n)$-perfect
arrays can exist only for $M$, $N$ satisfying $q^{mn}=$ $\left(  M-m+1\right)
\left(  N-n+1\right)  $.

\begin{def}
\label{d8a}The function $H_{q,M,N}:\left\{  1,2,\ldots,M\right\}
\times\left\{  1,2,\ldots,N\right\}  \rightarrow\mathbb{N}$ given by
\begin{equation}
H_{q,M,N}(m,n)=\min\left\{  q^{mn},\left(  M-m+1\right)  \left(  N-n+1\right)
\right\}  \label{f4}
\end{equation}
is called \textbf{maximal complexity function}.{\normalsize  }
\end{def}

\begin{def}
\label{d9}The $q$-ary $M\times N$ array {\normalsize $\mathcal{A}$} \textbf{is
}$(q,m,n)$-\textbf{maximal }if
\begin{equation}
{\normalsize C_{\mathcal{A}}(m,n)=\ }H_{q,M,N}(m,n)\text{;} \label{n}%
\end{equation}
it is \textbf{maximal} if (\ref{n}) holds for all $m=1,2,\ldots,M,$
$n=1,2,\ldots,N$.{\normalsize  }
\end{def}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Bounds of complexity functions}
We present the natural bounds of the complexity function for $q$-ary arrays
$\mathcal{A}\in X^{M\times N}$, as well as those of the total complexity function.

\begin{allit} \emph{Anisiu, Iv�nyi \cite{AnisiuI2006}}
\label{l1}For each $q$-ary $M\times N$ array $\mathcal{A}$\ we have
\begin{equation}%
\begin{array}
[c]{l}%
1\leq C_{\mathcal{A}}(m,n)\leq\min\left\{  q^{mn},(M-m+1)(N-n+1)\right\}  ,\\
m=1,2,\ldots,M,\ n=1,2,\ldots,N \koz.
\end{array}
\label{f5}%
\end{equation}
The lower bound is sharp for homogeneous arrays and the upper bound is sharp
for rainbow arrays. The total complexity of $\mathcal{A}$\ satisfies the
inequality
\begin{equation}
MN\leq T_{\mathcal{A}}\leq\sum_{i=1}^{M}\sum_{j=1}^{N}H_{q,M,N}(i,j) \koz.
\label{f6}%
\end{equation}
\end{allit}
\begin{biz}
From the definition of the subarray it follows that $C_{\mathcal{A}}%
(m,n)\geq 1,$ $m=1,2,\ldots,M,\ n=1,2,\ldots,N;$\ for a homogeneous array the
equality holds.

It is obvious that the complexity $C_{\mathcal{A}}(m,n)$\ cannot exceed the
total number of subarrays over $X$, that is $q^{mn}$; it also cannot exceed
the total number of subarrays of dimension\ $m\times n$ of the given array
(possible not all different), namely $(M-m+1)(N-n+1).$\ It follows that $1\leq
C_{\mathcal{A}}(m,n)\leq\ \min\left\{  q^{mn},(M-m+1)(N-n+1)\right\}
,\ m=1,2,\ldots,M,\ n=1,2,\ldots,N$. For a rainbow array $\mathcal{R}$\ we
have $C_{\mathcal{R}}(m,n)=(M-m+1)(N-n+1)=$ $\min\left\{  q^{mn}%
,(M-m+1)(N-n+1)\right\}  .$

By summing up the inequalities (\ref{f5}) we obtain (\ref{f6}).
\end{biz}

\begin{megj}
In terms of the maximal complexity functions, inequality (\ref{f5}) may be
reformulated as
\[
1\leq C_{\mathcal{A}}(m,n)\leq H_{q,M,N}(m,n),\text{ \ \ \ }m=1,2,\ldots
,M,\text{ }n=1,2,\ldots,N.
\]
It follows that every $(q,m,n)$-perfect array, as well as any rainbow array,
is $(q,m,n)$-maximal.
\end{megj}

The values of the complexity and total complexity for homogeneous and rainbow
arrays can be easily computed.

\begin{allit} \emph{Anisiu, Iv�nyi \cite{AnisiuI2006}}
\label{l3}If $\mathcal{H}$ is a homogeneous $M\times N$ array and
$\mathcal{R}$ is an $M\times N$ rainbow array, then
\[%
\begin{array}
[c]{l}%
C_{\mathcal{H}}(m,n)=1,\ \ \ \ C_{\mathcal{R}}(m,n)=(M-m+1)(N-n+1),\\
m=1,2,\ldots,M,\ n=1,2,\ldots,N
\end{array}
\]
and
\begin{equation}
T_{\mathcal{H}}=MN,\ \ \ T_{\mathcal{R}}=\frac{M(M+1)N(N+1)}{4}.
\end{equation}
\end{allit}
\begin{biz}
The complexity functions $C_{\mathcal{H}}$ and $C_{\mathcal{R}}$\ were given
in the proof of Proposition \ref{l1}. Easy\ calculations give the formulas for
$T_{\mathcal{H}}$\ and $T_{\mathcal{R}}$.
\end{biz}

The shape of the complexity function for words was proved in \cite{Luca1999,LeveS01,jaegerLM2003,AnisiuC2004}%
\ to be \ki{trapezoidal},\inddef{trapezoidal shape} i. e. it has an ascending part, possibly a
horizontal one, and the last part is a descending line . The main feature is
that after becoming constant, the complexity function of an arbitrary word
cannot increase again. The question for arrays is: for a fixed $m_{0}$, is
$C_{\mathcal{A}}(m_{0},\cdot)$\ still trapezoidal? For $m_{0}=1$,\ the answer
is positive, as a consequence of the mentioned result for words; nevertheless,
this is not true for all the values $m_{0}=1,2,\ldots,M$. The array
$\mathcal{A}$\ in the following example has the property that $C_{\mathcal{A}%
}(2,\cdot)$\ increases again after becoming a constant.

\begin{pelda}
For the array $\mathcal{A}\in\{0,1\}^{3\times19}$ given by
\begin{equation}
\mathcal{A}=\left(
\begin{array}
[c]{c}%
1\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 1\\
1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\\
0\ 0\ 0\ 1\ 1\ 1\ 1\ 0\ 1\ 1\ 0\ 0\ 1\ 0\ 1\ 0\ 0\ 0\ 0
\end{array}
\right)
\end{equation}
one has $C_{\mathcal{A}}(2,4)=C_{\mathcal{A}}(2,5)=21$, $C_{\mathcal{A}%
}(2,6)=C_{\mathcal{A}}(2,7)=22$ and $C_{\mathcal{A}}(2,8)=21$.
\end{pelda}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ Properties of the maximal complexity function}
We shall describe some properties of the function $H_{q,M,N}$ related to the
shape of its graph, namely its monotonicity and its maximum.

For $M=1$ (or $N=1$) the arrays are in fact finite sequences (words). It was
shown in \cite{AnisiuBK02,AnisiuC2004,Luca1999} that for a given $N$ we have
\begin{equation}
H_{q,1,N}(1,n)=\left\{
\begin{array}
[c]{l}%
q^{n},\;n\leq k\\
N-n+1,\;k+1\leq n\leq N,
\end{array}
\right.
\end{equation}
where $k$ is the only natural number for which $q^{k}+k\leq N<q^{k+1}+k+1$.
The maximum of $H_{q,1,N}$ is equal to $N-k$ and is attained at the unique
point $k+1$ for $q^{k}+k<N\leq q^{k+1}+k+1$ , and at both $k$ and $k+1$ for
$N=q^{k}+k$, hence $H_{q,1,N}$ is trapezoidal.

In the remaining part of this section we shall consider proper arrays (with
$M,N\geq 2$).

\begin{megj}
If both sizes of the array are smaller than the cardinal of the alphabet $X$
$(M,N\leq q)$, we have
\[
\left(  M-m+1\right)  \left(  N-n+1\right)  \leq q^{2}\leq q^{mn}\text{ for
}mn\neq 1,
\]
hence
\[
H_{q,M,N}(m,n)=\left\{
\begin{array}
[c]{l}%
\min\left\{  q,MN\right\}  ,\;m=n=1\\
\left(  M-m+1\right)  \left(  N-n+1\right)  ,\;\text{otherwise.}%
\end{array}
\right.
\]
The maximum will be given by
\[
H_{\max}=\max\left\{  \min\left\{  q,MN\right\}  ,N(M-1),M(N-1)\right\}
\]
and will be attained at one of the points $(1,1)$, $(1,2)$ or $(2,1)$. If
$q<MN,$ we have $H_{\max}=\max\left\{  q,N(M-1),M(N-1)\right\}  ;$ if $q\geq
MN,$ $H_{\max}=MN=h(1,1).$
\end{megj}

In what follows we shall consider $\max\{M,N\}>q.$

\begin{allit} \emph{Anisiu, Iv�nyi \cite{AnisiuI2006}}
\label{p1}Let $m_{0}\in\{1, ..., M\}$ be fixed; the function $H_{q,M,N}%
(m_{0},\cdot)$ is trapezoidal, the horizontal part containing at most two
points; the last part is a descending line and the maximum of $H_{q,M,N}%
(m_{0},\cdot)$ is attained at the first point $d_{m_{0}}$ situated on the
descending line, or on $d_{m_{0}}-1.$
\end{allit}
\begin{biz}
The values of $H_{q,M,N}(m_{0},n),n\in\{1,...,N\}$ are given by the minimum of
the values of an increasing exponential and of a descending line. At the
beginning, if $\left(  M-m_{0}+1\right)  N>q^{m_{0}},$ $H_{q,M,N}(m_{0}%
,\cdot)$ will be situated on the exponential, and surely it will end on the
descending line. Therefore $H_{q,M,N}(m_{0},\cdot)$ will have a trapezoidal
shape, with a horizontal part with at most two points.

There will be a point $d_{m_{0}}\leq N$ which is the least value of $n$ for
which $H_{q,M,N}(m_{0},n)$ is on the descending line, i.e. if $d_{m_{0}}>1$
\[%
\begin{array}
[c]{l}%
(M-m_{0}+1)(N-d_{m_{0}}+1)\leq q^{m_{0}d_{m_{0}}}\\
(M-m_{0}+1)(N-d_{m_{0}}+2)\geq q^{m_{0}\left(  d_{m_{0}}-1\right)  }.
\end{array}
\]

The maximal value of $H_{q,M,N}(m_{0},\cdot)$ will be given by
\[
\mu _{m_{0}}=\max\left\{  q^{m_{0}\left(  d_{m_{0}}-1\right)  },(M-m_{0}%
+1)(N-d_{m_{0}}+1)\right\}  .
\]
The maximum of $H_{q,M,N}$ over $\{1,...,M\}\times\{1,...,N\}$ will be then
$H_{\max}=\max$\{$\mu_{m}:m\in\{1,...,M\}\}.$
\end{biz}

\begin{megj}
The maximum of $H_{q,M,N}$ can be attained at a unique point (for example
$H_{2,4,5}(2,2)=12$) or at several points ($H_{2,4,2}(1,2)=H_{2,4,2}%
(2,1)=H_{2,4,2}(3,1)=4$).
\end{megj}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{ On the existence of maximal arrays}
In \cite{AnisiuC2004} it was proved, using the results 
in \cite{Bruijn46,CummingsW1986,Martin34,Shallit93} that there
exist finite words with maximal complexity, of any given length; it follows
that there are $M\times 1$\ and $1\times N$\ maximal arrays for all positive
integers\ $M$ and $N$. More than that, in \cite{AnisiuBK02} the number of the words
with maximal complexity is presented. Nevertheless, if both $M$ and $N$\ are
$\geq 2,$ the situation differs, as the following proposition shows.

\begin{allit} \emph{Anisiu, Iv�nyi \cite{AnisiuI2006}}
\label{p3}There are sizes $M,$ $N \geq 2$ for which there are no arrays with
maximal complexity.
\end{allit}
\begin{biz}
For $M = N = 4$\ calculations show that the total complexity $T_{\mathcal{A}}$\ of
any $4\times 4$ array is $\leq 69,$\ while $\sum _{i=1}^{4}\sum _{j=1}%
^{4}\ H_{2,4,4}(i,j)=70$. It follows that for each $4\times 4$\ array
$\mathcal{A}$\ there exists at least one pair ($m,n$) for which
$C_{\mathcal{A}}(m,n)<H_{2,4,4}(m,n)$.
\end{biz}

\medskip

\textbf{Open question} Find the pairs $M,N$ for which there exist maximal
arrays in $X^{\ast\ast}$.

\medskip

The result in Proposition \ref{p3} prevents us from obtaining a $q$-ary array
with maximal complexity for any $M$ and $N \geq 2$. A further question is: given
$M$, $N$ and $m\leq M,$ $n\leq N,$ is there an $M\times N$ array
$\mathcal{A}_{m,n}$ which is $(q,m,n)$-maximal?

A partial answer is given in \cite{Mitchell1995}: in the binary case, if
$(M-m+1)(N-n+1)=2^{mn},$ there exists a $M\times N$\ array which is
($2,m,n$)-maximal (in fact it is ($2,m,n$)-perfect).



\begin{gyak}
\ujgyak Design arrays with maximal comp�exity for different parameters. 
\end{gyak}

\begin{fld}
\ujfld{Comparison of the Martin-type algorithms}
{Write a program and compare the real running times of \textsc{Martin}\felindex{Martin@\textsc{Martin}} 
(describen in the chapter on the complexity of words), 
\textsc{Quick-Martin}\felindex{Quick-Martin@\textsc{Quick-Martin}} and 
\textsc{Optimal-Martin}.\felindex{OptimalMartin@\textsc{Optimal-Martin}}}

\ujfld{Characterization of the solutions of equation (\ref{eq-neclong1})}
{Characterize the solutions of (\ref{eq-neclong1}) for $d = 1, \ 2, \ 3$ and $4.$}
\end{fld}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}.

A good and recent review on the one-dimensional results is given in Chapter \textit{Complexity of words}
of this volume.\nevindex{K�sa, Zolt�n}\nevindex{Anisiu, Mira-Cristiana}

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 \textit{growing sequences}\index{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, John C.} in 1988 \cite{Cock1988}, and in 1994 of Hurlbert\nevindex{Hurlbert, Glenn} and 
Isaak \cite{HurlbertI1994}.\nevindex{Isaak, Garth} 

The first growing cubes were constructed by Horv�th and Iv�nyi 
\cite{HorvathI2008},\nevindex{Horv�th, M�rk} while the first hypercube 
by Iv�nyi and Madar�sz \cite{IvanyiM2011ENDM}.\nevindex{Madar�sz, J�nos}\nevindex{Iv�nyi, Antal Mikl�s}

The most general existence theorem of double symmetric perfect arrays can be found in \cite{IvanyiM2011ENDM}.

$d$-complexity was introduced in \\cite{Ivanyi1987} and extended by Zolt�n K�sa in 
\cite{Kasa1998,Kasa10,Kasa11}\nevindex{K�sa, Zolt�n} 

Interesting properties of De Bruijn graphs are reviewed by James Bond\nevindex{Bond, James} 
and Antal Iv�nyi\nevindex{Iv�nyi, Antal Mikl�s} in \cite{Bond87}.

Carla Savage\nevindex{Savage, Carla} \cite{Savage1997} analysed De Bruijn sequences as special 
Gray codes\index{Gray code}\nevindex{Gray, Frank}  
\end{fejmegj}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{AlgofInf3-21Sept}
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 home page 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}
