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

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

\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{multirow}
\usepackage{enumerate}

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

\addtocounter{part}{0}
\addtocounter{chapter}{25}
\setcounter{page}{1300}
\setcounter{tocdepth}{2}

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

\makeindex


\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\Zset{\mathbb{Z}}
\newcommand{\pal}{\textrm{pal}}


\begin{document}

\chapter{Complexity of Words}

\noindent The complexity of words is a continuously growing field of the combinatorics of words. Hundreds 
of papers are devoted to different  kind of complexities. We try to present in this chapter far 
from beeing exhaustive the basic notions and results for finite  and infinite words.

\indent First of all we summarize the simple (classical) complexity measures, giving formulas and algorithms 
for several cases. After this, generalized complexities are treated, with different type of algorithms.
We finish this chapter by presenting the palindrome complexity.

Finally, references from a rich bibliography are given.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Simple complexity measures} \inddef{word!complexity}
In this section simple (classical) complexities, as measures of the diversity of the subwords in finite 
and infinite words, are discussed. First, we present some useful notions related to the finite and infinite words 
with examples. Word graphs, which play an important role in understanding and obtaining the complexity, 
are presented in detail with pertinent examples. After this, the subword complexity (as number of  subwords), 
with related notions, is expansively presented.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Finite words}\inddef{word!finite}
Let $A$ be a finite, nonempty set, called  \ki{alphabet.}  Its elements are called  \ki{letters} or \ki{symbols.} 
A string $a_1a_2\ldots a_n$, formed by  (not necessary different) elements of  $A$, is a \ki{word.} 
The length of the word  $u=a_1a_2\dots a_n$ is $n$,   and is denoted by  $|u|$. 
The word without any element is the  empty word, denoted by   $\varepsilon$ (sometimes  $\lambda$). 
The set of all finite words over $A$ is denoted by $A^*$. We will use the following notations too:
\[ A^+= A^*\setminus \{\varepsilon\}, \qquad A^n=\Big\{u\in A^*\;\big|\; |u|=n\Big\}=
\Big\{a_1a_2\ldots a_n \;|\;  a_i\in A\Big\}\koz,\] 
that is  $A^+$ is the set of all finite and nonempty words over  $A$, whilst $A^n$ 
is the set of all  words  of length $n$  
over $A$. Obviously $A^0=\{\varepsilon\}$. The sets $A^*$ and $A^+$  are infinite denumerable sets.  

We define in  $A^*$ the binary operation called \ki{concatenation} (shortly \ki{catenation}). 
If $u=a_1a_2\ldots a_n$ and $v=b_1b_2\ldots b_m$, then
\[w=uv= a_1a_2\ldots a_nb_1b_2\ldots b_m, \qquad |w|=|u|+|v|\koz.\]
This binary operation is associative, but not commutative. Its neutral element 
is $\varepsilon$ because $\varepsilon  u=u \varepsilon = u$.  The set $A^*$ with this neutral element 
is a monoid. We introduce recursively the \ki{power of a word:}   

\smallskip
$\bullet$ $u^0=\varepsilon$

$\bullet$ $u^n=u^{n-1}u$, if $n\ge 1$.
 
\smallskip
A word is  \ki{primitive} if it is no power of any word, so $u$ is  primitive if 
\[ u=v^n, \; v\neq \varepsilon \quad \Rightarrow \quad n=1\koz.\]
For example, $u=abcab$ is a primitive word, whilst  $v=abcabc=(abc)^2$ is not.

The word $u=a_1a_2\ldots a_n$ is  \ki{periodic} if there is a value $p$,  $1\le p< n$ 
such that
 \[a_i=a_{i+p}, \textrm{ for all } i=1,2,\ldots, n-p\koz,\] and $p$ is the period of $u$.  
The least such $p$ is the  \ki{least period} of $u$. 

The word $u=abcabca$ is periodic with the least period $p=3$.

Let us denote by $(a,b)$ the greatest common divisor of the naturals $a$ and $b$.  
The following result is obvious.
\begin{tetel}
If $u$ is periodic, and $p$ and $q$ are periods, then $(p,q) $ is  a period too.  
\end{tetel}

The \ki{reversal} (or \ki{mirror image}) of the word   $u=a_1a_2\ldots a_n$ is  
$u^R=a_na_{n-1}\ldots a_1$. Obviously $\big(u^R\big)^R=u$. If $u=u^R$, 
then  $u$ is a \ki{palindrome.} \index{word!reversal} \index{palindrome}\index{reversal word}   

The word  $u$ is a  \ki{subword} (or \ki{factor}) \index{word!subword}\index{subword} of  $v$ 
if there exist the words
 $p$ and $q$ such that $v=puq$. If $pq\neq \varepsilon$, \index{word!prefix}\index{word!suffix}
then  $u$ is a proper subword of  $v$. If $p=\varepsilon$, then $u$ is a 
\ki{prefix} of  $v$, and if  $q=\varepsilon$, then  $u$ is a \ki{suffix} of $v$. 
The set of all  subwords of length $n$ of $u$ is denoted by  $F_n(u)$. 
$F(u)$ is the set of nonempty subwords of  $u$, so \[F(u)= \bigcup_{n=1}^{|u|}F_n(u)\koz.\]
For example, if $u=abaab$, then

\smallskip
$F_1(u)=\{a,b\}, \; F_2(u)=\{ ab, ba, aa\}, \; F_3(u)=\{aba, baa, aab \},$

$F_4(u)=\{abaa, baab\}, \; F_5(u)=\{abaab\}. $

\smallskip
\noindent The words $u=a_1a_2\ldots a_m$ and $v=b_1b_2\ldots b_n$ are equal, if

\smallskip
\quad {\small $\bullet$} $m=n$ and

\quad {\small $\bullet$} $a_i=b_i$, for $i=1,2,\ldots, n\koz.$

\index{Wilf--Fine theorem}
\begin{tetel}[Fine--Wilf] If  $u$ and $v$ are words of length $n$, respective $m$, 
and if there are the natural numbers  $p$ and $q$, such that  $u^p$ and $v^q$ have a common prefix of 
length $n+m-(n,m)$, then  $u$ and $v$ are powers of the same word. 
\end{tetel}
The value  $n+m-(n,m)$ in the theorem is tight. This can be illustrated by the following example.
Here the words $u$ and $v$ have a common prefix of length $n+m-(n,m)-1$, but $u$ and $v$ 
are not powers of the same word.
\begin{tabbing}
$u=abaab$, \quad \=  $\; m=|u|=5$, \quad \= $\;u^2=abaababaab$\koz,\\
$v=aba$,   \>  $\; n=|v|=3$, \> $\;v^3=abaabaaba\koz.$
\end{tabbing}
By the theorem a common prefix of length 7 would ensure that $u$ and $v$ are powers of the same word. 
We can see that $u^2$ and $v^3$ have a common prefix of length 6 ($abaaba$), but $u$ and 
$v$ are not powers of the same word, so the length of the common prefix given by the theorem is tight.  

\subsection{Infinite words}\inddef{word!infinite}
Beside the finite words we consider \ki{infinite} (more precisely infinite at right) words too: 
 \[ u=u_1u_2\ldots u_n\ldots , \quad \textrm{where } u_1, u_2, \ldots \in A\koz.\]
The set of infinite words over the alphabet $A$ is denoted by $A^\omega$. 
If we will study together finite and infinite words the following notation will be useful:
\[A^\infty=A^*\cup A^\omega\koz.\]
The notions as subwords, prefixes, suffixes can be defined similarly for infinite words too.
 
The word  $v\in A^+$ is a subword of  $u\in A^\omega$ if there are the words  $p\in A^*, \; 
q\in A^\omega$, such that  $u=pvq$. If  $p\neq\varepsilon$, then $p$ is a prefix of  $u$, whilst  
$q$ is a suffix of $u$.  Here $F_n(u)$ also represents the set of all subwords of length $n$ of $u$.


\smallskip
Examples of infinite words over a binary alphabet:

\smallskip
1) The \ki{power word} is defined as:  \index{word!power} \index{power word}
\[p = 010011000111\ldots 0^n 1^n \ldots = 
010^21^20^31^3\ldots 0^n1^n\ldots\koz.\]
It can be seen that 

\smallskip
$F_1(p)=\{0,1\}, \; F_2(p)=\{01, 10, 00, 11\},$

$F_3(p)= \{010, 100, 001, 011,  110, 000, 111\}, \ldots$

\smallskip
2) The \ki{Champernowne word}\index{Champernowne word}\index{word!Champernowne word}
\nevindex{Champernowne, David Gawen (1912--2000)} 
is obtained by writing in binary representation the natural numbers $0,1,2,3,\ldots$:
\[c=0\,1\,10 \,11\,100\,101\,110\,111\,1000\,1001\,1010\,1011\,1100\,1101\,1110\,1111\,10000\ldots \koz.\]
It can be seen that 

\smallskip
$F_1(p)=\{0,1\}, \; F_2(p)=\{00, 01, 10, 11\},$

$F_3(p)= \{000, 001, 010, 011, 100,  101, 110, 111\}, \ldots$


\smallskip
3) The finite \ki{Fibonacci words}\nevindex{Fibonacci, Leonardo Pisano (1170--1250)} can be defined recursively 
as:\index{Fibonacci!word} \index{word!Fibonacci}

\smallskip
\quad $f_0=0,\; f_1=01$

\quad $f_n=f_{n-1}f_{n-2}$, if $n\ge 2$.

\smallskip
From this definition we obtain:

\quad $f_0=0$,

\quad $f_1=01$,

\quad $f_2=010$,

\quad $f_3=01001$,

\quad $f_4=01001010$,

\quad $f_5=0100101001001$,

\quad $f_6=010010100100101001010.$

%%\quad $f_7=0100101001001010010100100101001001$

\smallskip
\noindent The infinite Fibonacci word\index{word!Fibonacci}\index{Fibonacci!word} can be 
defined as the limit of the sequence of finite Fibonacci words:
\[ f=\lim_{n\rightarrow \infty}f_n\koz.\]
The subwords of this word are: 

\smallskip
$F_1(f)=\{0,1\}, \; F_2(f)=\{01,10,00\}, \; F_3(f)=\{010, 100, 001, 101\},$

$F_4(f)=\{0100, 1001, 0010, 0101, 1010 \}, \ldots\koz.$

\smallskip The name of Fibonacci words stems from the Fibonacci numbers, because the length 
of finite Fibonacci words is related to the Fibonacci numbers:  $|f_n|=F_{n+2}$, i.e. the length of 
the  $n$th finite Fibonacci word $f_n$ is equal to the  $(n+2)$th  Fibonacci number.

The infinite Fibonacci word has a lot of interesting properties. For example, from the definition, 
we can see that it cannot contain the subword 11.
  
The number of 1's in a word $u$ will be denoted by $h(u)$.  An infinite word  $u$ is  
\ki{balanced,} \index{word!balanced}\index{balanced word} if for arbitrary subwords  
$x$ and $y$ of the same length, we have $|h(x)-h(y)|\le 1$, i.e. \[x, y\in F_n(u) 
\;\Rightarrow \; |h(x)-h(y)|\le 1\koz.\] 

\begin{tetel}
The infinite Fibonacci word  $f$ is balanced.
\end{tetel}

\begin{tetel}\label{KZprop3}
$F_n(f)$ has  $n+1$ elements.
\end{tetel}

If word  $u$ is concatenated by itself infinitely, then the result is denoted by $u^\omega$.

The infinite word $u$ is \index{periodic word}\index{word!periodic} \ki{periodic,} if there 
is a finite word  $v$, such that $u=v^\omega$. This is a generalization of the finite case periodicity. 
The infinite word  $u$  is   \ki{ultimately periodic,} if there are the words  $v$ and $w$, such that  
$u=vw^\omega$.\index{word!ultimately periodic}\index{ultimately periodic word}\index{periodic word!ultimately}

The infinite Fibonacci word can be generated by a (homo)morphism too.
Let us define this morphism: 
\[\chi:A^*\rightarrow A^*, \quad \chi(uv)=\chi(u)\chi(v), \quad \forall u,v \in A^*\koz.\]
Based on this definition, the function  $\chi$ can be defined on letters only.  A morphism can be 
extended for infinite words too: 
\[\chi:A^\omega\rightarrow A^\omega, \quad \chi(uv)=\chi(u)\chi(v), \quad
 \forall u\in A^*, v\in A^\omega\koz.\]

The finite Fibonacci word  $f_n$ can be generated by the following morphism:
\[ \sigma(0)=01, \; \sigma(1)=0\koz.\] 
In this case we have the following theorem.  
\begin{tetel}
    $f_{n+1}=\sigma(f_n)\koz.$
\end{tetel}
\begin{biz}
The proof is by induction. Obviously  $f_1=\sigma(f_0)$.
Let us presume that  $f_{k}=\sigma(f_{k-1})$ for all  $k\le n$.
Because

\smallskip
$f_{n+1}=f_nf_{n-1},$

\smallskip
\noindent by the induction hypothesis  

\smallskip
$ f_{n+1}=\sigma (f_{n-1})\sigma (f_{n-2})=\sigma(f_{n-1}f_{n-2})=\sigma (f_n).$
\end{biz}

From this we obtain:
\begin{tetel}
  $f_n=\sigma^n(0)\koz.$
\end{tetel}
The infinite Fibonacci word  $f$ is the fixed point  of the morphism  $\sigma$.
\[f=\sigma(f)\koz.\]

\subsection{Word graphs}\index{word graph}
Let  $V\subseteq A^m$ be a set of  words of length $m$ over  $A$, and $E\subseteq AV\cap VA$. 
We define a digraph, whose vertices are from $V$, and whose arcs from $E$. There is an arc from the vertex 
 $\;a_1a_2\ldots a_m\;$ to the vertex  $\;b_1b_2\ldots b_m\;$ if 
\[
a_2=b_1, \;\; a_3=b_2,\; \ldots, \;\; a_m=b_{m-1} \textrm{ and }  a_1a_2\ldots a_mb_m\in E\koz,\]
that is the last $m-1$ letters in the first word are identical to the first $m-1$ letters in the second word. 
This arc is labelled by  $a_1a_2\ldots a_mb_m$ (or $a_1b_1\ldots b_m$).  

\subsubsection{De Bruijn graphs}
If $V=A^m$ and $E=A^{m+1}$, where $A=\{a_1,a_2, \ldots a_n\}$, then the graph is called  
\ki{De Bruijn graph,} denoted by $B(n,m)$. \index{graph!De Bruijn graph} \index{De Bruijn!De Bruijn graph} 

Figures  \ref{KZfig1} and \ref{KZfig2} illustrate De Bruijn graphs $B(2,3)$ and $B(3,2)$. 

\begin{figure}[!t]
\begin{center}
%\includegraphics[scale=1]{KZ-2-1.png}
\includegraphics[scale=0.075]{KZ-2-1.eps}
\end{center}
\caption{The De Bruijn graph\abraindex{De Bruijn graph} $B(2,3)$.\label{KZfig1}}
\end{figure}

\begin{figure}[!ht]
\noindent
\begin{center}
\includegraphics[scale=0.08]{KZ-2-2.eps}
\end{center}
\caption{The De Bruijn graph  $B(3,2)$.\label{KZfig2}}
\end{figure}

To a walk\footnote{In a graph a walk is a sequence of neighbouring edges (or arcs with the same orientation). 
If the edges or arcs of the walk are all different the walk is called trail, and when 
all vertices are different, the walk is a path.} $x_1x_2\ldots x_m,  \;\;x_2x_3\ldots x_mx_{m+1}, 
\;\ldots , \;z_1z_2\ldots z_m$  in the De Bruijn graph\index{De Bruijn graph} we attach the label  
$x_1x_2\ldots z_{m-1}z_m,$ which is obtained by maximum overlap of the vertices of the walk. 
In Figure \ref{KZfig1} in the graph $B(2,3)$ the label attached to the walk $001, 011, 111, 110$  (which 
is a path)  is $001110.$
The word attached to a Hamiltonian path\index{Hamiltonian path}\nevindex{Hamilton, William Rowan (1805--1865)} 
(which contains all vertices of the graph) in the graph  
$B(n,m)$  \label{KZCuvBruijn} is an $(n,m)$-type  \ki{De Bruijn word.}  For example, words $0001110100$ 
and $0001011100$  are  $(2,3)$-type De Bruijn word. An $(n,m)$-type 
De Bruijn word\index{De Bruijn word} contains all words of length $m$.
\index{word!De Bruijn word}\index{De Bruijn!De Bruijn word}

A connected digraph\footnote{A digraph (oriented graph) is connected if between every pair of vertices 
there is an oriented path at least in a direction.} is 
Eulerian\nevindex{Euler, Leonhard ((1707--1783))}\footnote{A digraph is 
Eulerian\labindex{Eulerian digraph} 
if it contains a closed oriented trail with all arcs of the graph.} if the in-degree of each vertex 
is equal to its out-degree\footnote{In-degree (out-degree) of a vertex is the number of arcs which enter 
(leave) this vertex.}. 

\begin{tetel}
The De Bruijn graph\index{De Bruijn graph} $B(n,m)$ is Eulerian.\index{Eulerian digraph} 
\end{tetel}
\begin{biz}
a) The graph is connected because between all pair of vertices  $x_1x_2\ldots x_m$ and $z_1z_2\ldots z_m$ 
there is an oriented path. For vertex $x_1x_2\ldots x_m$ there are $n$ leaving arcs, which enter 
vertices whose first  $m-1$ letters  are $x_2x_3\ldots x_m$, and the last letters in this words are 
all different. Therefore, there is the path  $x_1x_2\ldots x_m, \;\; x_2x_3\ldots x_mz_1$, \; \ldots, 
\;\; $x_mz_1\ldots z_{m-1}, \;\; z_1z_2\ldots z_m$. 

b) There are incoming arcs to vertex $x_1x_2\ldots x_m$ from vertices $yx_1\ldots x_{m-1}$, where $y\in A$ 
($A$ is the alphabet of the graph, i.e.   $V=A^m$). The arcs leaving vertex $x_1x_2\ldots x_m$ enter vertices 
 $x_2x_3\ldots x_my$, where  $y\in A$. Therefore, the graph is Eulerian,\index{Eulerian digraph} because the 
 in-degree and out-degree of each vertex are equal.
\end{biz}

\noindent From this the following theorem is simply obtained.

\begin{tetel}
 An oriented Eulerian trail\index{oriented Eulerian trail} of the graph  $B(n,m)$ (which contains 
 all arcs of graph) is a Hamiltonian path\index{Hamiltonian path} in the graph  $B(n,m+1),$ preserving the order. 
\end{tetel}

For example, in  $B(2,2)$ the sequence  000, 001, 010, 101, 011, 111, 110, 100 of arcs is an 
Eulerian trail.\index{Eulerian trail} At the same time these words are vertices of a Hamiltonian path\inddef{Hamiltonian path} 
in  $B(2,3).$ 

\subsubsection{Algorithm to generate De Bruijn\index{De Bruijn word} words}
Generating De Bruijn words is a common task with respectable number of algorithms. 
 We present here the well-known Martin algorithm. \index{Martin algorithm}\nevindex{Martin, M. H.}  
 Let $A=\{a_1, a_2, \ldots, a_n\}$ be an alphabet. Our goal is to generate an $(n,m)$-type  De Bruijn 
 word over the alphabet $A$.

We begin the algorithm with the word $a_1^m,$  
and add at its right end the letter $a_k$ with the greatest possible subscript, such that the  suffix of length 
$m$ of the obtained word does not duplicate a previously occurring subword of length $m.$ Repeat this until such a 
 prolongation  is impossible.
 
When we cannot continue, a De Bruijn word\index{De Bruijn word} is obtained, with the length  $n^m+m-1$.
In the following detailed algorithm,  $A$ is the  $n$-letters alphabet, and $B=(b_1,b_2, \ldots )$ 
represents the result, an  $(n,m)$-type De Bruijn word.

\begin{algN}{Martin($A,n,m$)}\inddef{\textsc{Martin}} \label{KZmartin}
1 \' \key{for} \= $i\leftarrow 1$ \key{to} $m$ \\
2 \'            \> \key{do} $b_i\leftarrow a_1$\\
3 \'  $i \leftarrow  m$\\
4 \' \key{repeat}\\
5 \'  \> \emph{done} $\leftarrow$  \textsc{true} \\
6 \'  \> $k\leftarrow n$ \\
7 \'  \> \key{while} \= $k>1$ \\
8 \'  \>            \> \key{do} \= \key{if} \= $b_{i-m+2}b_{i-m+3}\ldots b_{i}a_k \not\subset b_1b_2\ldots b_i$  
           \` $\rhd$ Not a subword.\\
9 \'  \>                \>        \>         \> \key{then} \= $i\leftarrow i+1$\\
10 \'  \>               \>        \>         \>             \> $b_i\leftarrow a_k$\\
11 \'  \>                \>       \>         \>             \>  \emph{done} $\leftarrow$  \textsc{false}\\
12 \'  \>                \>      \>          \>             \>  \key{exit while}\\                    
13 \'  \>               \>        \>         \>  \key{else} \> $k\leftarrow k-1$\\
14 \' \key{until} \emph{done}\\
15 \' \key{return} $B$   \` $\rhd$   $B=(b_1^ , b_2, \ldots, b_{n^m + m + 1}).$
\end{algN}

Because this algorithm generates all letters of a De Bruijn word\index{De Bruijn word} 
of length  $(n^m+m-1),$ and $n$ and $m$ are independent, its time complexity is $\Omega(n^m)$. 
The more precise characterization of the running time depends on the implementation of line 8. 
The \key{repeat} statement is executed $n^m-1$ times. The \key{while} statement is executed at most $n$ 
times for each step of the \key{repeat.} The test
$b_{i-m+2}b_{i-m+3}\ldots b_{i}a_k \not\subset b_1b_2\ldots b_i$ can be made in the worst case in 
$mn^m$  steps. So,  the total number of steps is not greater than $mn^{2m+1}$, resulting a worst case bound 
$\Theta(n^m+1).$ If we use Knuth-Morris-Pratt string mathching algorithm, then the worst case running time 
is $\Theta(n^{2m}).$ 

In chapter \ref{chapterPerfect} a more efficient implementation of the idea of Martin is presented. 

Based on this algorithm the following theorem can be stated.

\begin{tetel}
    An $(n,m)$-type De Bruijn\nevindex{De Bruijn, Nicolaas Govert} word is the shortest possible 
among all words containing all words of length $m$ over an  alphabet with  $n$ letters.
\end{tetel}

To generate all ($n,m$)-type De Bruijn words\index{De Bruijn word} the following recursive algorithm is given. 
Here $A$ is also an   alphabet with $n$ letters, and $B$ represents an $(n,m)$-type 
De Bruijn word. 
The algorithm is called for each position $i$ with $m+1\le i\le n^m+m-1$. 

\begin{alg}{All-De-Bruijn($B,i,m$)}\inddef{Alldebruijn@\textsc{All-De-Bruijn}} \label{KZbruijn}
1 \' \key{for} \= $j\leftarrow 1$ \key{to} $n$ \\
2 \'          \> \key{do} \= $b_i \leftarrow  a_j$\\
3 \'          \>               \>  \key{if} \=  $b_{i-m+1}b_{i-m+2} \ldots b_{i} \not\subset b_1b_2\ldots b_{i-1}$  
\` $\rhd$ Not a subword.\\
4 \'          \>               \>            \> \key{then} \= \textsc{All-De-Bruijn}($b,i+1,m$)\\
5 \'          \>               \>            \> \key{else}  \key{if} \= $length(B)=n^m+m-1$\\ 
6 \'          \>               \>            \>                                \> \key{then} \= print $B$ \` $\rhd$ A De Bruijn word.\\
7 \'         \>               \>            \>                                \>            \>   \key{exit for}\\
\end{alg}

The call of the procedure: 

\begin{tabbing}
\key{for} \= $i= 1$ \key{to} $ m$\\
             \> \key{do} $b_i \leftarrow a_1$\\ 
\textsc{All-De-Bruijn} $(B,m+1,m)$.
\end{tabbing}

This algorithm naturally is exponential.

In following, related to the De Bruijn graphs, the so-called De Bruijn trees\index{De Bruijn tree} 
will play an important role.

A \ki{De Bruijn tree}\inddef{De Bruijn tree} $T(n,w)$ with the root $w\in A^m$ is a $n$-ary tree defined 
recursively as follows:

\medskip
\noindent \emph{i.} The  word $w$ of length $m$ over the alphabet $A=\{a_1,a_2,\ldots, a_n\}$ 
is the root of $T(n,w)$.

\noindent \emph{ii.} If $x_1x_2\ldots x_m$ is a leaf in the tree $T(n,w)$, then 
each word $v$ of the form  
$x_2x_3\ldots x_ma_1$, $x_2x_3\ldots x_ma_2$, \ldots , $x_2x_3\ldots x_ma_n$ 
will be a descendent of $x_1x_2\ldots x_m$, if in the path from root to 
$x_1x_2\ldots x_m$ the vertex $v$ does not appears. 
 
\noindent \emph{iii.} The rule \emph{ii} is applied as many as it can.
\inddef{De Bruijn!De Bruijn tree}\inddef{tree!De Bruijn tree} 

In Figure \ref{KZfig3} the De Bruijn tree $T(2,010)$ is given.


\begin{figure}[!t]
\noindent
\begin{center}
\includegraphics[scale=0.065]{KZ-2-3.eps}
\end{center}
%\vspace*{-6pt}
\caption{The De Bruijn tree\abraindex{De Bruijn tree} $T(2,010)$.\label{KZfig3}}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsubsection{Rauzy graphs}\index{Rauzy graph}\index{graph!Rauzy}
\noindent  If  the word $u$ is infinite,  and $V=F_n(u)$, $E=F_{n+1}(u)$, then the corresponding word graph 
is called  \ki{Rauzy graph}\nevindex{Rauzy, Gerard} (or \ki{subword graph}). 
\index{Rauzy graph}\index{graph!Rauzy}\index{subword!graph}\index{graph!subword}
Figure \ref{KZfig4} illustrates the Rauzy graphs of the infinite Fibonacci word for $n=3$ and  $n=4$.  
As we have seen, the infinite  Fibonacci word is
\[ f=0100101001001010010100100101001001\ldots \koz,
\] 
and $ \;\;  F_1(f)=\{0, 1\}, \quad F_2(f)=\{01, 10, 00\},$
\\
$ F_3(f)=\{010, 100, 001, 101\}, \quad F_4(f)=\{0100, 1001, 0010, 0101, 1010\},$
\\
$ F_5(f)=\{01001, 10010, 00101, 01010, 10100, 00100\}.$

\begin{figure}[!t]
\noindent
\begin{center}
\includegraphics[scale=0.065]{KZ-2-4.eps}
\end{center}
\caption{Rauzy graphs for the infinite Fibonacci word.
\label{KZfig4}\index{word!Fibonacci} \index{Fibonacci}\index{Fibonacci word}}
\end{figure} 

In the case of the power word 
$\displaystyle p=01001100011100001111 \ldots 0^n 1^n \ldots,
$ 
where
$F_1(p)=\{ 0,1\}, \quad F_2(p)=\{ 01,10, 00, 11\},$
\\
$F_3(p)=\{ 010,100, 000, 001, 011, 111, 110\}, $
\\
$F_4(p)= \{ 0100, 1001, 0011, 0110, 1100, 1000,   0000,0001, 0111, 1110, 1111 \},$

\noindent the corresponding Rauzy graphs are given in Figure \ref{KZfig5}.

\begin{figure}[!t]
\noindent
\begin{center}
\includegraphics[scale=0.065]{KZ-2-5.eps}
\end{center}
%\vspace*{-12pt}
\caption{Rauzy graphs for the power word.\label{KZfig5}}
\end{figure} \index{word!power} \index{power word}

As we can see in Fig,  \ref{KZfig4} and  \ref{KZfig5} there are  subwords of length $n$ 
which can be continued only in  a single way (by adding a letter), and there are subwords 
which can be continued in two different ways (by adding two different letters). These latter subwords 
are called \ki{special subwords.} \index{subword!special}
A subword  $v\in F_n(u)$ is a \ki{right special subword,} if there are at least two different 
letters $a\in A$, such that $va\in F_{n+1}(u)$. Similarly,  $v\in F_n(u)$ is  \ki{left special subword,} 
if there are at least two different  letters $a\in A$, such that $av\in F_{n+1}(u)$. 
A subword is \ki{bispecial,}\index{subword!bispecial} if
at the same time is right and left special. 
For example, the special subwords  in Figures \ref{KZfig4} and  \ref{KZfig5}) are:
  
\noindent
\begin{tabbing}
\noindent  left special subwords: \qquad \=  010,  0100 ({Figure \ref{KZfig4}}),\\
                                   \> 110, 000, 111, 1110, 0001,  1111, 0011 ({Figure \ref{KZfig5}}),  \\
\noindent right special subwords:: \> 010, 0010 ( {Figure \ref{KZfig4}}),\\
                                   \>  011, 000, 111, 0111,  1111, 0011 ({Figure \ref{KZfig5}})\\
\noindent bispecial subwords:      \>  010  ({Figure \ref{KZfig4}}),\\
                                    \> 000, 111, 1111, 0011 ({Figure \ref{KZfig5}}).
\end{tabbing}

\subsection{Complexity of words}
\noindent  The complexity of words measures the diversity of the subwords of a word. 
In this regard the word $aaaaa$ has smaller complexity then the word $abcab$.

We define the following complexities for a word.


\medskip
1) The \ki{subword complexity} or simply  the \ki{complexity} of a  word assigns 
to each $n\in \mathbf{N}$ the number of different subwords of length $n$. For a word $u$ the number 
of different  subwords of length $n$  is denoted by  $f_u(n)$.
\[f_u(n)=\#F_n(u), \quad u\in A^{\infty} \koz.\] \index{complexity}
\index{complexity!word}\index{complexity!subword}\index{subword!complexity}
If the word is finite, then $f_u(n)=0$, if $n>|u|$.

\medskip
2) The \ki{maximal complexity} \index{complexity!maximal} is considered only for finite words. 
\[ C(u)= \max\{f_u(n)\;|\;n\ge 1,  u\in A^*\} \koz.\] 
If $u$ is an infinite word, then  $C^-_u(n)$ is the \ki{lower maximal complexity,} respectively  
$C^+_u(n)$ the  \ki{upper maximal complexity.}  \index{complexity!lower maximal} \index{complexity!upper maximal}
\index{lower maximal complexity} \index{upper maximal complexity}

\[ C^-_u(n)= \min_i C(u_iu_{i+1}\ldots u_{i+n-1}), \quad  C^+_u(n)= \max_i C(u_iu_{i+1}\ldots u_{i+n-1})\koz.\]

\medskip
3) The \ki{global maximal complexity}\index{complexity!global maximal}\inddef{global maximal complexity} 
is defined on the set  $A^n$:
\[ G(n)= \max\{C(u)\;|\; u\in A^n\}\koz.\]


\medskip
4) The  \ki{total complexity}  \index{complexity!total}\index{complexity!lower total} for a finite word 
is the number of all different nonempty subwords\footnote{Sometimes the empty subword is considered too. 
In this case the value of total complexity\labindex{total complexity} is increased by 1.} 
\[ K(u)=\sum_{i=1}^{|u|}{f_u(i)}, \quad u\in A^* \koz.\]
For an infinite word $K^-_u(n)$  is the \ki{lower total complexity,} and  $K^+_u(n)$ 
is the \ki{upper total complexity:}
\[K^-_u(n)= \min_i K(u_iu_{i+1}\ldots u_{i+n-1}), \quad   K^+_u(n)= \max_i K(u_iu_{i+1}\ldots u_{i+n-1}) \koz. \]

5) A decomposition $u=u_1u_2\ldots u_k$ is called a 
\ki{factorization}\inddef{factorization}\index{word!factorization} of $u$. If each $u_i$ (with the possible 
exception of $u_k$) is the shortest prefix of $u_iu_{i+1}\ldots u_k$ which does not occur before in $u,$ 
then this factorization is called the Lempel-Ziv factorization. The number of subwords $u_i$ in 
such a factorization is the \ki{Lempel-Ziv factorization complexity}\nevindex{Lempel, Abraham}\nevindex{Ziv, Jacob} 
of $u.$ For example for the word 
$u=ababaaabb$ the Lempel-Ziv factorization is: $u=a.b.abaa.abb$. So, the Lempel-Ziv factorization 
complexity of $u$ is $\textsc{lz}(u)=4.$ 

6) If in a factorization $u=u_1u_2\ldots u_k$ each $u_i$ is the longest possible palindrome, 
then the factorization is called a palindromic factorization, and the number of subwords $u_i$ 
in this is the \ki{palindromic factorization complexity.}  For $u=aababbabbabb=aa.babbabbab.b$, 
so the palindromic factorization complexity of $u$ is $\textsc{pal}(u)=3.$

7) The \ki{window complexity} $P_w$ \inddef{window complexity}\index{complexity!window} 
is defined for infinite words only. For $u=u_0u_1u_2\ldots u_n\ldots$ the window complexity is
\[P_w(u,n)= \#\big\{ u_{kn}u_{kn+1}\ldots u_{(k+1)n-1} \,\big| \, k\ge 0 \big\}\koz.\]

\subsubsection{Subword complexity}\index{complexity!subword}

As we have seen 
\[ f_u(n)= \#F_n(u), \quad \forall u\in A^\infty, \; n\in \mathbf{N}\koz.\]
 $f_u(n)=0$, if $n>|u|$.

For example, in the case of $u=abacab$:
\[ f_u(1)=3, \; f_u(2)=4,\; f_u(3)=4, \; f_u(4)=3, f_u(5)=2,\;f_u(6)=1\koz.\]
In Theorem \ref{KZprop3} was stated that for the  infinite 
Fibonacci word\index{word!Fibonacci}\index{Fibonacci!word}:
\[f_f(n)=n+1\koz.\]
In the case of the power word $p=010011\ldots 0^k1^k\ldots$  \index{word!power}\index{power word}
the complexity is:
\[f_p(n)=\frac{n(n+1)}{2}+1\koz.\]
This can be proved if we determine the difference  $f_p(n+1)-f_p(n)$, which is equal to the number of   
words of length $n$ which can be continued in two different ways to obtain words of length $n+1$.
In two different ways can be extended only 
the words of the form $0^k1^{n-k}$ (it can be followed by 1 always, and by 0 when $k\le n-k$)  and   
$1^k0^{n-k}$  (it can be followed by 0 always, and by 1 when $k<n-k$).
Considering separately the cases when $n$ is odd and even, we can see that:
\[ f_p(n+1)-f_p(n)=n+1\koz,\]
and from this we get 
\begin{eqnarray*}
f_p(n) &=& n+f_p(n-1)= n+(n-1)+ f_p(n-2)=\ldots \\ 
       &=& n+(n-1)+\ldots +2+f_p(1)=\frac{n(n+1)}{2}+1\koz.
\end{eqnarray*} 
In the case of the \ki{Champernowne word} 
\begin{eqnarray*}
c=u_0u_1\ldots u_n\ldots &=& 0\,1\,10\,11\,100\,101\,110\,111\,1000\ldots \\
   &=&  0110111001011101111000\ldots, 
\end{eqnarray*} the complexity is  $f_{c}(n)=2^n$.

\begin{tetel}\label{KZteo14}
If for the infinite word   $u\in A^\omega$ there exists an $n\in\mathbf{N}$ such that  $f_u(n)\le n,$ 
then  $u$ is ultimately periodic. 
\end{tetel}
\begin{biz}
$f_u(1)\ge 2$, otherwise the word is trivial  (contains just equal letters). 
Therefore there is a  $k\le n$, such that  $f_u(k)=f_u(k+1)$. But   
\[ f_u(k+1)-f_u(k) = \sum_{v\in F_k(u)}{\Big(\#\big\{a\in A\;|\; va\in F_{k+1}(u) \big\}-1 \Big)}\koz.
\]
It follows that  each subword  $v\in F_k(u)$  has only one extension to obtain $va\in F_{k+1}(u)$.
So, if  $v=u_iu_{i+1}\ldots u_{i+k-1}=u_ju_{j+1}\ldots u_{j+k-1}$, then $u_{i+k}=u_{j+k}$. Because  $F_k(u)$ 
is a finite set, and $u$ is infinite, there are $i$ and  $j$  ($i<j$), for which  
$u_iu_{i+1}\ldots u_{i+k-1}=u_ju_{j+1}\ldots u_{j+k-1}$, but in this case $u_{i+k}=u_{j+k}$ is true too. 
Then from $u_{i+1}u_{i+2}\ldots u_{i+k}=u_{j+1}u_{j+2}\ldots u_{j+k}$ we obtain the following equality results: 
$u_{i+k+1}=u_{j+k+1}$, therefore $u_{i+l}=u_{j+l}$ is true for all $l\ge 0$ values. Therefore $u$ 
is ultimately periodic. 
\end{biz}

A word  $u\in A^\omega$ is \ki{Sturmian,}\inddef{Strurmian word} if  $f_u(n)=n+1$ 
for all $n\ge 1$.\nevindex{Sturm, Jacques Charles Fran\c sois (1803--1855)}

Sturmian words are the least complexity \index{word!Sturmian}\index{Sturmian word} 
infinite and  non periodic 
words. The infinite Fibonacci word\index{Fibonacci word} is  Sturmian.
Because $f_u(1)=2$, the Sturmian words are two-letters words. 

From the Theorem \ref{KZteo14} it follows that each infinite and not ultimately periodic 
word has complexity at least   $n+1$, i.e. 
\[u\in A^\omega, u \textrm{ not ultimately periodic } \Rightarrow  \; f_u(n)\ge n+1\koz.\]
The equality holds for Sturmian words.  

Infinite words can be characterized  using the lower and upper total complexity too.
\begin{tetel}\label{T26.12} 
If an infinite word $u$ is not ultimately periodic and   $n\ge 1$, then  
 \[C^+_u(n)\ge \left[ \frac{n}{2}\right]+1, \quad  K^+_u(n)\ge \left[ \frac{n^2}{4}+n \right]\koz.\]
For the Sturmian words equality holds.
\end{tetel}

\medskip
Let us denote by $\{x\}$  the fractional part of $x$, and by $\lfloor x\rfloor$ its integer part. 
Obviously   $x=\lfloor x\rfloor +\{x\}$. The composition of a function $R$ by itself  
$n$ times will be denoted by $R^n$. So  $R^n =R\circ R\circ \ldots \circ R$ ($n$ times). 
Sturmian words can be characterized in the following way too:
\begin{tetel}
A word $u=u_1u_2\ldots $ is Sturmian if and only if there exists an irrational number $\alpha$  
and a real number $z$, such that for  $R(x)=\{x+\alpha\}$ 
\[u_n=\left\{ \begin{array}{ll}
                0, \textrm{ if } R^n(z)\in (0,1-\alpha )\koz,\\
                1, \textrm{ if } R^n(z)\in [1-\alpha,1)\koz,\\
              \end{array}    \right.\] or
\[u_n=\left\{ \begin{array}{ll}
                1, \textrm{ if } R^n(z)\in (0,1-\alpha )\koz,\\
                0, \textrm{ if } R^n(z)\in [1-\alpha,1)\koz.\\
              \end{array}    \right.\]
\end{tetel}
In the case of the infinite Fibonacci number, these numbers are:  $\alpha = z = (\sqrt{5} + 1)/2.$ 

Sturmian words\index{Sturmian word} can be generated by the orbit of a billiard ball inside a square too.
A billiard ball is launched under an irrational angle from a boundary point of the square. 
If we consider an endless  move of the ball with reflection on boundaries and without friction, 
an infinite trajectory will result. 
We put an 0 in the word if the ball reaches a horizontal boundary, and 1 when it reaches a vertical one. 
In such a way we generate an infinite word. This can be generalized using an $(s+1)$-letter alphabet 
and an  $(s+1)$-dimensional hypercube.
In this case the complexity is 
\[f_u(n,s+1)= \sum_{i=0}^{\min (n,s)}{\frac{n!s!}{(n-i)!i!(s-i)!}}\koz.\]
If $s=1$, then  $f_u(n,2)=f_u(n)=n+1$, and if $s=2$, then $f_u(n,3)=n^2+n+1.$ 

\subsubsection{Maximal complexity}\index{complexity!maximal complexity}
For a finite word  $u$   
\[ C(u)= \max\{f_u(n)\;|\;n\ge 1\}\]
is the maximal complexity.  In Figure \ref{KZ-table1} the values of the complexity function 
for several words are given for all possible length. From this, we can see for example that  
$C(00100011)=5,$ $C(00100100) = 3$ etc.  

\begin{figure}[t]
\noindent\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}\hline
 $u$ & $f_u(1)$ & $f_u(2)$ &$f_u(3)$ &$f_u(4)$ &$f_u(5)$ &$f_u(6)$ &$f_u(7)$ &$f_u(8)$  \\
 \hline
00100011 &    2 & 4 & 5 & 5 & 4 & 3 & 2 & 1 \\ \hline
00100100 &    2 & 3 & 3 & 3 & 3 & 3 & 2 & 1 \\ \hline
00100101 &    2 & 3 & 4 & 4 & 4 & 3 & 2 & 1 \\ \hline
00100110 &    2 & 4 & 5 & 5 & 4 & 3 & 2 & 1 \\ \hline
00100111 &    2 & 4 & 5 & 5 & 4 & 3 & 2 & 1 \\ \hline
00101000 &    2 & 3 & 5 & 5 & 4 & 3 & 2 & 1 \\ \hline
00101001 &    2 & 3 & 4 & 5 & 4 & 3 & 2 & 1 \\ \hline
00101011 &    2 & 4 & 4 & 4 & 4 & 3 & 2 & 1 \\  \hline
01010101 &    2 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ \hline
11111111 &    1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\  
\hline
\end{tabular} 
\end{center}
\caption{Complexity of several binary words.\label{KZ-table1}}
\end{figure}


\medskip
For the complexity of finite words the following interesting result is true.
\begin{tetel}
 If  $w$ is a finite word, $f_w(n)$ is its complexity, then there are the natural numbers  $m_1$ and  $m_2$ with   
 $1\le m_1\le m_2 \le |w|$ such that 
\begin{tabbing}
 $\bullet$ $f_w(n+1) > f_w(n)$, \qquad \= for  $\;\; 1\le n < m_1$,\\
 $\bullet$ $f_w(n+1) = f_w(n)$,       \> for   $\;\; m_1 \le n < m_2$,\\
 $\bullet$ $f_w(n+1) = f_w(n)-1$,     \> for   $\;\; m_2\le n \le |w|$.
\end{tabbing} 
  \end{tetel}
From the Figure \ref{KZ-table1}, for example, if 
 
 $w=00100011$, then $m_1=3$, $m_2=4$,

 $w=00101001$, then $m_1=4$, $m_2=4$,

 $w=00101011$, then $m_1=2$, $m_2=5$.

\subsubsection{Global  maximal complexity}\index{complexity!global maximal}

\noindent The global maximal complexity is 
\[ G(n)= \max\{C(u)\;|\; u\in A^n\}\koz,\]
that is the greatest (maximal) complexity in the set of all  words of length $n$ on a given alphabet.
The following problems arise:

$\bullet$ what is length of the subwords for which the global maximal complexity is equal to the maximal complexity?  

$\bullet$  how many such words exist?

\begin{pelda}  
For the alphabet  $A=\{0,1\}$ the Figure \ref{KZ-table2} and  \ref{KZ-table3}  contain the complexity 
of all 3-length and 4-length words.
\begin{figure}[!t]
\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
      & \multicolumn{3}{c|}{$f_u(i)$} \\ 
$u$   & $i=1$& $i=2$ & $i=3$ \\ \hline
$000$ & 1    &   1   & 1 \\ \hline
$001$ & 2    &   2   & 1 \\ \hline
$010$ & 2    &   2   & 1 \\ \hline
$011$ & 2    &   2   & 1 \\ \hline
$100$ & 2    &   2   & 1 \\ \hline
$101$ & 2    &   2   & 1 \\ \hline
$110$ & 2    &   2   & 1 \\ \hline
$111$ & 1    &   1   & 1 \\ \hline
\end{tabular}
\end{center}
\caption{Complexity of all 3-length binary words}\label{KZ-table2}
\end{figure}

In this case of the 3-length words  (Figure \ref{KZ-table2}) the global maximal complexity 
is 2, and this value is obtained for 1-length  and 2-length subwords. There are 6 such words.

For 4-length words  (Figure \ref{KZ-table3}) the global maximal complexity is  3, and this value 
is obtained for 2-length words. The number of such words is 8. 
\begin{figure}[!th]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}\hline
      & \multicolumn{4}{c|}{$f_u(i)$} \\ 
$u$   & $i=1$& $i=2$ & $i=3$ & $i=4$ \\ \hline
$0000$ & 1    &   1   & 1 & 1 \\ \hline
$0001$ & 2    &   2   & 2 & 1\\ \hline
$0010$ & 2    &   3   & 2 & 1 \\ \hline
$0011$ & 2    &   3   & 2 & 1\\ \hline
$0100$ & 2    &   3   & 2 & 1\\ \hline
$0101$ & 2    &   2   & 2 & 1\\ \hline
$0110$ & 2    &   3   & 2 & 1\\ \hline
$0111$ & 2    &   2   & 2 & 1\\ \hline
$1000$ & 2    &   2   & 2 & 1 \\ \hline
$1001$ & 2    &   3   & 2 & 1\\ \hline
$1010$ & 2    &   2   & 2 & 1 \\ \hline
$1011$ & 2    &   3   & 2 & 1\\ \hline
$1100$ & 2    &   3   & 2 & 1\\ \hline
$1101$ & 2    &   3   & 2 & 1\\ \hline
$1110$ & 2    &   2   & 2 & 1\\ \hline
$1111$ & 1    &   1   & 1 & 1\\ \hline
\end{tabular}
\end{center}
\caption{Complexity of all  4-length binary words.\label{KZ-table3}}
\end{figure}
\end{pelda}

To solve the above two problems, the following notations will be used:
\[R(n)=\{ i\in \{1,2,\ldots, n \} \;|\; \exists u\in A^n: f_u(i)=G(n)\}\koz, \]
\[ M(n)= \#\{u\in A^n : C(u)=G(n) \}\koz. \]

\medskip In the table of Figure \ref{KZfigGRM} values of $G(n),$ $R(n),$ $M(n)$ 
are given for length up to 20 over on a binary alphabet. 

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{|r|r|r|r|}\hline
$\quad n\quad$ & $\quad G(n)\quad$ & $\quad R(n)\quad$ & 
   $\quad M(n)\quad$ \\ \hline\hline
1  & 1  & 1    & 2 \\
2  & 2  & 1    & 2 \\ \hline
3  & 2  & 1, 2 & 6 \\
4  & 3  & 2    & 8 \\
5  & 4  & 2    & 4 \\ \hline
6  & 4  & 2, 3 & 36 \\
7  & 5  & 3    & 42 \\
8  & 6  & 3    & 48 \\
9  & 7  & 3    & 40 \\
10 & 8  & 3    & 16 \\ \hline
11 & 8  & 3, 4  & 558 \\
12 & 9   & 4     & 718 \\
13 & 10  & 4     & 854 \\ 
14 & 11  & 4     &  920\\
15 & 12  & 4     &  956\\
16 & 13  & 4     &  960\\
17 & 14  & 4     &  912\\
18 & 15  & 4     &  704\\
19 & 16  & 4     &  256\\ \hline
20 & 16  & 4, 5  &  79006\\
\hline\hline
\end{tabular}
\end{center}
\caption{Values of $G(n)$, $R(n)$, and $M(n)$.\label{KZfigGRM}}
\end{figure}

We shall use the following result to prove some theorems on maximal complexity.

\begin{lemma}\label{KZlem1}
For each $k\in \mathbf{N}^*$, the shortest word containing all the $q^k$ words of 
length $k$ over an alphabet with $q$ letters has $q^k+k-1$ letters (hence in this word each of the $q^k$ 
words of length $k$ appears only once).
\end{lemma}

\begin{tetel} \label{KZthm1} If  $ \#A=q$ and $q^k+k\le n\le q^{k+1}+k$, then   $G(n)=n-k\koz.$
\end{tetel}
\begin{biz}
Let us consider at first the case $n=q^{k+1}+k$, $k\ge 1$.
 
From Lemma \ref{KZlem1} we obtain the existence of
a word $w$ of length $q^{k+1}+k$ which contains all the $q^{k+1}$ words
of length $k+1$, hence $f_w(k+1)=q^{k+1}$. It is obvious that 
$f_w(l)=q^l<f_w(k+1)$ for $l\in \{1,2,\ldots, k\}$ and 
$f_w(k+1+j)=q^{k+1}-j< f_w(k+1)$ for $j\in \{1,2,\ldots q^{k+1}-1 \}$.
 Any other word of length $q^{k+1}+k$ will have the maximal complexity 
less than or equal to $C(w)=f_w(k+1)$, hence we have $G(n)=q^{k+1}=n-k$.

For $k\ge 1$ we consider now the values of $n$ of the form 
$n=q^{k+1}+k-r$ with $r\in \{1,2,\ldots, q^{k+1}-q^k\}$, hence 
$q^k+k\le n< q^{k+1}+k$. If from the word $w$ of length $q^{k+1}+k$
considered above we delete the last $r$ letters, we obtain a word $w_n$ 
of length $n=q^{k+1}+k-r$ with $r\in \{1,2,\ldots, q^{k+1}-q^k\}$. 
This word will have $f_{w_n}(k+1)=q^{k+1}-r$ and this value will be 
its maximal complexity. Indeed, it is obvious that $f_{w_n}(k+1+j)=
      f_{w_n}(k+1)-j < f_{w_n}(k+1)$ for $j\in \{1,2,\ldots, n-k-1\}$;
for $l\in \{1,2,\ldots , k\}$ it follows that
$f_{w_n}(l)\le q^l\le q^k\le q^{k+1}-r= f_{w_n}(k+1)$, hence 
$C(w_n)=f_{w_n}(k+1)=q^{k+1}-r$. Because it is not possible for a 
word of length $n=q^{k+1}+k-r$, with $r\in \{1,2,\ldots, q^{k+1}-q^k\}$
to have the maximal complexity greater than $q^{k+1}-r$, it follows that
$G(n)= q^{k+1}-r=n-k$.
\end{biz}

\begin{tetel} \label{KZthm2}
If $\#A=q$ and  $q^k+k < n < q^{k+1}+k+1$ then $R(n)= \{k+1\}$;
if $n=q^k+k$ then $R(n)= \{k,k+1\}$.
\end{tetel}
\begin{biz}
In the first part of the proof of Theorem \ref{KZthm1}, we proved for $n=q^{k+1}+k$, $k\ge 1,$ 
the existence of a word $w$ of length $n$ for which $G(n)=f_w(k+1)=n-k$. This means that $k+1\in R(n)$.
For the word $w$, as well as for any other word $w'$ of length $n$, we have 
$f_{w'} (l) < f_w(k+1)$, $l\not = k+1$, because of the special construction 
of $w$, which  contains all the words of length $k+1$ in the most compact way.
It follows that $R(n)=\{k+1\}$.

As in the second part of the proof of Theorem \ref{KZthm1}, we consider 
$n=q^{k+1}+k-r$ with $r\in \{1,2,\ldots q^{k+1}-q^k\}$ and the word $w_n$ for 
which $G(n)=f_{w_n}(k+1)=q^{k+1}-r$. We have again $k+1\in R(n)$. For 
$l>k+1$, it is obvious that the complexity function of $w_{n}$, or of any 
other word of length $n$, is strictly less than $f_{w_{n}}(k+1)$. We examine
now the possibility of finding a word $w$ with $f_w(k+1)=n-k$ for which
$f_w(l)=n-k$ for $l\le k$. We have $f_w(l)\le q^l\le q^k\le q^{k+1}-r$, hence 
the equality $f_w(l)=n-k=q^{k+1}-r$ holds only for $l=k$ and $r=q^{k+1}-q^k$, 
that is for $w=q^k+k$.
 
We show that for $n=q^k+k$ we have indeed $R(n)=\{k,k+1\}$. If we start with the word of length
$q^k+k-1$ generated by the Martin's algorithm\index{Martin algorithm} (or with another 
De Bruijn word)\index{De Bruijn word} and add to this any letter from 
$A$, we obtain obviously a word $v$ of length $n=q^k+k$, which 
contains all the $q^k$ words of length $k$ and $q^k=n-k$ words of length 
$k+1$, hence $f_v(k)=f_v(k+1)=G(n).$
\end{biz}

Having in mind the \textsc{Martin} algorithm  \index{Martin@\textsc{Martin}}  
(or other more efficient algorithms), words $w$ 
with maximal complexity $C(w)=G(n)$ can be easily constructed for each
$n$ and for both situations in Theorem \ref{KZthm2}.

\begin{tetel}\label{KZthm5} 
If $\#A=q$ and $q^k+k\le n \le q^{k+1}+k$ then $M(n)$ is equal to
the number of different paths of length $n-k-1$ in the de Bruijn graph\index{De Bruijn graph}
$B(q,k+1)$.
\end{tetel}
\begin{biz}
From Theorems \ref{KZthm1} and \ref{KZthm2} it follows that the number $M(n)$ of the words
of length $n$ with global maximal complexity is given by the number of words 
$w\in A^n$ with $f_w(k+1)=n-k$. It means that these words contain 
$n-k$ subwords of length $k+1$, all of them distinct. To enumerate all of
them we start successively with each word of $k+1$ letters (hence with each
vertex in $B(q,k+1$)) and we add at each step, in turn, one of the symbols
from $A$ which does not duplicate a word of length $k+1$ which has 
already appeared.  Of course, not all of the trials will finish in a word 
of length $n$, but those which do this,  are precisely paths in $B(q,k+1)$
starting with each vertex in turn and having the length $n-k-1$. Hence to 
each word of length $n$ with $f_w(k+1)=n-k$ we can associate a path and 
only one of length $n-k-1$ starting from the vertex given by the first
$k+1$ letters of the initial word; conversely, any path of length
$n-k-1$ will provide a word  $w$ of length $n$ which contains $n-k$ 
distinct subwords of length $k+1$.
\end{biz}

$M(n)$ can be expressed also as the number of vertices at level $n-k-1$ in the set 
$\Big\{ T(q,w)\, \big | \, w\in A^{k+1}  \Big\}$ of De Bruijn trees.

\begin{tetel}
 If $n=2^k+k-1$, then   $M(n)=2^{2^{k-1}}$.
\end{tetel}
\begin{biz}
In the De Bruijn graph  $B(2,k)$ there are  $2^{2^{k-1}-k}$ 
different Hamiltonian cycles.\index{Hamiltonian cycle} 
With each vertex of a Hamiltonian cycle a De Bruijn word\index{De Bruijn word} begins (containing all $k$-length 
subwords), which has maximal complexity, so  $M(n)=2^k\cdot 2^{2^{k-1}-k}=   2^{2^{k-1}}$, which proves the theorem.
\end{biz}

A generalization for an alphabet with   $q\ge 2$ letters:
\begin{tetel}
If $n=q^k+k-1$, then  $M(n)=(q!)^{q^{k-1}}$.
\end{tetel}

\subsubsection{Total complexity}\index{complexity!total}

\noindent The  \ki{total complexity} is the number of different nonempty subwords of a given word: 
\[ K(u)=\sum_{i=1}^{|u|}{f_u(i)}\koz.\]

\medskip
The total complexity of a  trivial word of length $n$ (of the form $a^n$, $n\ge 1$) is  equal to $n.$ 
The total complexity of a rainbow word (with pairwise different letters) of length $n$ is equal 
to \index{rainbow word}\index{word!rainbow} $\displaystyle\frac{n(n+1)}{2}$.  

\medskip
The problem of existence of words with a given total complexity are studied in the following theorems.

\begin{tetel} If $C$  is a natural number different from 1, 2 and
 4,  then there exists a nontrivial word of total complexity equal to $C.$
\end{tetel}

\begin{biz} To prove this theorem we give the total complexity of the  following
$k$-length words:
\begin{eqnarray*} 
{K}(a^{k-1}b) &=& 2k-1, \quad \textrm{for }  k \ge 1\koz, \\
{K}(ab^{k-3}aa)  &=& 4k-8,   \quad \textrm{for }  k \ge 4\koz,  \\ 
{K}(abcd^{k-3}) &=& 4k-6,  \quad \textrm{for } k \ge 3 \koz.
\end{eqnarray*}
These can be proved immediately from the definition of
the total complexity.

 1. If $C$ is odd then we can write $ C = 2k-1$ for a given $k.$
 It follows that $k =(C+1)/2$, and the word $a^{k-1}b$ has total complexity $C.$

2. If $C$ is even, then $C = 2\ell $.

\hspace*{0.5 cm} 2.1. If $\ell  = 2h$, then $4k-8 =C$ gives $4k-8 = 4h$,
 and from this $k=h+2$ results.
The word $ ab^{k-3}aa$  has total complexity $C.$

\hspace*{0.5 cm} 2.2. If $\ell  = 2h+1$ then $4k-6 = C$ gives
$4k-6 = 4h+2,$ and from this $k=h+2$ results.
The word $abcd^{k-3}$  has total complexity $C.\;$  
\end{biz}

\medskip
In the proof we have used more than two letters in a word only  in  the
case of the numbers of the form $4h+2$ (case 2.2 above).
The new question is, if
there exist always nontrivial words formed only of two letters with a  given total 
complexity. The answer is yes anew. We must prove this only for the numbers of
the form $4h+2.$ If $C = 4h+2$ and $C \ge  34,$ we use the followings:
\begin{eqnarray*}
{K}(ab^{k-7}abbabb) &=& 8k-46, \quad \textrm{for } k \;\ge 10\koz,\\
{K}(ab^{k-7}ababba) &=& 8k-42, \quad \textrm{for } k \;\ge 10\koz.
\end{eqnarray*}
If $h = 2s$, then $8k-46 = 4h+2$ gives $k = s+6,$ and the word
$ab^{k-7}abbabb$ has total complexity $4h+2.$

If $h = 2s+1,$ then $8k-42 = 4h+2$ gives $k = s+6,$ and the word
$ab^{k-7}ababba$  has total complexity $4h+2.$ For $C < 34$ only 14, 26 and 30 are
feasible. The  word $ab^4a$
has total complexity 14, $ab^6a$ has 26, and $ab^5aba$ 30. Easily
it can be proved, using a tree, that for 6, 10, 18
and  22 such words does not exist. Then the following theorem is true.

\begin{tetel}
If $C$ is a natural number different from 1, 2, 4, 6,
 10, 18 and 22, then there exists a nontrivial word formed only of two 
letters, with the given total complexity $C.$
\end{tetel}

The existence of a word with a given length and total complexity is not always assured, 
as we will prove in what follows. 

In relation with the second problem a new one arises: How many words of
length $n$ and complexity $C$ there exist? For small $n$ this problem can be
studied exhaustively. Let $A$ be of $n$ letters, and let us consider all
words of length $n$ over $A.$ By a computer program we have got Figure \ref{KZTable2},
which  contains the frequency of words with given length and total complexity.

\medskip
\qquad \begin{figure}[!t]
 $n=2$ 

\smallskip
 \begin{tabular}{|l|rr|}\hline
{\em C} & 2 & 3 \\           
$\phi_n(C)$  & 2 & 2 \\ \hline   
\end{tabular}

\smallskip

 $n=3$

\smallskip
 \begin{tabular}{|l|rrrr|}\hline
{\em C}  & 3 & 4 & 5 & 6  \\
$\phi_n(C)$ &3 & 0 & 18 & 6\\ \hline
\end{tabular}


\smallskip

 $n=4$

\smallskip
 \begin{tabular}{|l|rrrrrrr|}\hline
{\em C} & 4 & 5 & 6 & 7 &  8 & 9 & 10   \\
$\phi_n(C)$ & 4 & 0 & 0 & 36 &48 & 144 & 24   \\ \hline
\end{tabular}

\smallskip

 $n=5$

\smallskip
 \begin{tabular}{|l|rrrrrrrrrrr|} \hline
{\em C} & 5 & 6 & 7 &  8 & 9 & 10 & 11 & 12 & 13 & 14 & 15  \\
$\phi_n(C)$ & 5 & 0 & 0 &  0 & 60& 0  & 200& 400&1140&1200&120   \\ \hline
\end{tabular}

\smallskip
 $n=6$

\smallskip
 \begin{tabular}{|l|rrrrrrrrr|} \hline
{\em C}     & 6 & 7 &  8& 9 & 10 & 11 & 12 & 13 &   \\
$\phi_n(C)$    & 6 & 0 & 0 & 0 & 0  & 90 & 0  & 0  & \\  
  &  &  &  &  &  &  &   & & \\
{\em C}         & 14  & 15 &16 &17  &18   &19   &  20 &  21 &         \\
$\phi_n(C)$         & 300  &990 &270&5400&8280 &19800&10800& 720 &        \\ \hline
\end{tabular}
\caption{Frequency of words with given total complexity}\label{KZTable2}
\end{figure}

Let $|A|=n$ and let $\phi_n(C)$ denote the frequency of the 
words of length $n$ over $A$ having a complexity $C$. Then we have the following easy to prove results:

\medskip
 $\phi_n(C) = 0,$\qquad
            if $C<n$ or $ C>\displaystyle\frac{n(n+1)}{2}, $

 $\phi_n(n) = n,$

 $\phi_n(2n-1) = 3n(n-1),$ 

$\phi_n\left( \displaystyle\frac{n(n+1)}{2} -1\right) =
  \displaystyle\frac{n(n-1)n!}{2}, $\\

 $\phi_n\left( \displaystyle\frac{n(n+1)}{2} \right) =
  n! $


\medskip
As regards the distribution of the frequency $0$,  the following are true:

\smallskip
{If $C=n+1, n+2, \ldots , 2n-2,\;\;$ then $\; \phi_n(C)=0\koz.$}

{If $C=2n, 2n+1, \ldots , 3n-5,\;\;$ then $\; \phi_n(C)=0\koz.$}

\smallskip
The question is, if there exists a value from which up to $\frac{n(n+1)}{2}$ no more 0 frequency exist. 
The answer is positive. Let us denote by $b_n$ the least number between $n$ and $n(n+1)/2$ for which

\medskip
{$\phi_n(C) \neq 0\;\;$ for all $C$ with $\;\;b_n \le C \le
\displaystyle\frac{n(n+1)}{2}\koz.$ }

\medskip
The number $b_n$ exists for any $n$ (in the worst case it may be equal to
$n(n+1)/2$):


\begin{tetel}\label{KZLeve}
If $\ell \ge 2$, $0\le i\le \ell $, $n= \displaystyle\frac{\ell (\ell +1)}{2}+2+i$,
 then
\[ b_n = \frac{\ell (\ell^2 -1)}{2}+3\ell+2+i(\ell+1)\koz.\]
\end{tetel}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Generalized complexity measures\label{sectiongeneralized}}
As we have seen in the previous section, a contiguous part of a word (obtained by erasing a prefix 
or/and a suffix) is a \ki{subword} or \ki{factor.} If we eliminate arbitrary letters from a word, 
what is obtained is a \ki{scattered subword,} sometimes called \ki{subsequence.} Special scattered subwords, 
in which the consecutive letters are at distance at least $d_1$ and at most  $d_2$ in the original word, 
are called $(d_1,d_2)$-\ki{subwords}. More formally we give the following 
definition.\index{subword!$(d_1,d_2)$-subword}

Let  $n,$ $d_1\le d_2,$ $s$ be positive integers, and let $u=x_1x_2\ldots x_n\in A^n$ be a word over 
the alphabet $A.$  The word $v=x_{i_1}x_{i_2}\ldots x_{i_s},$ where  

$i_1\ge 1,$ 

$d_1\le i_{j+1}-i_j\le d_2,$  for $j=1,2,\ldots, s-1,$ 

$i_s\le n,$

\noindent is a  $(d_1,d_2)$\ki{-subword}\inddef{deonedetwosubword@$(d_1,d_2)$-subword} of length $s$ of  $u.$ 

\noindent For example the $(2,4)$-subwords of $aabcade$ are:
 $a$, $ab$, $ac$, $aba$, $aa$, $acd$, $abd$, $aae$, $abae$, $ace$, $abe$,  $ad$, 
 $b$, $ba$, $bd$, $bae$, $be$,
 $c$, $cd$, $ce$, 
 $ae,$
 $d,$ 
 $e.$

The number of different $(d_1,d_2)$-subwords of a word $u$ is called 
$(d_1,d_2)$\ki{-complexity}\inddef{déonedétwocomplexity@$(d_1,d_2)$-complexity}
and is denoted by $C_u(d_1,d_2)$.   \index{d1@$(d_1,d_2)$-complexity}\index{complexity!$(d_1,d_2)$-complexity}

\noindent For example, if $u=aabcade$, then $C_u(2,4)=23.$

\subsection{Rainbow words\label{subsectionrainbow}}
Words with pairwise different letters are called \ki{rainbow words.} \index{rainbow word}\index{word!rainbow}
  The $(d_1,d_2)$-complexity of a rainbow word of length $n$ does not depends on what letters it contains, 
  and is denoted by $C(n;d_1,d_2)$.

To compute the $(d_1,d_2)$-complexity  of a rainbow word of length $n$, let us consider the word  
$a_1a_2\ldots a_n$ (if $i \neq j,$ then $a_i \neq a_j)$ and the corresponding digraph $G=(V, E),$ with 

$V=\big\{ a_1, a_2, \ldots, a_n \big\}$, 

$E=\big\{ (a_i,a_j) \mid d_1\le j-i \le d_2, \, i=1,2,\ldots, n,  j=1,2,\ldots, n  \big\}$. 

\noindent For $n=6, d_1=2, d_2=4$ see Figure \ref{KZfig31}.
\begin{figure}
\begin{center}
\includegraphics[scale=0.1]{KZ-3-1.eps}
\end{center}\vspace*{-0.8cm}
\caption{Graph for $(2,4)$-subwords when $n=6.$}\label{KZfig31}
\end{figure}

\noindent The adjacency matrix  $A=\big(a_{ij}\big)_{\!\!\!\tiny\begin{array}{c}i\!\!=\!\!\overline{1,\!n}\\
                                                            j\!\!=\!\!\overline{1,\!n}\end{array}}$ 
of the graph is defined by:

\[a_{ij}=\left\{  \begin{array}{ll}
                    1,  &  \textrm{if } d_1\le j-i \le d_2,\\
                    0,     &  \textrm{otherwise},
                 \end{array}  \quad \textrm{  for  }   i=1,2,\ldots, n, j=1,2,\ldots, n.                        
           \right.
\]

Because the graph has no directed cycles, the entry in row $i$ and column $j$ in  $A^k$ 
(where $A^k=A^{k-1}A$, with $A^1=A$) will represent the number of $k$-length  directed paths 
from $a_i$ to $a_j$.  If $A^0$ is the identity matrix  (with entries equal to 1 only on the first diagonal, 
and 0 otherwise), let us define the matrix $R = (r_{ij})$:
\[R= A^0+A+A^2+\cdots + A^k, \textrm{ where } A^{k+1} = O \, (\textrm{the null matrix}).\]
The $(d_1,d_2)$-complexity of a rainbow word is then
\[ C(n;d_1,d_2)= \sum_{i=1}^{n}{\sum_{j=1}^{n}{r_{ij}}}.\]
The matrix $R$  can be better computed using a variant of the 
well-known Warshall\nevindex{Warshall, Stephen (1935--2006)} algorithm: 
 
\inddef{Warshall algorithm} \inddef{Warshall@\textsc{Warshall}} 
\begin{alg}{Warshall($A,n$)}
1 \'  $W \leftarrow A$\\
2 \' \key{for} \= $k \leftarrow 1$ \key{to} $n$ \\
3 \'           \> \key{do}  \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
4 \'           \>                      \>  \key{do} \key{for} \= $j \leftarrow 1$ \key{to} $n$ \\ 
5 \'            \>                     \>             \>  \key{do} $w_{ij}\leftarrow w_{ij}+w_{ik}w_{kj}$   \\ 
6 \'  \key{return} $W$
\end{alg}
From $W$ we obtain easily $R=A^0+W$. The time complexity of this algorithms is $\Theta(n^3).$

 For example let us consider the graph in Figure \ref{KZfig31}. The corresponding adjacency matrix is:

\[A=\left(\begin{array}{cccccc}
0&0&1&1&1&0 \\
0&0&0&1&1&1 \\
0&0&0&0&1&1 \\
0&0&0&0&0&1 \\
0&0&0&0&0&0 \\
0&0&0&0&0&0 \\
\end{array}
\right)\koz. 
\]
After applying the Warshall algorithm:
\[W=\left(\begin{array}{cccccc}
0&0&1&1&2&2 \\
0&0&0&1&1&2 \\
0&0&0&0&1&1 \\
0&0&0&0&0&1 \\
0&0&0&0&0&0 \\
0&0&0&0&0&0 \\
\end{array}
\right),
\qquad 
R=\left(\begin{array}{cccccc}
1&0&1&1&2&2 \\
0&1&0&1&1&2 \\
0&0&1&0&1&1 \\
0&0&0&1&0&1 \\
0&0&0&0&1&0 \\
0&0&0&0&0&1 \\
\end{array}
\right),
\]
and then $C(6;2,4)=19,$  the sum of entries in $R.$ 


\begin{figure}
\begin{center}
 $n=6$ \hspace*{4.5cm} $n=7$ 

\begin{tabular}[t]{|c|rrrrr|}\hline
\begin{picture}(15,10)\put(-6,10){\line(2,-1){27}}\put(-5,-2){$d_1$}\put(12,3){$d_2$}\end{picture} 
& 1 &2& 3& 4& 5\\ \hline
1 & 21&46&58&62&63\\
2&- & 12&17&19&20 \\
3&- & -&9&11&12 \\
4&- & -&-&8&9 \\
5&- & -&-&-&7 \\ \hline
\end{tabular}
\begin{tabular}[t]{|c|rrrrrr|}\hline
\begin{picture}(15,10)\put(-6,10){\line(2,-1){27}}\put(-5,-2){$d_1$}\put(12,3){$d_2$}\end{picture} 
& 1 &2& 3& 4& 5&6\\ \hline
1 & 28&79&110&122&126&127\\
2&- & 16&25&30&32 &33\\
3&- & -&12&15&17&18 \\
4&- & -&-&10&12& 13\\
5&- & -&-&-&9&10 \\ 
6&-&-&-&-&-&8\\ \hline
\end{tabular}
\end{center}
\caption{$(d_1,d_2)$-complexity for rainbow words of length 6 and 7.\label{KZtable2}}
\end{figure}

The Warshall algorithm combined with the Latin square method \index{Latin square method} 
can be used to obtain all nontrivial (with length at least 2) $(d_1,d_2)$-subwords of a given  
rainbow word $a_1a_2\ldots a_n$  of length $n$. Let us consider a matrix ${\cal A}$ with the elements 
$A_{ij}$ which are set of words. Initially this matrix is defined as
\[A_{ij}=\left\{  \begin{array}{ll}
                    \{a_ia_j\},  &  \textrm{if } d_1\le j-i\le d_2,\\
                    \emptyset,     &  \textrm{otherwise},
                 \end{array}  \quad \textrm{ for } \, i=1,2,\ldots, n, \, j=1,2,\ldots, n\koz. 
           \right.
\]
If ${\cal A}$ and ${\cal B}$ are sets of words, ${\cal AB}$ will be formed by the set of concatenation 
of each word from ${\cal A}$ with each word from ${\cal B}$: 
\[ {\cal AB} = \big\{ ab  \, \big| \, a\in {\cal A},  b\in {\cal B}  \big\}\koz.
\] 
If $s=s_1s_2\ldots s_p$ is a word, let us denote by $'s$ the word obtained from $s$ by erasing 
the first character: $'s=s_2s_3\ldots s_p$.  Let us denote by $'{A_{ij}}$ the set ${A_{ij}}$ 
in which we erase from each element the first character. In this case $'{\cal A}$ is a matrix 
with entries $'A_{ij}.$ 

Starting with the matrix ${\cal A}$ defined as before, the algorithm to obtain all nontrivial 
$(d_1,d_2)$-subwords is the following:

\inddef{\textsc{Warshall-Latin}}
\begin{alg}{Warshall-Latin(${\cal A},n$)}
1 \'  ${\cal W} \leftarrow {\cal A} $\\
2 \' \key{for} \= $k \leftarrow 1$ \key{to} $n$ \\
3 \'           \> \key{do}  \key{for} \= $i \leftarrow 1$ \key{to} $n$ \\
4 \'           \>                      \>  \key{do} \key{for} \= $j \leftarrow 1$ \key{to} $n$ \\ 
5 \'            \>                     \>             \>  \key{do} \key{if} \= $W_{ik}\neq \emptyset$ 
and  $W_{kj}\neq \emptyset$ \\
6 \'        \>      \>             \>   \> \key{then} $W_{ij}\leftarrow W_{ij} \cup W_{ik}\, 'W_{kj}$   \\ 
7 \'  \key{return} ${\cal W}$
\end{alg}

The set of nontrivial $(d_1,d_2)$-subwords is ${\displaystyle\bigcup_{i,j\in \{ 1,2,\ldots, n \} } W_{ij}}$. 
The time complexity is also $\Theta(n^3)$.

For $n=7,$ $d_1=2,$ $d_2=4,$ the initial matrix is:

\medskip
\begin{center}
${\cal A} = \left(\begin{array}{ccccccc}
\emptyset & \emptyset & \{ac\} & \{ad\} & \{ae\} & \emptyset & \emptyset   \\ 
\emptyset & \emptyset & \emptyset & \{bd\} & \{be\}& \{bf\} &\emptyset\\ 
\emptyset & \emptyset & \emptyset & \emptyset & \{ce\} & \{cf\}&  \{cg\} \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\{df\} & \{dg\}  \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\{eg\}  \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\emptyset  \\
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\emptyset \\
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\emptyset  \\
\end{array}
\right),
$
\end{center}

\noindent and 

\smallskip
\begin{center}
${\cal W} = \left(\begin{array}{cccccccc}
\emptyset & \emptyset & \{ac\} & \{ad\} & \{ace,ae\} &\{adf,acf\} &\{aeg,aceg, adg,acg\}  \\ 
\emptyset & \emptyset & \emptyset & \{bd\} & \{be\}& \{bdf, bf\} & \{beg, bdg\} \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \{ce\}& \{cf\}&  \{ceg, cg\}  \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\{df\} & \{dg\}  \\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\{eg\}\\ 
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\emptyset  \\
\emptyset & \emptyset & \emptyset & \emptyset & \emptyset &\emptyset &\emptyset  \\\end{array}
\right).
$
\end{center}
 
Counting the one-letter subwords too, we obtain  $C(7;2,4)=30.$ 

\vspace{-1mm}
\subsubsection{The case $\pmb {d_1=1}$}
In this case instead of $d_2$ we will use $d$.  
For a rainbow word,  $a_{i,d}$ we will denote the number of $(1,d)$-subwords  which  
finish at the position $i.$ For $ \;\;i = 1,2, \ldots ,n$
\begin{equation}
a_{i,d} = 1 + a_{i-1,d} + a_{i-2,d}+ \ldots  + a_{i-d,d}\koz. \label{KZ631}  
\end{equation}

For simplicity, let us denote $C(n;1,d)$ by  $N(n,d)$.
The $(1,d)$-complexity of a rainbow word  can be obtained
  by  the formula
$$ N(n,d) =\sum_{i=1}^{n}a_{i,d}\koz. $$
 Because of (\ref{KZ631})  we can  write  in the case of $ d \ge  2$
\[  a_{i,d} + \frac{1}{d-1} = \left(a_{i-1,d} + \frac{1}{d-1}\right) + \cdots
 + \left(a_{i-d,d} + \frac{1}{d-1} \right)\koz. \]
Denoting 
\[b_{i,d}=a_{i,d}+\frac{1}{d-1}\koz,\hspace*{0.5 cm}{\rm and}\hspace*{0.5 cm}
c_{i,d}=(d-1)b_{i,d}\koz,\]
we get
\[ c_{i,d} = c_{i-1,d} + c_{ i-2,d}+\ldots + c_{i-d,d}\koz,\]
and the sequence $c_{i,d}$ is one of Fibonacci-type.
For any $d$ we have $a_{1,d} = 1$  and from this $c_{1,d} = d$  results.
Therefore the numbers $ c_{i,d}$ are defined by the following recurrence
equations:

\smallskip
 $ c_{n,d} = c_{n-1,d} + c_{n-2,d} + \ldots + c_{n-d,d},$
   \hfill for $\;\;n > 0,\hspace*{4 cm} \;$

$ c_{n,d}=1,$ \hfill for $\;\; n \le 0.\hspace*{4 cm} \; $
\newpage
These numbers can be generated by the following generating function:
\begin{eqnarray}
F_d(z)&=&\sum_{n\ge 0}^{}{c_{n,d}z^n}=
         \frac{1+(d-2)z - z^2 - \cdots - z^d}{1-2z+z^{d+1}}\nonumber \\
     &=& \frac{1+(d-3)z - (d-1)z^2 +z^{d+1} }{(1-z) (1-2z+z^{d+1})}\koz.\nonumber
\end{eqnarray}

The $(1,d)$-complexity $N(n,d)$ can be expressed with these numbers $ c_{n,d}$
 by  the following formula:
\[  N(n,d) = \frac{1}{d-1}\left(\sum_{i=1}^{n}{c_{i,d}-n}\right), \;\;\;
\hspace*{0.5 cm}\hbox{for} \;\; d > 1\koz, \]
 and
\[ N(n,1) = \frac{n(n+1)}{2}\koz, \]
or
\[
 N(n,d) = N(n-1,d) +\frac{1}{d-1} ( c_{n,d}- 1), \qquad \hbox{for}\;\;\;
 d > 1, \;\; n > 1\koz.\]
If $d = 2$ then
\[ F_2(z) =\frac{1-z^2}{1-2z+z^3} = \frac{1+z}{1-z-z^2}=\frac{F(z)}{z}+F(z)\koz, \]
where $F(z)$ is the generating function of the Fibonacci numbers $ F_n$
 (with $F_0= 0,\;\; F_1 = 1$). Then, from this formula we have
\[  c_{n,2} = F_{n+1} +F_{ n} = F_{n+2} \koz,\]
and
\[ N(n,2) = \sum_{i=1}^{n}{F_{i+2}}-n = F_{n+4}-n -3\koz. \]

\medskip
\noindent Figure \ref{KZtable3} contains the values of $N(n,d)$ for
$k \le  10$ and $d \le  10.$

\begin{figure}
\begin{center}
\begin{tabular}{|r|rrrrrrrrrr|}\hline
{\small $n$} $\left\backslash {\normalsize d}\right.$
          & 1& 2 & 3& 4& 5& 6& 7& 8& 9& 10 \\ \hline
1    & 1& 1& 1& 1& 1& 1& 1& 1& 1& 1 \\
2    & 3& 3& 3& 3& 3& 3& 3& 3& 3& 3 \\
3    & 6& 7& 7& 7& 7& 7& 7& 7& 7& 7 \\
4    & 10& 14& 15& 15& 15& 15& 15& 15& 15& 15 \\
5    & 15& 26& 30& 31& 31& 31& 31& 31& 31& 31 \\
6    & 21& 46& 58& 62& 63& 63& 63& 63& 63& 63 \\
7    & 28& 79& 110& 122& 126& 127& 127& 127& 127& 127 \\
8    & 36& 133& 206& 238& 250& 254& 255& 255& 255& 255 \\
9    & 45& 221& 383& 464& 494& 506& 510& 511& 511& 511 \\
10   & 55& 364& 709& 894& 974& 1006& 1018& 1022& 1023& 1023 \\ \hline
\end{tabular}
\end{center}
\caption{The $(1,d)$-complexity of  words  of length $n$}\label{KZtable3}
\end{figure}

\medskip
\[ N(n,d) = 2^n - 1, \qquad \hbox{for any}\quad   d \ge  n-1. \]
The following theorem gives the value of $N(n,d)$ in the case $n \ge  2d-2$:

\begin{tetel}  For $n \ge  2d-2$  we have
\[ N(n,n-d) = 2^n - (d-2)\cdot 2^{d-1} - 2\koz.\]
\end{tetel}

The main step in the proof is based on the formula
\[N(n,n-d-1) = N(n,n-d) - d\cdot 2^{{\rm d-1}}\koz.\]

The value of $N(n,d)$ can be also obtained by computing the number of
sequences of length $ k$ of $0$'s and $1$'s, with no more than
$ d-1$ adjacent zeros. In such a sequence one 1 represents the presence, one
0 does the  absence  of a letter of the word in a given $(1,d)$-subword.
Let $b_{n,d}$  denote  the  number  of
$n$-length sequences of zeros and ones, in which the first and last
position  is 1, and the number of adjacent zeros is at most $d-1.$
Then it can be proved easily  that

\medskip
 \hspace*{1 cm} $b_{n,d} = b_{n-1,d} + b_{n-2,d} + \ldots  +b_{n-d,d}\koz,$
                 for $ \;\;k > 1\koz,$ 

\hspace*{1 cm} $ b_{1,d} = 1\koz,$

\hspace*{1 cm} $ b_{n,d} = 0$,  for all $n \le  0\koz,$ 

\medskip
\noindent because any such sequence of length $ n-i$  ($i=1,2,...,d$)
  can  be  continued  in
order to obtain a similar sequence of length $n$ in only one way
(by  adding  a sequence of the form $0^{i-1}1$ on the right).
For $b_{n,d}$ the following formula also
can be derived:
\[ b_{n,d} = 2b_{n-1,d} - b_{n-1-d,d}\koz.\]
If we add one 1 or 0 at an internal position  (e.g  at  the $(n-2)^{th}$ position)   of 
each $ b_{n-1,d}$ sequences, then we obtain $2b_{n-1,d}$ sequences of length
$n,$  but  from these, $ b_{n-1-d,d}$ sequences will have $d$ adjacent zeros. \label{KZgenfunc2}

The generating function corresponding to $b_{n,d}$ is
\[
B_{d}(z) = \sum_{n\ge 0}^{}{b_{n,d}z^n} =
 \frac{z}{1-z \cdots - z^d}= \frac{z(1-z)}{1-2z+z^{d+1}}\koz.  \]
By adding zeros on the left and/or on the right to these sequences, we can obtain
the number $N(k,d),$ as the number of all these sequences.\label{KZgenfunc1} Thus
\[ N(k,d) = b_{k,d} + 2b_{k-1,d} + 3b_{k-2,d} + \cdots + kb_{1,d}\koz. \]
($i$ zeros can be added in $i+1$ ways to these sequences: $0$ on the left and
$i$  on the right, $1$ on the left and $i-1$ on the right, and so on).

From the above formula, the generating function corresponding to the
complexities $N(k,d)$ can be  obtained as a product of the two generating
functions $B_d(z)$ and $A(z) = \sum_{n\ge 0}^{}{nz^n}= 1/(1-z)^2$, thus:
\[ N_d(z)=\sum_{n\ge 0}^{}{N(n,d)z^n} = \frac{z}{(1-z)(1-2z+z^{d+1})}\koz.\]

\subsubsection{The case $\pmb{d_2=n-1}$}
In the sequel instead of $d_1$ we will use $d.$ In this case the distance between two letters picked up 
to be neighbours in a subword is at least $d$.

Let us denote by $b_{n,d}(i)$ the number of $(d,n-1)$-subwords which begin at the position $i$ 
in a  rainbow word  of length $n$. Using our previous example (\emph{abcdef}), 
we can see that $b_{6,2}(1)=8,$ $b_{6,2}(2)=5,$ $b_{6,2}(3)=3,$ $b_{6,2}(4) = 2,$ $b_{6,2}(5) = 1,$  and $b_{6,2}(6)=1.$  

The following formula immediately results:
\begin{equation}
b_{n,d}(i)= 1 + b_{n,d}(i\!+\!d)+ b_{n,d}(i\!+\!d\!+\!1)+\!\cdots\! +  b_{n,d}(n)\koz,   \label{KZ1}
\end{equation}

for $n> d,$ and $ 1\le i\le n-d\koz,$
\[b_{n,d}(1)=1  \textrm{ for  } \; n\le d\koz.\]

For simplicity, $C(n;d,n)$ will be denoted by $K(n,d)$.

The $(d,n-1)$-complexity of rainbow words can be computed by the formula:
\begin{equation}
K(n,d)= \sum_{i=1}^{n}{b_{n,d}(i)}\koz. \label{KZketto}
\end{equation}

This can be expressed also as
\begin{equation} K(n,d)=\sum_{k=1}^{n}{b_{k,d}(1)}\koz, \label{KZt1} \end{equation}
because of the formula
\[K(n+1,d)=K(n,d)+b_{n+1,d}(1)\koz.\]

\begin{figure}
\begin{center}
\begin{tabular}{|r|rrrrrrrrrrr|}\hline
\begin{picture}(15,10)\put(-6,10){\line(2,-1){27}}\put(-2,-2){$n$}\put(13,3){$d$}\end{picture}& 
1& 2  & 3  & 4  & 5 &6 &7 &8 &9&10&11\\ \hline
1& 1 &1&1&1&1&1&1&1&1&1&1 \\
2& 3 &2&2&2&2&2&2&2&2&2&2 \\
3& 7& 4&3&3&3&3&3&3&3&3&3\\
4& 15&7 &5&4&4&4&4&4&4&4&4\\
5& 31&12 &8&6&5&5&5&5&5&5&5\\
6 & 63& 20  &12 &9 & 7&6&6&6&6&6&6\\
7 & 127&33  &18 &13 &10 &8 &7&7&7&7&7\\
8 & 255&54  &27& 18 & 14 & 11 &9&8&8&8&8\\
9 & 511&88  &40 &25 & 19&15&12&10&9&9&9\\
10 & 1023& 143&59 &35 & 25&20&16&13&11&10&10\\
11 &2047& 232&87 &49 & 33&26&21&17&14&12&11\\
12 &4095& 376&128 &68 & 44&33&27&22&18&15&13\\
\hline
\end{tabular}\caption{Values of $K(n,d)$. \label{KZtable4}}
\end{center}
\end{figure}

In the case $d = 1$ the complexity $K(n,1)$ can be computed easily: $K(n,1)= 2^n-1.$ 

 From (\ref{KZ1}) we get the following algorithm for the computation of $b_{n,d}(i).$  
 The numbers $b_{n,d}(k) \,   (k=1,2,\ldots)$ for a given $n$ and $d$ are obtained in  
 the array $b=(b_1,b_2, \ldots $). Initially all these elements are equal to $-1.$
The call for the given $n$ and $d$ and the desired $i$ is:

\begin{tabbing}
Input $(n,d,i)$ \\
\key{for} \= $k\leftarrow 1$ \key{to} $n$\\
          \> \key{do} $b_k \leftarrow -1$\\
\textsc{B}$(n,d,i)$ \` $\rhd$ Array $b$ is a global one.\\
Output $b_1, \ b_2, \ \ldots, \ b_n$          
\end{tabbing}

\medskip
The recursive algorithm is the following:

\begin{alg}{B($n,d,i$)}\inddef{Béndi@B$(n,d,i)$}
1 \' $p\leftarrow 1$ \\
2 \' \key{for} \= $k\leftarrow i + d$ \key{to} $n$ \\
3 \'           \> \key{do} \= \key{if}  \= $b_k = -1$\\
4 \'           \>          \>           \>  \key{then} \textsc{B}$(n,d,k)$\\
5 \'           \>          \> $p\leftarrow p + b_k$              \\
6 \' $b_i\leftarrow p$ \\ 
7 \'  \key{return}
\end{alg}

This algorithm is a linear one. 

If the call is $B(8,2,1),$ the elements will be obtained in the following order:
$b_7=1,$ $b_8 = 1,$ $b_5=3,$ $b_6 = 2,$ $b_3 = 8,$ $b_4 = 5,$ and $b_1 = 21.$ 
\begin{lemma}\label{KZl1} $b_{n,2}(1)=F_{n},$ where $F_n$ is the $n$th Fibonacci number.\index{Fibonacci number}
\end{lemma}
\begin{biz}
Let us consider a rainbow word $a_1a_2\ldots a_n$ and let us count all its $(2,n-1)$-subwords 
which begin with $a_2$. If we change $a_2$ for $a_1$ in each $(2,n-1)$-subword which begin with $a_2$, 
we obtain $(2,n-1)$-subwords too. If we add $a_1$ in front of each $(2,n-1)$-subword which begin 
with $a_3,$ we obtain $(2,n-1)$-subwords too.  Thus
\[b_{n,2}(1)=b_{n-1,2}(1)+b_{n-2,2}(1)\koz.\]
So $b_{n,2}(1)$ is a Fibonacci number, and because $b_{1,2}(1)=1$, we obtain that $b_{n,2}(1)=F_n.$ 
\end{biz}

\begin{tetel}\label{KZtt}
$K(n,2)=F_{n+2}-1$, where $F_n$ is the $n$th Fibonacci number.
\end{tetel}
\begin{biz}
From equation (\ref{KZt1}) and Lemma \ref{KZl1}:
\begin{eqnarray*}
K(n,2)&=&b_{1,2}(1)+ b_{2,2}(1)+ b_{3,2}(1)+b_{4,2}(1)+ \cdots + b_{n,2}(1)\\
      &=& F_1+F_2+\cdots + F_{n}\\
      &=& F_{n+2}-1\koz. 
\end{eqnarray*}

\vspace*{-0.8cm}
\end{biz}

If we use the notation $M_{n,d}=b_{n,d}(1)$, because of the formula
\[b_{n,d}(1)=b_{n-1,d}(1)+b_{n-d,d}(1)\koz,\]
a generalized middle sequence will be obtained:
\begin{eqnarray}
M_{n,d}\!\!\!\!&=&\!\!\!\!M_{n-1,d} +M_{n-d,d}\koz, \quad\textrm{for } n\ge d\ge 2\koz,\label{KZMMM}\\
M_{0,d}\!\!\!\!&=&\!\!\!\!0, \, M_{1,n}=1,\, \ldots,\, M_{d-1,d}=1\koz.\nonumber
\end{eqnarray}
Let us call this sequence \ki{$d$-middle sequence.} Because of the equality $M_{n,2}=F_n$, the 
$d$-middle sequence can be considered as a generalization of the Fibonacci 
sequence.\index{d@$d$-middle sequence}\index{middle sequence}


Then next linear algorithm  computes $M_{n,d}$, by using an array $M_0, M_1, \ldots, M_{d-1}$ 
to store the necessary previous elements:

\index{Middle@\textsc{Middle}}
\begin{alg}{Middle($n,d$)}
1 \' $M_0 \leftarrow 0$ \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $d-1$ \\
3 \'           \> \key{do} $M_i\leftarrow 1 $\\
4 \'  \key{for} \= $i \leftarrow d$ \key{to} $n$ \\ 
5 \'    \> \key{do} \= $M_{i \textrm{ \scriptsize mod } d} \leftarrow M_{(i-1) \textrm{ 
\scriptsize mod } d} + M_{(i-d) \textrm{ \scriptsize mod } d} $  \\
6 \'    \>          \> print  $M_{i \textrm{ \scriptsize mod } d} $                 \\ 
7 \'  \key{return}
\end{alg}


\medskip
Using the generating function $M_d(z)=\displaystyle\sum_{n\ge 0 }{M_{n,d}z^n},$  
the following closed formula can be obtained:
\begin{equation}
M_d(z)=\frac{z}{1-z-z^d}\koz. \label{KZgen}
\end{equation}
This can be used to compute the sum $s_{n,d}=\displaystyle\sum_{n=1 }^{n}{M_{i,d}},$ 
which is the coefficient of $z^{n+d}$ in the expansion of the function 
\[\frac{z^{d}}{1-z-z^d}\cdot\frac{1}{1-z}= \frac{z^{d}}{1-z-z^d}+\frac{z}{1-z-z^d}-\frac{z}{1-z}\koz.\]
So $s_{n.d}=M_{n+(d-1),d}+M_{n,d}-1 = M_{n+d,d}-1.$ Therefore
\begin{equation} 
\sum_{i=1}^{n}{M_{i,d}}= M_{n+d,d} -1\koz. \label{KZm}
\end{equation}

\begin{tetel}\label{KZt2}
$K(n,d)=M_{n+d,d}-1$, where $n>d$ and $M_{n,d}$ is the $n$th elements of $d$-middle sequence.
\end{tetel}

\begin{biz} The proof is similar to that in Theorem \ref{KZtt} taking into account the equation (\ref{KZm}).
\end{biz}

\begin{tetel}  $K(n,d)=\displaystyle\sum_{k\ge 0}{\binom{n-(d-1)k}{{k+1}}}\koz,$ \ for $n\ge 2, d\ge 1\koz.$
\end{tetel}
\begin{biz}
   Let us consider the generating function $\displaystyle G(z)=\frac{1}{1-z}= 1+z+z^2+\cdots.$ 
   Then, taking into account the equation (\ref{KZgen}) we obtain 
   $M_d(z)=zG(z+z^d)=z + z(z+z^{d})+z(z+z^{d})^2+\cdots +z(z+z^{d})^i +\cdots.$ 
   The general term in this expansion is equal to  
   \[ z^{i+1}\sum_{k=1}^{i}{\binom{i}{k}z^{(d-1)k}}\koz, \]
and the coefficient of $z^{n+1}$ is equal to \[ \sum_{k\ge 0}^{}{\binom{n-(d-1)k}{k} }  \koz.\]  
The coefficient of $z^{n+d}$ is 
\begin{equation}
   M_{n+d,d}= \sum_{k\ge 0}^{}{\binom{n+d-1 -(d-1)k}{k} }\koz. \label{KZMnd}
\end{equation} 
By Theorem \ref{KZt2}  $K(n,d)=M_{n+d,d}-1$, and an easy computation yields 
   \[K(n,d)= \sum_{k\ge 0}{\binom{n-(d-1)k}{k+1}}\koz.\]   

\vspace*{-1.5\baselineskip}
\end{biz}

\subsection{General words} 


The algorithm \textsc{Warshall-Latin} can be used for nonrainbow words too, with 
the remark that repeating subwords must be eliminated. For the word $aabbbaaa$ and $d_1=2,$ 
$d_2=4$  the result is: $ab, abb, aba, abba, abaa, 
aa,  aaa, bb, ba, bba, baa,$  and with $a$ and $b$ we have $C_{aabbbaaa}(2,4)=13.$



\section{Palindrome complexity}\index{complexity!palindrome}\index{palindrome complexity} 
The \ki{palindrome complexity function} \text{pal}$_{w}$ of a finite or
infinite word $w$ attaches to each $n\in\mathbf{N}$ the number of palindrome
subwords of length $n$ in $w$, denoted by $\text{pal}_{w}(n).$ 

The \ki{total palindrome complexity} of a finite word $w\in A^{\ast}$ is
equal to the number of all nonempty palindrome subwords of $w,$ i.e.:
\[
P(w)=\sum_{n=1}^{\left\vert w\right\vert }\text{\text{pal}}_{w}(n)\koz.
\]
This is similar to the total complexity of words.


\subsection{Palindromes in finite words}
\begin{tetel}
\label{KZ5t1} The total palindrome complexity $P(w)$ of any finite word $w$
satisfies $P(w)\leq|w|.$ 
\end{tetel}

\begin{biz}
We proceed by induction on the length $n$\ of the word $w$. For $n=1$ we have
$P(w)=1$.

We consider $n\geq2$ and suppose that the assertion holds for all words of
length $n-1$. Let $w=a_{1}a_{2}\ldots a_{n}$ be a word of length $n$\ and
$u=a_{1}a_{2}\ldots a_{n-1}$\ its prefix of length $n-1$. By the induction
hypothesis it is true that $P(u)\leq n-1$.

If $a_{n}\neq a_{j}$ for each $j\in\{1,2,\ldots n-1\}$, the only palindrome in
$w$\ which is not in $u$\ is $a_{n}$, hence $P(w)=P(u)+1\leq n$.

If there is an index $j,$ $1\leq j\leq n-1$ such that $a_{n}=a_{j}$, then
$P(w)>P(u)$ if and only if $w$\ has suffixes which are palindromes. Let us
suppose that there are at least two such suffixes $a_{i}a_{i+1}\ldots a_{n}$
and $a_{i+k}a_{i+k+1}\ldots a_{n}$, $1\leq k\leq n-i$, which are palindromes.
It follows that%
\[%
\begin{array}{l}%
a_{i} = a_{n} = a_{i+k}\\
a_{i+1}=a_{n-1}=a_{i+k+1}\\
 \cdots  \\
a_{n-k}=a_{i+k}=a_{n},
\end{array}
\]
hence $a_{i+k}\ldots a_{n}=a_{i}\ldots a_{n-k}$. The last palindrome appears
in $u$\ (because of $k\geq 1$) and has been already counted in $P(u)$. It follows
that $P(w)\leq P(u)+1\leq n$.
\end{biz}

This result shows that the total number of palindromes in a word cannot be
larger than the length of that word. We examine now if there are words which
are `poor' in palindromes. In the next lemma we construct finite words $w_{n}%
$\ of arbitrary length $n\geq 9,$ which contain precisely 8 palindromes. 

Let us denote by $w^{\frac{p}{q}}$ the fractional power of the word $w$ of \index{word!fractional power}
length $q$, which is the prefix of length $p$ of $w^{p}$.

\begin{lemma}
\label{KZ5l1} If $w_{n}=(001011)^{\frac{n}{6}}$, $n\geq9$, then $P(w_{n})=8.$
\end{lemma}
\begin{biz}
In $w_{n}$ there are the following palindromes: 0, 1, 00, 11, 010, 101, 0110,
1001. Because 010 and 101 are situated in $w_{n}$ between 0 on the left and 1
on the right, these cannot be continued to obtain any palindromes. The same is
true for 1001 and 0110, which are situated between 1 on the left and 0 on the
right, excepting the cases when 1001 is a suffix. So, there are no other
palindromes in $w_{n}$.
\end{biz}

\begin{megj} 
If $u$ is a circular permutation of $001011$ and $n\geq9$ then $P(u^{\frac
{n}{6}})=8$ too. Because we can interchange $0$ with $1$, for any $n$ there
will be at least $12$ words of length $n$ with total complexity equal to $8.$ 
\end{megj}

We shall give now, beside the upper delimitation from Theorem \ref{KZ5t1},
lower bounds for the number of palindromes contained in finite binary words.
(In the trivial case of a $1$-letter alphabet it is obvious that, for any word
$w,$ $P(w)=\left\vert w\right\vert.$)
\begin{tetel}
\label{KZ5t2} If $w$ is a finite word of length $n$ on a $2$-letter alphabet,
then 

 \smallskip
 \quad$\begin{array}{ll}
   P(w)=n,            & \textrm{for } 1\leq n\leq 7\koz, \\
   7\leq P(w)\leq 8,  & \textrm{for } n=8\koz,\\
   8\leq P(w)\leq n,        & \textrm{for } n\geq 9\koz.                       
\end{array}$ 
\end{tetel}
\begin{biz}
Up to 8 the computation can be made by a computer program. For $n\geq 9,$ Lemma
\ref{KZ5l1} gives words $v_{n}$\ for which $P(v_{n})=8$. The maximum value is
obtained for words of the form $a^{n},\;a\in A,\;n\in\mathbf{N}.$
\end{biz}
 
\begin{megj}
For all the short binary words (up to $\left\vert w\right\vert =7$), the
palindrome complexity takes the maximum possible value given in Theorem
\ref{KZ5t1}; from the words with $\left\vert w\right\vert =8$, only four (out of
$2^{8}$) have $P(w)=7$,\ namely $00110100$, $00101100$ and their complemented words.
\end{megj}

In the following lemmas we construct binary words which have a given total
palindrome complexity greater than or equal to $8$.

\begin{lemma}
\label{KZ5l2} If $u_{k,\ell}=0^{k}10110^{\ell}1$ for $k\geq2$ and $1\leq\ell\leq
k-1,$ then $P(u_{k,\ell})=k+6.$
\end{lemma}
\begin{biz}
In the prefix of length $k$ of $u_{k,\ell}$ there are always $k$\ palindromes
($1,\ldots,1^{k}$). The other palindromes different from these are $1$, $11$,
$010$, $101$, $0110$\ and $10^{\ell}1$ $($for $\ell\geq2)$, respectively
$101101$ (for $\ell=1$). In each case $P(u_{k,\ell})=k+6$.
\end{biz}
\begin{lemma}
\label{KZ5l3} If $v_{k,\ell}=(0^{k}1011)^{\frac{k+\ell+5}{k+4}}$ for $k\geq2$ and
$k\leq\ell\leq n-k-5,$ then $P(v_{k,\ell})=k+6.$
\end{lemma}
\begin{biz}
Since $\ell\geq k$, the prefix of $u_{k,j}$ is at least $0^{k}10110^{k}1$,
which includes the palindromes $0,\ldots,0^{k},$ $1$, $11$, $010$, $101$,
$0110$\ and $10^{k}1$, hence $P(v_{k,\ell})\geq k+6$. The palindromes
$010$\ and $101$\ are situated between $0$ and $1$, while $0110$\ and
$10^{k}1$ are between $1$\ and $0$ (excepting the cases when they are
suffixes),\ no matter how large is $\ell$. It follows that $v_{k,\ell}%
$\ contains no other palindromes, hence $P(v_{k,\ell})=k+6$.
\end{biz}

\begin{megj} 
If $k = 2,$ then the word $v_{2,\ell}$ is equal to $w_{\ell+7}$, with $w_{n}$
defined in Lemma \ref{KZ5l1}.
\end{megj}

We can determine now precisely the image of the restriction of the palindrome
complexity function to $A^{n}$, $n \geq 1.$

\begin{tetel}
\label{KZ5t3} Let $A$ be a binary alphabet. Then
\[ P(A^{n}) = \left\{
\begin{array}{ll}
       \big\{ n\big\},  & \textrm{for } 1\leq n\leq 7\koz, \\
       
       \big\{ 7,8 \big\},& \textrm{for } n=8\koz,\\
       \big\{  8,\ldots,n\big\},    & \textrm{for } n\geq 9\koz.                       
\end{array} 
\right.
\]
\end{tetel}
\begin{biz}
Having in mind the result in Theorem \ref{KZ5t2}, we have to prove only that for
each $n$ and $i$\ so that $8\leq i\leq n$, there exists always a binary word
$w_{n,i}$ of length $n$ for which the total palindrome complexity is
$P(w_{n,i})=i$. Let $n$ and $i$\ be given so that $8\leq i\leq n$. We denote
$k=i-6\geq 2$\ and $\ell=n-k-5$.

If $\ell\leq k-1$, we take $w_{n,i}=u_{k,\ell}$ (from Lemma \ref{KZ5l2}); if
$\ell\geq k,$ $w_{n,i}=v_{k,\ell}$ (from Lemma \ref{KZ5l3}). It follows that
$\left\vert w_{n,i}\right\vert =n$ and $P(w_{n,i})=k+6=i.$
\end{biz}
\begin{pelda} 
Let us consider $n = 25$ and $i = 15.$ Then $k=15-6=9$, $\ell=26-15=11$. Because
$\ell>k-1$, we use $v_{9,11}=(0^{9}1011)^{\frac{25}{13}}=0^{9}10110^{9}101$,
whose total palindrome complexity is $15$.
\end{pelda}

We give similar results for the case of alphabets with $q\geq 3$ letters.

\begin{tetel}
\label{KZ5t4} If $w$ is a finite word of length $n$ over a $q$-letter ($q\geq 3$)
alphabet, then 
\[\begin{array}{ll}
P(w)=n,           & \textrm{for } n\in\{1,2\} \koz,\\  
3\leq P(w)\leq n, & \textrm{for } n\geq 3\koz.
\end{array}
\]
\end{tetel}
\begin{biz}
For $n\in\{1,2\}$\ it can be checked directly. Let us consider now $n\geq
3$\ and a word of length at least $3$. If this is a trivial word (containing
only one letter $n$ times), its total palindrome complexity is $n\geq3$. If in
the word there appear exactly two letters $a_{1}$\ and $a_{2}$, it will have
as palindromes those two letters and at least one of $a_{1}^{2},$ $a_{2}^{2},$
$a_{1}a_{2}a_{1}$ or $a_{2}a_{1}a_{2}$, hence again $P(w)\geq3$. If the word
contains a third letter, then obviously $P(w)\geq3$. So, the total complexity
cannot be less then $3$.
\end{biz}
\begin{tetel}
\label{KZ5t5} Let $A$ be a $q$-letter ($q\geq3$) alphabet. Then for 
\[P(A^{n}) = 
\left\{ 
\begin{array}{ll}
\big\{  n\big\}, & \textrm{for } 1\leq n\leq 2 \koz,\\
\big\{3,\ldots,n\big\}, & \textrm{for } n\ge 3\koz.
\end{array}
\right.
\]
\end{tetel}
\begin{biz}
It remains to prove that for each $n$ and $i$\ so that $3\leq i\leq n$, there
exists always a word $w_{n,i}$ of length $n$, for which the total palindrome
complexity is $P(w_{n,i})=i$. Such a word is $w_{n,i}=a_{1}^{i-3}(a_{1}%
a_{2}a_{3})^{\frac{n-i+3}{3}}$, which\ has $i-2$ \ palindromes in its prefix
of length $i-2$, and other two palindromes $a_{2}$ and $a_{3}\ $in\ what follows.
\end{biz}

\subsection{Palindromes in infinite words}
\subsubsection{Sturmian words}\index{Sturmian word}\index{word!Sturmian}
The number of palindromes in the infinite Sturmian words is given by the following theorem.
\begin{tetel}
If $u$ is an infinite Sturmian word, then
\[
\textrm{\emph{pal}}_{u}(n)=\left\{\begin{array}{ll}
                             1, & \textrm{ if }  n  \textrm{ is even\koz,}  \\
                             2, & \textrm{ if } n  \textrm{ is odd\koz.}
                           \end{array}
                    \right.
\]
\end{tetel}

\subsubsection{Power word}\index{word!power}\index{power word}
Let us recall the power word as being  

$p=01001100011100001111\ldots 0^n 1^n \ldots \koz.$

\begin{tetel} The palindrome complexity of the power word $p$ is
\[\emph{pal}_p(n)=2\left\lfloor \frac{n}{3}\right\rfloor+1+\varepsilon\koz, \]
where \[\varepsilon=\left\{ \begin{array}{ll}
                             0, & \textrm{if } n \textrm{ divisible by 3}\koz,\\
                             1, & \textrm{otherwise}\koz.
                         \end{array}
                 \right.\] 
\end{tetel}

\begin{biz}
There exist the following cases:

\medskip
\noindent Case $n=3k$. 
Palindrome subwords are:

\smallskip
 $0^i1^{3k-2i}0^i$ \quad for $i=0,1,\ldots k\koz,$

 $1^i0^{3k-2i}1^i$ \quad  for $i=0,1,\ldots k-1$,  \quad so $\pal_p(3k)=2k+1\koz.$

\medskip
\noindent Case $n=3k+1.$ Palindrome subwords are:

\smallskip
 $0^i1^{3k+1-2i}0^i$ \quad for $i=0,1,\ldots k\koz,$

 $1^i0^{3k+1-2i}1^i$ \quad  for $i=0,1,\ldots k$,  \quad so $\pal_p(3k+1)=2k+2\koz.$


\medskip
\noindent Case $n=3k+2.$ Palindrome subwords are:

\smallskip
 $0^i1^{3k+2-2i}0^i$ \quad for $i=0,1,\ldots k\koz,$
 
 $1^i0^{3k+2-2i}1^i$ \quad  for $i=0,1,\ldots k$,  \quad so $\pal_p(3k+2)=2k+2\koz.$
\end{biz}

The palindrome subwords of the power word have the following  properties:\\
$\bullet$ Every palindrome subword which contains both 0's and 1's occurs only once in the power word.
\\
$\bullet$ If we use the notations $U_{iji}=0^i1^j0^i$ and $V_{iji}=1^i0^j1^i$ then there are 
the unique decompositions:
\[p=U_{111}U_{121}U_{232}U_{242}U_{353}U_{363}\ldots U_{k,2k-1,k}U_{k,2k,k}\ldots\koz,\]
\[p=0V_{121}V_{232}V_{141}V_{353}V_{262}V_{474}V_{383}\ldots V_{k+1,2k+1,k+1}V_{k,2k+2,k} \ldots\koz.\]

\subsubsection{Champernowne word}\index{word!Champernowne}\index{Champernowne word}
The Champernowne word is defined as the concatenation of consecutive binary written natural numbers:

$c = 0\,1\,10\,11\,100\,101\,110\,111\,1000\,1001\,1010\,1011\,1100\ldots \koz.$


\begin{tetel} The palindrome complexity of the Champernowne word is
\[ \emph{\pal}_c(n)=2^{\lfloor \frac{n}{2}\rfloor+\varepsilon}, \]
where \[\varepsilon=\left\{ \begin{array}{ll}
                             0, & \textrm{if } n \textrm{ is even}\koz,\\
                             1, & \textrm{if } n \textrm{ is odd\koz.}
                         \end{array}
                 \right.\] 
\end{tetel}
\begin{biz}
Any palindrome $w$ of length $n$ can be continued as $0w0$ and $1w1$ to obtain palindromes of length $n+2$.
This theorem results from the following:  $\pal_c(1)=2$, $\pal_c(2)=2$ and for $n\ge 1$ we have
 
$\pal_c(2n+1)=2\pal_c(2n-1)\koz,$

$\pal_c(2n+2)=2\pal_c(2n)\koz.$
\end{biz}

\medskip
The following algorithm generates all palindromes up to a given length of a Sturmian word\index{Sturmian word} 
beginning with the letter $a,$ and generated by the morphism $\sigma.$  

The idea is the following. If $p$ is the least value for which $\sigma^p(a)$ and $\sigma^p(b)$ 
are both of odd length (such a $p$ always exists), we consider conjugates\footnote{If $w = uv$ then $vu$ is a 
conjugate of $w$.} of these words,  
which are palindromes (such conjugates always exists), and we define the following morphism:

 $\pi(a)= \textrm{conj}\big(\sigma^p(a)\big)$,
 
 $\pi(b)= \textrm{conj}\big(\sigma^p(b)\big)$,  

\noindent where conj($u$) produces a conjugate of $u$, which is a palindrome.

The sequences $\big(\pi^n(a)\big)_{n\ge 0}$ and $\big(\pi^n(b)\big)_{n\ge 0}$ generate all odd length 
palindromes, and the sequence $\big(\pi^n(aa)\big)_{n\ge 0}$ all even length palindromes.

If $\alpha$ is a word, then $'\!\alpha'$ represents the word which is obtained from $\alpha$ 
by erasing its  first and last letter. More generally, 
${}^{m}{}'\!\alpha{}{'^m}$ is obtained from $\alpha$ by erasing its first $m$ and last $m$ letters. 

\begin{algN}{Sturmian-Palindromes($n$)}\inddef{SturmianPalindromes@\textsc{Sturmian-Palindromes}} \label{KZ-SP}
1 \' \key{if} $n$ is even\\
2 \' \quad \key{then}  $n \leftarrow n-1$\\ 
3 \' let  $p$ be the least value for which $\sigma^p(a)$ and $\sigma^p(b)$ are both of odd length\\
4 \'  let define the morphism:  $\pi(a)= \textrm{conj}\big(\sigma^p(a)\big)$ and 
$\pi(b)= \textrm{conj}\big(\sigma^p(b)\big)$\\
5 \'  $\alpha\leftarrow a$         \\
6 \'  \key{while} \= $|\alpha| < n$         \\
7 \'              \> \key{do}  \= $\alpha\leftarrow \pi(\alpha)$  \\
8 \'  $m\leftarrow (|\alpha|-n)/2 $\\
9 \'  $\alpha\leftarrow {}^{m}{}'\!\alpha{}{'^m}$  \\
10 \'  $\beta\leftarrow b$         \\
11 \'  \key{while} \= $|\beta| < n$         \\
12 \'              \> \key{do}  \= $\beta\leftarrow \pi(\beta)$  \\
13 \'  $m\leftarrow (|\beta|-n)/2 $\\
14 \'  $\beta\leftarrow {}^{m}{}'\!\beta{}{'^m}$  \\
15 \'  \key{repeat} \= \key{print} $\alpha, \beta$  \` $\rhd$ Printing odd length palindromes.\\ 
16 \'               \>  $\alpha \leftarrow '\!\!\alpha'$    \\
17 \'               \>  $\beta \leftarrow '\!\!\beta'$  \\
18 \'  \key{until}   $\alpha=\varepsilon$ and  $\beta=\varepsilon$\\
19 \'  $\gamma\leftarrow aa$  \\
20 \'  \key{while} \= $|\gamma| < n+1$         \\
21 \'              \> \key{do}  \= $\gamma\leftarrow \pi(\gamma)$  \\
22 \'  $m\leftarrow (|\gamma|-n-1)/2 $\\
23 \'  $\gamma\leftarrow {}^{m}{}'\!\gamma{}{'^m}$  \\
24 \'  \key{repeat} \= \key{print} $\gamma$     \` $\rhd$ Printing even length palindromes.\\
25  \'                  \>  $\gamma \leftarrow '\!\!\gamma'$     \\
26 \'  \key{until}  $\gamma=\varepsilon$  \\
\end{algN}

Because any substitution requires no more than $cn$ steps, where $c$ is a constant, the algorithm is a linear one.   

In the case of  the Fibonacci word\index{Fibonacci word} the morphism $\sigma$ is defined by 

$\sigma(a)=ab,$
$\sigma(b)=a,$

\noindent and because

$\sigma(a)=ab,$ $\sigma^2(a)=aba,$ $\sigma^3(a)=abaab,$ $|\sigma^3(a)|=|abaab|=5,$

$\sigma(b)=a,$ $\sigma^(b)=ab,$ $\sigma^3(b)=aba,$ $|\sigma^3(b)|=|aba|=3,$ 

\noindent both being odd numbers, $p$ will be equal to 3.
 
 The word $abaab$ is not a palindrome, and for the morphism $\pi$ we will use the adequate conjugate $ababa,$ 
 which is a palindrome. 
 
In this case the morphism $\pi$ is defined by 

$\pi(a)=ababa,$

$\pi(b)=aba.$

\noindent For example, if $n=14$, the following are obtained:

$\pi^2(a)=ababa\,aba\,ababa\,aba\,ababa,$ and then $\alpha= aabaababaabaa,$

$\pi^2(b)=ababa\,aba\,ababa,$ and  $\beta= ababaabaababa,$

$\pi^3(aa)= ababaabaababaabaababaababaabaababaabaababa$, and 

$\gamma= baababaababaab$.  

\begin{minipage}[t]{6.5cm}
\noindent  The odd palindromes obtained are: 

\medskip
 $aabaababaabaa,$ \quad   $ababaabaababa,$
 
 $abaababaaba,$   \quad\quad   $babaabaabab,$ 
 
 $baababaab,$     \quad\quad\quad  $abaabaaba,$ 
 
 $aababaa,$       \quad\quad\quad\quad  $baabaab,$ 
 
 $ababa,$         \quad\quad\quad\quad\quad    $aabaa,$ 
 
 $bab,$           \quad\quad\quad\quad\quad\quad  $aba,$ 
 
 $ a,$            \quad\quad\quad\quad\quad\quad\quad   $b,$ 
\end{minipage}
\begin{minipage}[t]{6.5cm}
\noindent  The even palindromes obtained are:

\medskip
$baababaababaab$,

$aababaababaa$,

$ababaababa,$ 

$babaabab, $ 

$abaaba, $ 

$baab, $ 

$aa. $
\end{minipage}

\begin{fld}
\ujfld{Generating function 1}% 
{Let $b_{n,d}$  denote  the  number  of
 sequences of length $n$ of zeros and ones, in which the first and last
position  is 1, and the number of adjacent zeros is at most $d-1.$
Prove that the generating function corresponding to $b_{n,d}$ is
\[
B_{d}(z) = \sum_{n\ge 0}^{}{b_{n,d}z^n} =\frac{z(1-z)}{1-2z+z^{d+1}}\koz.  \]
\emph{Hint.} See Subsection \ref{subsectionrainbow}.)}
\ujfld{Generating function 2}%
{Prove that the generating function of $N(n,d)$, the number of all $(1,d)$-subwords 
of a rainbow word of length $n$, is
\[ N_d(z)=\sum_{n\ge 0}^{}{N(n,d)z^n} = \frac{z}{(1-z)(1-2z+z^{d+1})}\]
(\emph{Hint.} (See Subsection \ref{subsectionrainbow}.)}
\ujfld{Window complexity}%
{Compute the window complexity of the infinite Fibonacci word.}
\ujfld{Circuits in De Bruijn graphs}%
{Prove that in the De Bruijn graph\felindex{De Bruijn graph} $B(q,m)$ 
there exist circuits\felindex{circuit} (directed
cycles)\felindex{directed cycle} of any length from 1 to $q^m$.}
\end{fld}


\begin{fejmegj}
The basic notions and results on combinatorics of words are given in Lothaire's 
\cite{Lothaire05,Lothaire97,Lothaire02} and Fogg's books \cite{Fogg02}. 
Neither Lothaire nor Fogg is a single author, they are pseudonyms of groups of authors.
A chapter on combinatorics of words  written by Choffrut and Karhum\"aki \cite{Choffrut1997} 
appeared in a handbook on formal languages. 

The different complexities are defined as follows: 
total complexity in Iv\'anyi \cite{Ivanyi1987},\nevindex{Iványi, Antal Miklós} 
maximal\index{maximal complexity} and total\index{total maximal complexity} 
maximal complexity in Anisiu, Bl\'azsik, K\'asa 
\cite{Anisiu02},\nevindex{Anisiu, Mira-Cristiana}\nevindex{Bl\'azsik, Zolt\'an}\nevindex{K\'asa, Zolt\'an}
$(1,d)$-complexity in Iv\'anyi \cite{Ivanyi1987}\nevindex{Iványi, Antal Miklós} 
(called  $d$-complexity) and used also 
in K\'asa \cite{Kasa98}),\nevindex{K\'asa, Zolt\'an} $(d,n-1)$-complexity 
(called super-$d$-complexity) in K\'asa \cite{Kasa10},
scattered complexity in K\'asa \cite{Kasa11}, 
factorization complexity in Ilie \cite{Ilie06} and 
window complexity in Cassaigne, Kabor\'e, Tapsoba \cite{Cassaigne10}.\nevindex{Cassaigne, Julien}

The power word,\index{power word} lower/upper maximal/total complexities are defined 
in Ferenczi, K\'asa \cite{Ferenczi99}. In this paper a characterization of Sturmian words\index{Sturmian word} 
by upper maximal and upper total complexities (Theorem \ref{T26.12}) is also given. 
The maximal complexity of finite words is studied in Anisiu, Bl\'azsik, K\'asa \cite{Anisiu02}.  
The total complexity of finite words is described in K\'asa \cite{Kasa98}, 
where the results of the Theorem \ref{KZLeve} is conjectured too, and proved later by 
Lev\'e and S\'e\'ebold \cite{Leve01}.
\nevindex{Lev\'e, Florence}\nevindex{S\'e\'ebold, Patrice}

Different generalized complexity measures of words are defined and studied 
by Iv\'anyi\nevindex{Iványi, Antal Miklós} \cite{Ivanyi1987} and 
K\'asa\nevindex{Kása, Zoltán} \cite{Kasa98,Kasa10,Kasa11}. 

The results  on palindrome complexity are described in M.-C. Anisiu, 
V. Anisiu, K\'asa \cite{Anisiu10}  
 for finite words, and in Droubay, Pirillo \cite{Droubay99} for infinite words. 
 The algorithm for palindrome generation in Sturmian words\index{Sturmian word} is from this paper too.\nevindex{Anisiu, Valeriu}
 
Applications of complexities in social sciences are given in  Elzinga \cite{Elzinga08,Elzinga10}, 
and in biology in Troyanskaya et al. \cite{Troyanskaya02}. \nevindex{Elzinga, Cees H.}
 
It is worth to consult other papers too, such as  \cite{Arnoux94,Cassaigne1997,Aldo99,Ferenczi1999a,Shallit93}  
(on complexity problems) and \cite{Allouche03,Baake99,Berthe01,Borel05,Brlek04,Damanik00,I2010} (on palindromes).    
\end{fejmegj}

\bibliography{AlgofInf3-2March}
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}

