Content-Type: multipart/mixed; boundary="-------------0012051554166"
This is a multi-part message in MIME format.
---------------0012051554166
Content-Type: text/plain; name="00-487.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="00-487.keywords"
Continuous Map, Discontinuous Map,
Representation, Subshift, Symbolic Dynamics
---------------0012051554166
Content-Type: application/x-tex; name="duan.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="duan.tex"
%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
% LaTeX File
%
% Symbolic Representations of Iterated Maps
%
%
by Xin-Chu Fu, Weiping Lu, Peter Ashwin and Jinqiao Duan
%
duan@iit.edu
%
% Submitted to: Transactions of Ameri. Math. Soc.
%
%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}
\usepackage{amssymb}
\topmargin -1.3cm
\textheight 24cm
\textwidth 15cm
\oddsidemargin 0.5cm
\unitlength 0.93mm
%\setlength{\textwidth}{15.5cm}
%\setlength{\textheight}{23cm}
%\setlength{\oddsidemargin}{1cm}
%\setlength{\topmargin}{-1cm}
%\setlength{\unitlength}{0.93mm}
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\ep{\varepsilon}
\def\f{\varphi}
\def\e{\eta}
\def\l{\lambda}
\def\L{\Lambda}
\def\p{\psi}
\def\r{\rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\x{\xi}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\T{\mathbb{T}}
\newcommand{\MA}{{\mathcal{A}}}
\newcommand{\MI}{{\mathcal{I}}}
\newcommand{\MP}{{\mathcal{P}}}
\newcommand{\MR}{{\mathcal{R}}}
\newcommand{\MS}{{\mathcal{S}}}
\def\rep{representation }
\newcommand{\card}{\mbox{card}}
\newtheorem{defn}{{\sc Definition}}[section]
\newtheorem{thm}{{\sc Theorem}}[section]
\newtheorem{lem}[thm]{{\sc Lemma}}
\newtheorem{pro}[thm]{{\sc Proposition}}
\newtheorem{cor}[thm]{{\sc Corollary}}
\newtheorem{rem}{\sc Remark}[section]
\newtheorem{eg}{\sc Example}[section]
\def\proof{{\noindent\em Proof.} }
\def\qed{\hfill $\Box$ \newline \vspace{2mm}}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
\catcode`\@=11
\@addtoreset{equation}{section}
%\renewcommand{\baselinestretch}{2.0}
\begin{document}
\title{ Symbolic Representations of Iterated Maps }
\author{}
\date{November 14, 2000 }
\maketitle
% authors:
\begin{center}
{\large Xin-Chu Fu$^{1}$}, {\large Weiping Lu$^{2}$},
{\large Peter Ashwin$^{1}$} and {\large Jinqiao Duan$^{3}$}
\vspace{0.2cm}
1. {\em School of Mathematical Sciences, Laver Building\\
University of Exeter, Exeter EX4 4QJ, UK}\\
2. {\em Department of Physics, Heriot-Watt University \\
Riccarton, Edinburgh EH14 4AS, UK} \\
3. {\em Department of Applied Mathematics\\
Illinois Institute of Technology, Chicago, IL 60616, USA}
\vspace{0.2cm}
\end{center}
\begin{abstract}
\noindent This paper presents a general and systematic discussion of
various symbolic representations of iterated maps through subshifts.
We give a unified model for all continuous maps on a metric space,
by representing
a map through a general subshift over usually an uncountable alphabet.
It is shown that at most the second order representation
is enough for a continuous map.
In particular, it is shown that the dynamics of one-dimensional
continuous maps to a great extent can be transformed to
the study of subshift structure of a general symbolic
dynamics system. By introducing distillations, partial representations
of some general continuous maps are obtained.
Finally, partitions and representations of a class of discontinuous maps,
piecewise continuous maps are discussed, and as examples, a representation
of the Gauss map via a full shift over a countable alphabet and
representations of interval exchange transformations as subshifts of infinite
type are given.
\vspace{0.3cm}
\noindent {\bf Key words:} \ Continuous Map, Discontinuous Map,
Representation, Subshift, Symbolic Dynamics
\end{abstract}
% \begin{center}
\section{Introduction}
% \end{center}
It has long been known that interesting
behaviour can occur when iterating continuous maps.
Such maps define discrete dynamical systems, which
have been used as simplified prototypical
models for some engineering and biological
processes; see, e.g.~\cite{May, Hao89, Fu98}.
Through the Poincar\'e section maps, discrete dynamical systems have also
been used to study continuous dynamical systems, e.g.~\cite{GH83, Wiggins88}.
Considerable progress has been made in the last two decades in the
understanding of dynamical behaviour of nonlinear continuous maps.
These systems, while mostly studied individually because of their
distinct nature of nonlinear interactions, show similar dynamical features,
especially when the parameters of the systems are close to some critical values
where abrupt change in behavior takes place. The universality of such behavior
has been a key subject in the study of nonlinear dynamics. A mathematical
framework has, however, yet to be established under which a class of dynamical
systems, such as one-dimensional continuous maps, can be described by a unified
model. Such a framework will improve our understanding of general properties
of dynamical systems and may be useful in our effort to classify
dynamical systems.
Shifts and subshifts defined on a space of abstract symbols
are special discrete dynamical systems which are called
symbolic dynamics systems. Symbolic dynamics is a powerful tool to study
more general discrete dynamical systems, because the latter often contain
invariant subsets on which the dynamics is similar or even
equivalent to a shift or subshift.
Moreover, there are a number of definitions of chaos, namely
(1) the Li-Yorke definition;
(2) Devaney's definition; (3) topological mixing;
(4) Smale's horseshoe; (5) transversal homoclinic points; and
(6) symbolic dynamics.
The symbolic dynamics definition is especially important of these definitions,
as it unifies aspects of many of the definitions. More precisely, it
implies the first three definitions, is topologically conjugate to
the fourth one and occurs as a subsystem of the fifth.
Furthermore (see for example Ford \cite{Alekseev})
symbolic dynamics is very important for analysis of applications of
nonlinear dynamics in physical sciences.
For a dynamical system, we can study it either directly or via other
systems which are better understood. Symbolic representations are methods to
study dynamical systems through shifts and subshifts.
In the study of hyperbolic dynamics of homeomorphisms, symbolic dynamics is
one of the most fundamental models. Since the discovery of the Markov
partitions of the two dimensional torus by Berg \cite{Berg} and the
related work by Adler and Weiss \cite{Adler2}, symbolic representations of
hyperbolic systems through the Markov partitions have been studied
extensively (e.g., see \cite{Adler}).
The equivalence between Smale's horseshoe and the symbolic dynamical system
$(\S(2), \s)$ (see \cite{Smale}) implies that the former has a symbolic
representation through the full shift $(\S(2), \s)$. A similar symbolic
representation has also been revealed by Wiggins (see \cite{Wiggins88})
on higher dimensional versions of the Smale's horseshoe. Earlier works
in \cite{Zhang} and \cite{Fu96}
established that, under certain conditions, the
restrictions of a general continuous self-map $f: X \rightarrow X$ to some
horseshoe-like invariant subsets are topologically conjugate to
$\s|_{\S(N)}$ or $\s|_{\S(\Z_+)}$
(see \cite{Fu96}), where $(\S(\Z_+), \s)$ is the symbolic dynamics system
with a countable alphabet. These results actually demonstrated the partial
symbolic representation of a class of maps as a full shift over a
countable alphabet.
Motivated by the above work, we study in this paper symbolic representations of
continuous self-maps
by using a more general and systematic approach. We present a unified model for
all continuous maps on a metric space, by representing a map as a general
subshift $(\S(X),\s)$. We show that the subshifts of $(\S(X), \s)$ may be
used as such a unified model for all continuous self-maps on a metric space $X$.
And it is shown that at most the second order representation
is enough for a continuous map.
In particular, when $X$ is a closed interval, we show that the dynamics of
one-dimensional continuous maps to a great extent can be transformed to
the study of subshifts of a symbolic dynamical system.
We also discuss quasi-representations, and by introducing distillations,
partial representations of some general continuous maps are obtained.
Finally, partitions and representations of a class of discontinuous maps,
piecewise continuous maps, are discussed, and as examples, a regular
representation of the Gauss map via a full shift over a countable alphabet
and regular representations of interval exchange transformations as
subshifts of infinite type are given.
\section{Some Definitions, Notation and Lemmas}
Before turning to the next section to discuss representation theorems, we
recall some definitions, introduce some notation, and provide some lemmas.
Let $(X,d)$ be a metric
space and denote by $\S(X)$ the space $X^{\Z_+}$ which
consists of functions from the nonnegative integers $\Z_+$ to the
metric space $X$. $x \in \S(X)$ may thus be denoted by $x=(x_0, x_1, \cdots,
x_i, \cdots)$, $x_i \in X, i \ge 0$. Further, let $\S(X)$ be endowed with the
product
topology, so $\S(X)$ is metrizable. The metric on $\S(X)$ can
be chosen to be
$$
\r(x, y)=\sum^{+\infty}_{i=0} \frac{1}{2^i} \frac{d(x_i, y_i)}{1+
d(x_i, y_i)}, \;\;\;\; x=(x_0, x_1, \cdots), \;\; y=(y_0,y_1, \cdots) \in
\S(X).
$$
The shift map $\s: \S(X) \rightarrow \S(X)$ is defined by
$(\s(x))_i=x_{i+1}, \; i=0,1, \cdots.$
Since $ \r (\s(x), \s(y)) \le 2 \r(x, y), $
$\s$ is continuous. $(\S(X), \s)$ is a general symbolic dynamics system
(see \cite{Wiggins88, Fu92, Fu98}). We call $X$ the
symbol space or alphabet, and $\S(X)$ the symbol sequence space.
When $X$ is chosen as $\{0,1,\cdots, N-1 \}$ and the metric $d$ on
$\{0,1,\cdots, N-1 \}$ is the discrete metric:
$$ d(m,n)=\left\{\begin{array}{ll} 0, \;\;\;\; m=n\\ 1, \;\;\;\; m\ne n
\end{array} \right., $$
then $(\S(X), \s)$ becomes the usual symbolic dynamics system
$(\S(N), \s)$ as in \cite{GH83}.
Let $\S \subseteq \S(X)$ be closed, and invariant for $\s$, i.e., $\s(\S)
\subseteq \S $, then $(\S, \s)$ forms a subsystem of $(\S(X), \s)$. We call
$(\S, \s)$ a subshift of the full shift $(\S(X), \s)$, denoted by $(\S, \s) \le
(\S(X), \s) $.
We denote by $C(X)$ the set of all continuous self-maps on $X$ and $M(X)$
the set of all self-maps on $X$. We also call the iteration system of an
$f \in M(X)$ a dynamical system, denoted by $(X, f)$.
For two dynamical systems $f_1 : X_1 \rightarrow X_1 $ and $f_2 : X_2
\rightarrow X_2 $, where $X_i$ are metric spaces and $f_i \in M(X_i), i=1,2,$
if there exists a homeomorphism $h: X_1 \rightarrow X_2 $ such that $hf_1=f_2h$,
then we call $f_1$ is topologically conjugate to $f_2$, denoted by $f_1 \sim
f_2$. If $h$ is continuous and surjective, but not necessarily invertible,
and if $hf_1=f_2h$,
then we call $f_1$ is topologically semi-conjugate to $f_2$, and also call
$f_2$ a factor of $f_1$ (and $f_1$ an extension of $f_2$).
We call $f_1$ and $f_2$ are weakly conjugate if each is a factor of the other.
We give the following definitions for various symbolic representations:
\begin{defn}
If for an $f \in M(X)$, there exists a subshift $(\S, \s)$ of certain a
symbolic dynamical system and a surjective map $h: \S \to X$, and a countable
subset $D \subseteq \S$, such that $h$ is one-to-one and continuous on
$\S\setminus D$, finite-to-one on $D$, and
$f\circ h = h \circ \s $, then we call the subshift $(\S, \s)$ a
{\rm regular representation} of the dynamical system $(X, f)$.
If $D=\varnothing$, we call the subshift $(\S, \s)$ a
{\rm faithful representation} of the dynamical system $(X, f)$.
If $h$ is a topological conjugacy, we call $(\S, \s)$ a
{\rm conjugate representation} of $(X, f)$.
If $\s|_{\S}$ and $f$ are weakly conjugate, we call $(\S, \s)$ a
{\rm weakly conjugate representation} of $(X, f)$.
If $h$ is a topological semi-conjugacy, i.e., $(X, f)$ is a factor of
$(\S, \s)$, we call $(\S, \s)$ a {\rm semi-conjugate representation} of
$(X, f)$.
If $(\S, \s)$ is a factor of $(X, f)$, we call $(\S, \s)$ a
{\rm quasi-representation} of $(X, f)$.
In all the above representations, we call a correspondence between
symbol sequences in $\S$ and points in $X$ (either from $\S$ to $X$ or from
$X$ to $\S$) a {\rm coding}.
\end{defn}
{}From the definition above, among the six representations, conjugate
representation is the strongest one, since it implies all the others. A weakly
conjugate representation is always a semi-conjugate representation and a
quasi-representation. A faithful representation is also a semi-conjugate
representation. Quasi-representation is the weakest one, but it still tells us
some information. For example, if $(\S, \s)$ is a quasi-representation of
$(X, f)$, then $h_{\rm top} (f)\ge h_{\rm top} (\s |_{\S})$, while the
latter is usually easier to calculate
($h_{\rm top} (\cdot)$ denotes the topological entropy).
In the definition of a regular representation, we allow $h$ to
be possibly discountinuous
on $D$ so that we can apply this definition to symbolic representations of some
discontinuous maps.
Note that weak conjugacy is strictly weaker than conjugacy (\cite{Lind}).
For example, the Fibonacci subshift (consists of all sequences of $0$'s and
$1$'s with $1$'s separated by $0$'s) and the even subshift
(consists of all sequences of $0$'s and $1$'s with $1$'s separated by an
even number of $0$'s) are weakly conjugate, but they are not conjugate since
one is a subshift of finite type and the other is a subshift of infinite
type.
Throughout this paper, for $a \in I=[0, 1]$, we denote by $r_m(a)$ the $m$-adic
fraction
$$
r_m(a)=\sum^{+\infty}_{i=0} \frac{a_i}{m^{i+1}} \ ,
$$
and when $a\ne 0$, we require that there are infinite number of non-zero
$a_i$'s, $ i \ge 0$, and denote $a_i$ by $r^i_m(a)$. Unless indicated
otherwise, we will always make this choice when we write an $m$-adic fraction
expansion of a real number.
For an integer sequence $x \in \S(N),
x=(x_0, x_1, \cdots, x_i, \cdots)$, we also denote in form by $r_m(x)$ the
$m$-adic fraction
$$
r_m(x)=\sum^{+\infty}_{i=0} \frac{x_i}{m^{i+1}} \ , ~~\mbox{where} \ m \ge N.
$$
For $ a, b \in I,$ let
\begin{eqnarray*}
d_0(a, b) & = & |a-b|, \\
d_1(a, b) & = & \sum^{+\infty}_{i=0}\frac{1}{2^i}|r^i_2(a)-r^i_2(b)|,
\end{eqnarray*}
and denote by $I_k$ the metric space $(I, d_k),\ k=0,1.$
Define the metric $\r_k$ on $\S(I_k)$ as
$$
\r_k(x,y)=\sum^{+\infty}_{i=0} \frac{1}{2^i}
\frac{d_k(x_i,y_i)}{1+d_k(x_i,y_i)}, \ \ k=0,1.
$$
The lemmas below are necessary for the proof
of the theorems in the following sections.
\begin{lem} \label{lem_metric}
Suppose $x=(x_0, x_1,\cdots,x_i, \cdots),
y=(y_0, y_1,\cdots,y_i, \cdots) \in \S(X)$, then
\begin{eqnarray*}
\r(x,y) < \frac{1}{2^{2N+1}} ~~ & \Longrightarrow &~~
d(x_i, y_i)< \frac{1}{2^N},~\forall ~i \le N;\\
\mbox{For}~ \d > 0, ~d(x_i, y_i)< \d,~\forall ~i \le N ~~ &
\Longrightarrow &~~
\r(x,y) < 2 \d+ \frac{1}{2^N}.
\end{eqnarray*}
\end{lem}
\proof
Otherwise, if there exists $i_0\le N,$ such that
$d(x_{i_0}, y_{i_0})\ge 1/2^N, $ then
$$
\r(x, y)\ge \frac{1}{2^{i_0}}\frac{\frac{1}{2^N}}{1+\frac{1}{2^N}}\ge
\frac{1}{2^N}\frac{1}{1+2^N}\ge \frac{1}{2^{2N+1}} ~ .
$$
This is a contradiction. So we have the first inequalities.
We can check directly the second inequality. \hfill $\Box$
\begin{lem} \label{lem_compact}
If $A\subseteq I$ is compact in $I_1$, then $A$ is also compact in $I_0$;
and if $\S\subseteq \S(I)$ is compact in $\S(I_1)$,
then $\S$ is also compact in $\S(I_0)$.
\end{lem}
\proof
$\forall a, b \in I$,
$$
d_0(a, b)=|a-b|=|\sum^{+\infty}_{i=0}2^{-(i+1)}(r^i_2(a)-r^i_2(b))|
\le \frac{1}{2}d_1(a, b).
$$
So any limit points of $A$ in the metric $d_1$ are also limit points of $A$
in the metric $d_0$. Hence compactness of $A$ in $I_1$ implies compactness of
$A$ in $I_0$.
Similarly, we can check the compactness of $\S$ in $\S(I_0)$.
\qed
We say a subshift $(\S, \s)$ satisfies the condition (\ref{condition}) if
\begin{eqnarray}
\forall \ x=(x_0, x_1,\cdots ), \ y=(y_0,y_1, \cdots )\in \S, \ x=y \mbox{ if
and only if } x_0 = y_0. \label{condition}
\end{eqnarray}
\begin{lem} \label{lem_condition}
For any $(\S, \s) \le (\S(I_1), \s)$,
there exists $(\S^*, \s) \le (\S(I_1), \s)$ such that
$\s|_{\S} \sim \s|_{\S^*}$, and $(\S^*, \s)$ satisfies
the condition (\ref{condition}).
\end{lem}
\proof
$\forall \x \in \S, \x=(\x_0, \x_1, \cdots, \x_i, \cdots). $ Rewrite $\x_i$ by
$$
\x_i=r_2(\x_i)=\sum^{+\infty}_{j=0} \frac{\x_{ij}}{2^{j+1}}, \ \ i=0, 1, \cdots.
$$
Let
\begin{eqnarray*}
r(\x)&=& 0.\x_{00}\x_{10}\x_{01}\cdots\x_{k0}\x_{k-1,1}\cdots\x_{1,k-1}\x_{0k}
\cdots \ \ \ \mbox{(binary fraction),}\\
R(\x)&=& (r(\x), r(\s(\x)), \cdots, r(\s^k(\x)), \cdots).
\end{eqnarray*}
{}From $R(\x)=R(\e)$ we have $r(\x)=r(\e)$, thus $\x_{ij}=\e_{ij} \ , \
i,j=0,1,
\cdots.$ As a result, $\x=\e$, that is, $R$ is one-to-one.
Whenever $\x, \e \in \S$ with $\r_1(\x, \e)<1/2^{2N+1}$,
from Lemma~\ref{lem_metric} we have $d_1(\x_i,
\e_i)<1/2^N, i\le N.$ So $\x_{ij}=\e_{ij} \ , \ i,j\le N$. Denote
\begin{eqnarray*}
r(\x)&=&\sum^{+\infty}_{k=0}2^{-(k+1)}(r(\x))_k \ , \\
r(\e)&=&\sum^{+\infty}_{k=0}2^{-(k+1)}(r(\e))_k \ ,
\end{eqnarray*}
we have
\begin{eqnarray*}
(r(\x))_k&=& (r(\e))_k \ , \ \ k\le \frac{1}{2}(N+1)(N+2),\\
(r(\s(\x)))_k&=& (r(\s(\e)))_k \ , \ \ k\le \frac{1}{2}N(N+1),\\
& \cdots &\\
(r(\s^l(\x)))_k&=& (r(\s^l(\e)))_k \ , \ \ l\le N, \ k\le
\frac{1}{2}(N+1-l)(N+2-l),\\
& \cdots &
\end{eqnarray*}
Take $N=2M.$ Denote $N_l=\frac{1}{2}(N+1-l)(N+2-l)$. Then for $l\le M$, we have
\begin{eqnarray*}
d_1(r(\s^l(\x)), r(\s^l(\e)))&=&\sum^{+\infty}_{k=0}\frac{1}{2^k}
|(r(\s^l(\x)))_k-(r(\s^l(\e)))_k|\\
& \le &\sum^{+\infty}_{k=N_l+1}\frac{1}{2^k}=\frac{1}{2^{N_l}}\le
2^{-\frac{1}{2}(M+1)(M+2)}<\frac{1}{2^M} \ ,
\end{eqnarray*}
therefore
$$
\r_1(R(\x), R(\e))\le
\sum^{M}_{l=0}\frac{1}{2^l}\frac{2^{-M}}{1+2^{-M}}
+\frac{1}{2^M}<\frac{3}{2^M} \ ,
$$
which implies that $R: \S \to R(\S)$ is continuous.
Take $\S^*=R(\S)$. Let $\tilde \x, \tilde \e \in\S^*$, then
$\exists~ \x, \e \in \S,$ such that
\begin{eqnarray*}
\tilde \x &=& (r(\x), r(\s(\x)), \cdots, r(\s^k(\x)), \cdots),\\
\tilde \e &=& (r(\e), r(\s(\e)), \cdots, r(\s^k(\e)), \cdots)
\end{eqnarray*}
Let $N=\frac{1}{2} (2k+1)(2k+2)$, when
$$
\r_1 (\tilde \x, \tilde \e)< \frac{1}{2^{2N+1}},
$$
from Lemma~\ref{lem_metric} we have
$$
d_1(r(\s^i(\x)), r(\s^i(\e))) < \frac{1}{2^N}, ~ i \le N.
$$
We get $\x_{ij}=\e_{ij}, ~i \le k,~j\le 2k$, and therefore
$d_1(\x_i, \e_i) \le \frac{1}{2^{2k}},~i \le k$.
Again from Lemma~\ref{lem_metric} we have
$$
\r_1(R^{-1}(\tilde \x),R^{-1}(\tilde \e)) <
\frac{1}{2^{2k-1}}+\frac{1}{2^k}.
$$
Therefore $R^{-1}: \S^* \to \S$ is also continuous,
hence $R$ is a homeomorphism. And $\forall \x \in \S,$
$$
R\s (\x)=(r(\s (\x )), r(\s ^2(\x )), \cdots, r(\s ^k(\x )), \cdots)=\s R(\x ),
$$
so $\s|_{\S} \sim \s|_{\S^*}$, while the subshift $(\S^*, \s)$ satisfies the
condition (\ref{condition}). \hfill $\Box$
\begin{lem} \label{lem_factor}
The full shift $(\S(I_1), \s)$ is a faithful representation of $(\S(I_0), \s)$.
And $\forall ~(\S, \s) \le (\S(I_1), \s)$ with $\S$ compact,
there exists a subshift $(\S', \s) \le (\S(I_0), \s)$, such that
$\s|_{\S} \sim \s|_{\S'}$.
\end{lem}
\proof
$\forall a,b \in [0, 1]$,
$$
d_0(a, b) \le \frac{1}{2}d_1(a, b).
$$
So $\forall \x, \e \in \S(I_1)$,
$$
\r_0(\x, \e)\le \r_1(\x, \e),
$$
hence the identity mapping $i: \S(I_1)\rightarrow \S(I_0)$ is continuous.
Moreover, the following diagram
commutes:
$$
\begin{array}{ccc}
\S(I_1) & \mathop{\longrightarrow}\limits^{\s} & \S(I_1) \\
i\downarrow & & \downarrow i \\
\S(I_0) & \mathop{\longrightarrow}\limits^{\s} & \S(I_0)
\end{array}
$$
So $(\S(I_1), \s)$ is a faithful representation of $(\S(I_0), \s)$.
$\forall ~ (\S, \s) \le (\S(I_1), \s)$ with $\S$ compact,
$i: \S \to \S'=i(\S)=\S \subseteq \S(I_0)$ is a homeomorphism, therefore
$(\S, \s)\le (\S(I_0),\s)$ and $\s|_{\S} \sim \s|_{\S'}$. \hfill $\Box$
The result in Lemma~\ref{lem_factor} can be generalized to:
\begin{pro}
If $(\S,\s)$ is a compact subshift of a faithful representation of $(X, f)$ under
coding $h$, then $(\S, \s)$ is a conjugate representation of $(h(\S), f)$, a compact
subsystem of $(X, f)$. \hfill $\Box$
\end{pro}
\begin{rem} \label{rem_factor2}
$ \forall f \in M(I), \ \ f|_{I_0}$ is a factor of $f|_{I_1}$.
\end{rem}
For the identity mapping $i: I_1 \rightarrow I_0$, from the proof of Lemma
\ref{lem_factor}, we have
$$
d_0(i(x), i(y))=d_0(x, y)\le \frac{1}{2}d_1(x, y), \ \ \forall x, y \in I_1 \ .
$$
So $i: I_1 \rightarrow I_0$ is continuous.
$\forall f \in M(I)$, it is obvious that the following diagram
commutes:
$$
\begin{array}{ccc}
I_1 & \mathop{\longrightarrow}\limits^{f} & I_1 \\
i\downarrow & & \downarrow i \\
I_0 & \mathop{\longrightarrow}\limits^{f} & I_0
\end{array}
$$
So $f|_{I_0}$ is a factor of $f|_{I_1}$.
\section{Conjugate Representations} \label{conjugate}
As discussed in \cite{Adler}, representing a general dynamical system by a
symbolic one involves a fundamental complication: it is difficult and
sometimes impossible to find
a coding of a continuous one-to-one correspondence between orbits and
symbolic sequences, and especially when we desire the shift system to be
one of finite type and with a finite (or at most
countable \cite{Fu92, Fu96, Kitchens}) alphabet.
% Therefore sometimes we need either to abandon the quest of finding a
% conjugate representation for a given dynamical system, or to abandon the
% quest of representing only by a subshift
% of finite type with a finite (or countable) alphabet.
In this section,
we will discuss conjugate representations of general continuous maps through general
subshifts, which usually involve an uncountable alphabet.
For a metric space $(X,d)$, there exists a huge number of
continuous self-maps on
$X$. The dynamics on $X$ is therefore diverse.
The following theorem shows that
the general subshifts of $(\S(X), \s)$ can be used as a unified
model for all continuous self-maps on the space $X$.
\begin{thm} \label{th_conj_rep}
Let $(X, d)$ be a metric space,
$\forall f \in C(X), \exists (\S, \s) \le (\S(X), \s)$,
such that $ (\S, \s)$ is a conjugate representation of $(X, f)$.
\end{thm}
\proof
Define a mapping $h: X \rightarrow \S(X)$ as
$$
h(x)=(x, f(x), f^2 (x), \cdots, f^n (x), \cdots),
$$
then $h$ is a one-to-one mapping.
Since $f$ is continuous, for any
positive integer $N$ and any sequence $\{ x_n\} \subset X$ with
$ \lim_{n\rightarrow +\infty }x_n=x_0 \in X$, we have
$$
\lim_{n\rightarrow +\infty }d(f^k(x_n), f^k(x_0))=0, \ \ k=0, 1, \cdots, N.
$$
{}From
\begin{eqnarray*}
0 & \le & \r(h(x_n), h(x_0))=\sum^{+\infty}_{i=0} \frac{1}{2^i}
\frac{d(f^i(x_n), f^i(x_0))}{1+d(f^i(x_n), f^i(x_0))}\\
& \le & \sum^{N}_{i=0} \frac{1}{2^i}
\frac{d(f^i(x_n), f^i(x_0))}{1+d(f^i(x_n), f^i(x_0))}+\sum^{+\infty}_{i=N+1}
\frac{1}{2^i} \ ,
\end{eqnarray*}
we have
$$
0 \le \lim_{n\rightarrow +\infty}\r(h(x_n), h(x_0)) \le \frac{1}{2^N} \ ,
\ \forall N \ge 1,
$$
that is, $h: X \rightarrow \S(X)$ is continuous.
Suppose we have a sequence
$\{ \x^{(n)}=(\x^{(n)}_0,\x^{(n)}_1,\cdots,\x^{(n)}_i), \cdots \} \subset h(X)$
with
$$
\lim_{n\rightarrow +\infty}\x^{(n)}=\e=(\e_0,\e_1,\cdots, \e_i, \cdots) \in
h(X),
$$
then
$$
\lim_{n\rightarrow +\infty}\r(\x^{(n)}, \e)=0.
$$
{}From
$$
0 \le \frac{d(\x^{(n)}_0, \e_0)}{1+d(\x^{(n)}_0, \e_0)} \le \r(\x^{(n)}, \e)
\rightarrow 0 \mbox{ as } n \rightarrow +\infty,
$$
we obtain
$$
\lim_{n\rightarrow +\infty}d(\x^{(n)}_0, \e_0)=0.
$$
So $h^{-1}: h(X)\rightarrow X$ is also continuous, and therefore $h$ is a
homeomorphism from $X$ to $h(X)$.
Moreover,
$$
hf(x)=(f(x), f^2(x), \cdots)=\s h(x), \ \ \forall x \in X,
$$
i.e., $ hf=\s h. $
Take $\S =h(X)$, then $\S $ is invariant for the shift map $\s $, and $\S $
is a closed subset of $\S (X)$. So $(\S, \s) \le (\S(X), \s)$, and $f$ is
topologically conjugate to $\s|_{\S}$.
\qed
\begin{rem}
The theorem above shows how to symbolize $(X, f)$ to $(\S, \s)$.
Although the phase space of the latter may be more complex than that of the
former, the map action of the latter is definitely simpler than that of the
former. If we can understand the construction of the space $\S$ by some means,
then the dynamics of $f$ on $X$ can be known accordingly.
\end{rem}
We note that the subshift $(\S, \s)$ in the proof of Theorem \ref{th_conj_rep}
satisfies the condition (\ref{condition}), i.e.,
$$
\forall \ x=(x_0, x_1,\cdots ), \ y=(y_0,y_1, \cdots )\in \S, \ x=y \mbox{ if
and only if } x_0 = y_0
$$
This is a restriction under which Theorem \ref{th_conj_rep} is reversible, as stated
below.
\begin{thm} \label{th_conj_rep2}
Suppose $(X, d)$ is a compact metric space, $(\S, \s) \le (\S(X), \s)$, and
$(\S, \s)$ satisfies condition (\ref{condition}); then there exists a compact subset
$X_0 \subseteq X$, and a continuous self-map $f$ on $X_0$, such that $(\S, \s)$
is a conjugate representation of $(X_0, f)$.
\end{thm}
\proof
Let $(\S, \s)$ be a subshift of $(\S(X), \s)$ satisfying condition (\ref{condition}).
Define $\f: \S \rightarrow X$ as
$$
\f((x_0, x_1,\cdots))=x_0, \ \ \forall \ (x_0, x_1,\cdots) \in \S.
$$
Then $\f$ is a one-to-one mapping. Denote $\f(\S)$ by $X_0$. $\forall (x_0,
x_1,\cdots), (y_0,y_1, \cdots) \in \S,$
\begin{eqnarray*}
d(\f((x_0, x_1,\cdots)), \f((y_0,y_1, \cdots))) & = & d(x_0, y_0)\\
& < & (1+d(x_0, y_0))\r((x_0, x_1,\cdots), (y_0,y_1, \cdots)),
\end{eqnarray*}
$\forall \ep > 0, $ let $\d=\ep /(1+\ep)$, then $0 < \d < 1.$ Whenever
$\r((x_0, x_1,\cdots), (y_0,y_1, \cdots)) < \d$,
\begin{eqnarray*}
\frac{d(x_0,y_0)}{1+d(x_0,y_0)} & < & \r((x_0, x_1,\cdots), (y_0,y_1, \cdots)) <
\d, \\
d(x_0, y_0) & < & \frac{\d}{1-\d}, \\
d(\f((x_0, x_1,\cdots)), \f((y_0,y_1, \cdots))) & < & (1+\frac{\d}{1-\d})\d=\ep,
\end{eqnarray*}
so $\f: \S \rightarrow X_0$ is continuous.
Since $X$ is compact, $\S(X)$ is also compact and so is $\S$. As a
result, $\f: \S \rightarrow X_0$ is a homeomorphism and hence $X_0 \subseteq X$
is compact.
Take $f: X_0 \rightarrow X_0 $ as $f=\f \s \f^{-1}$, then $f$ is continuous, and
$f|_{X_0} \sim \s|_{\S}$.
\qed
Naturally, one would like to ask if Theorem \ref{th_conj_rep2} still holds for
subshifts $(\S, \s)$ which don't satisfy the condition (\ref{condition})? The answer
is yes if one can construct another subshift $(\S^*, \s)$ such that $(\S, \s)
\sim (\S^*, \s)$, and $(\S^*, \s)$ satisfies the condition (\ref{condition}). This can
be done at least for one-dimensional self-maps, as shown in the following
example.
\vspace{0.3cm}
\noindent {\sc Example} \ Let $X=[0, 1], d(x,y)=|x-y|, \S=\S(2)=\{(x_0, x_1,
\cdots, x_i, \cdots): x_i=0, 1, i \ge 0 \}$. Take $\S^*=R(\S)=\{R(x): x \in
\S \}$, where $R: \S \rightarrow \S(X)$ is defined as
\begin{eqnarray*}
R(x) & = & (r_{10}(x), r_{10}(\s(x)), \cdots, r_{10}(\s^k(x)), \cdots),\\
r_{10}(x)& = & 0.x_0x_1 \cdots x_k \cdots \ \ \mbox{(decimal fraction)},
\forall x=(x_0, x_1, \cdots, x_k, \cdots) \in \S,
\end{eqnarray*}
then it can be verified (see Remark~\ref{rem_embed} in
Section~\ref{quasi} for detail) that $R: \S
\rightarrow \S^*$ is a topological conjugacy. So $\s|_{\S} \sim \s|_{\S^*}$,
while $(\S^*, \s)$ satisfies the condition (\ref{condition}).
\vspace{0.3cm}
In the following theorem, we reach a more general
conclusion for the case of $X=[0,1]$. That is, when $X=[0,1]$, Theorem
\ref{th_conj_rep2}
holds for all subshifts $(\S, \s)\le (\S(I_0), \s)$ with $\S$ compact
in $(\S(I_1), \s)$, regardless of the condition (\ref{condition}).
\begin{thm} \label{th_symb_rep}
$\forall ~ (\S, \s) \le (\S(I_0), \s)$ with $\S$ compact in $\S(I_1)$,
there exists an $f \in C(I_0)$
and $\L \subseteq I_0$ with $\L$ compact and invariant for $f$,
such that $(\S, \s)$ is a conjugate representation of $(\L, f)$.
\end{thm}
\proof
Since $\S$ is compact in $\S(I_1)$, $(\S, \s)$ is also a subshift of
$(\S(I_1), \s)$.
{}From Lemma \ref{lem_condition}, there exists a subshift $(\S^*, \s)$ of
$(\S(I_1), \s)$ with $\S^*$ also compact, such that
$\s|_{\S} \sim \s|_{\S^*}$, and $(\S^*, \s)$ satisfies the
condition~(\ref{condition}).
{}From Lemma~\ref{lem_factor}, $(\S^*, \s)$ is also a subshift of
$(\S(I_0), \s)$ satisfying the condition~(\ref{condition})
{}Similar to the proof of Theorem \ref{th_conj_rep2}, it can be shown that
there exists a compact subset $\L \subseteq I_0$, and a
continuous self-map $f$ on $\L$ such that $(\S^*, \s)$ is a conjugate
representation of $(\L, f)$, a subsystem of $(I_0, f)$. Therefore $(\S, \s)$ is
a conjugate representation of $(\L, f)$.
\qed
Putting Theorem \ref{th_conj_rep} and Theorem \ref{th_symb_rep} together, we have the
following representation theorem for one-dimensional continuous self-maps.
\begin{thm} \label{th_rep}
$\forall f \in C(I_0), \exists (\S, \s)\le
(\S(I_0),
\s)$, such that $(\S, \s)$ is a conjugate representation of $(I_0, f)$;
conversely, $\forall (\S, \s) \le (\S(I_0), \s)$ with $\S$ compact in
$\S(I_1), \exists f \in C(I_0)$ and $\L \subseteq I_0$, where $\L$ is
compact and invariant for $f$, such that
$(\S, \s)$ is a conjugate representation of $(\L, f)$. \hfill $\Box$
\end{thm}
\section{The Second Order Representations}\label{sec_second}
Theorem \ref{th_conj_rep} indicates that $\forall f \in C(X),
(X, f)$ can be embedded
in $(\S(X), \s)$, denoted by $(X, f)\hookrightarrow (\S(X), \s)$. This
embedding relation means that the system $(X, f)$ may be represented by a
subshift of $(\S(X), \s)$. Naturally, one may further consider the
representation of the system $(\S(X), \s)$ itself. To do so,
one can regard $\S(X)$ as a symbol space and denote by $\S^2(X)$ the symbol
sequence space
$\S(\S(X))$, i.e.,
$$
\S^2(X)=\{x=(x_0, x_1, \cdots, x_i, \cdots): x_i\in \S(X), i\ge 0 \}.
$$
We specify a metric $\r^{(2)}$ on $\S^2(X)$ by
$$
\r^{(2)}(x, y)=\sum^{+\infty}_{k=0} \frac{1}{2^k}
\frac{\r(x_k, y_k)}{1+\r(x_k, y_k)},
$$
where $\r$ is the metric on $\S(X)$. We denote by $\s_2$ the shift map on
$\S^2(X)$, and if no confusion caused, we also denote by $\s$ the shift map
on $\S^2(X)$. And so we get a general symbolic dynamics system
$(\S^2(X), \s)$. Similarly, we can define general symbolic dynamics system
$(\S^k(X), \s_k)$ (or denote by $(\S^k(X), \s)$ if no confusion caused) for
$k\ge 3,$ and call it the $k$-th order symbolic representation of
dynamics on $X$.
For higher order symbolic sequence spaces, we have the following
general result.
\begin{thm} \label{th_homeo}
Suppose $(X, d)$ is a metric space. Then $\S^2(X)$ is homeomorphic to $\S(X)$.
In general, for $k\ge 2,~ \S^k(X)$ is homeomorphic to $\S^{k-1}(X)$.
\end{thm}
\proof
For $\tilde x, \tilde y \in \S^2(X)$, denote
\begin{eqnarray*}
\tilde x = (\tilde x_0, \tilde x_1, \cdots,\tilde x_i, \cdots), \ \
\tilde y = (\tilde y_0, \tilde y_1, \cdots,\tilde y_i, \cdots);
\end{eqnarray*}
and
\begin{eqnarray*}
\tilde x_i = (x_{i0}, x_{i1}, \cdots, x_{ij}, \cdots), \ \
\tilde y_i = (y_{i0}, y_{i1}, \cdots, y_{ij}, \cdots),
\end{eqnarray*}
where $x_{ij}, y_{ij} \in X$.
Define $h: \S^2(X) \to \S(X)$ as:
$$
h(\tilde x) =
(x_{00}x_{10}x_{01} \cdots x_{i0}x_{i-1,1}\cdots x_{1,i-1}x_{0i}\cdots),
$$
then $h$ is one-to-one and onto.
When
$$
\r^{(2)}(\tilde x , \tilde y) < \frac{1}{2^{2(2N+1)+1}},
$$
from Lemma~\ref{lem_metric}, we have
$$
\r(\tilde x_i, \tilde y_i) < \frac{1}{2^{2N+1}}, ~ i \le 2N+1,
$$
therefore
$d(x_{ij}, y_{ij}) < 2^{-N}, ~ i\le 2N+1,~ j\le N$, so we get
$$
\r(h(\tilde x), h(\tilde y)) < \frac{1}{2^{N-1}} + \frac{1}{2^{N_1}},
$$
where $N_1= \frac{1}{2} (N+1)(N+2) + N+1$.
On the other hand, let $x=(x_0x_1 \cdots x_k \cdots),
y=(y_0y_1 \cdots y_k \cdots) \in \S(X)$,
when $\r(x,y)< 2^{-(2N+1)}$, where we suppose
$N=\frac{1}{2} (2k+1)(2k+2)$, we have $d(x_i, y_i)< 2^{-N}, ~ i \le N$.
Let
\begin{eqnarray*}
h^{-1}(x)=\tilde x = (\tilde x_0, \tilde x_1, \cdots,\tilde x_i, \cdots),
& & \tilde x_i=(x_{i0}, x_{i1}, \cdots, x_{ij}, \cdots),\\
h^{-1}(y)=\tilde y = (\tilde y_0, \tilde y_1, \cdots,\tilde y_i, \cdots),
& & \tilde y_i = (y_{i0}, y_{i1}, \cdots, y_{ij}, \cdots),
\end{eqnarray*}
then $d(x_{ij}, y_{ij}) < 2^{-N}, ~ i+j \le 2k+1$, therefore
$d(x_{ij}, y_{ij}) < 2^{-N}, ~ i\le k,~ j \le k$. This implies
$\r(\tilde x_i, \tilde y_i) < 2^{1-N} + 2^{-k},~i \le k$, therefore
$\r^{(2)}(\tilde x, \tilde y)< 2^{2-N}+2^{1-k} + 2^{-k}$, i.e., we have
$$
\r^{(2)}(h^{-1}(x), h^{-1}(y)) <
\frac{1}{2^{N-2}} + \frac{1}{2^{k-1}} + \frac{1}{2^{k}}.
$$
Hence both $h$ and $h^{-1}$ are continuous, and therefore
$\S^2(X)$ is homeomorphic to $\S(X)$.
Similarly, we can check that for $k\ge 2,~ \S^k(X)$ is homeomorphic to
$\S^{k-1}(X)$.
\qed
On the other hand, define $\f: \S(X)\rightarrow \S^2(X)$ as
$$
\f(x)=(x, \s(x), \cdots, \s^k(x), \cdots),
$$
then if $X$ is compact, $\f$ can be verified to be a topological conjugacy
from $\S(X)$ to $\f(\S(X))\subseteq \S^2(X)$. So $(\S(X), \s)\hookrightarrow
(\S^2(X), \s)$.
In general, for a compact metric space $X$, we have the following embedding
sequence:
\begin{eqnarray}
(X, f)\hookrightarrow (\S(X), \s)\hookrightarrow (\S^2(X), \s)\hookrightarrow
\cdots \hookrightarrow (\S^k(X), \s)\hookrightarrow \cdots \label{3.1}
\end{eqnarray}
That's why we discuss the higher order representations. And the topic is also
motivated by Nasu (\cite{Nasu}) and is helpful to study maps in symbolic
dynamics discussed in \cite{Nasu}, as well.
%If there exists $k>1$ such that $(\S^{k-1}(X), \s)\sim (\S^k(X), \s)$, then
% the embedding sequence~(\ref{3.1}) will be finite, because of the following
% result.
%
%\begin{thm} \label{th_high-order}
%Suppose $X$ is a compact metric space. If there exists $k>1$ such that
%$(\S^{k-1}(X), \s)\sim (\S^k(X), \s)$, then $(\S^n(X), \s)\sim (\S^{n+1}(X),
%\s), \forall n \ge k-1.$
%\end{thm}
%\proof
%With the above conditions, there exists a homeomorphism $\f:
%\S^{k-1}(X)\rightarrow \S^k(X)$ that satisfies
%$
%\f \s_{k-1}=\s_{k}\f.
%$
%Define $\p: \S^k(X)\to \S^{k+1}(X)$ as
%$$
%\p((x_0, x_1, \cdots, x_i, \cdots))=(\f(x_0), \f(x_1), \cdots, \f(x_i),
%\cdots),\ \ x_i\in \S^{k-1}(X), \ \ i=0, 1, \cdots,
%$$
%then $\p: \S^k(X)\rightarrow \S^{k+1}(X)$ is one-to-one, onto, and continuous,
%and therefore is a homeomorphism.
%
%It is obvious that $\p\s_{k}=\s_{k+1}\p$. So $\s|_{\S^k(X)}\sim
%\s|_{\S^{k+1}(X)}.$ And thus $(\S^n(X), \s)\sim (\S^{n+1}(X), \s), \forall n
%\ge k-1.$
%\qed
As we discussed earlier that $(X, f)\hookrightarrow (\S(X), \s)$
shows a transformation between dynamics on $X$ and subshifts structure in
$(\S(X), \s), (\S^k(X), \s)\hookrightarrow (\S^{k+1}(X), \s)$ indicates that the
subshifts structure in $(\S^k(X), \s)$ can be transformed to the subshifts
structure in $(\S^{k+1}(X), \s)$. In other words, the symbolic
dynamics system $(\S^k(X), \s)$, and its subshifts, can be further represented
by the one order higher symbolic dynamics system $(\S^{k+1}(X), \s)$.
If the embedding sequence (\ref{3.1}) is finite, then the above transformation
or representations will not go on without limit. This means that the piling up
of symbol sequence spaces $\S^k(X)$ will not cause an unlimited increase of the
complexity of the corresponding shift systems. In particular, if we have
$(\S(X), \s)\sim (\S^2(X), \s)$, then $(\S(X), \s)$ is an ultimate
(or final) representation. We may ask under what conditions does
$(\S(X), \s)\sim (\S^2(X), \s)$ hold? We have the following theorems.
\begin{thm} \label{th_iff}
$(\S^2(X), \s)$ is topologically conjugate to $(\S(X), \s)$
if and only if $\S(X)$ is homeomorphic to $X$.
In general, for $k\ge 1,~(\S^{k+1}(X), \s)\sim (\S^k(X), \s)$
if and only if $\S^k(X)$ is homeomorphic to $\S^{k-1}(X)$.
\end{thm}
\proof
Suppose $\a: \S(X)\to X$ is a homeomorphism. Define $\f: \S^2(X)\to \S(X)$ as:
$$
\f(\x)=(\a(\x_0),\a(\x_1),\cdots,\a(\x_k),\cdots), ~
\x=(\x_0,\x_1,\cdots,\x_k,\cdots) \in \S^2(X),
$$
then $\f$ is a homeomorphism, and $\f \s_2 =\s \f$. Therefore
$(\S^2(X), \s)\sim (\S(X), \s)$.
Conversely, let $\f: \S^2(X)\to \S(X)$ is a topological conjugacy.
$\forall ~ x \in \S(X)$, denote $\tilde x = (x,x,\cdots,x,\cdots)$,
then $\tilde x$ is a fixed point of $\s_2$ in $\S^2(X)$.
Since $\s_2 \sim \s$, $\f(\tilde x)$ is also a fixed point of $\s$
in $\S(X)$. So $\exists ~ x^* \in X$, such that
$\f(\tilde x)=(x^*,\cdots, x^*, \cdots)$. Define $\a: \S(X)\to X$ as:
$\a(x)=x^*$. Then $\a$ is a homeomorphism.
Similarly, we can prove the general case of the Theorem.
\qed
{}From Theorems~\ref{th_homeo}~and~\ref{th_iff},
the following corollary is immediate:
\begin{cor} \label{cor_3-rep}
Suppose $(X, d)$ is a metric space,
then we always have
$$
(\S^k(X), \s)\sim (\S^2(X), \s),~\forall ~ k \ge 3.
$$ \hfill $\Box$
\end{cor}
So the embedding sequence~(\ref{3.1}) is finite,
and the third or higher order representations are therefore not necessary.
The following results show that we further have
$(\S(X), \s)\sim (\S^2(X), \s)$ when $X=I_1$.
\begin{thm} \label{th_high-order2}
$(\S(I_1), \s)$ is topologically conjugate to $(\S^2(I_1), \s)$,
i.e., $(\S(I_1), \s)\sim (\S^2(I_1), \s)$.
\end{thm}
\proof
$\forall (x_0, x_1, \cdots, x_k, \cdots)\in \S^2([0, 1])$, where
$$
x_i\in \S([0, 1]), \ x_i=(a_0^{(i)},a_1^{(i)}, \cdots, a_k^{(i)}, \cdots), \
a_k^{(i)} \in [0, 1], \ i\ge 0,\ k\ge 0.
$$
Rewrite $a_k^{(i)}$ by
$$
a_k^{(i)}=r_2(a_k^{(i)})=\sum^{+\infty}_{j=0}2^{-(j+1)}a_{kj}^{(i)} \ , \ \
i,k\ge
0,
$$
then define $\a: \S([0, 1])\rightarrow [0, 1]$ as:
$$
\a(x_i)=\sum^{+\infty}_{l=0}\displaystyle\sum^l_{{j=0 \atop k+j=l}\atop k\ge
0}2^{-(\frac{1}{2}l(l+1)+j+1)}a^{(i)}_{kj} \ , \ \ i\ge 0,
$$
So $\a(x_i)$ is also a binary fraction. Further, $\a: \S([0, 1])\rightarrow [0,
1]$
is a one-to-one and onto mapping. Choose $d_1$ as the metric on $[0, 1]$, and
correspondingly $\r_1$ as the metric on $\S([0, 1])$. Then $\forall x_i, y_i \in
\S(I_1)$,
\begin{eqnarray*}
x_i = (a^{(i)}_0, a^{(i)}_1, \cdots, a^{(i)}_k, \cdots), \ \
y_i = (b^{(i)}_0, b^{(i)}_1, \cdots, b^{(i)}_k, \cdots),
\end{eqnarray*}
rewrite $a^{(i)}_k$ and $b^{(i)}_k$ as
\begin{eqnarray*}
a^{(i)}_k &=& r_2(a_k^{(i)}) = \sum^{+\infty}_{j=0}2^{-(j+1)}a_{kj}^{(i)} \ ,\\
b^{(i)}_k &=& r_2(b_k^{(i)}) = \sum^{+\infty}_{j=0}2^{-(j+1)}b_{kj}^{(i)} \ .
\end{eqnarray*}
Whenever
$$
\r_1(x_i, y_i)< \frac{1}{2^{2N+1}},
$$
we have
$$
d_1(a^{(i)}_k, b^{(i)}_k)< \frac{1}{2^N}, \ \ k\le N,
$$
therefore
$$
a_{kj}^{(i)}=b_{kj}^{(i)}, \ \ k\le N, \ j\le N-1.
$$
So we have
$$
d_1(\a(x_i), \a(y_i))\le 2^{1-\frac{1}{2}N(N+1)},
$$
namely, $\a: \S(I_1)\rightarrow I_1$ is continuous.
Similarly, we can check that $\a^{-1}: I_1 \to \S(I_1)$ is also continuous.
Hence $\S([0, 1])$ is homeomorphic to $[0, 1]$.
From Theorem~\ref{th_iff} we have
$$
(\S(I_1), \s)\sim (\S^2(I_1), \s).
$$
The Theorem is proved.
\qed
We may ask if we also have $(\S(I_0), \s)\sim (\S^2(I_0), \s)$? We guess this
is not true but only have:
\begin{pro}
$(\S(I_1), \s)$ is a faithful representation for both
$(\S(I_0), \s)$ and \\ $(\S^2(I_0), \s)$.
\end{pro}
\proof
{}From Lemma \ref{lem_factor}, $(\S(I_1), \s)$ is a faithful representation of
$(\S(I_0), \s)$.
Since $d_0(\a, \b)\le \frac{1}{2}d_1(\a, \b), \ \ \forall \a, \b \in [0, 1]$, we
have
\begin{eqnarray*}
\r_0(a, b)& \le & \r_1(a, b), \ \ \forall a, b \in \S([0, 1]),\\
\r^{(2)}_0(x, y)& \le & \r^{(2)}_1(x, y), \ \ \forall x, y \in \S^2([0, 1]).
\end{eqnarray*}
Similar to the proof of Lemma \ref{lem_factor},
we can prove that $(\S^2(I_1), \s)$
is topologically semi-conjugate to $(\S^2(I_0), \s)$ under the identity mapping
$i: \S^2(I_1)\rightarrow \S^2(I_0)$. Therefore
$(\S^2(I_1), \s)$ is a faithful representation of $(\S^2(I_0), \s)$.
So $(\S(I_1), \s)$ is a faithful representation for both $(\S(I_0), \s)$
and $(\S^2(I_0), \s)$.
\qed
Note that from Theorem~\ref{th_iff},
$$
(\S^2(N), \s) \nsim (\S(N), \s).
$$
We suspect that
$$(\S^2(I_0), \s) \nsim (\S(I_0), \s).
$$
And we also suspect in most circumstances
$$
(\S^2(X), \s) \nsim (\S(X), \s).
$$
So it is very necessary to study the second order representations.
$(\S^2(N), \s) \nsim (\S(N), \s)$ also means that shift maps with a finite or
countable alphabet is not sufficient for the study of symbolic
representations of dynamical systems, and so it is necessary to study
symbolic dynamics with an uncountable alphabet.
\section{Quasi-Representations} \label{quasi}
While we have shown the existence of the topological conjugacy between a
one-dimensional map and a subshift of a symbolic dynamics system, in practice
it is often difficult to construct such conjugacy for applications. Instead, it
may be easier to find a topological semi-conjugacy, which sometimes is
sufficient for the problems under investigation. In this section we discuss
quasi-representations of one-dimensional dynamical systems.
The symbolic dynamics system $(\S(I), \s)$ is an extension of the usual
symbolic dynamics system $(\S(N), \s)$. Equip $\S(N)$ with a metric $\r$ as
follows:
$$
\r(x, y)=\sum^{+\infty}_{i=0} \frac{1}{2^i}
\frac{|x_i-y_i|}{1+|x_i-y_i|}.
$$
Take from $I_1$ a convergent sequence $\{a_k\}$ with the limit $a \in I_1$,
where $a_i \ne a_j,~ \forall~ i\ne j$. Let
\begin{eqnarray*}
S_{\infty} & = & \{a_1,a_2, \cdots, a\}, \\
\S_{\infty} & = & \{(x_0, x_1, \cdots) \in \S(I_1): x_i \in S_{\infty}, i \ge
0\},
\end{eqnarray*}
then $\S_{\infty}$ is compact in $\S(I_1)$, and
$(\S_{\infty}, \s)\le (\S(I_0), \s)$. From Theorem \ref{th_symb_rep},
$\exists f \in C(I_0)$ and $\L \subseteq I_0, \L $ is compact and invariant
for $f$, such that $f|_{\L} \sim \s|_{\S_{\infty}}$.
$\forall (\S, \s) \le (\S(N), \s)$, we have
$$
{h_{\rm top}}(\s|_{\S}) \le {h_{\rm top}}(\s|_{\S(N)})=\log N
\ne{h_{\rm top}}(\s|_{\S_{\infty}})=+\infty,
$$
So $\s|_{\S} \not\sim
\s|_{\S_{\infty}}$, and $f|_{\L} \not\sim \s|_{\S}$. Therefore the following
result is obvious:
\begin{thm} \label{th_not_conj}
There exists an $f \in C(I_0)$, such that
$\forall (\S, \s) \le (\S(N), \s), f|_{\L}
\not\sim \s|_{\S}$, where $\L \subseteq I_0$ is a closed invariant subset for
$f$. \hfill $\Box$
\end{thm}
Theorem \ref{th_not_conj} indicates once again that the scope of application
for $(\S(N), \s)$ is
quite limited. So it is necessary to study its extensions, such as $(\S(I_0),
\s)$, etc. Nevertheless, the system $(\S(N), \s)$ still has its special
significance. For example, $(\S(N), \s)$ can be used effectively to characterize
the dynamics of multimodal one-dimensional maps (see \cite{Hao89} and the
references therein). The significance of $(\S(N), \s)$ can also be shown by the
following theorem.
\begin{thm} \label{th_quasi}
$\forall f \in C(I_0), \exists (\S, \s) \le
(\S(N), \s), N \ge 2,$ such that $(\S, \s)$ is a quasi-representation of
$(I_0, f)$.
\end{thm}
\proof
First, we prove $(\S(I_0), \s)$ is topologically semi-conjugate to $(\S(N),
\s)$.
Let
$$
[0, 1]=\bigcup^{N-1}_{k=0}A_k, \ \ \mbox{where}\ A_0=[0, \frac{1}{N}],
A_k=(\frac{k}{N}, \frac{k+1}{N}], \ k=1, 2, \cdots, N-1.
$$
Define $\a: [0, 1]\rightarrow \{0, 1, \cdots, N-1\}$ as $\a(a)=k, \ a\in A_k.$
And define $\f: \S(I_0) \to \S(N)$ as:
$$
\f((x_0, x_1, \cdots, x_k, \cdots))=(\a(x_0), \a(x_1), \cdots, \a(x_k), \cdots).
$$
Then
$$
|\a(x_i)-\a(y_i)|=|k-l|, \ \ x_i \in A_k, \ y_i\in A_l.
$$
If $k\ne l$, we have
$$
\frac{1}{N}\le |x_i-y_i|\le 1, \ \ 1\le |\a(x_i)-\a(y_i)|\le N-1,
$$
therefore
$$
\frac{|\a(x_i)-\a(y_i)|}{1+|\a(x_i)-\a(y_i)|} < N^2
\frac{|x_i-y_i|}{1+|x_i-y_i|}.
$$
If $k=l$, it is obvious that
$$
\frac{|\a(x_i)-\a(y_i)|}{1+|\a(x_i)-\a(y_i)|}\le N^2
\frac{|x_i-y_i|}{1+|x_i-y_i|}.
$$
So $\r(\f(x), \f(y))\le N^2\r_0(x, y)$, thus $\f$ is continuous. $\f$ is also
surjective. And the following diagram commutes:
$$
\begin{array}{ccc}
\S(I_0) & \mathop{\longrightarrow}\limits^{\s} & \S(I_0) \\
\f \downarrow & & \downarrow \f \\
\S(N) & \mathop{\longrightarrow}\limits^{\s} & \S(N)
\end{array}
$$
So we have proved that $(\S(I_0), \s)$ is topologically semi-conjugate to
$(\S(N), \s)$.
$\forall f\in C(I_0)$, there exists $(\S^*, \s)\le (\S(I_0), \s)$ such that
$f|_{I_0}\sim \s|_{\S^*}$. Denote the topological conjugacy by $\p$. Then we
can define $\l: I_0 \rightarrow \f(\S^*)$ as $\l=\f\p$,
$$
\begin{array}{rcccc}
I_0 &\mathop{\longrightarrow}\limits^{\p}& \S^* &
\mathop{\longrightarrow}\limits^{\f}
& \f(\S^*) \\
f\downarrow & & \downarrow \s& & \downarrow \s\\
I_0 & \mathop{\longrightarrow}\limits^{\p} & \S^*&
\mathop{\longrightarrow}\limits^{\f}&
\f(\S^*)
\end{array}
$$
So $\l$ is a continuous and onto map, and $\l f=\s \l.$
Since $\s(\S^*)\subseteq \S^*, \s(\f(\S^*))\subseteq \f(\S^*)$. So $\f(\S^*)$
is invariant for $\s.$
$\S^*$ is closed, $\S(I_0)$ is compact, so $\f(\S^*)$ is closed.
So $(\f(\S^*), \s) \le (\S(N), \s)$.
Take $\S=\f(\S^*)$, then $f|_{I_0}$ is topologically semi-conjugate to
$\s|_{\S}.$
\qed
{}From the above discussions, we have the following remarks.
\vspace{0.3cm}
\begin{rem}
$\exists (\S^*, \s)\le (\S(I_0), \s)$, such that
$\forall (\S, \s)\le (\S(N), \s), \s|_{\S}\not\sim \s|_{\S^*}$.
\end{rem}
\begin{rem}
$(\S(N), \s)$ is a factor of $(\S(M), \s)$ when $M>N$.
And $(\S(N), \s)$ is a factor of $(\S(I_0), \s)$.
\end{rem}
\begin{rem} \label{rem_embed}
$(\S(N), \s)$ can be embedded in $(\S(I_0), \s)$,
i.e., $\exists (\S, \s)\le (\S(I_0), \s)$, such that $\s|_{\S(N)}\sim \s|_{\S}$
\ , where $N \ge 2.$
\end{rem}
In fact, the subshift $\S$ may be chosen as: $\S=R_N(\S(N))$, where
\begin{eqnarray*}
R_N(x) & = & (r_N(x), r_N(\s(x)), \cdots, r_N(\s^k(x)), \cdots),\\
r_N(x)& = & \sum^{+\infty}_{i=0} \frac{x_i}{N^{i+1}}, \ \forall x=(x_0, x_1,
\cdots)\in \S(N).
\end{eqnarray*}
Then if $R_N(x)=R_N(y)$, we have $\forall k \ge 0,$
\begin{eqnarray*}
r_N(\s^k(x))&=&r_N(\s^k(y)),\\
r_N(\s^{k+1}(x))&=&r_N(\s^{k+1}(y)),
\end{eqnarray*}
These imply $x_k=y_k, \forall k \ge 0.$ So $x=y$, and $R_N: \S(N)\rightarrow \S$
is a one-to-one mapping.
When $x, y \in \S(N)$ and $\r(x, y)<1/2^{M+1}$, we have $x_i=y_i, \ i=0, 1,
\cdots, M.$ So
$$
|r_N(\s^k(x))-r_N(\s^k(y))|\le \sum^{+\infty}_{i=M-k+1}
\frac{|x_{k+i}-y_{k+i}|}{N^{i+1}}<\frac{1}{N^{M-k}}, \ 0\le k\le M.
$$
Therefore
$$
\r_0(R_N(x), R_N(y))\le
\sum^{M}_{k=0}\frac{1}{2^k}\frac{1}{N^{M-k}+1}+\sum^{+\infty}_{k=M+1}
\frac{1}{2^k}.
$$
Since $N\ge 2, \ \ 1/N\le 1/2$,
$$
\r_0(R_N(x), R_N(y))<\frac{M+2}{2^M}.
$$
So $R_N$ is continuous, and therefore is a homeomorphism.
It is obvious that $R_N\s|_{\S(N)}=\s|_{\S}R_N.$ So $\s|_{\S(N)}\sim
\s|_{\S}$. So we have the result in Remark~\ref{rem_embed}
\section{Partitions and Representations} \label{partition}
In Section~\ref{quasi} quasi-representations of one-dimensional dynamical
systems are discussed. From the proof of Theorem~\ref{th_quasi}, when the
whole interval (phase space) is divided into some smaller pieces, and code
each piece with a symbol, then we get a quasi-representation of the original
system. This shows a direct connection between partitions and representations.
Partitions are natural ways to associate a symbolic
sequence with an orbit by tracking its history.
As pointed out in \cite{Adler}, in order to get a useful symbolism, one needs
to construct a partition with special properties. For example, when a partition
is Markov, the sysytem can be represented by a subshift of finite type. Some
hyperbolic systems, such as Anosov systems, axiom A systems, psuedo-Anosov
systems, and hyperbolic automorphisms on $n$-tori, $n \ge 2$, admit Markov
partitions. However, for non-hyperbolic systems, there may be no Markov
partitions. Therefore other than Markov partitions, some more general
partitions for these systems need to be used, so that if a certain kind of
partition exists for a non-hyperbolic system, the system then can be
represented by a subshift of infinite type.
In this section we generalize some concepts and main results discussed
in \cite{Adler}.
The discussion below are for dynamical systems $(X, \f)$, where $X$ is a
compact metric space with metric $ d ( \cdot \, , \cdot ) $ and
$\f $ is a homeomorphism of $X$ onto itself.
\begin{defn} \label{defn_top_part}
A finite or countable family of subsets
$\MR = \{ R_{i}, i \in \MI \}$
is called a {\em topological partition} for a dynamical system $(X, \f)$ if:
{\rm (1)} each $R_{i}$ is open;
{\rm (2)} $R_{i} \cap R_{j} = \varnothing , i \ne j $;
{\rm (3)} $X = \bigcup_{i \in \MI}\overline{R_{i}}$;
{\rm (4)} $\forall i \in \MI,
\card \{k \in \MI, \f R_i \cap R_k \ne \varnothing\}< + \infty$.
\end{defn}
\begin{rem}
Other authors have taken the sets $R_i$ to be closed sets
with the property that each is the closure of its interior. The
variation introduced by Adler here is slightly more general, just
enough to make some notation and certain arguments simpler. In fact,
there is a example of
partition whose elements are not the interiors of their closures
{\rm (\cite{Adler})}.
\end{rem}
\begin{rem}
When $\card~\MI <+\infty$, then Definition~\ref{defn_top_part} coincides with
the definition of topological partitions in {\rm \cite{Adler}}.
\end{rem}
Given two topological partitions
$$ \MR = \{ R_{i}, i \in \MI_1 \} ~ \mbox{and}~
\MS = \{ S_{j}, j \in \MI_2 \},
$$
we define their {\em common topological refinement}
$\MR \vee \MS $ as
$$
\MR \vee \MS = \{ {R_{i} \cap
S_{j}} , i \in \MI_1, \ j \in \MI_2 \} .
$$
\begin{lem}
For dynamical system $(X , \f )$ with topological
partition $\MR$, the set $\f ^{n} \MR $ defined by
$$
\f ^{n} \MR = \{ \f ^{n} R_{i}, i \in \MI \}
$$
is also a topological partition; and $\forall m \le n,
\bigvee _{k=m}^{n} \f ^{k} \MR$ is again a topological partition.
\end{lem}
A topological partition is called a {\em generator} for a
dynamical system $(X , \f)$ if
$$\lim _{n \to \infty }
D \left ( \bigvee _{-n}^{n} \f ^{k} \MR \right ) = 0 .
$$
Where $D (\MR)$ denotes the {\em diameter} of a partition
$\MR$,
$$D(\MR) = \max _{R_{i} \in \MR}
D( R_{i}) $$
where $D (R_{i}) \equiv \sup _{x,y \in R_{i}} d (x , y).$
We say that a topological partition
$\MR$ for a dynamical system $(X , \f)$
satisfies
{\em the $n$-fold intersection property}
for a positive integer $n \ge 3$ if
$$
R_{s_{k}} \cap \f ^{-1} R_{s_{k+1}} \ne \varnothing , \
1 \le k \le n-1 \Rightarrow \bigcap _{k=1}^{n} \f ^{-k} R_{s_{k}} \ne
\varnothing .
$$
Furthermore, we call a topological partition {\em Markov} if it
satisfies the $n$-fold intersection property for all $n \ge 3 .$
A homeomorphism $\f$ is said to
be {\em expansive} if there exists a real number $c>0$ such that
if $ d (\f ^{n} (x) , \f^{n} (y) ) < c$ for all $n \in \Z$,
then $x = y$.
Suppose a dynamical system $(X, \f)$ has a Markov generator
$\MR\!=\!\{ R_{i}, i \in \MI \} $.
We define an associated subshift of finite type $(\S_{\MR}, \s)$
over a finite or countable alphabet by
$$\S_{\MR} = \{ s = (s_{n})_{n \in \Z} :
R_{s_{n-1}} \cap \f ^{-1} R_{s_{n}} \ne \varnothing ,
s_{n}\in \MI, n \in \Z \} .
$$
Similar to Theorems 6.5 and 6.13 in \cite{Adler}, we have the following result.
\begin{thm}
If the dynamical system $(X , \f)$ is expansive and
has a Markov generator $\MR = \{ R_{i} , i \in \MI \}$,
then the map $\pi : \S_{\MR} \to X$ defined by
$$
\pi (s) = \bigcap _{ n = 0}^{\infty }
\overline{\f^{n} R_{s_{-n}} \cap \f ^{n-1} R_{s_{-n+1}} \cap \dots
\cap \f^{-n} R_{s_{n}}}
$$
gives a regular representation $(\S_{\MR}, \s)$ of $(X, \f)$.
Moreover, a subshift of finite type is a semi-conjugate representation of an
expansive dynamical system $(X, \f )$ if and only if $(X, \f)$ has
a Markov partition. \qed
\end{thm}
% \section{Distillations and Partial Representations} \label{distillation}
\section{Partial Representations} \label{distillation}
It would be better, under certain conditions, to symbolize a dynamical
system by a conjugate representation and using a finite or countable alphabet.
This section will show that
if there exists a distillation, then we can achieve this target, although
we have to abandon the quest of representing all points in the phase space,
instead, only represent an invariant subset, that is, we obtain a
partial representation.
In contrast with partitions, if there exist pairwise disjoint non-empty closed or
compact subsets $A_0, A_1, \cdots, A_{N-1}$ of the phase space $X$ (here the
union of all $A_i$'s need not to cover $X$), satisfying certain conditions,
then the restriction of the system to a invariant subset of $X$ can be
represented by the full shift on $N$ symbols. When the number of such
closed (compact) subsets need to be countably infinite, then a subsystem can
be represented by the full shift with a countable alphabet (\cite{Fu96}).
The family of such closed (compact) subsets with certain conditions is called
a distillation. More precisely, we give the following definitions.
\begin{defn}
If for an $f \in M(X)$, there exists an invariant subset $\L \subseteq X$ and
a subshift $(\S, \s)$ of a certain symbolic dynamical system such that
$(\S, \s)$ is a symbolic representation of $(\L, f)$, then we call the subshift
$(\S, \s)$ a {\rm partial representation} of $(X, f)$.
\end{defn}
A partial representation is also helpful to our understanding of the original system,
especially when $\L$ is a maximal invariant subset or a global attractor of
$(X, f)$. In these cases, apart from some transient states in
$X \setminus \L$, all significant dynamical behaviour will asymptotically
take place in $\L$.
\begin{defn} \label{def_disti}
Let $X$ be a topological space, $f \in M(X)$. We call a finite family of
subsets $\MA = \{A_0, A_1, \cdots, A_{N-1} \}$ a {\rm quasi-distillation
of order N} for the system $(X, f)$ if: \\
{\rm (1)} each $A_i$ is compact and non-empty; \\
{\rm (2)} $A_i \cap A_j = \varnothing,~ \forall i \ne j$;\\
{\rm (3)} $f(A_i)\supseteq \bigcup _{j \in a(i)}A_j,~ \forall 0\le i \le N-1$.\\
Where $a(i)\subseteq \{0, 1, \cdots, N-1\}$, and each $a(i)$ is non-empty
and is maximal in the sense that $\forall j \notin a(i), ~ f(A_i)\cap A_j =
\varnothing$.
We call $\MA$ a {\rm distillation of order N} for $(X, f)$ if it satisfies a
further condition: \\
{\rm (4)} $\card\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})\le 1,~
\forall~ (i_0i_1\cdots i_s \cdots) \in \S(N)$.\\
Where $\card(\cdot)$ denotes the cardinal number of a set.
\end{defn}
\begin{defn} \label{def_distil}
Let $X$ and $f$ be as above. We call a countable family of subsets
$\MA = \{A_0, A_1, \cdots, A_k, \cdots \}$ a {\rm quasi-distillation
of order infinity} for the system $(X, f)$ if:\\
{\rm (1)} each $A_i$ is closed and non-empty;\\
{\rm (2)} there are open subsets $O_i \subseteq X, ~ i \in \Z_+$, such that
$$
\forall~ i \in \Z_+ , ~ A_i \subseteq O_i ~~\mbox{and}~~
O_i \cap (\bigcup_{i\ne j}A_j)= \varnothing;
$$
{\rm (3)} $f(A_i)\supseteq \bigcup_{j\in a(i)}A_j,~ \forall i \in \Z_+$.\\
Where $a(i)\subseteq \Z_+$, and each $a(i)$ is non-empty
and is maximal in the same sense as in Definition~\ref{def_disti}.
We call $\MA$ a {\rm distillation of order infinity} for a self-map on a
metric space $(X, d)$ if it satisfies a further condition:\\
{\rm (4)} $\lim_{n \to + \infty}D(\bigcap_{s=0}^{n} f^{-s}(A_{i_s}))=0,~
\forall~ (i_0i_1\cdots i_s \cdots) \in \S(\Z_+)$.\\
Where $D(S)$ denotes the diameter of a subset $S$, i.e.,
$D(S)=\sup_{a,b \in S} d(a, b)$.
\end{defn}
At first we give a general lemma.
\begin{lem} \label{lem_equal}
For a finite or countable family of subsets $\{ A_i, i\in \MI\}$ of a
topological space $X$ and a map $f: X \to X$, if
$f(A_j)\supseteq \bigcup _{i \in \MI}A_i,~ \forall j \in \MI$,
then $\forall l \ge 1, \forall i_k \in \MI, k=0,1, \cdots,$
$$
f^l (\bigcap_{s=0}^{l} f^{-s}(A_{i_s}))= A_{i_l}.
$$
\end{lem}
\proof
{}From
$$
f(A_j)\supseteq \bigcup _{i \in \MI}A_i,~ \forall j \in \MI,
$$
we have
$$
f(A_i)\bigcap A_j=A_j, ~ \forall i, j \in \MI.
$$
So when $l=1$, we have
$$
f(A_{i_0}\bigcap f^{-1}(A_{i_1}))\subseteq f(A_{i_0})\bigcap A_{i_1}=A_{i_1}.
$$
$\forall x \in A_{i_1}$, since $f(A_{i_0})\supseteq A_{i_1},
\exists y \in A_{i_0}$ such that $f(y)=x$. Therefore $y \in f^{-1}(A_{i_1})$,
and hence $y \in A_{i_0}\cap f^{-1}(A_{i_1})$, and
$x=f(y)\in f(A_{i_0}\cap f^{-1}(A_{i_1}))$. That is,
$$
A_{i_1}\subseteq f(A_{i_0}\bigcap f^{-1}(A_{i_1})).
$$
So we get
$$
f(A_{i_0}\bigcap f^{-1}(A_{i_1}))=A_{i_1}.
$$
By the similar arguement the Lemma can be proven inductively.
\qed
Some known results about distillations and symbolic representations are Smale's horseshoe
theorem (\cite{Smale}), higher dimensional versions of horseshoes
(\cite{Wiggins88}) and some generalizations to horseshoe-like invariant sets
(\cite{Fu96, Zhang}), and etc. Below we give some more general results about
distillations and representations.
The following theorem gives results on partial representations over a
finite alphabet.
\begin{thm} \label{th_part_quasi}
Suppose $X$ is a Hausdorff space and $f \in C(X)$, and $(X, f)$ has a
quasi-distillation of order $N$. Then there exists a subshift of finite type
$(\S, \s)\le (\S(N), \s)$ such that $(\S, \s)$ is a partial quasi-representation of
$(X, f)$.
If $(X, f)$ has a distillation of order $N$, then there exists a subshift of
finite type $(\S, \s)\le (\S(N), \s)$ such that $(\S, \s)$ is a partial
conjugate representation of $(X, f)$.
\end{thm}
\proof
Let $\S_A=\{x\in \S(N): x=(x_0x_1 \cdots x_k \cdots),~a_{x_kx_{k+1}}=1,
\forall ~ k \ge 0\}$,
where $A$ is the transition matrix,
$$
A=(a_{ij})_{N\times N}, ~~
a_{ij}=\left\{\begin{array}{ll} 1, \;\;\;\; j\in a(i) \\
0, \;\;\;\; \mbox{otherwise} \end{array} \right. .
$$
{}From Lemma~\ref{lem_equal}, $\forall l \ge 1$,
$$
f^l (\bigcap_{s=0}^{l} f^{-s}(A_{i_s}))= A_{i_l}, \ \
\forall (i_0i_1 \cdots) \in \S_A.
$$
So $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})\ne \varnothing$, since $X$ is
a Hausdorff space. Let
$$
\L=\bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{N-1}A_i)
=\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}),
$$
then $\L$ is an invariant compact subset for $f$. Define a coding
$\f: \L \to \S_A$ as:
$$
\f(x)= (i_0i_1 \cdots i_k \cdots),~~
\forall~ x \in \bigcap_{s=0}^{+\infty}f^{-s}(A_{i_s}).
$$
Then $\f$ is surjective.
$\forall x \in \L$, suppose
$x \in A_{i_0}, f^s (x)\in A_{i_s}, s=0, 1, \cdots, K$. Then
$$
\f (x)\in \bigcap_{s=0}^{K}\f f^{-s}(A_{i_s}).
$$
{}From the continuity of
$f^s$,there exists a neighborhood $V_s (x)$ of $x$ such that
$$
f^s (V_s (x)\cap \L) \subseteq A_{i_s},\ s=0, 1, \cdots, K.
$$
Let
$V(x)=\bigcap_{s=0}^K V_s(x)$, then
$V(x)\cap\L \subseteq \bigcap_{s=0}^{K}f^{-s}(A_{i_s})$. So
$\forall y \in V(x)\cap\L$, we have
$\f (y) \in \bigcap_{s=0}^{K}\f f^{-s}(A_{i_s})$. Thus the first $K$ entries
of $\f (y)$ and $\f (x)$ agree, therefore
$$
\r (\f (x), \f (y))\le \frac{1}{2^K}.
$$
So $\f$ is continuous.
The commutativity $\f f|_{\L}=\s|_{\S_A} \f$ is obvious. So $(\S_A, \s)$ is
a partial quasi-representation of $(X, f)$.
When $(X, f)$ has a distillation of order $N$, then $\f$ is also one-to-one.
Note that $X$ is a Hausdorff space, $\f$ is therefore a homeomorphism, and
hence $(\S_A, \s)$ is a partial conjugate representation of $(X, f)$.
\qed
The following two theorems give results on partial representations over
a countable alphabet.
\begin{thm} \label{th_quasi_distil}
Let $X$ be a sequentially compact $T_1$ space and $f \in C(X)$.
If $(X, f)$ has a quasi-distillation of order infinity, then there exists
a countable state Markov subshift $(\S, \s)\le (\S(\Z_+), \s)$ such that
$(\S, \s)$ is a partial quasi-representation of $(X, f)$.
\end{thm}
\proof
$\forall (s_0, s_1, \cdots) \in \S_A$, where $\S_A$ is defined similarly as in
the proof of Theorem~\ref{th_part_quasi}, but here $A$ is a matrix of infinite
order. From
$$
\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})=
\bigcap_{l=0}^{+\infty} \bigcap_{s=0}^{l}f^{-s}(A_{i_s}),
$$
$\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is the intersection of a decreasing
sequence of nonempty closed subsets in a sequentially compact $T_1$ space, so
it is nonempty. Define a coding $\f: \L \to \S_A$ as:
$$
\f(x)= (i_0i_1 \cdots i_k \cdots),~~
\forall~ x \in \L :=
\bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{+\infty}A_i)
=\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}),
$$
then $\f$ is onto. Let $N>0$ satisfy $\ep > \sum_{n=N}^{+\infty}\frac{1}{2^n}$.
Suppose $x \in A_{i_0}$ and $f^s(x) \in f^s (x)\in A_{i_s}$,
then $ x\in f^{-s}(A_{i_s})$ and $ \f (x)\in \f f^{-s}(A_{i_s}),
s=0, 1, \cdots, N$. From the continuity of $f^s$, there exists a neighborhood
$V_s (x)$ of $x$ such that
$f^s (V_s (x)) \subseteq O_{i_s},\ s=0, 1, \cdots, N.$ Let
$V(x)=\bigcap_{s=0}^N V_s(x)$, then $f^s (V(x))\subseteq O_{i_s}$, therefore
$f^s (V (x)\cap \L) \subseteq A_{i_s},\ s=0, 1, \cdots, N,$ and
$V (x)\cap \L \subseteq \bigcap_{s=0}^N f^{-s}(A_{i_s})$. So
$y \in V(x)\cap\L$ implies
$\f (y)\in \f \bigcap_{s=0}^N f^{-s}(A_{i_s})
\subseteq \bigcap_{s=0}^N \f f^{-s}(A_{i_s})$.
Thus the first $N$ entries of $\f (y)$ and $\f (x)$ agree, hence
$\r (\f (x), \f (y)) < \ep$. This proves the continuity of $\f$. Therefore
$(\S_A, \s)$ is a partial quasi-representation of $(X, f)$.
\qed
\begin{thm}
Let $(X, d)$ be a complete metric space and $f \in C(X)$.
If $(X, f)$ has a distillation of order infinity, then there exists a
countable state Markov subshift $(\S, \s)\le (\S(\Z_+), \s)$ such that
$(\S, \s)$ is a partial conjugate representation of $(X, f)$.
\end{thm}
\proof
As being shown in the proofs of
Theorems~\ref{th_part_quasi}~and~\ref{th_quasi_distil},
$\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is a nonempty set for all
$(i_0i_1 \cdots i_k \cdots)\in \S_A$. From the condition (4) in
Definition~\ref{def_distil}, $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is a
one-point set. Define a coding $\f: \L \to \S_A$ as:
$$
\f (\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}))=(i_0i_1 \cdots i_s \cdots),
$$
where
$\L=\bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{+\infty}A_i)
=\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}).$
Then as shown in the proof of Theorem~\ref{th_quasi_distil}, $\f$ is
continuous.
For $x=(x_0x_1 \cdots) \in \S_A, \ \ \forall \ \ep >0, \ \ \exists \ N >0, $
whenever $n \ge N$, we have
$$
D(\bigcap_{s=0}^{n}f^{-s}(A_{a_s})) < \ep.
$$
$\forall \ y \in \S_A,$ when $\r (x, y)< 1/2^N$, the first $N+1$ entries of
$x$ and $y$ agree. Thus
$$
d(\f ^{-1}(x), \f ^{-1}(y))\le D(\bigcap_{s=0}^{N}f^{-s}(A_{x_s})) < \ep,
$$
hence $\f ^{-1}$ is continuous. This shows that $\f$ is a homeomorphism.
Therefore $(\S_A, \s)$ is a partial conjugate representation of $(X, f)$.
\qed
\section{Representations for Discontinuous Maps} \label{discontinuous}
This section will discuss some specific
examples and show that it is possible to use symbolic dynamics as a tool for
further studies of dynamics of a class of discontinuous maps: piecewise
continuous maps.
%%% \subsection{Representations of Piecewise
%%%% Continuous Maps} \label{piecewise}
Let $X \subseteq \R^n$, and $\MP= \{ P_0, P_1, \cdots, P_{N-1}\}$ be
a finite family of subsets of $X$, satisfying $\bigcup_{i=0}^{N-1}P_i = X$,
and $P_i \cap P_j=\varnothing$ for $i\ne j$. A piecewise continuous map
is a map $f: X \to X$ whose restriction to each
$P_i,~ 0\le i \le N-1$, is continuous, and $\MP$ is minimal in the sense
that $f$ is not continuous on $P_i \cup P_j$ for $i \ne j$.
A partition $\MP = \{ P_0, \cdots, P_{N-1}\}$ associated to a piecewise
continuous map provides a natural coding $\f: X \to \S(N)$ by
$\f(x) = (i_0 i_1 \cdots i_k \cdots)$ where $f^k(x)\in P_{i_k}$.
Let $G=\{ (x, \f(x)),~ x \in X\}$ be the graph of $\f: X \to \S(N)$ endowed
with the metric
$$
d_G((x, \f(x)), (y, \f(y))) = \max \{ d(x,y), \r(\f(x), \f(y))\},
$$
where $d$ is the metric on $X$. Then the extension map
$f_G: G \to G, ~ f_G(x, \f(x))=(f(x), \f(f(x)))$, is continuous (\cite{Goetz}).
This result may be useful since sometimes it is a bridge between discontinuous
and continuous maps.
Here we give a definition of partitions for piecewise continuous maps.
\begin{defn}
For $X \subseteq \R^n,~f \in M(X)$. We call a finite family of subsets
$\MP = \{ P_0, P_1, \cdots, P_{N-1}\}$ a {\rm partition} of $(X, f)$ if:
{\rm (1)} each $P_i$ is open and convex;
{\rm (2)} $P_i \cap P_j = \varnothing$ for $i \ne j$;
{\rm (3)} $X= \bigcup_{i=0}^{N-1}\overline{P_i}$;
{\rm (4)} $\forall ~ 0\le i \le N-1,~ f|_{P_i}$ is continuous and can be
extended to a continuous map on $\overline{P_i}$.
We call a partition {\rm minimal} if $f$ is not continuous on
$\overline{P_i} \cup \overline{P_j}$ for $i \ne j$.
A {\rm cell}, denoted by $C(x)$, is a set of points in $X$ encoded by the
same symbolic sequence $\f(x)$, i.e., $C(x)= \{ y\in X: \f(y)=\f(x)\}$,
where $\f$ is called the {\rm coding} associated with the partition
$\MP$, $\f: X \to \S(N)$ is defined by
$\f(x) = (i_0i_1\cdots i_k\cdots)$ where $f^k(x)\in P_{i_k}$.
\end{defn}
\begin{eg} \label{eg_gauss}
Symbolic representation for the Gauss map.
\end{eg}
Let $ ( I , g )$ be the iterated system of the Gauss map (\cite{Adler91})
$ g : x \rightarrow x^{-1} ~(\bmod ~1)$ for $0< x \le 1$, and $g(0)=0$.
Let a sequence
$s = ( s_{n})_{n \in \Z_+} \in \S(\N)$ correspond to the continued fraction
expansion
$[s_{0}s_{1}s_{2}\cdots]$.
This defines the map $\pi $ from
$\S(\N)$ to $I=[0, 1]$:
$$
\pi ( s_{0} \,, s_{1} \,, \cdots )=[s_{0}s_{1}s_{2}\cdots].
$$
It can be verified that
\begin{itemize}
\item[{(i)}] $g \pi = \pi \s $,
\item[{(ii)}] $\pi $ is continuous,
\item[{(iii)}] $\pi $ is onto,
\item[{(iv)}] there is a bound on the number of pre-images (in this
case two),
\end{itemize}and
\begin{itemize}
\item[{(v)}] there is a unique pre-image of ``most" numbers in $I$ (here those
with infinite continued fraction expansions).
\end{itemize}
So $(\S(\N), \s)$ is a regular representation of $(I, g)$.
The map $\pi $ is not a homeomorphism, but we do have
a satisfactory representation of the dynamical system
by a one-sided full shift over a countable alphabet in the sense
of Adler \cite{Adler}, i.e.,
\begin{itemize}
\item orbits are preserved;
\item every point has at least one symbolic representative;
\item there is a finite upper limit to the number of representatives
of any point;
\item and every symbolic sequence represents some point.
\end{itemize}
There is an alternate definition of $\pi $ in terms of
a countable partition of $I$:
$$
\MR = \{ R_{i}, i \in \N \}, \ \ R_i = (\frac{1}{i+1}, \frac{1}{i}).
$$
$$
\pi ( s_{0} , s_{1} , \cdots ) = \bigcap _{ n =
0}^{\infty }\overline{ R_{s_{0}} \cap g^{-1} ( R_{s_{1}}) \cap \cdots
\cap g^{-n} (R_{s_{n}})}.
$$
Note that in a suitable torus topology the Gauss map becomes continuous
everywhere except at $x=0$. Below we give another example where the map is
``more discontinuous'' but is still easy to symbolize.
\begin{eg} \label{eg_interval}
Symbolic representations for interval exchange transformations.
\end{eg}
An interval exchange transformation $f: I \to I, I=[0, 1]$, over a partition
$\MP=\{I_0, I_1, \cdots, I_{N-1}\}$ is a one-dimensional piecewise isometry,
so we can follow the arguements in \cite{Ashwinf, Ashwinft, Goetz00} to discuss
symbolic representation for $f$.
By naturally coding orbits of $f$ using the partition $\MP, \f: I \to \S(N)$,
$$
\f(x)=(\cdots i_{-1} i_0 i_1 \cdots),
$$
where $f^k(x)\in I_{i_k}, k \in \Z$, we obtain a subset $\S \subseteq \S(N)$ of
bi-infinite symbolic sequences, $\S=\{ \f(x)\in \S(N), x \in I\}$.
$\S$ is closed and shift invariant, so $(\S, \s)\le (\S(N), \s)$.
Note that if a subinterval $S \subseteq I$ is invariant under $f^m$, then
$f^m |_S$ is either the identity or the reflection in the midpoint of $S$ (in this
case $f^{2m} |_S$ is the identity). So the disk/polygon packing discussed in
\cite{Ashwinf, Ashwinft, Goetz00} now reduce to rigid interval (\cite{Katok})
packing, i.e., the set
$$
J=\overline{I\setminus \bigcap_{n \in \Z}f^n (\hat{I})},~
\hat{I}= \bigcup_{k=0}^{N-1} {\rm int} I_k
$$
of points that never hit or approach the discontinuity can be decomposed into
finite (\cite{Katok}:Lemma 14.5.4) cells, or rigid intervals $J_k$,
$$
J=\bigcup_{k=1}^K J_k,~ K\le 2(N-1),
$$
all points in $J$ have periodic codings, and $f$ is periodic on each $J_k$.
As discussed in \cite{Katok}, when $f$ is generic (i.e., $J=\varnothing$), we
can define a map $h: \S \to I$,
$$
h((\cdots i_{-1} i_0 i_1 \cdots))=\bigcap_{k\in \Z}f^{-k}(I_{i_k}).
$$
$h$ satisfies:
\begin{itemize}
\item[{(1)}] $f h = h \s $,
\item[{(2)}] $h $ is continuous,
\item[{(3)}] $h $ is onto,
\item[{(4)}] there is a bound on the number of pre-images (in this
case $2^N$),
\end{itemize}and
\begin{itemize}
\item[{(5)}] there is a unique pre-image of ``most" points in $I$ (here those
no image or pre-image of them are discontinuity points).
\end{itemize}
So $(\S, \s)$ is a regular representation of $(I, f)$.
Although the map $h$ is not a homeomorphism, we do have
a satisfactory representation of the dynamical system
by a two-sided subshift over a finite alphabet with the properties listed
near the end of Example~\ref{eg_gauss}.
If $(\S, \s)$ is topologically transitive, then $(\S, \s)$ is a subshift
of {\em infinite} type, because otherwise the periodic points of $\s|_{\S}$
would be dense in $\S$.
%%%%% \subsection{Foliations and
%%%%%% Representations} \label{foliation}
%
% In this section we will discuss ... \cite{Hao_Zheng98}
%
% \vspace{1cm}{\bf TO FINISH...}\vspace{1cm}
\section{Final Remarks}
When we consider the symbolic representation of an iterated map,
one may hope to find one of the following:
\begin{itemize}
\item[{(A)}] a full representation (i.e., all points in the phase space
are symbolically represented);
\item[{(B)}] a conjugate representation;
\item[{(C)}] a representation via a subshift of finite type over a finite
or countable alphabet.
\end{itemize}
Unfortunately, it is very rare to get a symbolic representation satisfying all
of (A), (B) and (C). Usually, if we'd like to get a symbolic representation
satisfying (A) and (B), we may need to pay the price of giving up (C), i.e.,
we need to use an uncountable alphabet, as discussed in
Sections~\ref{conjugate} and \ref{sec_second}; if we'd like to obtain a
representation with properties (A) and (C), we may have to give up (B),
as discussed in Sections~\ref{quasi} and \ref{partition}; if we'd like to
find a representation with (B) and (C), we may have to give up (A), i.e.,
we only get a partial representation, as discussed in
Section~\ref{distillation}.
When we consider a symbolic representation of a discontinuous map, we at least
have to give up (B), as discussed in Section~\ref{discontinuous} using special
cases of piecewise continuous maps.
Symbolic representations provide a powerful method to investigate
general discrete dynamical systems through shifts or subshifts. This is
similar to the situation for the study of finite groups in algebra, where
all finite groups can be represented by subgroups of symmetric groups $S_n$,
which are better understood. We can view $S_n$ as `symbolic' groups.
There is a large body of theory that describes the dynamics of
continuous smooth dynamical systems. However, if there are discontinuities
in the system such as those caused by collisions (impacting) or
switching there is still comparatively little in the way of general theory to
describe such systems. In Section~\ref{discontinuous} we have shown through
specific examples that it is helpful to use symbolic dynamics to develop
the general theory of dynamics of a class of discontinuous maps: piecewise
continuous maps.
Most results in this paper are proven constructively. This makes our
results potentially useful for applications.
Finally, we conjecture that some results in
Sections~\ref{conjugate}, \ref{sec_second}, \ref{quasi} and \ref{discontinuous}
about representations for one
dimensional maps may be extended to higher dimensional cases.
Higher dimensional binary expansions and higher dimensional continued
fractions (\cite{Arnold}) may be useful in the extension. We hope to discuss
this topic in a separate paper.
\vspace{0.5cm}
\noindent {\bf Acknowledgments.}
{\small X. Fu and P. Ashwin thank the EPSRC for
support via grant GR/M36335, and they are grateful to Surrey University
where earlier versions of this paper were written. The authors would
like to thank Prof. Robert Harrison for his helpful comments and advice.
While an earlier version of this paper was written,
X. Fu was supported jointly by a scholarship from the Nonlinear
Dynamics Group in Physics Department of Heriot-Watt University and
a grant (No. 19572075) from China National Natural Science Foundation.}
\begin{thebibliography}{20}
\bibitem{Adler91} R. L. Adler, Geodesic flows, interval maps, and
symbolic dynamics, in {\em Ergodic Theory, Symbolic Dynamics, and
Hyperbolic Spaces} (eds. T. Bedford, M. Keane, C. Series),
Oxford Univ. Press, 1991.
\bibitem{Adler} R. L. Adler,
{\em Symbolic Dynamics and Markov Partitions},
{\em MSRI} Publications, {\bf 53}, 1996. Also in
{\em Bull. Amer. Math. Soc. (New Series)}, {\bf 35}(1998)1-56.
\bibitem{Adler2} R. L. Adler, and B. Weiss,
Similarity of automorphisms of the torus,
{\em Memor. Amer. Math. Soc.}, {\bf 98}(1970)ii+43pp.
\bibitem{Alekseev} V. M. Alekseev, and M. V. Yakobson,
Symbolic dynamics and hyperbolic dynamic systems,
{\em Phys. Reports}, {\bf 75}(1981)287-325.
\bibitem{Arnold} V. I. Arnold,
Higher dimensional continued fractions,
{\em Regular and Chaotic Dynamics}, {\bf 3}(1998)10-17.
\bibitem{Ashwinf} P. Ashwin and X. Fu,
On the geometry and dynamics of planar piecewise isometries,
(in preparation, 2000)
\bibitem{Ashwinft} P. Ashwin, X. Fu and J. Terry,
Riddling of invariant sets for some discontinuous maps preserving
Lebesgue measure,
(submitted, 2000)
\bibitem{Berg} K. Berg,
{\em On the Conjugacy Problem for K-Systems},
PhD Thesis, University of Minnesota, 1967.
\bibitem{Fu96} X.-C. Fu,
Criteria for a general continuous self-map to have chaotic sets,
{\em Nonlinear Analysis TMA}, {\bf 26}(1996)329-334.
\bibitem{Fu92} X.-C. Fu, and H.-W. Chou,
Chaotic behavior of the general symbolic dynamics,
{\em Applied Math. and Mech.} {\bf 13}(1992)117-123.
\bibitem{Fu98} X.-C. Fu, and J. Duan,
Infinite-dimensional linear dynamical systems with chaoticity,
{\em J. of Nonlinear Sci.}, {\bf 9}(1999)197-211.
\bibitem{Goetz} A. Goetz,
Dynamics of a piecewise rotation,
{\em Contin. Discrete Dyn. Sys.}, {\bf 4}(1998)593-608.
\bibitem{Goetz00} A. Goetz,
Dynamics of piecewise isometries,
{\em Illinois J. Math.}, {\bf 44}(2000)465-478.
\bibitem{GH83} J. Guckenheimer, and P. Holmes,
{\em Nonlinear Oscillations, Dynamical Systems, and Bifurcations of
Vector Fields},
Springer-Verlag, 1983 (3rd printing, 1990).
\bibitem{Hao89} B.-L. Hao,
{\em Elementary Symbolic Dynamics and Chaos in Dissipative Systems},
World Scientific, 1989.
\bibitem{Hao_Zheng98} B.-L. Hao, and W.-M. Zheng,
{\em Applied Symbolic Dynamics and Chaos},
World Scientific, 1998.
\bibitem{Katok} A. Katok and B. Hasselblatt,
{\em Introduction to the Modern Theory of Dynamical Systems},
Cambridge Univ. Press, 1995.
\bibitem{Kitchens} B. P. Kitchens,
{\em Symbolic Dynamics: One-sided, Two-sided and Countable State
Markov Shifts},
Springer-Verlag Berlin, 1998.
\bibitem{Lind} D. Lind, and B. Marcus,
{\em An Introduction to Symbolic Dynamics and Coding},
Cambridge Univ. Press, 1995.
\bibitem{May} R. M. May,
Simple mathematical models with very complicated dynamics,
{\em Nature}, {\bf 261}(1976)459-467.
\bibitem{Nasu} M. Nasu,
Maps in symbolic dynamics,
{\em Lecture Notes of the Tenth KAIST Mathematics Workshop}
(G. H. Choe ed.),
Korea Advanced Institute of Science and Technology, 1996.
\bibitem{Smale} S. Smale,
Differentiable dynamical systems,
{\em Bull. Amer. Math. Soc.}, {\bf 73} (1967) 747-817.
\bibitem{Wiggins88} S. Wiggins,
{\em Global Bifurcations and Chaos: Analytical Methods},
Springer-Verlag, 1988.
\bibitem{Zhang} Z.-S. Zhang,
On the shift-invariant sets of endomorphisms,
{\em Acta Math. Sinica}, {\bf 27}(1984)564-576.
\end{thebibliography}
\end{document}
---------------0012051554166--