\documentclass[draft]{adm-paper}
\usepackage{amsfonts,amsmath,amsthm,amscd,amssymb,latexsym}
\usepackage{graphicx}
\graphicspath{{./graphics/}}
\usepackage{tikz}
\begin{document}

\title{The growth function of the adding machine}%Paper title
\author{Volodymyr Skochko}%Authors names
\shorttitle{}%Short paper title for the headers
\shortauthor{V. Skochko}%Short authors names for the headers
\address[V.~Skochko]{Department of Mechanics and Mathematics,
Kyiv National Taras Shevchenko Univ.,
Volodymyrska str., 64, 01033 Kyiv, Ukraine}{vovaskochko@gmail.com} {}%www.fauthor.domain.com



%\communicated{Communicated person}

\research% Type of the paper. \survey command may be used also.

\date{29.09.2016}

%Change theorem environments according to your needs...
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\theoremstyle{definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}


\newcommand{\States}{{\rm States}}
\newcommand{\inv}{\textit{i}}
\newcommand{\Aut}{\textrm{Aut}}
\newcommand{\Sym}{\textrm{Sym}}



\thanks{The author would like to thank his advisor Ievgen Bondarenko for his help, guidance and time spent during discussions and corrections of this article.}

\maketitle

\begin{abstract}
We compute the growth function of the generalized adding machine and show that its generating function is not algebraic.
\end{abstract}
\subjclass{2010}{20M35, 68Q70}

\keywords{automaton, growth function, adding machine}

%68Q70  Algebraic theory of languages and automata
%20M05  Free semigroups, generators and relations, word problems
%20M35  Semigroups in automata theory, linguistics, etc.
%68Q45  Formal languages and automata




\section*{Introduction}

Abstract automata are mathematical models of machines and computational processes. There are many classes of automata, and in this paper we consider (initial) automata-transducers, which generate an output string depending on an input string. Therefore, automata-transducers generate transformations of words over alphabet. The standard question is how to realize a given transformation by an automaton, and what is the minimal number of states required for such implementation.

Another problem is to find for a given automaton transformation $f$ the minimal number of states required
to implement composition $f^{(n)}=f\circ f\circ\ldots\circ f$ ($n$ times). In order to solve this problem
we have to understand the behavior of the growth function $\gamma_A(n)$ of an (initial) automaton $A$,
which counts the number of states in the $n$-th iteration of $A$ after its minimization. Note that here we
should deal with automata with fixed initial state, while the theory of automaton groups deals with groups
generated by all transformations obtained by changing the initial state of a given automaton. In this
case, the growth function of an automaton counts the number of different elements of length $n$ in the
semigroup generated by this automaton. We have a connection with growth of groups which has essential
influence in both group theory and automata theory. The most spectacular example is the automaton group of
Grigorchuk \cite{Gr:Intermed}, which was the first example of a group of intermediate growth between
polynomial and exponential. Later, Bartholdi, Reznykov, and Sushchansky constructed the smallest automaton
with intermediate growth function \cite{SmallestMealy} and many examples of automata with polynomial
growth of irrational degree \cite{PolyMealy}. The growth function of automata plays important role in
decision problems around automaton group: see \cite{B:GrowthSchreier,B:Hanoi} for applications to the word
problem and \cite{BBSZ} for the order and conjugacy problems.



%A finite initial automaton is a model which realizes some map on the words over a fixed finite set. Naturally it %appears the question about "minimal" realization for the given map e.g. automaton with the minimal number of states.


%The growth function of the automaton $a$ can be introduced as the function which counts the number of states in minimized automaton for $n$-th iteration of $a$. The growth function shows what minimal amount of states we need to implement $n$-th power of the given map.

%Bartholdi-Reznykov-Sushchansky studied the growth of automata. Also they give some estimations for the growth type for %some Mealy automata(e.g. power coefficients and asymptotic).

In this paper we consider the growth function of initial automata, namely, the generalized adding machine.
The standard adding machine (odometer) realizes addition of one to binary numbers. Therefore, its growth
function $\gamma(n)$ counts the minimal number of states required to realize an automaton that adds $n$ to
binary numbers. We consider a generalized version of the adding machine and give an exact formula for its
growth function. As a corollary, we obtain that the generating function of the growth function is
algebraic only in the trivial cases.


%growth of automata, relation to growth of groups (Grigrochuk, the first example of a group of intermediate growth between polynomial and exponential)

%Bartholdi-Reznikov

%initial automata, adding machine


\section{Automata and their growth functions}

\begin{definition}
An \textit{automaton} $A$ is a tuple $(X,S,\lambda)$, where $X$ is a finite set (alphabet) with at least two elements, $S$ is the set of states, and $\phi:S\times X\rightarrow X\times S$ is the output-transition map.
\end{definition}

An automaton $A=(X,S,\lambda)$ is usually identified with the directed labeled graph with the vertex set
$S$, where an arrow $s\rightarrow t$ with label $x|y$ exists if and only if $\lambda(s,x)=(y,t)$. We say
that a state $t$ is \textit{reachable} from a state $s$ if there is a directed path in $A$ from $s$ to
$t$. If the labels $x_1|y_1$, $x_2|y_2$,\ldots $x_n|y_n$ are read along this path, then we use notation
$t=s|_{x_1x_2\ldots x_n}$. We also say that $t$ is a (sub)state of $s$ at the $n$-th level.


The \textit{composition} of automata $A=(X,S_1,\lambda_1)$ and $B=(X,S_2,\lambda_2)$ is the automaton $A\circ B=(X,S_1\times S_2,\lambda_3)$, where $\lambda_3$ is defined as follows. Let $\lambda_2(s_2,x)=(z,t_2)$, $\lambda_1(s_1,z)=(y,t_1)$ then
\[
\lambda_3((s_1,s_2),x)=(y, (t_1,t_2) ).
\]

\begin{definition}
An automaton $A$ with fixed state $s\in S$ is called \textit{initial} and is denoted by $A_s$.
\end{definition}

Every initial automaton $A_s$ defines a transformation of the space $X^{*}$ of all finite words over $X$. The output $A_s(x_1x_2\ldots x_n)$ is defined recursively as follows:
\[
A_s(x_1x_2\ldots x_n)=y_1y_2\ldots y_n
\]
if $\lambda(s,x_1)=(y_1,t)$ and $A_t(x_2\ldots x_n)=y_2\ldots y_n$. Informally speaking, the initial
automaton reads the input word letter by letter, generates an output letter depending on the current
state, and changes its current state according to the transition map. Note that the terminal state of
$A_s$ after processing a word $x_1x_2\ldots x_n$ is $s|_{x_1x_2\ldots x_n}$.

%In other words, in order to compute the output $A_s(x_1x_2\ldots x_n)$ we can follow the unique path in the graph representation of $A$ that starts at the state $s$ and is labeled by pairs $x_1|y_1$, $x_2|y_2$,\ldots, $x_n|y_n$; then, $y_1y_2\ldots y_n$ is the output.


The composition of two initial automata $A_s$ and $B_t$ over the alphabet $X$ is the initial automaton $(A\circ B)_{(s,t)}$. It is easy to see that the composition of automata agrees with the composition of transformations:
\[
(A_s\circ B_t)(x_1x_2\ldots x_n)=(A\circ B)_{(s,t)}(x_1x_2\ldots x_n) \ \mbox{ for all $x_i\in X$, $n\in \mathbb{N}$}.
\]

Different states of an automaton may define the same transformation of $X^{*}$. The following concept eliminates this difficulty.

\begin{definition}
Two automata $A$ and $B$ over the same alphabet $X$ are called equivalent if for every state $s$ of $A$ there exists a state $t$ of $B$ such that the transformations defined by $A_s$ and $B_{t}$ are equal, and vise versa.

The minimal automaton $Min(A)$ is an automaton equivalent to $A$ with the property that different states define different transformations.

For an initial automaton $A_s$, its minimal automaton $Min(A_s)$ is a subautomaton of $Min(A)$ with initial state $t$, where $A_s$ and $Min(A)_t$ define the same transformation, and every state of $Min(A_s)$ is reachable from $t$.
\end{definition}

Note that for finite automata the minimal automaton $Min(A)$ has the least number of states required to realize all transformations defined by the states of an automaton $A$. The automaton $Min(A_s)$ has the least number of states required to realize the transformation $A_s$.

\begin{definition}
The growth function of an initial automaton $A_s$ is defined as the function which counts the number of states in the minimized $n$-th power of $A_s$, e.g.
\[
\gamma_{A_s}(n)=\gamma_s(n)=\#States(Min(A_s^{(n)})), \ n\in\mathbb{N},
\]
where $A_s^{(n)}=A_s\circ\ldots\circ A_s$ ($n$ times).
\end{definition}



In other words, if we take the automaton $Min(A^{(n)})$ and its state $s^n=(s,\ldots,s)$ ($n$ times),
which corresponds to $n$-th time iteration of $A_s$, then the growth function $\gamma_{A_s}(n)$ counts the
number of all states $s^n|_v$ for $v\in X^{*}$ in $Min(A^{(n)})$.

%\[
%\gamma_{A_s}(n)=\#\{ s^n|_v : v\in X^{*} \}.
%\]

One of the classical examples of automata is the adding machine.

\begin{definition}
The \textit{adding machine on $d$ digits} is the initial automaton over the alphabet $X=\{0,1,\ldots,d-1\}$ with two states $S=\{e,a\}$, initial state $a$, where the output-transition map is defined by
\begin{eqnarray*}
\lambda(e,x)&=&(x,e) \ \mbox{ for all $x\in X$},\\
\lambda(a,x)&=&\left\{
             \begin{array}{ll}
               (0,a), & \hbox{ if $x=d-1$;} \\
              (x+1,e), & \hbox{ otherwise.}
             \end{array}
           \right.
\end{eqnarray*}
We denote the adding machine by $a$.
\end{definition}

The state $e$ defines the trivial transformation, while the transformation defined by the state $a$ corresponds to the addition of $1$ in the position numeral system with base $d$. In other words $a(x_1x_2\ldots x_n)=y_1y_2\ldots y_n$ if and only if
\[
1+x_1+x_2d+\ldots +x_nd^{n-1}\equiv y_1+y_2d+\ldots +y_nd^{n-1}\bmod{d^n}
\]
for all $n\in\mathbb{N}$. Hence, the growth function $\gamma_a(n)$ gives us the minimal number of states required to construct the automaton that realizes the addition of $n$ to numbers written in base $d$.

In this paper we consider the following generalization of the adding machine.

\begin{definition}
For every permutation $\pi$ on the alphabet $X=\{0,...,d-1\}$ the \textit{generalized adding machine} is defined as the initial automaton over $X$ with two states $S=\{e,a_{\pi}\}$ and initial state $a_{\pi}$, where the output-transition map
is defined by
\begin{eqnarray*}
\lambda(e,x)&=&(x,e) \ \mbox{ for all $x\in X$},\\
\lambda(a_{\pi},x)&=&\left\{
             \begin{array}{ll}
              (\pi(d-1),a_{\pi}), & \hbox{ if $x=d-1$;} \\
              (\pi(x),e), & \hbox{ otherwise.}
             \end{array}
           \right.
\end{eqnarray*}
\end{definition}




\section{Main results}

First we compute the growth function of the standard adding machine.

\begin{theorem}
    The growth function $\gamma(n)$ of the adding machine $a$ on $d$ digits can be computed as follows. Let
    $n=\varepsilon_0+\varepsilon_1d+\ldots+\varepsilon_m d^m$ be the expansion of $n$ in base $d$ and $p$ be the
    first non-zero position.
    \begin{enumerate}
        \item If $d > 2$ then
        \[
        \gamma(n)=\left\{
        \begin{array}{cc}
        2m-p+2, &\mbox{if $\varepsilon_m=1$;}\\
        2m-p+3, &\mbox{otherwise.}
        \end{array}
        \right.
        \]
        \item If $d = 2$ then
        \[
        \gamma(n)=\left\{
        \begin{array}{cl}
        2m-p+2, &\mbox{if $\varepsilon_{m-1}=1$ or p=m;}\\
        2m-p+1, &\mbox{otherwise.}
        \end{array}
        \right.
        \]
    \end{enumerate}
\end{theorem}

\begin{proof}
    Each state of $a^n$ is of the form $a^i$ for some $0\leq i\leq n$, and since the adding machine has
    infinite order, $a^i=a^j$ only when $i=j$. Let $A(n)$ be the set of all nonnegative integers $i$ such that
    $a^i$ is a state of $a^n$. Then $\gamma(n)$ counts the number of elements in $A(n)$. We show how to
    construct $A(n)$ iteratively and then conclude the result.

    %We denote the current state after processing a word $u\in X^*$ on $a$ as $a|_{u}$.
    Let us divide $n$ by $d$ with reminder: $n=dq+r$, $0\leq r < d$. Then the states of $a^n$ on the first
    level are
    \begin{equation}\label{eqn_states_an}
    a^{n}|_x=\left\{%
    \begin{array}{ll}
    a^{q+1}, & \hbox{for $x=0,\ldots,r-1$;} \\
    a^q, & \hbox{for $x=r,\ldots,d-1$.} \\
    \end{array}%
    \right.
    \end{equation}
    Notice that $q<q+1<n$ for all $n$ and $d$, except for $n=d=2$ when $q+1=n$. The above rule suggests an
    iterative construction of the set $A(n)$. Let $A_k(n)$ consists of all integers $i$ such that
$a^n|_v=a^i$ for some word $v\in X^{k}$; we have $A(n)=\cup_{k\geq 0} A_k(n)$. The equation (\ref{eqn_states_an}) tells us that one can construct $A_{k+1}(n)$ from $A_k(n)$ as follows: for every number $y\in A_k(n)$, if $d$ divides $y$, then put $\left[\frac{y}{d}\right]$ into $A_{k+1}(n)$; otherwise put two numbers  $\left[\frac{y}{d}\right]$ and $\left[\frac{y}{d}\right]+1$. Since each time we divide by $d$, it is direct to get the following properties of $A_k(n)$ by induction:
    \begin{enumerate}
        \item[1)] $A_k(n)=\left\{\left[\frac{n}{d^k}\right]\right\}$ for $k=0,1,\ldots,p$;
        \item[2)] $A_k(n)=\left\{\left[\frac{n}{d^k}\right],\left[\frac{n}{d^k}\right]+1\right\}$ for $k=p+1,\ldots,m-1$;
        \item[3)] $A_k(n)$ are disjoint for $k=0,1,\ldots,m-1$;
        \item[4)] $A(n)=A_0(n)\cup A_1(n)\cup\ldots\cup A_{m+1}(n)$;
    \end{enumerate}
    The last two sets in the union may have non-empty intersection and must be considered more carefully.
    \begin{enumerate}
        \item[5)] If $p=m$ then in this case $n=\varepsilon_m d^m$ and $\varepsilon_m\neq 0$. So we get $A_k(n)=\{\varepsilon_m d^{m-k}\}$ for $k=0,1,\ldots,m$ and $A_{m+1}(n)=\{0,1\}$. Therefore, $A_{m}(n)\cup A_{m+1}(n)=\{0,1,\varepsilon_m\}$ and its cardinality is equal to $2$ or $3$ depending on whether $\varepsilon_m$ is equal to $1$ or not.
    \end{enumerate}
    %If $s\leq m-1$ then we consider two cases depending on $d$.

    %If $s=m-1$ (this means $n=\varepsilon_{m-1} d^{m-1}+\varepsilon_m d^m$), then $A_k(n)=\{\varepsilon_{m-1} d^{m-1-k}+\varepsilon_m d^{m-k}\}$ for $k=0,1,\ldots,m-1$ and $A_{m}(n)=\{\varepsilon_m,\varepsilon_m+1\}$, $A_{m+1}(n)=\{0,1\}$. Therefore, $A_{m}(n)\cup A_{m+1}(n)=\{0,1,\varepsilon_m,\varepsilon_m+1\}$ and its cardinality is $3$ or $4$ depending on whether $\varepsilon_m$ is equal to $1$ or not.

    %
    %it is easy to calculate the growth function immediately from $1)-4)$ and construction algorithm. But in case when $s<m-1$  We handle them in the next items:

    \begin{enumerate}
        \item[6)]If $p\leq m-1$ and $d>2$, then $$A_m(n)\cup A_{m+1}(n)=\{0,1,\varepsilon_{m},\varepsilon_{m}+1\}$$ and this set is disjoint with $A_k(n)$ for $k<m$ (note that the cardinality of the union is $3$ or $4$ depending on whether $\varepsilon_m$ is equal to $1$ or not).
    \end{enumerate}
    Indeed, in this case
    \[
        A_{m-1}(n)=\left\{
        \begin{array}{ll}
        \{[\frac{n}{d^{m-1}}]\}, &\mbox{if $p=m-1$;} \\
        \{[\frac{n}{d^{m-1}}], [\frac{n}{d^{m-1}}]+1\}, &\mbox{if $p < m-1$.}
        \end{array}
        \right.
        \]
    and $\left[\frac{n}{d^{m-1}}\right]>\left[\frac{n}{d^m}\right]+1$.

    Therefore, $A_m(n)=\{[\frac{n}{d^{m}}], [\frac{n}{d^{m}}]+1\}=\{\varepsilon_{m}, \varepsilon_{m}+1\}$ and it is disjoint with $A_{k}(n)$ for $k<m$. But $1\leq\varepsilon_{m}<\varepsilon_{m}+1\leq d$. Hence, $A_{m+1}(n)=\{0,1\}$ by construction and we get $A_m(n)\cup A_{m+1}(n)=\{0,1,\varepsilon_{m},\varepsilon_{m}+1\}$.

    \begin{enumerate}
        \item[7)] If $p\leq m-1$ and $d=2$, then $A_m(n)\cup A_{m+1}(n)=\{0,1,2\}$. However, this set may have a non-empty intersection with $A_{m-1}(n)$; this happens exactly in the case $\varepsilon_{m-1}=0$ when $2\in A_{m-1}(n)$.
    \end{enumerate}
    In this case $\varepsilon_{m}=1$ and $[\frac{n}{2^{m-1}}]=2\varepsilon_{m}+\varepsilon_{m-1} = 2+\varepsilon_{m-1}$. Therefore,
    \[
    A_{m-1}(n)=\left\{
    \begin{array}{ll}
    \{3\}, &\mbox{if $p=m-1$;} \\
    \{3,4\}, &\mbox{if $\varepsilon_{m-1}=1$, $p\neq m-1$;}\\
    \{2,3\}, &\mbox{otherwise.}
    \end{array}
    \right.
    \]
    In any case we have $A_{m}(n)= \{1,2\}$ and $A_{m+1}(n)=\{0, 1\}$. So we get that $A_{m}(n) \cup A_{m+1}(n)=\{0, 1, 2\}$.

    The value of the growth function $\gamma(n)$ immediately follows from items 1)-7).
\end{proof}




\begin{corollary}
    Let $a_{\pi}$ be the generalized adding machine on $d$ digits with $\pi\in\Sym(X)$.
    \begin{enumerate}
        \item If $\pi(d-1)=d-1$, then $a_{\pi}$ has finite order $|a_{\pi}|=|\pi|$ and its growth function is
        periodic.

        \item If $\pi(d-1)\neq d-1$, then $\gamma_{a_{\pi}}(n)$ coincides with the growth function of the standard adding machine
        on $l$ digits, where $l$ is the length of the orbit of $1$ under $\pi$. More precisely, let
        $n=\varepsilon_0+\varepsilon_1l+\ldots+\varepsilon_m l^m$ be the expansion in base $l$ of $n$ and
        $p$ be the first non-zero position. Then
        \begin{enumerate}
            \item if $l > 2$ then
            \[
            \gamma_{a_{\pi}}(n)=\left\{
            \begin{array}{cc}
            2m-p+2, &\mbox{if $\varepsilon_m=1$;}\\
            2m-p+3, &\mbox{otherwise.}
            \end{array}
            \right.
            \]
            \item if $l = 2$ then
            \[
            \gamma_{a_{\pi}}(n)=\left\{
            \begin{array}{cc}
            2m-p+2, &\mbox{if $\varepsilon_{m-1}=1$ or p=m;}\\
            2m-p+1, &\mbox{otherwise.}
            \end{array}
            \right.
            \]
        \end{enumerate}
    \end{enumerate}
\end{corollary}
\begin{proof}
    1. If $\pi(d-1)=d-1$, then $a_{\pi}$ changes only the first letter not equal to $d-1$ by $\pi$. Hence, $a_{\pi}^k=e$, where $k$ is the order of $\pi$.

    2. Without loss of generality we can suppose that the orbit of $d-1$ under $\pi$ corresponds to the cycle $\tau = (d-l,...,d-1)$. Then the subtree $\{d-l,\ldots,d-1\}^*$ of $X^{*}$ is invariant under the action of $a_{\pi}$ and the restricted action is exactly the standard adding machine on $l$ letters. Therefore, $a_{\pi}^n$ has the same states at words from $\{d-l,\ldots,d-1\}^*$ as the standard adding machine. For a word $v$ not in $\{d-l,\ldots,d-1\}^*$ (here $v$ contains a letter $x\not\in \{d-l,\ldots,d-1\}$), we have $a_{\pi}^n|_v=e$. The statement follows.
\end{proof}

\begin{corollary}\label{cor_growth_coeff_estim}
    The growth function of the generalized adding machine $a_{\pi}$ on $d$ digits for $\pi(d-1)\neq d-1$ satisfies
    \[
    \left[\frac{\log n}{\log l}\right] + 2 \leq \gamma(n)\leq 2\left[\frac{\log n}{\log l}\right]+c_d \mbox{ for all $n\geq 1$},
    \]
    where $c_d=2$ for $d=2$ and $c_d=3$ for $d>2$. Moreover, the lower and the upper bounds are reached for infinitely many values of $n$.
\end{corollary}

Let us recall that the \textit{generating function} of a function $\gamma:\mathbb{N}\cup\{0\}\rightarrow\mathbb{N}$ is the formal power series $\Gamma(t)=\sum_{n\geq 0}\gamma(n)t^n$. A formal power series is called \textit{algebraic} if it is algebraic over the field of rational functions.

\begin{corollary}
    Let $a_{\pi}$ be the generalized adding machine on $d$ digits. The generating function of
    $\gamma_{a_{\pi}}(n)$ is algebraic if and only if $\pi(d-1)=d-1$; moreover, in this case the generating
    function is rational.
\end{corollary}
\begin{proof}
    If $\pi(d-1)=d-1$, then the growth function of $a_{\pi}$ is periodic and its generating function is rational.

    The coefficients of an algebraic power series $\sum_{n\geq 0} c_nt^n$ have asymptotic of the type $c_n\sim Cn^\alpha A^n$ (see theorem VII.8 \cite{FlajSedj:AC}) and cannot be of logarithmic growth as in Corollary~\ref{cor_growth_coeff_estim}.
\end{proof}


\begin{corollary}
    The growth function of the standard adding machine has non-algebraic generating function.
\end{corollary}

%\section*{Conclusion}
%In this article we found the exact formula for the growth function of the generalized adding machine.


%\section*{Acknowledgments}




\begin{thebibliography}{20}

    \bibitem{SmallestMealy}
    L. Bartholdi, I. I. Reznykov, V. I. Sushchansky,
    \newblock \textit{The smallest Mealy automaton of intermediate growth},
    J. Algebra 295 (2006), no. 2, 387--414.

    \bibitem{PolyMealy}
    L. Bartholdi, I. I. Reznykov,
    \newblock \textit{A Mealy machine with polynomial growth of irrational degree},
    Internat. J. Algebra Comput. 18 (2008), no. 1, 59--82.

    \bibitem{B:GrowthSchreier}
    I. Bondarenko,
    \newblock \textit{Growth of Schreier graphs of automaton groups},
    Mathematische Annalen 354 (2012), no. 2, 765--785.

    \bibitem{B:Hanoi}
    I. Bondarenko,
    \newblock \textit{The word problem in Hanoi Towers groups},
    Algebra and Discrete Mathematics 17 (2014), no. 2, 248--255.

    \bibitem{BBSZ}
    I. Bondarenko, N.Bondarenko, S.Sidki, F.Zapata,
    \newblock \textit{On the conjugacy problem for finite-state automorphisms of regular rooted
trees} (with an appendix by Raphael M. Jungers),
    Groups, Geometry, and Dynamics 7 (2013), no. 2, 323--355.

	\bibitem{FlajSedj:AC}
	Ph. Flajolet, R. Sedgewick,
	\textit{Analytic combinatorics}, Cambridge University Press, 2009.

    \bibitem{Gr:Intermed}
    R. I. Grigorchuk,
    \newblock \textit{On the Milnor problem of group growth},
    Dokl. Akad. Nauk SSSR 271 (1983), no. 1, 30-33.

    \bibitem{GNS:ADG}
    R.I. Grigorchuk, V.V. Nekrashevych, V.I.~Sushchansky,
    \newblock Automata, dynamical systems and groups,
    \newblock \textit{Proceedings of the Steklov Institute of Mathematics} \textbf{231} (2000), 128--203.



\end{thebibliography}

\end{document}
