\documentclass[12pt,reqno]{article}
\usepackage{amsmath,amssymb,amsthm,graphicx}
\usepackage[all]{xy}
\usepackage{fullpage}
\usepackage[usenames]{color}
\usepackage{amscd}
\usepackage[margin=3cm,top=4cm,footskip=2cm,nohead]{geometry}
\usepackage{psfig}
\usepackage{epsf}
\usepackage[colorlinks=true,
linkcolor=webgreen, filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newcommand\A{{\mathcal{A}}}
\newcommand\treek{{X_k^*}}
\newcommand\Ht{{\mathcal H^{(3)}}}
\newcommand\llim{{\underset{n \to \infty}{\lim}}}
\begin{document}
\begin{center}
\epsfxsize=4in \leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm
{\LARGE\bf Rational Tree Morphisms and Transducer\\ \vskip .1in
Integer Sequences: Definition and Examples}
\vskip 1cm \large
Zoran {\v S}uni{\'c} \footnote{Partially supported by NSF grant DMS-0600975.}\\
Department of Mathematics\\ Texas A\&M University\\ College Station, TX 77843-3368
\\ USA\\
\href{mailto:sunic@math.tamu.edu}{\tt sunic@math.tamu.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
The notion of transducer integer sequences is considered through a
series of examples (the chosen examples are related to the Tower of Hanoi
problem on 3 pegs). By definition, transducer integer
sequences are integer sequences produced, under a suitable
interpretation, by finite transducers encoding rational tree
morphisms (length and prefix preserving transformations of words
that have only finitely many distinct sections).
\end{abstract}
\section{Introduction}
It is known from the work of Allouche, B\'etr\'ema, and Shallit
(see~\cite{allouche-b-s:hanoi,allouche-s:as}) that a squarefree
sequence on 6 letters can be obtained by encoding the optimal
solution to the standard Tower of Hanoi problem on 3 pegs by an
automaton on six states. Roughly speaking, after reading the binary
representation of the number $i$ as input word, the automaton ends
in one of the 6 states. These states represent the six possible
moves between the three pegs; if the automaton ends in state
$q_{xy}$, this means that the one needs to move the top disk from
peg $x$ to peg $y$ in step $i$ of the optimal solution. The obtained
sequence over the 6-letter alphabet $\{\ q_{xy} \mid 0 \leq x,y \leq
2, \ x \neq y \ \}$ is an example of an automatic sequence.
We choose to work with a slightly different type of automata, which
under a suitable interpretation, produce integer sequences in the
output. The difference with the above model, again roughly speaking,
is that not only the final state matters, but the output depends on
every transition step taken during the computation and both the
input and the output words are interpreted as encodings of integers.
The integer sequences that can be obtained this way are called
transducer integer sequences. We provide some examples that
illustrate the notion of a transducer integer sequence. The chosen
examples are related to the Tower of Hanoi problem on 3 pegs, but one
could certainly provide and study a variety of different examples.
The choice was guided by the need for relatively familiar and
appealing setting that is, at the same time, mathematically
challenging and interesting.
In recent years, a very fruitful line of research in group theory
has led to the notion of a self-similar
group~\cite{nekrashevych:b-selfsimilar} (also known as automata
groups~\cite{grigorchuk-n-s:automata} or state closed
groups~\cite{sidki:circuit}). Many challenging problems have been
solved by using finite automata to encode groups of tree
automorphisms with interesting properties, leading to solutions to
outstanding problems. To name just a few, examples include
first Grigorchuk group~\cite{grigorchuk:burnside}, solving the
problem of Milnor on existence of groups of intermediate growth and
the Day-von Neumann problem on existence of amenable but not
elementary amenable groups; the Basilica
group~\cite{grigorchuk-z:basilica1,bartholdi-v:basilica}, providing
an example of amenable but not subexponentially amenable group;
Wilson groups~\cite{wilson:nonuniform}, solving the problem of
Gromov on existence of groups of non-uniform exponential growth; the
realization of the lamplighter group $L_2$ by an
automaton~\cite{grigorchuk-z:l2}, leading to the solution of the
Strong Atiyah Conjecture on $L^2$-Betti
numbers~\cite{grigorchuk-al:atiyah}, and the recent solution to
Hubbard's twisted rabbit problem in holomorphic
dynamics~\cite{bartholdi-n:rabbit}. The geometric language and
insight coming from the interpretation of the action of the automata
as tree automorphisms greatly simplifies the presentation and helps
in the understanding of the underlying phenomena, such as
self-similarity, contraction, branching, etc
(see~\cite{grigorchuk-n-s:automata,bartholdi-g-s:branch,bartholdi-g-n:fractal,nekrashevych:b-selfsimilar}
for definitions, examples, and details).
In the current article we use automata in the sense of transducers.
As such, they generate self-similar groups (or semigroups) of tree
automorphisms (or endomorphisms). In the same time, the input and
the output words are interpreted as encodings of integers, bringing
the topic closer to the topic of automatic sequences. Thus, it is
not surprising that the concrete examples of transducer integer
sequences that are exhibited here all gave high level of
self-similarity and can be defined as limits of certain iterations
of sequences.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Rational tree morphisms and finite transducers}\label{s:tree}
For $k \geq 2$ denote $X_k=\{0,1,\dots,k-1\}$. The free monoid
$\treek$ has the structure of a $k$-ary \emph{rooted tree} $\treek$
in which the \emph{empty word} $\emptyset$ is the \emph{root}, the
words of length $n$ constitute \emph{level $n$} and each vertex
$v$ has $k$ \emph{children}, namely $vx$, for $x$ a letter in $X_k$
(see Figure~\ref{3tree} for the ternary tree).
\begin{figure}[!ht]
\begin{center}
\[
\xymatrix@C=7pt{
&&&& \emptyset \ar@{-}[llld] \ar@{-}[d] \ar@{-}[rrrd]&
\\
& 0 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] &&
& 1 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] &&
& 2 \ar@{-}[ld] \ar@{-}[d] \ar@{-}[rd] &&
\\
00& 01& 02& 10& 11& 12& 20& 21& 22
\\
\dots& \dots& \dots& \dots& \dots& \dots& \dots& \dots& \dots& }
\]
\caption{Ternary rooted tree}\label{3tree}
\end{center}
\end{figure}
The tree structure imposes order on $X_k^*$, which is the well known
\emph{prefix order}. Namely, we say that $u \leq v$ if $u$ is a
vertex on the unique geodesic from $\emptyset$ to $v$ in $\treek$,
which is equivalent to saying that $u$ is a \emph{prefix} of $v$. A
map $\mu: X_{k_1}^* \to X_{k_2}^*$ is a \emph{tree morphism} if it
preserves the word length and the prefix relation, i.e
\[ |\mu(u)| = |u| \qquad\text{and}\qquad \mu(u) \leq \mu(uw), \]
for all words $u$ and $w$ over $X_{k_1}$. In the case when
$k_1=k_2$, morphisms are called \emph{endomorphisms} and bijective
endomorphisms are called \emph{automorphisms}.
Every tree morphism $\mu:X_{k_1}^* \to X_{k_2}^*$ can be decomposed
as
\[ \mu = \pi_\mu (\mu_0,\dots,\mu_{k_1-1}) \]
where $\pi_\mu:X_{k_1} \to X_{k_2}$ is a map called the \emph{root
transformation} of $\mu$ and $\mu_x: X_{k_1}^* \to X_{k_2}^*$, $x$
in $X_{k_1}$, are tree morphisms called the \emph{sections} of
$\mu$. The root permutation and the sections of $\mu$ are uniquely
determined by the recursive relation
\[ \mu(xw) = \pi_\mu(x) \mu_x(w),\]
which holds for every letter $x$ and word $w$ over $X_{k_1}$. Thus
the sections describe the action of $\mu$ on the $k_1$ subtrees
hanging below the root in $X_{k_1}^*$ and the root transformation
$\pi_\mu$ describes the action of $\mu$ at the root.
The tree morphisms act on the left and the composition is performed
from right to left, yielding the formula
\begin{equation}\label{composition}
\mu \nu = \pi_\mu (\mu_0,\dots,\mu_{k_1-1}) \pi_\nu (\nu_0,\dots,\nu_{k_1-1}) =
\pi_\mu \pi_\nu (\mu_{\pi_\nu(0)}\nu_0, \dots,
\mu_{\pi_\nu(k_1-1)}\nu_{k_1-1}).
\end{equation}
The notion of a section of a tree morphism $\mu:X_{k_1} \to X_{k_2}$
can be recursively extended to all vertices of the tree $X_{k_1}^*$
by setting $\mu_\emptyset = \mu$ and $\mu_{wx} = (\mu_w)_x$, for $w$
a word over $X_{k_1}$ and $x$ a letter in $X$. A tree morphism is
\emph{rational} if it has only finitely many distinct sections.
A quite efficient way of defining rational tree morphisms is by
using finite synchronous transducers. A \emph{finite $k_1$ to $k_2$
synchronous transducer} is a 5-tuple
$\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$, where $Q$ is a finite set of
\emph{states}, $X_{k_1}$ and $X_{k_2}$ are the \emph{input and
output alphabets}, $\tau:Q \times X_{k_1} \to Q$ is a map called the
\emph{transition map} of $\A$, and $\pi:Q \times X_{k_1} \to
X_{k_2}$ is a map called the \emph{output map} of $\A$. Every state
$q$ of the finite transducer $\A$ defines a tree morphism, also
denoted $q$ by setting $q_x=\tau(q,x)$, for $x \in X_{k_1}$, and
$\pi_q: X_{k_1} \to X_{k_2}$ to be the restriction of $\pi$ defined
by $\pi_q(x) = \pi(q,x)$. Thus, for each state $q$ of $\A$ we have
\begin{equation}\label{qxw}
q(\emptyset) = \emptyset \qquad\text{and}\qquad
q(xw) = \pi_q(x)q_x(w),
\end{equation}
for $x$ a letter in $X_k$ and $w$ a word over $X_k$. When started at
state $q$, the transducer reads the first input letter $x$, produces
the first letter of the output according to the transformation
$\pi_q$ and changes its state to $q_x$. The state $q_x$ then handles
the rest of the input and output. The states of a $k$-ary transducer
(transducer in which $k_1=k_2=k$) define $k$-ary tree endomorphisms.
An \emph{invertible} $k$-ary transducer is a transducer in which
$k_1=k_2=k$ and the transformation $\pi_q$ is a permutation of
$X_k$, for each state $q$ in $Q$. The states of an invertible
$k$-ary transducer define $k$-ary tree automorphisms.
When $k_1 \leq k_2$ and, for each state $q$, the vertex
transformation $\pi_q$ is injective then every state of the
transducer $\A$ is an embedding of the $k_1$-ary tree into the
$k_2$-ary tree. We call such a transducer an \emph{injective
transducer}. When $\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$ is injective
transducer one can define a partial inverse transducer $\A^{-1} =
(Q^{-1}, X_{k_2},X_{k_1},\tau^{-1},\pi^{-1})$ in which
$Q^{-1}=\{q^{-1}\mid q\in Q\}$, and $\tau^{-1}:Q^{-1} \times X_{k_2}
\to Q^{-1}$ and $\pi^{-1}:Q^{-1} \times X_{k_2} \to X_{k_1}$ are
partial maps, defined by $\tau^{-1}(q^{-1},y) = p^{-1}$ and
$\pi^{-1}(q^{-1},y)=x$ whenever $\tau(q,x) = p$ and $\pi(p,x)=y$.
For a state $q$ in $Q$ and words $u$ in $X_{k_1}^*$ and $v$ in
$X_{k_2}^*$ we then have
\[ q(u) = v \qquad \text{if and only if} \qquad q^{-1}(v)=u. \]
Moreover, the composition $q^{-1}q: X_{k_1}^* \to X_{k_1}^*$ is the
identity map on $X_{k_1}^*$ and the composition $qq^{-1}:
q(X_{k_1}^*) \to q(X_{k_1}^*)$ is the identity map on the range
$q(X_{k_1}^*)$ of the morphism $q$ in $X_{k_2}^*$. The partial
morphism $q^{-1}$ is not defined at any vertex of $X_{k_2}^*$ that
is not in the range $q(X_{k_1}^*)$ of $q$. For such an input word
$w$, starting at the state $q^{-1}$, the work of the partial inverse
transducer $\A^{-1}$ stops before reading the whole input word,
because not all possible transition steps are defined. In this
sense, the partial inverse transducer may be used to recognize the
range of the injective morphism $q$. Namely, the transducer $\A^{-1}$
\emph{accepts} the word $w$ if and only if it can read it
completely, in which case the output word is precisely $q^{-1}(w)$.
The boundary $\partial \treek$ of the $k$-ary tree $\treek$ consists
of all infinite (to the right) words over $X_k$. The boundary has a
structure of an ultrametric space homeomorphic to a Cantor set. The
recursive definition \eqref{qxw} applies to both finite and infinite
words $w$. The action of a state $q$ of a $k$-ary transducer on the
boundary $\partial \treek$ is by continuous maps, while the action
of an invertible $k$-ary transducer is by isometries.
More on relations between rational morphisms of rooted trees and
transducers can be found in~\cite{grigorchuk-n-s:automata}.
There are two common ways to represent finite $k_1$ to $k_2$
transducers by labeled directed graphs such as the ones in
Figure~\ref{ah-al}. The graph on the left represents an invertible
ternary transducer. The vertices are the states, each state $q$ is
labeled by its corresponding root transformation (in this case
permutation) $\pi_q$, and the edges labeled by the letters from
$X_3$ define the transition function $\tau$ (for every $q$ in $Q$
and $x$ in $X_3$ there exists an edge from $q$ to $q_x=\tau(q,x)$
labeled by $x$). The graph on the right represents a non-invertible
ternary transducer. The vertices are the states and for each pair
$(q,x)$ in $Q \times X_3$ an edge labeled by $x \ | \ \pi_q(x) $
connects $q$ to $q_x$. One can easily switch back and forth between
the two formats. We refer to the second form (the one in which the
output is indicated on the edges) as the \emph{Moore diagram} of the
transducer.
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\SelectTips{cm}{}
\xymatrix@C=45pt@R=45pt{
&
*++[o][F-]{{\scriptstyle(01)}}\ar@/_/[d]_{0}\ar@/^/[d]^{1}\ar@(ul,l)_{2}\ar@{}[ddr]^<<<{a_{01}} &
\\
& *++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0,1,2} \ar@{}[r]^<<<{id}&
\\
*++[o][F-]{{\scriptstyle(02)}}\ar@/_/[ur]_{2}\ar@/^/[ur]^{0}\ar@(ul,l)_{1}\ar@{}[rr]_<<<{a_{02}} &
\A_H &
*++[o][F-]{{\scriptstyle(12)}}\ar@/_/[ul]_{1}\ar@/^/[ul]^{2}\ar@(ur,r)^{0}\ar@{}[ll]^<<<{a_{12}}
}
&
\SelectTips{cm}{}
\xymatrix@C=35pt{
\\ \\
&
*++[o][F-]{}
\ar@/^1pc/[rr]^{2/1} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/1} \ar@{}[l]|<<<<{\textstyle\alpha}
&&
*++[o][F-]{}
\ar@/^1pc/[ll]^{0/1} \ar@(u,ur)^{1/1} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta}
&
\\
&& \A_L
}
\end{tabular}
\caption{An invertible ternary transducer $\A_H$ and a
non-invertible ternary transducer $\A_L$} \label{ah-al}
\end{center}
\end{figure}
For $0\leq i < j \leq 2$, the ternary tree automorphisms $a_{ij}$
from the transducer $\A_H$ are defined recursively by
\[
\begin{cases}
a_{ij}(\emptyset) = \emptyset, \\
a_{ij}(iw) = jw, \\
a_{ij}(jw) = iw, \\
a_{ij}(xw) = xa_{ij}(w), & x \not\in \{i,j\},
\end{cases}
\]
for a word $w$ over $X_3$. In simple terms, the only effect the
transformation $a_{ij}$ has on a word $w$ over $X_3$ is that it
changes the very first appearance of either of the symbols $i$ or
$j$ in $w$ to the other symbol, if such an appearance exists. To
simplify the notation, we write
\[ a = a_{01}, \qquad b = a_{02}, \qquad\text{and}\qquad c = a_{12}. \]
The state labeled by $id$ does not change any input word and
represents the identity automorphism of the ternary tree. It is
clear that $a$, $b$ and $c$ are self-invertible transformations of
$X_3^*$, i.e~$a^2=b^2=c^2=id$.
The 3 to 2 tree morphisms defined by the transducer $\A_L$ are
defined recursively by
\begin{alignat*}{4}
\alpha(\emptyset) &= \emptyset, \qquad & \alpha(0w) &= 0\alpha(w),\qquad &
\alpha(1w) &= 1\alpha(w), \qquad & \alpha(2w) &= 1\beta(w), \\
\beta(\emptyset) &= \emptyset, \qquad & \beta(0w) &= 1\alpha(w),\qquad &
\beta(1w) &= 1\beta(w), \qquad & \beta(2w) &= 0\beta(w).
\end{alignat*}
\begin{definition}
The semigroup (group) of $k$-ary tree endomorphisms (automorphisms)
generated by all the states of an (invertible) $k$-ary transducer
$\A$ is called the semigroup (group) of $\A$ and is denoted by
$S(\A)$ ($G(\A)$).
\end{definition}
The group $G(\A_H)$ is introduced in~\cite{grigorchuk-s:hanoi-cr},
where it is called the Hanoi Towers group on 3 pegs (in fact, one Hanoi
Towers group $\mathcal{H}^{(k)}$ is introduced for each number of
pegs $k \geq 3$). The name is derived from the fact that the group
$\Ht$ models the well-known Tower of Hanoi problem on 3 pegs.
To recall, the Tower of Hanoi problem on 3 pegs and $n$ disks is the
following. In a valid $n$ disk configuration, disks of different
size, labeled by $1,2,\dots,n$ according to their size, are placed
on three pegs, labeled 0,1 and 2, in such a way that no disk is
placed on top of a smaller disk. In a single move the top disk from
one peg can be moved and placed on top of another peg, as long as
the newly obtained configuration is still valid. Initially all $n$
disks are placed on peg 0 and the problem asks for an optimal
algorithm that moves all disks to another peg.
Each valid configuration of $n$ disks can be encoded by a word of
length $n$ over $X_3$. The word $x_1 \dots x_n$ represents the
unique valid configuration in which disk $i$ is placed on peg $x_i$.
The ternary tree automorphism $a_{ij}$ then represents a move
between peg $i$ and peg $j$ (in either direction). For example the
move between peg 0 and peg 2 illustrated in Figure~\ref{move} is
encoded by $a_{02}(10212) = 12212$.
\begin{figure}[!ht]
\begin{center}
\includegraphics[height=60pt]{h35move-a.eps}
\end{center}
\caption{A move between peg 0 and peg 2}\label{move}
\end{figure}
The action of $\Ht$ on the ternary tree is level transitive, meaning
that it is transitive on the levels of the tree. This is equivalent
to the statement that any valid configuration on $n$ disks can be
obtained from any other valid configuration on $n$ disks by legal
moves.
Consider the stabilizer $P_n$ of the vertex $0^n$ in $\Ht$. The
group $\Ht$ acts on the set $\Ht/P_n$ of left cosets of $P_n$. The
action is described by the corresponding Schreier graph $\Gamma_n =
\Gamma_n(\Ht,P_n,S)$ of $P_n$ with respect to the generating set
$S=\{a,b,c\}$. The vertices are the cosets of $P_n$ and there is an
edge connecting $hP_n$ to $shP_n$ for every coset $hP_n$ and
generator $s$ in $S$. Since $h' \in hP_n$ if and only if $h'(0^n) =
h(0^n)$ the vertices of the Schreier graph $\Gamma_n$ can be encoded
by the vertices of the $n$-th level of the ternary tree (the coset
$hP_n$ is labeled by $h(0^n)$) and two vertices are connected if and
only if one is the image of the other under $s$, for some generator
$s$ in $S$. The Schreier graph $\Gamma_3$ corresponding to level 3
of the ternary tree is given in Figure~\ref{sierpinski3}.
\begin{figure}[!ht]
\begin{center}
\[
\SelectTips{cm}{}
\xymatrix@C=3pt{
& & & & & & & 111 \ar@{-}@(ur,ul)_{\textstyle b}
\\
& & & & & & 011 \ar@{-}[rr]_{\textstyle b} \ar@{-}[ur]^{\textstyle a} & & 211 \ar@{-}[ul]_{\textstyle c}
\\
& & & & & 021 \ar@{-}[ur]^{\textstyle c} & & & & 201 \ar@{-}[ul]_{\textstyle a}
\\
& & & & 221 \ar@{-}[rr]_{\textstyle c} \ar@{-}[ur]^{\textstyle b}
& & 121 \ar@{-}[rr]_{\textstyle b} \ar@{-}[ul]_{\textstyle a}
& & 101 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c}
& & 001 \ar@{-}[ul]_{\textstyle b}
\\
& & & 220 \ar@{-}[ur]^{\textstyle a} & & & & & & & & 002 \ar@{-}[ul]_{\textstyle c}
\\
& & 120 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 020 \ar@{-}[ul]_{\textstyle b} & & & &
& & 202 \ar@{-}[rr]_{\textstyle c} \ar@{-}[ur]^{\textstyle b} & & 102 \ar@{-}[ul]_{\textstyle a}
\\
& 100 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} \ar@{-}[ur]^{\textstyle b} &&&&
010 \ar@{-}[ld]_{\textstyle b} \ar@{-}[rd]^{\textstyle a} \ar@{-}[ul]_{\textstyle c} &&&&
212 \ar@{-}[ld]_{\textstyle c} \ar@{-}[rd]^{\textstyle b} \ar@{-}[ur]^{\textstyle a} &&&&
122 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} \ar@{-}[ul]_{\textstyle b}
\\
000 \ar@{-}[rr]_{\textstyle b} \ar@{-}@(l,d)_{\textstyle c} &&
200 \ar@{-}[rr]_{\textstyle a} && 210 \ar@{-}[rr]_{\textstyle c} &&
110 \ar@{-}[rr]_{\textstyle b} && 112 \ar@{-}[rr]_{\textstyle a} &&
012 \ar@{-}[rr]_{\textstyle c} && 022 \ar@{-}[rr]_{\textstyle b} &&
222 \ar@{-}@(r,d)^{\textstyle a}
}
\]
\caption{The Schreier graph of $\Ht$ at level 3}\label{sierpinski3}
\end{center}
\end{figure}
Since all generators have order 2, no directions are indicated on
the edges.
The sequence of graphs $\{\Gamma_n\}$ converges to an infinite graph
$\Gamma$ in the space of pointed graphs based at $0^n$
(see~\cite{grigorchuk-z:cortona} for definitions of this space),
which is the Schreier graph $\Gamma=\Gamma(\Ht,P,S)$, where
$P=\cap_{n=0}^\infty P_n$ is the stabilizer of the infinite ray
$0^\infty=000\dots$ on the boundary of the ternary tree. One can
think of the limiting graph both as the Schreier graph of the action
of $\Ht$ on the orbit of the infinite ray $0^\infty$ in $\partial
X_3^*$ or as the model of Tower of Hanoi problem representing all
valid configurations that can be reached from the configuration in
which (countably) infinitely many disks are placed on peg $0$ (this
configuration corresponds to the infinite word $0^\infty$). We
denote this graph by $\Gamma_{0^\infty}$.
Graphs similar to $\Gamma_n$, modeling the Tower of Hanoi problem are
well known in the literature, but there is a subtle difference.
Namely, the difference with the corresponding graphs
in~\cite{hinz:ens} modeling the Tower of Hanoi problem is that the
edges in $\Gamma_3$ are labeled (by the corresponding tree
automorphisms) and our graphs have loops at the corners
(corresponding to situations in which all disks are on one peg and
the generator corresponding to a move between the other two pegs
does not change anything), which turn them into 3-regular graphs.
Finite dimensional permutational representations of $\Ht$ based on
the action on the levels of the ternary tree were used
in~\cite{grigorchuk-s:hanoi-cr} to calculate the spectrum of the
graphs $\Gamma_n$ as well as the limiting infinite graph $\Gamma$.
Among interesting properties of $\Ht$ we mention that it is an
amenable (but not subexponentially amenable), regular branch group
over its commutator, it is not just infinite and its closure in the
pro-finite group of ternary tree automorphisms is finitely
constrained. Moreover, $\Ht$ is (up to conjugation) the iterated
monodromy group of the finite rational map $z \mapsto z^2 -
\frac{16}{27z}$, whose Julia set is the Sierpi{\'n}ski gasket. This
explains the fact that the sequence of Schreier graphs
$\{\Gamma_{0^n}\}$ approximates the Sierpi{\'n}ski gasket. For more
information on properties of $\Ht$ we refer the interested reader
to~\cite{grigorchuk-s:hanoi-cr,grigorchuk-s:standrews,grigorchuk-n-s:oberwolfach1,grigorchuk-n-s:oberwolfach2}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Transducer integer sequences}
We first recall the well established notion of automatic sequence.
The definition that follows (Definition~\ref{d:as}) uses one of the
equivalent formulations that can be found in~\cite{allouche-s:as}
(see Definition~5.1.1 and Theorem~5.2.3).
A $k$-ary \emph{finite automaton with final state output} ($k \geq
2$) is a 6-tuple $\A=(Q,X_k,Y,s,\tau,\pi)$, where $Q$ is a finite
set, called set of \emph{states}, $X_k=\{0,\dots,k-1\}$ is the
\emph{input alphabet}, $Y$ is a finite set called the \emph{output
alphabet}, $s$ is an element in $Q$ called the \emph{initial state},
$\tau:Q \times X \to Q$ is a map called \emph{transition map} and
$\pi:Q \to Y$ is a map called \emph{final state output map}. For
every input word $w$ over $X_k$, the automaton $\A$ produces a
unique output symbol $y_w$ from $Y$, defined as the image $\pi(q)$
of the state $q$ the automaton reaches after it reads the input word
$w$ starting from the initial state $s$. Thus $y_w =
\pi(\tau(s,w))$, where $\tau:Q \times X^* \to Q$ is the recursive
extension of $\tau$ on $Q \times X^*$ defined by
$\tau(q,\emptyset)=q$ and $\tau(q,xu) = \tau(\tau(q,x),u)$, for $q$
a state in $Q$, $x$ a letter in $X_k$, and $u$ a word over $X_k$.
If, for every word $w$ over $X_k$ and every finite sequence $0^m$ of
zeros, the output $y_w$ is equal to the output $y_{w0^m}$ we say
that the automaton $\A$ \emph{tolerates trailing zeros}. An
automaton $\A$ that tolerates trailing zeros defines an infinite
sequence $y_0,y_1,y_2,\dots$ over the output alphabet $Y$, called
the \emph{final state output sequence} of $A$, as follows. For a
natural number $i\geq 0$ let $[i]_k=i_0\dots i_m$ be any base $k$
representation of $i$ with $i = \sum_{j=0}^m i_j k^j$ (thus the
least significant digit is written first and we may have any number
of trailing zeros). The term $y_i$ in the final state output
sequence is defined as the image $\pi(q)$ of the state $q$ the
automaton reaches after it reads the input word $[i]_k$ starting
from the initial state $s$, i.e.,
\[ y_i = \pi(\tau(s,[i]_k)). \]
Automata with final state output can be represented by labeled
directed graphs similar to the ones representing transducers. The
only significant difference is that each state $q$ is labeled by the
corresponding output letter $\pi(q)$ and the initial state is
indicated by an incoming arrow. As an example, consider the ternary
automaton $\A_{0-2}$ in Figure~\ref{a02}.
\begin{figure}[!ht]
\begin{center}
\[
\SelectTips{cm}{}
\xymatrix@C=55pt{
*++[o][F-]{1} \ar@(ul,l)_{0,1,2} \ar@{}[r]^<<<<{\textstyle a_0}
&
*++[o][F-]{1}\ar@{->}[l]^{0}\ar@{->}[r]_{2}\ar@(dl,dr)_{1}\ar@(u,u)\ar@{}[r]^<<<<{\textstyle a_1}
&
*++[o][F-]{\text{-1}} \ar@(ur,r)^{0,1,2}\ar@{}[l]_<<<<{\textstyle a_2}
}
\]
\caption{A ternary automaton with final state output
$\A_{0-2}$}\label{a02}
\end{center}
\end{figure}
\begin{definition}\label{d:as}
A $k$-ary automatic sequence is an infinite sequence that can be
obtained as the final state output sequence of some $k$-ary finite
automaton that tolerates trailing zeros.
\end{definition}
Note that Theorem~5.2.3 in~\cite{allouche-s:as} allows us to choose
among several other, seemingly less restrictive, settings but we
selected the one that reads integer representations starting from
the least significant digit and that handles trailing zeros because
it parallels what we are about to see (Definition~\ref{d:tis}) when
we switch our attention to transducer integer sequences.
By Cobham's theorem~\cite{cobham:tags}, a sequence over a finite
alphabet is a $k$-ary automatic sequence if and only if it is an
image under a coding of a fixed point of a $k$-uniform endomorphism.
Given a free monoid $X^*$ over a finite alphabet $X$, an
endomorphism $\alpha:X^* \to X^*$ can be uniquely defined by
specifying the images of the letters in $X$ under $\alpha$. Suppose
that, for all letters $x$ in $X$, $\alpha(x)\neq \emptyset$ and that
there exists a letter $x$ in $X$ such that $\alpha(x) = xw$, where
$w$ is a non-empty word. Then, for all $n \geq 0$, the $n$-th
iterate $\alpha^n(x)$ is a proper prefix of the $(n+1)$-th iterate
$\alpha^{n+1}(x)=\alpha(\alpha^n(x))$ and the limit $\llim
\alpha^n(x)$ is a well defined infinite sequence over $X$. In the
particular case when the length of all the words $\alpha(x)$, $x \in
X$, is equal to $k$, the morphism $\alpha$ is called a $k$-uniform
endomorphism.
The following example provides a cube-free automatic sequence that
both illustrates the concept of automatic sequence and the claim of
Cobham's theorem. In addition, this example will play a role in our
further considerations.
\begin{example}[Cube-free automatic sequence]
Let $X=\{1,-1\}$ and denote by $w_\alpha$ the infinite binary
sequence
\[ w_\alpha = \llim \alpha^n(1) = 11 \, \text{-}1 \ 11\, \text{-}1 \ 1 \,
\, \text{-}1\, \text{-}1 \ 11 \, \text{-}1 \ 11\, \text{-}1 \ 1\, \text{-}1 \,
\text{-}1 \ 11 \, \text{-}1 \ 1 \,\text{-}1 \, \text{-}1 \ 1 \, \text{-}1
\, \text{-}1 \dots~ \]
obtained by iteration, starting from 1, of the endomorphism
$\alpha:X^* \to X^*$ given by (compare to sequence \seqnum{A080846};
all sequence references are to The On-Line Encyclopedia of Integer
Sequences~\cite{sloane:online})
\[ 1 \mapsto 11 \, \text{-}1 \qquad \text{-}1 \mapsto 1 \, \text{-}1 \, \text{-}1. \]
A finite or infinite word $w$ over an alphabet $X$ is cube-free if
it does not contain a subword of the form $uuu$, where $u$ is a
nontrivial finite word over $X$.
The infinite sequence $w_\alpha$ is cube-free. This claim can be
easily verified by using the criterion of Richomme and
Wlazinski~\cite{richomme-w:cube-free}, which only requires checking
that
\[
\alpha(11 \, \text{-}1 \, \text{-}11 \, \text{-}11 \, \text{-}1 \,
\text{-}11 \, \text{-}1 \, \text{-}111 \, \text{-}111 \,
\text{-}11 \, \text{-}111 \, \text{-}1 \, \text{-}1)
\]
is cube-free.
We offer two additional descriptions of $w_\alpha$.
Define a sequence of words $w_{[n]}$ of length $3^n$ by
\begin{align*}
w_{[0]} &= 1, \\
w_{[n+1]} &= w_{[n]} w_{[n]} w_{[n]}',
\end{align*}
where $w_{[n]}'$ is obtained from $w_{[n]}$ by changing the middle
symbol in $w_{[n]}$ from 1 to -1. The limit $\llim w_{[n]}$ is well
defined and is equal to $w_\alpha$.
For an integer $i \geq 0$, let $(i)_k=i_0i_1 \dots $ be the sequence
of digits in base $k$ representation of $i$, where $i =
\sum_{j=0}^\infty i_jk^j$ (the sequence ends in infinitely many
0's).
Call a natural number $i$ a 2-before-0 number if the least
significant digit in the ternary representation $(i)_3$ of $i$ that
is different from 1 is 2. Otherwise the number is called a
0-before-2 number. Define an infinite sequence $x_0,x_1,x_2,\dots,$
by
\[ x_i = \begin{cases}
1, & \text{if }i \text{ is a 0-before-2 number}\\
-1, & \text{if }i \text{ is a 2-before-0 number}
\end{cases}.
\]
The infinite binary sequence $x_0,x_1,x_2,\dots,$ is equal to
$w_\alpha$.
We claim that the infinite sequence $w_\alpha$ is a ternary
automatic sequence. It can be obtained as the final state output
sequence of the automaton $\A_{0-2}$. Indeed, the only time the
automaton $\A_{0-2}$ produces -1 in the output is if it reaches the
state $a_2$, which only happens if $i$ is a 2-before-0 number.
\end{example}
We define now the notion of a transducer integer sequence.
\begin{definition}\label{d:tis}
A $k_1$ to $k_2$ \emph{transducer integer sequence} is a sequence of
integers $\{z_i\}_{i=0}^\infty$ such that there exists a $k_1$ to
$k_2$ transducer $\A$ and a state $q$ in $\A$ such that, for every
$i \geq 0$, the output word $q((i)_{k_1})$ is the base $k_2$
representation of $z_i$.
\end{definition}
Note that, by the above definition, not every transducer defines a
transducer integer sequence, since some attention needs to be paid
to trailing zeros. Namely, it is implicit in the definition that the
state $q$ of $\A$ maps the cofinal class of $0^\infty$ in $\partial
X_{k_1}^*$ to the cofinal class of $0^\infty$ in $\partial
X_{k_2}^*$ (the cofinal class of $0^\infty$ is just the set of
infinite words ending in $0^\infty$). We keep our attention only to
this class since it is the one describing non-negative integers.
We should perhaps point out that the equivalent formulation of the
definition of automatic sequence provided by Theorem~5.2.4
in~\cite{allouche-s:as} even more closely parallels our definition
of transducer integer sequence than the one we gave in
Definition~\ref{d:as}.
\begin{example}
Let $\A_T$ be the ternary transducer in Figure~\ref{at}.
\begin{figure}[!ht]
\begin{center}
\[
\xymatrix{
*++[o][F-]{} \ar@{->}[rr]^{0/1}_{2/1} \ar@(ul,dl)_{1/0} \ar@(u,u) \ar@{}[rr]_<<<{\textstyle \sigma_1} &&
*++[o][F-]{} \ar@(ur,dr)^{0,1,2/0} \ar@{}[ll]^<<<{\textstyle \sigma_0}
}
\]
\caption{A ternary transducer $\A_T$}\label{at}
\end{center}
\end{figure}
The state labeled by $\sigma_0$ just rewrites all digits to 0.
Clearly,
\[ \sigma_1(1^n0w) = \sigma_1(1^n2w) = 0^n10^\infty \]
for any word $w$ in the cofinal class of $0^\infty$. Since
$(0^n10^\infty)_3 = 3^n$ the obtained integer sequence
$\{a_n\}_{n=0}^\infty$ is (compare to sequence \seqnum{A038500})
\[ 1,3,1,\ 1,9,1,\ 1,3,1,\ 1,3,1,\ 1,27,1,\ 1,3,1,\ 1,3,1,\ 1,9,1,\ 1,3,1,\dots~. \]
By thinking of the powers of 3 as an (infinite) alphabet, this
sequence can be thought of as the fixed point of the iterations
starting from 1 of the 3-uniform endomorphism defined by
\[ x \mapsto 1, \ 3x, \ 1~. \]
This sequence can also be defined by blocks $a_{[n]}$ of length
$3^n$ as
\[ a_{[0]} = 1 \qquad\qquad a_{[n+1]} = a_{[n]}a_{[n]}'a_{[n]}, \]
where $a_{[n]}'$ is obtained from $a_{[n]}$ by multiplying the
middle term by 3.
\end{example}
The next example shows that there exist sequences of integers, and
even bounded sequences of integers, that are not transducer integer
sequences.
\begin{example}
The sign sequence (see \seqnum{A057427})
\[ 0,1,1,1,1,1,1,1,1,1,1 \dots~ \]
is not a transducer integer sequence. Indeed, regardless of the
cardinality of the chosen alphabets $X_{k_1}$ and $X_{k_2}$, the
fact that $0^\infty$ must be mapped to $0^\infty$ (this is simply
because the 0 term of the sign sequence is 0) implies that the
positive number $k_1^n$ represented by $0^n10^\infty$ must be mapped
either to 0 or to a number of size at least $k_2^n$, which is
greater than 1 for $n \geq 1$. Here one sees in practice the
important difference between the work of automata with final state
output and the work of (synchronous) transducers. While the former
can wait for the whole input before deciding on the output the
latter must produce output at every transition step. In the above
situation it is impossible for the transducer ``to know in advance''
if non-zero digits will be read at some point in the input and this
makes it impossible to provide a correct output (since the
correctness of the output crucially depends on the first digit of
the output).
\end{example}
The following proposition provides a necessary condition for an
integer sequence to be a transducer integer sequence.
\begin{proposition}
Let $\A=(Q,X_{k_1},X_{k_2},\tau,\pi)$ be a finite $k_1$ to $k_2$
synchronous transducer, and let $\{z_i\}_{i=0}^\infty$ be the
transducer integer sequence defined by choosing $q$ in $Q$ as the
initial state. Then the growth of the sequence
$\{z_i\}_{i=0}^\infty$ is at most polynomial. More precisely,
\[ z_i < k_2^{|Q|} \cdot i^{\log_{k_1}(k_2)}, \]
for all $i\geq 0$.
In particular, the growth of transducer integer sequences defined by
rational tree endomorphisms is at most linear.
\end{proposition}
\begin{proof}
We may assume that all states of $Q$ are accessible from $q$
(otherwise we can delete the unnecessary states and get even tighter
upper bound on the growth of $\{z_i\}_{i=0}^\infty$).
A $0$-path (cycle) in the Moore diagram of $\A$ is a directed path
(cycle) in which each edge is labeled by $0|*$, where $*$ stands for
arbitrary letters from $X_{k_2}$. Call such a path (cycle)
nontrivial if at least one edge is labeled by $0|y$ for some nonzero
$y$ in $X_{k_2}$. It is clear that $\A$ does not have nontrivial
0-cycles (otherwise some elements in the cofinal class of $0^\infty$
would be mapped to elements outside this class). Thus, the longest
length of a non-trivial 0-path is $|Q|-1$ (any longer path would
have to repeat vertices and therefore would contain a cycle).
Therefore if $n$ is the smallest number of digits needed to write $i
\geq 0$ in base $k_1$, then $z_i$ can be written in base $k_2$ by
using no more than $n+|Q|-1$ digits. This gives the estimate
\[ z_i < k_2^{n+|Q|-1} = k_2^{|Q|} \cdot k_2^{n-1} \leq k_2^{|Q|} \cdot
k_2^{\log_{k_1}(i)} = k_2^{|Q|} \cdot i^{\log_{k_1}(k_2)}.
\qedhere\]
\end{proof}
We end the section by considering another example of a transducer
integer sequence (related to the transducer $\A_L$).
Let $N_2$ be the set of all non-negative integers whose base 3
representation does not use the digit 2 (they are listed in sequence
\seqnum{A005836}). Define a sequence $\{\ell_n\}_{n=0}^\infty$,
called \emph{$L$-sequence} (see sequence \seqnum{A060374}), by
\[ \ell_n = \ell_n^- + \ell_n^+ \]
where $\ell_n^-$ and $\ell_n^+$ are the unique non-negative integers
such that $\ell_n^-,\ \ell_n^+,\ \ell_n^- +\ell_n^+ \in N_2$ and
$n=\ell_n^+ - \ell_n^-$ (the $L^-$-sequence
$\{\ell_n^-\}_{n=0}^\infty$ is the sequence~\seqnum{A060373} and the
$L^+$-sequence $\{\ell_n^+\}_{n=0}^\infty$ is the
sequence~\seqnum{A060372})
\begin{theorem}
The $L$-sequence is a ternary transducer integer sequence. It is
generated by the transducer $\A_L$ with initial state $\alpha$.
\end{theorem}
\begin{proof}
In fact, we will prove that in addition to the $L$-sequence, both
the $L^-$-sequence and the $L^+$-sequence are ternary transducer
sequences, and they are generated by the transducers $\A_{L^-}$ and
$\A_{L^+}$ in Figure~\ref{L+} (in both cases with initial state
$\alpha$).
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\SelectTips{cm}{}
\xymatrix@C=35pt{
&
*++[o][F-]{}
\ar@/^1pc/[rr]^{2/1} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/0} \ar@{}[l]|<<<<{\textstyle\alpha}
&&
*++[o][F-]{}
\ar@/^1pc/[ll]^{0/0} \ar@(u,ur)^{1/1} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta}
&
\\
&& \A_{L^-}
}
&
\SelectTips{cm}{}
\xymatrix@C=35pt{
&
*++[o][F-]{}
\ar@/^1pc/[rr]^{2/0} \ar@(u,ul)_{0/0} \ar@(d,dl)^{1/1} \ar@{}[l]|<<<<{\textstyle\alpha}
&&
*++[o][F-]{}
\ar@/^1pc/[ll]^{0/1} \ar@(u,ur)^{1/0} \ar@(d,dr)_{2/0} \ar@{}[r]|<<<<{\textstyle\beta}
&
\\
&& \A_{L^+}
}
\end{tabular}
\caption{Ternary transducers $\A_{L^-}$ and $\A_{L^+}$} \label{L+}
\end{center}
\end{figure}
Define the sequences $\{r_n^-\}_{n=0}^\infty$,
$\{r_n^+\}_{n=0}^\infty$, and $\{r_n\}_{n=0}^\infty$ to be the
integer sequences defined by the transducers $\A_{L^-}$, $\A_{L^+}$,
and in $\A_L$, respectively.
Observe that all three transducers have the same transition function
(they only differ in the output function). The following table
contains the information on all three transducers
\[
\begin{array}{cc|ccc|ccc|c}
& && \alpha &&& \beta & \\
\hline
\text{input}
& & 0 & 1 & 2 & 0 & 1 &2 & n \\
\hline
&\A_{L^-} & 0 & 0 & 1 & 0 & 1 &0 & r_n^- \\
\text{output}
&\A_{L^+} & 0 & 1 & 0 & 1 & 0 &0 & r_n^+ \\
&\A_{L} & 0 & 1 & 1 & 1 & 1 &0 & r_n \\
\hline
\text{transition}& & \alpha & \alpha & \beta & \alpha & \beta & \beta
\end{array}
\]
For example, the middle column under $\alpha$, indicates that when
each of the transducers is in state $\alpha$ and the input digit in
$n$ is 1 then the output digit in $\A_{L^-}$, $\A_{L^+}$, and $\A_L$
(and therefore the corresponding digit in $r_n^-$, $r_n^+$, and
$r_n$) is 0, 1, and 1, respectively, and each of the transducers
stays in the state $\alpha$.
Since all three transducers use only the digits $0$ and $1$ in the
output, it is clear that $r_n^-, \ r_n^+, \ r_n \in N_2$, for all $n
\geq 0$.
Further, it is easy to see that $r_n = r_n^- + r_n^+$, for all $n
\geq 0$. Indeed, by checking the entries in the above table, we see
that each output digit in the row corresponding to $r_n$ is exactly
the sum of the two output digits in the rows corresponding to
$r_n^-$ and $r_n^+$ (there is never a carryover in the calculation
$r_n^- + r_n^+ = r_n$).
Next, we see that $n+r_n^-=r_n^+$, for all $n \geq 0$. Note that the
state $\alpha$ corresponds to the case when there is no carryover
and the state $\beta$ corresponds to the case when there is a
carryover of 1 for the next digit. For instance, when the
transducers are in state $\alpha$ and the input digit is 2, then the
output digit in $r_n^-$ is 1, the output digit in $r_n^+$ is 0 and
the transition entry indicates that all three transducers move to
the carryover state $\beta$ (note that $2+1=3$). When the
transducers are in the carryover state $\beta$ and the input digit
is 0, then the output digit in $r_n^-$ is 0, the output digit in
$r_n^+$ is 1, and all three transducers move back to the state
$\alpha$ (note that $0+0+1=1$; the last 1 in this sum comes from the
carryover). The other 4 cases in the table are just as easy to
verify.
Thus the sequences defined by the transducers $\A_{L^-}$,
$\A_{L^+}$, and $\A_L$ satisfy the requirements in the definition of
$L^-$-sequence, $L^+$-sequence, and $L$-sequence, respectively. Let
us prove a triple of sequences that satisfies these requirements is
unique.
By way of contradiction, assume that two distinct triples of
sequences $\{h_n^-\}_{n=0}^\infty$, $\{h_n^+\}_{n=0}^\infty$, and
$\{h_n\}_{n=0}^\infty$, as well as $\{s_n^-\}_{n=0}^\infty$,
$\{s_n^+\}_{n=0}^\infty$, and $\{s_n\}_{n=0}^\infty$ satisfy the
definition. Consider some $n$ at which these two triples of
sequences differ from each other.
Without loss of generality, assume that $s_n^- = h_n^-+m$, for some
non-negative integer $m$. Then $s_n^+ = n + s_n^- = n + h_n^- +m =
h_n^+ +m$ and $s_n = s_n^- + s_n^+ = h_n^- + h_n^+ +2m = h_n +2m$.
Since the triples differ, $m$ must be positive.
Note that there is no carryover in the ternary representation of the
additions $h_n=h_n^- + h_n^+$ and $s_n=s_n^- + s_n^+$ (only the
digits 0 and 1 are used). This means that the only possible pairs of
digits appearing in the same position in the ternary representations
of $h_n^-$ and $h_n^+$ (as well as $s_n^-$ and $s_n^+$) are $(0,0)$,
(0,1), and $(1,0)$. Indeed, if the pair $(1,1)$ appeared, then the
digit $2=1+1$ would appear in the ternary representation of the sum
$h_n=h_n^- + h_n^+$.
Let the least significant nonzero digit of $m$ appear in position
$i$ and denote this digit by $x$. The following table describes all
possible pairs of digits in position $i$ for $h_n^-$ and $h_n^+$ as
well as the corresponding pair of digits for $s_n^-$ and $s_n^+$,
depending on whether $x=1$ or $x=2$:
\[
\begin{array}{c|c|c}
& x=1 & x=2 \\
\hline
(h_n^-,h_n^+) & (s_n^-,s_n^+) & (s_n^-,s_n^+) \\
\hline
(0,0) & (1,1) & (2,2) \\
(0,1) & (1,2) & (2,0) \\
(1,0) & (2,1) & (0,2)
\end{array}
\]
We see that in each case, either the digit 2 appears in one of the
ternary representations of $s_n^-$ and $s_n^+$ or the pair of digits
$(1,1)$ appears in the same position in $s_n^-$ and $s_n^+$, none of
which is allowed.
Thus we have a contradiction and there is only one triple of integer
sequences satisfying the definition of $L^-$-sequence,
$L^+$-sequence and $L$-sequence, which then must be the triple
$\{r_n^-\}_{n=0}^\infty$, $\{r_n^+\}_{n=0}^\infty$, and
$\{r_n\}_{n=0}^\infty$ defined by the transducers $\A_{L^-}$,
$\A_{L^+}$, and $\A_L$, respectively.
\end{proof}
Let $\{p_n\}_{n=0}^\infty$ be the sequence defined by
\[
p_0 = 0, \qquad\qquad
p_n= \sum_{i=0}^{n-1} w_ia_i, \quad\text{ for }n \geq 1
\]
where the sequence $\{w_n\}_{n=0}^\infty$ providing the signs is the
cube-free sequence generated by the automaton $\A_{0-2}$ and
$\{a_n\}_{n=0}^\infty$ is the transducer integer sequence generated
by $\A_T$.
\begin{proposition}
The sequence $\{p_n\}$ is equal to the $L$-sequence.
\end{proposition}
\begin{proof}
We have $p_0=0=\ell_0$ and, for $n$ a positive integer and $w$ a
word over $X_3$,
\begin{align*}
\alpha(0w+1) &= \alpha(1w) = 1\alpha(w) = 0\alpha(w)+1 = \alpha(0w)+1,\\
\alpha(1^n0w+1) &= \alpha(21^{n-1}0w) = 11^{n-1}1\alpha(w) =
1^n0\alpha(w) + 3^n = \alpha(1^n0w) + 3^n,\\
\alpha(1^n2w+1) &= \alpha(21^{n-1}2w) = 11^{n-1}0\beta(w) =
1^n1\beta(w) - 3^n = \alpha(1^n2w) - 3^n, \\
\alpha(2^n0w+1) &= \alpha(0^n1w) = 0^n1\alpha(w) =
10^{n-1}1\alpha(w) - 1 = \alpha(2^n0w) - 1, \\
\alpha(2^n1w+1) &= \alpha(0^n2w) = 0^n1\beta(w) =
10^{n-1}1\alpha(w) - 1 = \alpha(2^n1w) - 1. \\
\end{align*}
In each case the change in the value of $\alpha(i)$ is exactly
$w_ia_i$, i.e., for all $i$,
\[ \ell_{i+1} = \alpha(i+1) = \alpha(i) + w_ia_i = \ell_i+ w_ia_i \]
and therefore the sequence of partial sums $\{p_n\}$ is exactly the
$L$-sequence.
\end{proof}
The sequence $\{\ell_n\}_{n=0}^\infty$ can also be described as a
fixed point of an endomorphism over the alphabet consisting of the
elements of $N_2$. The iterations start at 0 and the endomorphism is
given by
\[
0 \mapsto 0, 1 \qquad\qquad
x \mapsto 3x+1, 3x, 3x+1, \quad \text{ for } x\geq 1.
\]
\section{Relation to the Tower of Hanoi problem}
In this section we exhibit a connection between the Tower of Hanoi
problem, the automatic cube-free sequence $\{w_n\}$ and the
transducer integer sequence $\{a_n\}$.
Define a matrix $K_n$ of size $3^n \times n$, $n \geq 1$, with
entries in $X_3$ by
\[
K_1 = \begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix}, \hspace{3cm}
K_{n+1} = \begin{bmatrix} K_n & 0_n \\ K_n^R & 1_n \\ K_n & 2_n \end{bmatrix},
\]
where the matrix $K_n^R$ is obtained from the matrix $K_n$ by
flipping $K_n$ along the horizontal axis, and $0_n$, $1_n$ and $2_n$
are column vectors with $3^n$ entries equal to 0, 1 and 2,
respectively. Denote the infinite limit matrix $\underset{n \to
\infty}{\lim} K_n$ by $K$.
For example, the transpose of $K_3$ is given by
\[
K_3^T =
\begin{bmatrix}
012 & 210 & 012 & 210 & 012 & 210 & 012 & 210 & 012 \\
000 & 111 & 222 & 222 & 111 & 000 & 000 & 111 & 222 \\
000 & 000 & 000 & 111 & 111 & 111 & 222 & 222 & 222
\end{bmatrix}
\]
The limiting matrix $K$ is well defined due to the fact that $K_n$
appears as the upper left corner in $K_{n+1}$. By definition, the
indexing of the rows of $K$ starts with 0 while the indexing of the
columns starts with 1. For future use, denote the $i$-th row of $K$
by $k_i$. We will think of $k_i$ as of a right infinite word over
$X_3$. Similarly, denote the $i$-th row of the matrix $K_n$ by
$k_i^{(n)}$. We will think of $k_i^{(n)}$ as a word of length $n$
over $X_3$. Note that, for $i \in \{0,\dots,3^n-1\}$, $k_i =
k_i^{(n)}0^\infty$, $k_{i+2\cdot 3^n} = k_i^{(n)}20^\infty$, and
$k_{i+3^n} = k_{3^n-1-i}^{(n)}10^\infty$
A sequence $w_0,\dots,w_{k^n-1}$ of words of length $n$ over $X_k$
is a $k$-ary Gray code of length $n$ if all words of length $n$ over
$X_k$ appear exactly once in the sequence and any two consecutive
words differ in exactly one position. Note that the $3^n$ rows of
the matrix $K_n$ represent a ternary Gray code of length $n$.
By interpreting the rows of $K$ as ternary representations of
integers, we obtain the sequence
\[ 0,1,2,5,4,3,6,7,8,17,16,15,12,13,14,11,10,9,\dots, \]
which is not included in The On-Line Encyclopedia of Integer
Sequences (as of December 2006).
We observe that the successive rows in $K$ are obtained from each
other by applying the ternary tree automorphism $a$ at odd steps and
$c$ at even steps (the automorphisms $a$ and $c$ are defined by
$\A_H$ - the transducer generating the Tower of Hanoigroup).
\begin{proposition}\label{gray3}
For $j \geq 0$, define $t_{2j} = (ca)^j$ and $t_{2j+1} = a(ca)^j$.
Then
\[ k_i = t_i(k_0). \]
\end{proposition}
\begin{proof}
Recall that the result of the action of the rational ternary tree
automorphism $a$ on any ternary word $w$ is that the first
occurrence of a letter from $\{0,1\}$ in $w$, if such an occurrence
exists, is replaced by the other letter from that set, while the
result of the action of $c$ is that the first occurrence of a letter
from $\{1,2\}$ in $w$, if such an occurrence exists, is replaced by
the other letter from that set. As already observed, this implies
that both $a$ and $c$ have order 2. Also, note that $a$ and $c$
change at most one letter in any word.
We will prove by induction on $n$ that $k_i = t_i(k_0)$, for $0 \leq
i \leq 3^n-1$.
Since $a(0^\infty) = 10^\infty$ and $c(10^\infty) = 20^\infty$, the
claim is true for $i \leq 2$.
Assume that the claim is true for all $i \leq 3^n-1$, for some $n
\geq 1$.
Since the last row in $K_n$ is $2^n$, we see that $k_{3^n-1} =
2^n0^\infty$. This row is obtained from the previous row by applying
$c$ in step $3^n-1$. In the next step applying $a$ to $2^n0^\infty$
produces $2^n10^\infty$, which is equal to $k_{3^n}$. We wish to
understand the next $3^n-1$ steps, starting at the word
$2^n10^\infty$, in which $c$ and $a$ are applied alternately. By
inductive assumption, starting at $0^\infty$, alternate applications
of $a$ and $c$ ($3^n-1$ total) change the word in the first $n$
positions from $0^n$ to $2^n$ by going through the $3^n$ words in
the rows of $K_n$. Since both $c$ and $a$ are self-inverse, starting
at $2^n10\infty$, alternate applications of $c$ and $a$ ($3^n-1$
total) backtrack the word in the first $n$ positions from $2^n$ back
to $0^n$ by going through the $3^n$ words in the rows of $K_n^R$.
Moreover, during this backtracking, no part of the word beyond the
position $n$ is affected. This is simply because neither $c$ nor $a$
change more than 1 letter in any word. Thus, starting from
$0^\infty$, alternate applications of $a$ and $c$
($3^n-1+1+3^n-1=2\cdot 3^n-1$ total) produce the first $2 \cdot 3^n$
rows of $K$. The last taken step is $a$ and therefore, in the next
step, $c$ takes $0^n10^\infty$ to $0^n20^\infty$. Alternate
applications of $a$ and $c$ then again change the word in the first
$n$ positions from $0^n$ to $2^n$ in $3^n-1$ steps by going through
the $3^n$ words in the rows of $K_n$ without affecting any letter
beyond position $n$ and eventually producing $2^{n+1}0^\infty$ in
$2\cdot 3^n-1 + 1 + 3^n-1 = 3^{n+1}-1$ steps.
\end{proof}
It is clear that the rows of $K$ constitute the whole cofinal class
of $0^\infty$. Thus the subgroup $\langle a, c\rangle$ acts
transitively on this class. Since the order of both $a$ and $c$ is 2
this means that $\langle a,c\rangle$ is the infinite dihedral group
$D_\infty$. The transitivity of the action of $\langle a,c\rangle$
on the cofinal class of $0^\infty$ is equivalent to the known fact
that any valid $n$ disk configuration can be obtained from any other
in a restricted version of Tower of Hanoi problem in which no disk
can move between pegs 0 and 2 (in our terminology, applications of
the automorphism $b$ are not allowed). Figure~\ref{peano} shows the
path taken by $(ca)^{13}$ from $000$ to $222$ in $\Gamma_3$.
\begin{figure}[!ht]
\begin{center}
\[
\SelectTips{cm}{}
\xymatrix@C=3pt{
& & & & & & & 111
\\
& & & & & & 011 \ar@{-}[ur]^{\textstyle a} & & 211 \ar@{-}[ul]_{\textstyle c}
\\
& & & & & 021 \ar@{-}[ur]^{\textstyle c} & & & & 201 \ar@{-}[ul]_{\textstyle a}
\\
& & & & 221 \ar@{-}[rr]_{\textstyle c} & & 121 \ar@{-}[ul]_{\textstyle a}
& & 101 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 001
\\
& & & 220 \ar@{-}[ur]^{\textstyle a} & & & & & & & & 002 \ar@{-}[ul]_{\textstyle c}
\\
& & 120 \ar@{-}[rr]_{\textstyle a} \ar@{-}[ur]^{\textstyle c} & & 020 & & & &
& & 202 \ar@{-}[rr]_{\textstyle c} & & 102 \ar@{-}[ul]_{\textstyle a}
\\
& 100 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c} &&&&
010 \ar@{-}[rd]^{\textstyle a} \ar@{-}[ul]_{\textstyle c} &&&&
212 \ar@{-}[ld]_{\textstyle c} \ar@{-}[ur]^{\textstyle a} &&&&
122 \ar@{-}[ld]_{\textstyle a} \ar@{-}[rd]^{\textstyle c}
\\
000 && 200 \ar@{-}[rr]_{\textstyle a} && 210 \ar@{-}[rr]_{\textstyle c} &&
110 && 112 \ar@{-}[rr]_{\textstyle a} && 012 \ar@{-}[rr]_{\textstyle c} &&
022 && 222
}
\]
\caption{The ternary Gray code path generated by $a$ and $c$ in
$\Ht$ at level 3}\label{peano}
\end{center}
\end{figure}
Order all configurations (words in the cofinal class of $0^\infty$)
according to their position in the matrix $K$ (small configurations
correspond to rows with small index). When $b$ is applied to any
configuration $k_i$ the obtained configuration $b(k_i)$ is either
larger or smaller than $k_i$. Based on this alternative define an
infinite sequence $\{d_i\}_{i=0}^\infty$ over $X=\{1,-1\}$ by
\[ d_i = \begin{cases}
1, & \text{if } b(k_i) > k_i \\
-1, & \text{if } b(k_i) < k_i
\end{cases}.
\]
Call this sequence the $b$-direction sequence. Further, define an
integer sequence $\{\hat{b}_i\}_{i=0}^\infty$ by $\hat{b}_i =
|i-j|/2$, where $j$ is the index of the configuration $k_j=b(k_i)$.
Call this sequence the $b$-change sequence.
\begin{theorem}
The $b$-direction sequence is exactly the cube-free automatic
sequence $\{w_n\}$ generated by $\A_{0-2}$ and the $b$-change
sequence is exactly the transducer integer sequence $\{a_n\}$
generated by $\A_T$.
\end{theorem}
\begin{proof}
The proof is by induction on blocks of size $3^n$.
For $n=1$, the $b$-change sequence is $1,3,1$ which coincides with
the transducer integer sequence generated by $\A_T$, while the
$b$-direction sequence is $1,1,-1$, which coincides with the
cube-free automatic sequence generated by $\A_{0-2}$.
Assume that the $b$-change sequence $\{\hat{b}_i\}$ and the
transducer integer sequence $\{a_i\}$ defined by $\A_T$ agree up to
index $3^n-1$, and that the $b$-direction sequence $\{d_i\}$ and the
automatic sequence $\{w_i\}$ defined by $\A_{0-2}$ agree up to index
$3^n-1$, for some $n \geq 1$.
Note that this implies that for $i \in \{0,\dots,3^n-1\}$, $i \neq
(3^n-1)/2$,
\[
\hat{b}_i = \hat{b}_{3^n-1-i} \qquad \text{and} \qquad d_i = - d_{3^n-1-i}.
\]
This is true simply because both claims are true for the transducer
integer sequence $\{a_i\}$ and the automatic sequence $\{w_i\}$.
Also, note that for the middle term in this block we have
\[
\hat{b}_{(3^n-1)/2} = 3^n \qquad \text{and} \qquad d_{(3^n-1)/2} = 1.
\]
Let $i \in \{ 0,\dots,3^n-1 \}$, $i \neq (3^n-1)/2$. Note that the
exception $i \neq (3^n-1)/2$ corresponds to $k_i^{(n)}=1^n$ (the
middle row of $K_n$ consists entirely of $1$'s). Since either $0$ or
$2$ appears in $k_i^{(n)}$ we know that the tree automorphism $b$
acts on any ternary word that has $k_i^{(n)}$ as a prefix by simply
replacing the first occurrence of $0$ or $2$ in $k_i^{(n)}$ by the
other letter and leaving everything else unchanged. Therefore,
\[
b(k_{i+2\cdot3^n})
= b\left(k_{i}^{(n)}20^\infty\right) = k_{i+d_i \hat{b}_i}^{(n)}20^\infty = k_{i+d_i \hat{b}_i+2\cdot 3^n}.
\]
This implies that
\[
\hat{b}_{i+2\cdot 3^n} = \hat{b}_i \qquad \text{and} \qquad d_{i+2\cdot 3^n} = d_i.
\]
Similarly,
\[
b(k_{i+3^n})
= b\left(k_{3^n-1-i}^{(n)}10^\infty\right) = k_{3^n-1-i+d_{3^n-1-i} \hat{b}_{3^n-1-i}}^{(n)}10^\infty
= k_{3^n-1-i -d_i \hat{b}_i}^{(n)}10^\infty = k_{i+d_i \hat{b}_i+3^n},
\]
and this implies that
\[
\hat{b}_{i + 3^n} = \hat{b}_i \qquad \text{and} \qquad d_{i + 3^n} = d_i.
\]
We now handle the exceptional terms (those are the ``middle'' terms,
i.e., the terms corresponding to the indices $(3^n-1)/2 + 3^n$ and
$(3^n-1)/2 + 2\cdot 3^n$).
Since
\[
b(k_{(3^n-1)/2 + 2\cdot 3^n}) = b(1^n20^\infty) =
b(1^n00^\infty) = k_{(3^n-1)/2}
\]
we see that
\[
\hat{b}_{(3^n-1)/2 + 2\cdot 3^n} = 3^n = \hat{b}_{(3^n-1)/2}
\qquad \text{and} \qquad
d_{(3^n-1)/2 + 2\cdot 3^n} = -1 = - d_{(3^n-1)/2}.
\]
Further,
\[
b(k_{(3^n-1)/2 + 3^n}) = b(1^n10^\infty) =
1^{n+1}20^\infty = k_{(3^{n+1}-1)/2 + 2\cdot 3^{n+1}},
\]
and therefore
\[
\hat{b}_{(3^n-1)/2 + 3^n} = 3^{n+1} = 3 \cdot \hat{b}_{(3^n-1)/2}
\qquad \text{and} \qquad
d_{(3^n-1)/2 + 3^n} = 1 = d_{(3^n-1)/2}.
\]
Thus the block of length $3^{n+1}$ of the $b$-change sequence is
obtained by repeating the block of length $3^n$ three times and then
changing the middle term by multiplying it by 3. This is exactly how
the block of length $3^{n+1}$ of the sequence $\{a_n\}$ is obtained
from the block of length $3^n$. Similarly, the block of length
$3^{n+1}$ of the $b$-direction sequence is obtained by repeating the
block of length $3^n$ three times and then changing the middle term
in the third sub-block of length $3^n$ from 1 to -1. This is exactly
how the block of length $3^{n+1}$ of the sequence $\{w_n\}$ is
obtained from the block of length $3^n$.
This completes our induction step.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Geodesic configurations in the Tower of Hanoi problem}
Define a matrix $M_n$ of size $2^n \times n$, $n \geq 1$, with
entries in $X_2$ by
\[
M_1 = \begin{bmatrix} 0 \\ 1 \end{bmatrix}, \hspace{3cm}
M_{n+1} = \begin{bmatrix} M_n & 0_n \\ M_n^R & 1_n \end{bmatrix},
\]
where the matrix $M_n^R$ is obtained from the matrix $M_n$ by
flipping $M_n$ along the horizontal axis, and $0_n$ and $1_n$ are
column vectors with $2^n$ entries equal to 0 and 1, respectively.
The $2^n$ rows of the matrix $M_n$ represent a binary Gray code of
length $n$. Denote the infinite limit matrix $\underset{n \to
\infty}{\lim} M_n$ by $M$. For future use, denote the $i$-th row of
$M$ by $m_i$ and the $i$-th row of the matrix $M_n$ by $m_i^{(n)}$.
We will think of $m_i$ as an infinite word and of $m_i^{(n)}$ as a
word of length $n$ over $X_2$. Note that, for $i \in
\{0,\dots,2^n-1\}$, $m_i = m_i^{(n)}0^\infty$, $m_{i+ 2^n} =
m_{2^n-1-i}^{(n)}10^\infty$.
We observe that the successive rows in $M$ are obtained from each
other by applying the binary tree automorphism $f$ at odd steps and
the automorphism $g$ at even steps, where $f$ and $g$ are given by
the invertible transducer $\A_D$ given in Figure~\ref{ad}. The
self-similar group $G(\A_D)$ defined by $\A_D$ and generated by $f$
and $g$ is the infinite dihedral group $D_\infty$.
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{ccc}
$
\SelectTips{cm}{}
\xymatrix@C=35pt{
\A_D: &
*++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0,1}\ar@{}[r]|<<<{id}
&
*++[o][F-]{{\scriptstyle(01)}}\ar@/^1pc/[l]^{0}\ar@/_1pc/[l]_{1}\ar@{}[l]|<<{f}
&
*++[o][F-]{{\scriptstyle()}} \ar@{->}[l]^{1}\ar@(ur,r)^{0}\ar@{}[l]_<<{g}
}
$
&&
$
\SelectTips{cm}{}
\xymatrix@C=35pt{
\A_{L_2}: &
*++[o][F-]{{\scriptstyle()}}\ar@(ul,l)_{0} \ar@/_1pc/[r]_{1} \ar@{}[r]|<<<{\lambda_0}
&
*++[o][F-]{{\scriptstyle(01)}} \ar@(ur,r)^{1} \ar@/_1pc/[l]_{0} \ar@{}[l]|<<{\lambda_1}
}
$
\end{tabular}
\caption{Two binary invertible transducers: $\A_D$ and
$\A_{L_2}$}\label{ad}
\end{center}
\end{figure}
\begin{proposition}
For $j \geq 0$, define $s_{2j} = (gf)^j$ and $s_{2j+1} = f(gf)^j$.
Then
\[ m_i = s_i(m_0). \]
\end{proposition}
Note that the previous result is just a binary analogue of
Proposition~\ref{gray3} and can also be proved by a simple inductive
argument.
Consider now the transducer in the right half of Figure~\ref{at}. It
is known~\cite{grigorchuk-z:l2} (see
also~\cite{silva-s:lamplighter,bartholdi-s:bs}) that the group
$G(\A_{L_2})$ is the lamplighter group $L_2$ which is the wreath
product of the cyclic group of order 2 (representing a switch) and
the infinite cyclic group (representing moves between consecutive
lamps). The realization of the lamplighter group $L_2$ by the
transducer $\A_{L_2}$ was used by Grigorchuk and
\.Zuk~\cite{grigorchuk-z:l2} to calculate the spectrum of the Markov
operator on the Cayley graph of $L_2$, which then lead to the
solution of Strong Atiyah Conjecture in~\cite{grigorchuk-al:atiyah}.
For $i \geq 0$, denote by $\langle i \rangle_2^{(n)}$ the length $n$
binary representative (including leading zeros if necessary) in
which the most significant digits are written first. Define, for $i
\in \{0,\dots,2^n-1\}$, $\overline{m}_i^{(n)}$ to be the reversal of
the word $m_i^{(n)}$ (more generally, denote by $\overline{w}$ the
reversal of any word $w$).
\begin{proposition}
For $i = 0,\dots,2^n-1$,
\[
\lambda_0\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_i^{(n)}.
\]
\end{proposition}
\begin{proof}
We prove, by induction on $n$, that
\[
\lambda_0\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_i^{(n)}
\qquad\text{and}\qquad
\lambda_1\left(\langle i \rangle_2^{(n)}\right) = \overline{m}_{2^n-1-i}^{(n)},
\]
for $0 \leq i \leq 2^n-1$.
The claim is correct for $n=1$, since
$\lambda_0(0)=0=\overline{m}_0^{(1)}$,
$\lambda_0(1)=1=\overline{m}_1^{(1)}$,
$\lambda_1(0)=1=\overline{m}_1^{(1)}$, and
$\lambda_1(1)=0=\overline{m}_0^{(1)}$.
Assume that the claim is correct for some $n \geq 1$.
Then, for $0 \leq i \leq 2^n-1$,
\begin{align*}
\lambda_0\left(\langle i \rangle_2^{(n+1)}\right) &=
\lambda_0\left(0\langle i \rangle_2^{(n)}\right) =
0 \lambda_0\left(\langle i \rangle_2^{(n)}\right) =
0 \overline{m}_i^{(n)} = \overline{m_i^{(n)}0} = \overline{m}_i^{(n+1)},
\\
\lambda_1\left(\langle i \rangle_2^{(n+1)}\right) &=
\lambda_1\left(0\langle i \rangle_2^{(n)}\right) =
1 \lambda_0\left(\langle i \rangle_2^{(n)}\right) =
1 \overline{m}_i^{(n)} = \overline{m_i^{(n)}1} = \overline{m}_{2^{n+1}-1-i}^{(n+1)},
\end{align*}
while for $2^n \leq i \leq 2^{n+1}-1$,
\begin{align*}
\lambda_0\left(\langle i \rangle_2^{(n+1)}\right) &=
\lambda_0\left(1\langle i-2^n \rangle_2^{(n)}\right) =
1 \lambda_1\left(\langle i-2^n \rangle_2^{(n)}\right) = \\
&= 1 \overline{m}_{2^{n+1}-1-i}^{(n)} = \overline{m_{2^{n+1}-1-i}^{(n)}1} =
\overline{m}_i^{(n+1)},
\\
\lambda_1\left(\langle i \rangle_2^{(n+1)}\right) &=
\lambda_1\left(1\langle i-2^n \rangle_2^{(n)}\right) =
0 \lambda_1\left(\langle i-2^n \rangle_2^{(n)}\right) = \\
&= 0 \overline{m}_{2^{n+1}-1-i}^{(n)} = \overline{m_{2^{n+1}-1-i}^{(n)}0} =
\overline{m}_{2^{n+1}-1-i}^{(n+1)}. \qedhere
\end{align*}
\end{proof}
We can define a variation on the notion of transducer integer
sequences as sequences that can be obtained from transducers by
reading the input starting from the most significant digit (and
interpreting the output as starting from the most significant
digit). Call these sequences SF transducer integer sequences (for
significant first). Since the sequence of binary Gray code words can
be obtained by feeding the binary representations of integers, most
significant digit first, into $\A_{L_2}$ starting at $\lambda_0$, we
see that the sequence \seqnum{A003188} of integers
\[ 0 , 1, 3, 2, 6, 7, 5, 4, \dots \]
represented by the binary Gray code words is a SF binary transducer
integer sequence.
We offer two 2 to 3 transducers each of which generates all the
configurations on the three geodesic paths between the three regular
configurations $0^n$, $1^n$ and $2^n$ in the Schreier graph
$\Gamma_n$ modeling the Tower of Hanoi problem on 3 pegs and $n$ disks
(a geodesic path between two vertices is a path of shortest possible
length connecting the vertices). Call such configurations
\emph{geodesic configurations}. The first transducer (see
Theorem~\ref{oh}) uses the natural order, while the second one (see
Theorem~\ref{oh'}) uses the order implied by the binary Gray code.
\begin{theorem}\label{oh}
The 2 to 3 transducer $\mathcal{O}_H$ in Figure~\ref{geodesic}
generates the geodesic configurations in the Tower of Hanoi problem. More
precisely, for $x,y \in\{0,1,2\}$, $x \neq y$, starting at state
$q_{xy}$, and feeding the length $n$ binary representative $\langle
i \rangle_2^{(n)}$ of $i$ (including leading 0's if needed) into
$\mathcal{O}_H$ produces the reverse of the length $n$ ternary word
representing the unique $n$ disk configuration at distance $i$ along
the geodesic from $x^n$ to $y^n$ in the $n$-th level Schreier graph
$\Gamma_n$ of Tower of Hanoi group $\Ht$.
\end{theorem}
\begin{figure}[!ht]
\[
\SelectTips{cm}{}
\xymatrix@C=30pt@R=55pt{
{\mathcal{O}_H:}
&
*++[o][F-]{}
\ar@/^1pc/[rr]^{0/0} \ar@{}[ddrr]|<<<<<{\textstyle q_{01}}
\ar@/^1pc/[dl]^{1/1}
&&
*++[o][F-]{}
\ar@/^1pc/[dr]^{1/2} \ar@{}[ddll]|<<<<<{\textstyle q_{02}}
\ar@/^1pc/[ll]^{0/0}
&
\\
*++[o][F-]{}
\ar@/^1pc/[ur]^{1/1} \ar@{}[r]|<<<<<<{\textstyle q_{21}}
\ar@/^1pc/[dr]^{0/2}
&&&&
*++[o][F-]{}
\ar@/^1pc/[dl]^{0/1} \ar@{}[l]|<<<<<{\textstyle q_{12}}
\ar@/^1pc/[ul]^{1/2}
\\
&
*++[o][F-]{}
\ar@/^1pc/[ul]^{0/2} \ar@{}[uurr]|<<<<<{\textstyle q_{20}}
\ar@/^1pc/[rr]^{1/0}
&&
*++[o][F-]{}
\ar@/^1pc/[ll]^{1/0} \ar@{}[uull]|<<<<<{\textstyle q_{10}}
\ar@/^1pc/[ur]^{0/1}
&
}
\]
\caption{A 2 to 3 transducer generating geodesic configurations}\label{geodesic}
\end{figure}
\begin{proof}
For any permutation $x,y,z$ of the three letters in $X_3$ the states
of the transducer $\mathcal{O}_H$ have (as tree morphisms) the
decomposition
\[
q_{xy} = \pi_{xy} (q_{xz},q_{zy}),
\]
where $\pi_{xy}:X_2 \to X_3$ is the map defined by $\pi_{xy}(0)=x$
and $\pi_{xy}(1)=y$.
It is well known that the unique way to solve the Tower of Hanoi
problem in which $n$, $n \geq 1$, disks are moved from peg $x$ to
peg $y$ in $2^n-1$ steps can be recursively described as follows.
First, in $2^{n-1}-1$ steps move the top $n-1$ disks from peg $x$ to
peg $z$ (the third available peg). Then, in step number $2^{n-1}$,
move the largest disk from peg $x$ to peg $y$. Then, in $2^{n-1}-1$
steps, move the $n-1$ smallest disks from peg $z$ to peg $y$.
Observe that the largest disk is moved only once, in the middle step
(step number $2^{n-1}$).
Employing the encoding of configurations by words over $X_3$, we see
that the unique geodesic path of length $2^n-1$ from $x^n$ to $y^n$
connects $x^n$ to $z^{n-1}x$ in the first $2^{n-1}-1$ steps, then in
the next step it connects $z^{n-1}x$ to $z^{n-1}y$, and in the last
$2^{n-1}-1$ steps it connects $z^{n-1}y$ to $y^n$.
Since the largest disk is moved only once, the last digit in the
configurations on the geodesic from $x^n$ to $y^n$ is equal to $x$
in the first $2^{n-1}$ configurations along the way, and it is equal
to $y$ in the last $2^{n-1}$ configurations.
Thus, if we denote by $\xi_{xy}^{(n)}(i)$ the reversal of the word
over $X_3$ representing the vertex at distance $i$ from $x^n$ along
the geodesic between $x^n$ and $y^n$ in $\Gamma_n$, we have, for $n
\geq 2$,
\[
\xi_{xy}^{(n)}(i) =
\begin{cases}
x\xi_{xz}^{(n-1)}(i), & 0 \leq i \leq 2^{n-1}-1 \\
y\xi_{zy}^{(n-1)}(i-2^{n-1}), & 2^{n-1} \leq i \leq 2^n-1 \\
\end{cases}.
\]
We can now easily prove that
\[
q_{xy}\left(\langle i \rangle_2^{(n)}\right) = \xi_{xy}^{(n)}(i),
\]
by using induction on $n$.
Since $q_{xy}(0) = \pi_{xy}(0) = x = \xi_{xy}^{(1)}(0)$ and
$q_{xy}(1) = \pi_{xy}(1) = y = \xi_{xy}^{(1)}(1)$, the claim is true
for $n=1$.
Assume that the claim is true for all integers smaller than some
$n$, $n \geq 2$.
Then, for $0 \leq i \leq 2^{n-1}-1$,
\[
q_{xy}\left(\langle i \rangle_2^{(n)}\right) =
q_{xy}\left(0 \langle i \rangle_2^{(n-1)}\right) =
\pi_{xy}(0)q_{xz}\left(\langle i \rangle_2^{(n-1)}\right) =
x\xi_{xz}^{(n-1)}(i) = \xi_{xy}^{(n)}(i)
\]
and, for $0 \leq i \leq 2^{n-1}-1$,
\begin{multline*}
q_{xy}\left(\langle i \rangle_2^{(n)}\right) =
q_{xy}\left(1 \langle i-2^{n-1} \rangle_2^{(n-1)}\right) = \\
= \pi_{xy}(1)q_{zy}\left(\langle i-2^{n-1} \rangle_2^{(n-1)}\right) =
y\xi_{zy}^{(n-1)}(i-2^{n-1}) = \xi_{xy}^{(n)}(i). \qedhere
\end{multline*}
\end{proof}
\begin{theorem}\label{oh'}
The 2 to 3 transducer $\mathcal{O}_H'$ in Figure~\ref{geodesic2}
generates the geodesic configurations in the Tower of Hanoi problem. More
precisely, for $x,y \in\{0,1,2\}$, $x \neq y$, starting at state
$t_{xy}$, and feeding the reversal $\overline{m}_i^{(n)}$ of the
length $n$ row $i$ binary Gray code word from $M_n$ into
$\mathcal{O}_H'$ produces the reverse of the length $n$ ternary word
representing the unique $n$ disk configuration at distance $i$ along
the geodesic from $x^n$ to $y^n$ in the $n$-th level Schreier graph
$\Gamma_n$ of the Tower of Hanoi group $\Ht$.
\end{theorem}
\begin{figure}[!ht]
\[
\SelectTips{cm}{}
\xymatrix@C=75pt@R=55pt{
{\mathcal{O}_H':}&
*++[o][F-]{}
\ar@/_1pc/[r]^{1/1} \ar@/^1pc/[d]^{0/0} \ar@{}[l]|<<<<{\textstyle t_{01}}
&
*++[o][F-]{}
\ar@/_1pc/[r]^{1/2} \ar@/^1pc/[d]^{0/1} \ar@{}[l]_<<<{\textstyle t_{12}}
&
*++[o][F-]{}
\ar@/_2pc/[ll]_{1/0} \ar@/^1pc/[d]^{0/2} \ar@{}[r]|<<<<{\textstyle t_{20}}
&
\\
&
*++[o][F-]{}
\ar@/_2pc/[rr]_{1/2} \ar@/^1pc/[u]^{0/0} \ar@{}[l]|<<<<{\textstyle t_{02}}
&
*++[o][F-]{}
\ar@/_1pc/[l]^{1/0} \ar@/^1pc/[u]^{0/1} \ar@{}[l]^<<<{\textstyle t_{10}}
&
*++[o][F-]{}
\ar@/_1pc/[l]^{1/1} \ar@/^1pc/[u]^{0/2} \ar@{}[r]|<<<<{\textstyle t_{21}}
&
}
\]
\caption{A 2 to 3 transducer generating geodesic configurations}\label{geodesic2}
\end{figure}
\begin{proof}
Observe that, for any permutation $x,y,z$ of the three letters in
$X_3$ the states of the transducer $\mathcal{O}_H'$ have (as tree
morphisms) the decomposition
\[
t_{xy} = \pi_{xy} (t_{xz},t_{yz}),
\]
where $\pi_{xy}:X_2 \to X_3$ is the map defined by $\pi_{xy}(0)=x$
and $\pi_{xy}(1)=y$.
If we preserve the notation from the proof of Theorem~\ref{oh}, we
have, for $n \geq 2$,
\[
\xi_{xy}^{(n)}(i) =
\begin{cases}
x\xi_{xz}^{(n-1)}(i), & 0 \leq i \leq 2^{n-1}-1 \\
y\xi_{yz}^{(n-1)}(2^n-1-i), & 2^{n-1} \leq i \leq 2^n-1 \\
\end{cases}.
\]
The reason that this formula is correct for $2^{n-1} \leq i \leq
2^n-1$ is simply that vertices that are distance $i$ from $x^n$
along the geodesic between $x^n$ and $y^n$ are distance $2^n-1-i$
from $y^n$.
One can then use induction on $n$ just as in the proof of
Theorem~\ref{oh}. The only small difference is in the inductive step
for $0 \leq i \leq 2^{n-1}-1$, which now reads
\begin{multline*}
t_{xy}\left(\overline{m}_i^{(n)}\right) =
t_{xy}\left(\overline{m_{2^{n-1}-1-i}^{(n-1)}1}\right) =
t_{xy}\left(1 \overline{m}_{2^{n-1}-1-i}^{(n-1)}\right) = \\
= \pi_{xy}(1)t_{yz}\left( \overline{m}_{2^{n-1}-1-i}^{(n-1)} \right) =
y\xi_{yz}^{(n-1)}(2^{n-1}-1-i) = \xi_{xy}^{(n)}(i). \qedhere
\end{multline*}
\end{proof}
Observe that the $X_2^* \to X_3^*$ tree morphism defined by the
state $q_{xy}$ in the transducer $\mathcal{O}_H$ is just the
composition of the binary tree automorphism $X_2^* \to X_2^*$
defined by the state $\lambda_0$ with the $X_2^* \to X_3^*$ tree
morphism defined by the state $t_{xy}$ in the transducer
$\mathcal{O}_H'$ (recall that $\lambda_0$ translates from reversals
of binary representations to reversals of Gray code words and the
state $t_{xy}$ in $\mathcal{O}'_H$ translates from reversals of Gray
code words to reversals of geodesic configurations between $x^n$ and
$y^n$). This observation could be used to prove only one of the two
theorems above and then claim the result in the other as a simple
corollary.
The transducer $\mathcal{O}_H$, started at $q_{01}$, generates the
sequence \seqnum{A055661}
\[ 0,1,7,8,17,15,12,13,\dots, \]
but only when all input words are adjusted by leading zeros to have
odd length, and it gives the sequence
\[ 0,2,5,4,22,21,24,26,\dots, \]
which does not appear in The On-Line Encyclopedia of Integer
Sequences (as of December 2006), when the input words are adjusted
to have even length. In fact, the former sequence records the
integers whose ternary representations give the configurations in
the Tower of Hanoi problem on the geodesic line in the infinite
Schreier graph $\Gamma_{0^\infty}$ (recall the definition of the
limiting graph $\Gamma_{0^\infty}$ in Section~\ref{s:tree})
determined by applying repeatedly the automorphisms $a$, $b$ and $c$
(in that order) and the latter records the integers whose ternary
representations give the configurations on the geodesic line in
$\Gamma_{0^\infty}$ determined by applying repeatedly the
automorphisms $b$, $a$ and $c$ (in that order). There is nothing
strange in this split, since it is known that the optimal solution
transferring disks from peg 0 to peg 1 follows different paths
depending on the parity of the number of disks. Namely, for odd
number of disks, the optimal way to transfer the disks from peg 0 to
peg 1 is to apply repeatedly the ternary tree automorphisms $a$, $b$
and $c$ (in that order), and for even number of disks, the optimal
way is to apply repeatedly the ternary tree automorphisms $b$, $a$
and $c$ (in that order).
By flipping the input and the output symbol in the transducers
$\mathcal{O}_H$ and $\mathcal{O}_H'$ we obtain the partial inverse
transducers $\mathcal{O}_H^{-1}$ and $\mathcal{O}_H'^{-1}$ that can
be used to recognize the geodesic configurations in the Tower of Hanoi
problem and encode them either by using binary representations or by
Gray code words.
\begin{corollary}
The 3 to 2 transducer $\mathcal{O}_H^{-1}$ in
Figure~\ref{geodesic-inv} obtained by inversion from the 2 to 3
transducer $\mathcal{O}_H$, recognizes the geodesic configurations
in the Tower of Hanoi problem. More precisely, starting at the inverse
state $q_{xy}^{-1}$, $x,y\in X_3$, $x \neq y$, and feeding ternary
words of length $n$ into the inverse transducer
$\mathcal{O}_H'^{-1}$, only reversals of ternary words representing
the configurations on the geodesic from $x^n$ to $y^n$ in $\Gamma_n$
are read entirely by the transducer and, for such configurations,
the output represents reversals of the binary representation of the
distance to $x^n$.
\end{corollary}
\begin{corollary}
The 3 to 2 transducer $\mathcal{O}_H'^{-1}$ obtained by inversion
from the 2 to 3 transducer $\mathcal{O}_H'$, recognizes the geodesic
configurations in the Tower of Hanoi problem. More precisely, starting at
the inverse state $t_{xy}^{-1}$, $x,y\in X_3$, $x \neq y$, and
feeding ternary words of length $n$ into the inverse transducer
$\mathcal{O}_H^{-1}$, only reversals of ternary words representing
configurations on the geodesic from $x^n$ to $y^n$ in $\Gamma_n$ are
read entirely by the transducer and, for such configurations, the
reversal of the corresponding binary Gray code word of length $n$ is
produced in the output.
\end{corollary}
\begin{figure}[!ht]
\[
\SelectTips{cm}{}
\xymatrix@C=30pt@R=55pt{
{\mathcal{O}_H^{-1}:}
&
*++[o][F-]{}
\ar@/^1pc/[rr]^{0/0} \ar@{}[ddrr]|<<<<<<{\textstyle q_{01}^{-1}}
\ar@/^1pc/[dl]^{1/1}
&&
*++[o][F-]{}
\ar@/^1pc/[dr]^{2/1} \ar@{}[ddll]|<<<<<<{\textstyle q_{02}^{-1}}
\ar@/^1pc/[ll]^{0/0}
&
\\
*++[o][F-]{}
\ar@/^1pc/[ur]^{1/1} \ar@{}[r]|<<<<<<<{\textstyle q_{21}^{-1}}
\ar@/^1pc/[dr]^{2/0}
&&&&
*++[o][F-]{}
\ar@/^1pc/[dl]^{1/0} \ar@{}[l]|<<<<<<{\textstyle q_{12}^{-1}}
\ar@/^1pc/[ul]^{2/1}
\\
&
*++[o][F-]{}
\ar@/^1pc/[ul]^{2/0} \ar@{}[uurr]|<<<<<<{\textstyle q_{20}^{-1}}
\ar@/^1pc/[rr]^{0/1}
&&
*++[o][F-]{}
\ar@/^1pc/[ll]^{0/1} \ar@{}[uull]|<<<<<<{\textstyle q_{10}^{-1}}
\ar@/^1pc/[ur]^{1/0}
&
}
\]
\caption{A 3 to 2 transducer recognizing geodesic configurations}\label{geodesic-inv}
\end{figure}
For example, the configuration $10021$ is not a geodesic
configuration between $00000$ and $11111$. This follows from the
fact that the reversal word $12001$ is not accepted by
$\mathcal{O}_H^{-1}$ starting from the state $q_{01}^{-1}$ (the
reading stops in state $q_{20}^{-1}$ after reading the first 4
symbols and the transducer cannot read the last symbol).
On the other hand, starting from the state $q_{01}^{-1}$ the word
$12002$ is read completely and it produces the output $10110$, which
says that the configuration $20021$ is on the geodesic between
$00000$ and $11111$ and its distance to $00000$ is $2^4+2^2+2^1=22$.
If we read $12002$ starting from state $q_{10}^{-1}$ we obtain the
output $01001$, which confirms that the configuration $20021$ is on
the geodesic between $11111$ and $00000$ and that its distance to
$11111$ is $2^3+2^0=9$ (note that $22+9=31=2^5-1$, which is the
distance between $00000$ and $11111$).
\section{Acknowledgements} I would like to thank the referee for
the extremely careful reading of the manuscript and her/his numerous
helpful remarks.
\def\cprime{$'$}
\begin{thebibliography}{10}
\bibitem{allouche-b-s:hanoi}
J.-P.~Allouche, J.~B{\'e}tr{\'e}ma, and J.~O.~Shallit,
\newblock Sur des points fixes de morphismes d'un mono\"\i de libre,
\newblock {\em RAIRO Inform. Th\'eor. Appl.} {\bf 23} (1989), 235--249.
\bibitem{allouche-s:as}
J.-P.~Allouche and J.~Shallit,
\newblock {\em Automatic sequences},
\newblock Cambridge University Press, 2003.
\bibitem{bartholdi-g-n:fractal}
L.~Bartholdi, R.~Grigorchuk, and V.~Nekrashevych,
\newblock From fractal groups to fractal sets,
\newblock In {\em Fractals in Graz 2001}, Trends Math.,
Birkh\"auser, 2003, pp.\ 25--118.
\bibitem{bartholdi-g-s:branch}
L.~Bartholdi, R.~I.~Grigorchuk, and Z.~{\v{S}}uni{\'k},
\newblock Branch groups,
\newblock In {\em Handbook of algebra} Vol. {\bf 3}, North-Holland, 2003, pp.\ 989--1112.
\bibitem{bartholdi-n:rabbit}
L.~Bartholdi and V.~Nekrashevych,
\newblock Thurston equivalence of topological polynomials,
\newblock {\em Acta Math.} {\bf 197} (2006), 1--51.
\bibitem{bartholdi-s:bs}
L.~Bartholdi and Z.~{\v{S}}uni{\'k},
\newblock Some solvable automaton groups,
\newblock In {\em Topological and asymptotic aspects of group theory}, Vol.\
{\bf 394} of {\em Contemp. Math.}, Amer. Math. Soc., 2006, pp.\ pp.\ 11--29.
\bibitem{bartholdi-v:basilica}
L.~Bartholdi and B.~Vir{\'a}g,
\newblock Amenability via random walks,
\newblock {\em Duke Math. J.} {\bf 130} (2005), 39--56.
\bibitem{cobham:tags}
A.~Cobham,
\newblock Uniform tag sequences,
\newblock {\em Math. Systems Theory} {\bf 6} (1972), 164--192.
\bibitem{grigorchuk:burnside}
R.~I.~Grigorchuk,
\newblock On {B}urnside's problem on periodic groups,
\newblock {\em Funktsional. Anal. i Prilozhen.} {\bf 14} (1980), 53--54.
\bibitem{grigorchuk-n-s:automata}
R.~I.~Grigorchuk, V.~V.~Nekrashevich, and V.~I.~Sushchanski{\u\i},
\newblock Automata, dynamical systems, and groups,
\newblock {\em Tr. Mat. Inst. Steklova} {\bf 231} (2000), 134--214.
\bibitem{grigorchuk-n-s:oberwolfach2}
R.~Grigorchuk, V.~Nekrashevych, and Z.~{\v S}uni\'c,
\newblock Hanoi towers group on 3 pegs and its pro-finite closure,
\newblock {\em Oberwolfach Reports} {\bf 25} (2006), 15--17.
\bibitem{grigorchuk-n-s:oberwolfach1}
R.~Grigorchuk, V.~Nekrashevych, and Z.~{\v S}uni\'c,
\newblock Hanoi towers groups,
\newblock {\em Oberwolfach Reports} {\bf 19} (2006), 11--14.
\bibitem{grigorchuk-s:standrews}
R.~Grigorchuk and Z.~{\v S}uni{\'c},
\newblock Self-similarity and branching in group theory.
\newblock In {\em Groups St. Andrews 2005, I}, Vol.\ {\bf 339} of {\em London Math.
Soc. Lecture Note Ser.}, Cambridge Univ. Press, 2007, pp.\ 36--95.
\bibitem{grigorchuk-s:hanoi-cr}
R.~Grigorchuk and Z.~{\v{S}}uni{\'k},
\newblock Asymptotic aspects of {S}chreier graphs and {H}anoi {T}owers
groups,
\newblock {\em C. R. Math. Acad. Sci. Paris} {\bf 342}, (2006), 545--550.
\bibitem{grigorchuk-al:atiyah}
R.~I.~Grigorchuk, P.~Linnell, T.~Schick, and A.~{\.Z}uk,
\newblock On a question of {A}tiyah,
\newblock {\em C. R. Acad. Sci. Paris S\'er. I Math.} {\bf 331} (2000), 663--668.
\bibitem{grigorchuk-z:cortona}
R.~I.~Grigorchuk and A.~{\.Z}uk,
\newblock On the asymptotic spectrum of random walks on infinite families of
graphs,
\newblock In {\em Random walks and discrete potential theory (Cortona, 1997)},
Sympos. Math., {\bf 39}, Cambridge Univ. Press, 1999, pp.\ 188--204.
\bibitem{grigorchuk-z:l2}
R.~I.~Grigorchuk and A.~{\.Z}uk,
\newblock The lamplighter group as a group generated by a 2-state automaton,
and its spectrum,
\newblock {\em Geom. Dedicata} {\bf 87} (2001), 209--244.
\bibitem{grigorchuk-z:basilica1}
R.~I.~Grigorchuk and A.~{\.Z}uk,
\newblock On a torsion-free weakly branch group defined by a three state
automaton,
\newblock {\em Internat. J. Algebra Comput.} {\bf 12} (2002), 223--246.
\bibitem{hinz:ens}
A.~M.~Hinz,
\newblock The {T}ower of {H}anoi,
\newblock {\em Enseign. Math. (2)} {\bf 35} (1989), 289--321.
\bibitem{nekrashevych:b-selfsimilar}
V.~Nekrashevych.
\newblock {\em Self-similar {G}roups}, Vol.\ {\bf 117} of {\em Mathematical Surveys
and Monographs}.
\newblock Amer. Math. Soc., 2005.
\bibitem{richomme-w:cube-free}
G.~Richomme and F.~Wlazinski,
\newblock Some results on {$k$}-power-free morphisms,
\newblock {\em Theoret. Comput. Sci.} {\bf 273} (2002), 119--142.
\bibitem{sidki:circuit}
S.~Sidki,
\newblock Automorphisms of one-rooted trees: growth, circuit structure, and
acyclicity,
\newblock {\em J. Math. Sci. (New York)} {\bf 100} (2000), 1925--1943.
\bibitem{silva-s:lamplighter}
P.~V.~Silva and B.~Steinberg,
\newblock On a class of automata groups generalizing lamplighter
groups,
\newblock {\em Internat. J. Algebra Comput.} {\bf 15} (2005), 1213--1234.
\bibitem{sloane:online}
N.~J.~A.~Sloane, The on-line encyclopedia of integer sequences.
\newblock \href{http://www.research.att.com/\~njas/sequences/}{\tt {http://www.research.att.com/\~{}njas/sequences/}}.
\bibitem{wilson:nonuniform}
J.~S.~Wilson,
\newblock On exponential growth and uniformly exponential growth for groups,
\newblock {\em Invent. Math.} {\bf 155} (2004), 287--303.
\end{thebibliography}
\newpage
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary
11Y55;
Secondary 11B85, 20M20, 20M35. \\
\noindent {\it Keywords}: transducers, integer sequences, automatic
sequences, self-similar groups, self-similar semigroups, Tower of
Hanoi problem.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A003188}, \seqnum{A005836}, \seqnum{A038500},
\seqnum{A055661}, \seqnum{A057427}, \seqnum{A060236},
\seqnum{A060372}, \seqnum{A060373}, \seqnum{A060374}, and
\seqnum{A080846}.)
\bigskip
\hrule
\bigskip
\noindent Received December 4, 2006; revised version
received April 10 2007. Published in {\it Journal of Integer
Sequences}, April 13 2007.
\bigskip
\hrule
\bigskip
\noindent Return to \htmladdnormallink{Journal of Integer Sequences
home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in
\end{document}