Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you either view the HTML version or    *
%_ * retrieve the article in DVI, PostScript, or PDF format.                *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{28-JUN-1999,28-JUN-1999,28-JUN-1999,28-JUN-1999}
 
\documentclass{era-l}
\usepackage{latexsym}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand\mya{\alpha}
\newcommand\myb{\beta}
\newcommand\card{\operatorname{card}}
\newcommand\myd{\delta}
\newcommand\myD{\Delta}
\newcommand\mye{\epsilon}
\newcommand\g{\gamma}
\newcommand\G{\Gamma}
\newcommand\ii{(I,i)}
\newcommand\iie{(I,i,e)}
\newcommand\jj{(J,j)}
\newcommand\mass{\operatorname{mass}}
\newcommand\n{\eta}
\newcommand\om{\omega}
\newcommand\Om{\Omega}
\newcommand\pa{\partial}
\newcommand\p{\phi}
\newcommand\ps{\psi}
\newcommand\Ps{\Psi}
\newcommand\bs{\backslash}
\newcommand\s{\sigma}
\newcommand\diam{\operatorname{diam}}
\newcommand\dist{\operatorname{dist}}
\newcommand\Int{\operatorname{Int}}
\newcommand\per{\operatorname{per}}
\newcommand\wps{\operatorname{wps}}
\newcommand\wt{\operatorname{wt}}
\newcommand{\Log}{\operatorname{Log}}
\newcommand\NN{\mathbb N}
\newcommand\QQ{\mathbb Q}
\newcommand\RR{\mathbb R}
\newcommand\ZZ{\mathbb Z}
\newcommand\cA{\mathcal A}
\newcommand\cC{\mathcal C}
\newcommand\cE{\mathcal E}
\newcommand\cF{\mathcal F}
\newcommand\cG{\mathcal G}
\newcommand\cN{\mathcal N}
\newcommand\lan{\langle}
\newcommand\ran{\rangle}
\newcommand{\Ext}{\operatorname{Ext}}

\makeatletter
\gdef\th@change{\normalfont\slshape
  \newcommand\@begintheorem##1##2{\item
       [\hskip\labelsep \theorem@headerfont (##2)\ ##1]}%
\newcommand\@opargbegintheorem##1##2##3{%
  \item[\hskip\labelsep \theorem@headerfont ##2\ ##1\ (##3)]}}
\makeatother

\begin{document}

\title[POWERS OF POLYNOMIALS AND CODINGS OF MARKOV CHAINS]
{Powers of positive polynomials and codings of Markov chains onto
Bernoulli shifts}

% author one information
\author{Brian Marcus}
\address{IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120}
\email{marcus@almaden.ibm.com}

% author two information
\author{Selim Tuncel}
\address{Department of Mathematics, Box 354350, University of Washington,
Seattle, WA 98195}
\email{tuncel@math.washington.edu}
\thanks{Partially supported by NSF Grant DMS--9622866}

\issueinfo{5}{13}{}{1999}
\dateposted{June 30, 1999}
\pagespan{91}{101}
\PII{S 1079-6762(99)00066-9}
\def\copyrightyear{1999}
\copyrightinfo{1999}{American Mathematical Society}

\subjclass{Primary 28D20; Secondary 11C08, 05A10}

\date{January 21, 1999}

\commby{Klaus Schmidt}

\begin{abstract}
We give necessary and sufficient conditions for a
Markov chain to factor onto a Bernoulli shift (i) as an eventual
right-closing factor, (ii) by a right-closing factor map, (iii) by a
one-to-one a.e. right-closing factor map, and (iv) by a regular
isomorphism. We pass to the setting of polynomials in several
variables to represent the Bernoulli shift by a nonnegative polynomial
$p$ in several variables and the Markov chain by a matrix $A$ of such
polynomials. The necessary and sufficient conditions for each of
(i)--(iv) involve only an eigenvector $r$ of $A$ and basic invariants
obtained from weights of periodic orbits. The characterizations of 
(ii)--(iv) are deduced from (i). We formulate (i) as a combinatorial
problem, reducing it to certain state-splittings (partitions) of paths
of length $n$. In terms of positive polynomial masses associated with
paths, the aim then becomes the construction of partitions so that the
masses of the paths in each partition element sum to a multiple of
$p^n$, the multiple being prescribed by $r$. The
construction, which we sketch, relies on a description of the terms of 
$p^n$ and on estimates of the relative sizes of the coefficients of $p^n$.
\end{abstract}

\maketitle


\section{Introduction}
We will describe in this article several recent results for coding Markov
chains onto Bernoulli shifts. Adopting an approach first espoused by Parry
and Tuncel, we will associate polynomial matrices to Markov chains and
translate the jointly measure-theoretic and topological coding problems into
combinatorial ones. Bernoulli shifts will then be represented by polynomials
$p$ with nonnegative integral coefficients, and we will find ourselves
facing questions about powers of $p$: We start our exposition with a number
of results on the structure and coefficients of large powers of positive
polynomials in several variables. This material is isolated in section 2,
and readers whose interests lie with powers of polynomials may go directly
to section 2. We remark that proofs of the results in
section 2 rely, in turn, on ideas from ergodic theory, specifically, the
notion of entropy at a weight-per-symbol\  and the related equilibrium states \cite{MT2}.

It is well known from Ornstein's isomorphism theory \cite{O} that entropy is a
complete invariant of measure-theoretic isomorphism for mixing Markov
chains. In that result the isomorphism is \emph{two-sided}, meaning that it
and its inverse are allowed to use the entire past and the entire future of
a point in order to determine the present coordinate of its image. In a
one-sided isomorphism, the isomorphism and its inverse are allowed to use
the entire past, but none of the future. In \cite{AMT} Markov chains were
completely classified up to one-sided isomorphism, via an effective
algorithmic procedure. An intermediate notion is regular isomorphism. Here,
the isomorphism and its inverse are allowed to use the entire past and a
uniformly bounded amount of the future.

Ideas emanating from symbolic dynamics, in particular right-resolving and
right-closing maps of shifts of finite type (see below for definitions),
have a strong bearing on regular isomorphism and one-sided isomorphism of
Markov chains: If a right-closing map is one-to-one\  almost everywhere, then
it defines a (rather concrete) regular isomorphism between the shifts 
with respect to their measures of maximal entropy. More
generally, if the shifts of finite type are endowed with Markov measures and
the map preserves measure, then we obtain a regular isomorphism between the
Markov chains. It was shown in [BT] that two Markov chains are regularly
isomorphic if and only if there exists a Markov chain which factors onto
each of them by a right-closing map which is one-to-one\  almost everywhere.
Thus, the study of regular isomorphism largely reduces to that of
right-closing maps between Markov chains.

Likewise, two Markov chains are one-sidedly isomorphic if and only if there
exists a Markov chain which factors onto each of them by a right-resolving
map which is one-to-one\  almost everywhere. This fact serves as the first step of
the classification of \cite{AMT}. Right-closing maps form the closure of
right-resolving ones under block isomorphism, that is, measure-preserving
topological conjugacy.

We will give complete answers to the following questions for an arbitrary
Markov chain and a Bernoulli shift.
\begin{enumerate}
\item[(1)]Does the Markov chain eventually factor onto the Bernoulli shift by
right-closing maps?
\item[(2)]Does the Markov chain factor onto the Bernoulli shift by a
right-closing
map? By a right-closing map which is one-to-one\  almost everywhere?
\item[(3)]Is the Markov chain regularly isomorphic to the Bernoulli shift?
\end{enumerate}

Without consideration of measures or, equivalently, restricting attention to
measures of maximal entropy, analogues of (1)--(3) were answered for shifts
of finite type in the sequence of papers \cite{M,BMT,A}. It is natural to seek
generalizations of these results to Markov chains. The work presented here
realizes the generalizations for a Bernoulli image.

Definitions and the relationship between Markov chains and
matrices of polynomials are recalled in section 3 below. The answers to
(1)--(3) are
then presented in section 4.
Sections 5 and 6 outline their proofs.
Section 5 reduces (1)--(3) to (1) and, for
(1), formulates the problem in terms of state-splittings with certain
combinatorial properties. Section 6 is concerned with the construction of
the desired state-splitting.
Details and complete proofs may be found in \cite{MT4} and \cite{MT5}.

\section{Powers of positive polynomials}
Let $p$ be a Laurent polynomial in the variables $x_1,\dots, x_k$. For
$w=\!(w_1, \dots, w_k)\!\in\ZZ^k$, write $x^w=x^{w_1}_1\cdots x^{w_k}_k$ and
denote the coefficient of $x^w$ in $p$ by $p_w$. Then
$
p=\sum_{w\in\ZZ^k}\,p_w\,x^w\,
$
and $p_w$ are nonzero for only finitely many $w\in\ZZ^k$. Let
$\Log(p)=\{w\in\ZZ^k:p_w\ne 0\}$. The \emph{Newton polyhedron} $W(p)$ of $p$
is given by the rational convex hull of $\Log(p)$. Denote the collection of
nontrivial faces of $W(p)$ by $\cF(p)$. For $F\in\cF(p)$, let
\[
p_F=\sum_{w\in F}p_w\,x^w,
\]
and think of $p_F$ as the $F$-\emph{face} of $p$.
Let $\Delta(p)$ be the subgroup of $\ZZ^k$ generated by $\{a-b:a,
b\in\Log(p)\}$, and pick any $c_p\in\Log(p)$ to distinguish a coset
$c_p+\Delta(p)$ of $\Delta(p)$.

It is easy to see that $\Log(p^n)\subset nW(p)\cap (nc_p+\Delta(p))$. If
$H\ge 0$ and $S\subset\RR^k$, we use the usual norm and distance in $\RR^k$
to write $B(S, H)=\{w\in\RR^k: \dist(w,S)0$. There exist
$\epsilon_F>0$ and $N\in\NN$ such that for $a\in\ZZ^k$ the inequality
\[
(p^n)_{a+b}\ge K(p^n)_a
\]
holds whenever $n\ge N$, $\frac{a}{n}\in B(F, \epsilon_F)\backslash
B(\partial F, \bar\epsilon_F)$ and $b\in(\Log(p^L)\backslash
\Log(p^L_F))-\Log(p^L_F)$.
\end{prop}

\begin{prop}\label{prop2.3}
Let $p\in\ZZ^+[x^\pm_1, \dots, x^\pm_k]$ and $F\in\cF(p)$. Let
$\bar\epsilon_F$, $\theta>0$ and $D\in\NN$. There exist $\epsilon_F>0$
and $N\in\NN$ such that
\[
\left|\frac{(p^n)_a/(p^n)_{a+b}}{(p^n)_{a+u}/(p^n)_{a+u+b}}-1\right|<\theta
\]
whenever $n\ge N$ and $a, b, u\in\ZZ^k$ are such that $a$,
$a+u\in\Log(p^n)$, $b\in\Delta(p_F)$,
$\frac{a}{n}\in B(F, \epsilon_F)\backslash B(\partial F,
\bar\epsilon_F)$, and $\|b\|$, $\|u\|\le D$.
\end{prop}

\begin{prop}\label{prop2.4}
Let $p\in\ZZ^+[x^\pm,\dots, x^\pm_k]$ and $F\in\cF(p)$. Let $\mye_F>0$,
$l\in\ZZ$ and $D\in\NN$. There exist $\mye_F>0$ and $K, N\in\NN$ such that
\[
\frac{1}{K}(p^{n+l})_{a+lc_F+b}\le (p^n)_a \le K(p^{n+l})_{a+lc_F+b}
\]
whenever $n\ge N$ and $a, b\in\ZZ^k$ are such that $\frac{a}{n}\in
B(F,\mye_F)\bs B(\partial F, \bar\mye_F)$, $b\in\Delta(p_F)$ and $\|b\|\le
D$.
\end{prop}

Details of (\ref{thm2.1})--(\ref{prop2.4}) may be found in \cite{MT4}. In
the case of (\ref{prop2.2})--(\ref{prop2.4}), the method of proof
and the more technical results at its basis may be objects of greater
general interest. They involve the notion of entropy at a weight-per-symbol\  and
the corresponding equilibrium states, which are imported from \cite{MT2}
and strengthened in the
Bernoulli setting: Letting $W_\RR(p)$ denote the real convex hull of $\Log(p)$
and $d=\mathop{\sum}_{w\in\ZZ^k}p_w\,$, it turns out that the map
$w\mapsto s(w)$ that sends $w\in W_\RR(p)$ to the corresponding equilibrium
distribution $s(w)$, which is a probability vector of size $d$, is $C^1$ on
$W_\RR(p)$. It is also shown that, for small $\epsilon_F, \delta>0$ and
large $n$, multinomial coefficients lying in a
$\delta$-ball around $w=\frac{a}{n}$ will estimate $(p^n)_a$ uniformly
closely for $w\in B(F,\epsilon_F)\bs
B(\partial F, \bar\epsilon_F)$. From this common ground, the proof of each
of (\ref{prop2.2})--(\ref{prop2.4}) is reduced to a calculation involving
multinomial coefficients.

As far as we are aware, the $F$-faces $p_F$
were introduced by Handelman \cite{H}.

\section{Markov chains and polynomial matrices}
It is well known that a directed graph $G$ defines a shift of finite type
$(X_G, \sigma_G)$. A shift-commuting continuous surjection $\phi:X_G\to
X_H$ of shifts of finite type is known as a \emph{factor map}. The map
$\phi$ is \emph{right-closing} if left-asymptotic distinct points of $X_G$
have distinct images under $\phi$. Right-closing maps are bounded-to-one
and, assuming $G$ is irreducible, there exists $d=d(\phi)\in\NN$, called the
\emph{degree} of $\phi$, so that every doubly transitive $y\in X_H$ has
exactly $d$ pre-images. If $d=1$, the map $\phi$ is said to be one-to-one\ 
almost everywhere. For
these and other basic definitions and facts on shifts of finite type and
factor maps, see \cite{LM}.

The directed graph $G$ is \emph{weighted} if, for some multiplicative
Abelian group $\cG$, each edge $e$ of $G$ is assigned a \emph{weight}
$\wt_G(e)\in\cG$. The \emph{weight} of a path $\gamma=e_1e_2\cdots e_n$ is
the product $\wt_G(\gamma)=\wt_G(e_1)\cdots\wt_G(e_n)$. Let $\Gamma(G)$ be
the subgroup of $\cG$ generated by weights of cycles, and let $\Delta(G)$ be
the subgroup of $\Gamma(G)$ consisting of ratios $\wt_G(\gamma)/\wt_G(\eta)$
of weights of cycles $\gamma, \eta$ of the same length. For irreducible $G$
of period $d$, let $\gamma,\eta$ be cycles whose lengths satisfy
$l(\gamma)=l(\eta)+d$ and use $c_G=\wt_G(\gamma)/\wt_G(\eta)$ to distinguish
a coset $c_G\Delta(G)$. (For properties of $\Gamma$, $\Delta$, $c\Delta$
see \cite{PS,MT1}.)

The graphs we consider will always be directed, irreducible and, except for
a brief spell, weighted by monomials. Such graphs correspond to
irreducible matrices $A$ over $R^+_k$: Express each entry $A(I, J)$ as a
sum (with multiplicity) of monomials, place as many edges from $I$ to $J$ as
there are terms in this sum, and bijectively assign the monomials as
weights. Confusing $A$ with the associated graph $G(A)$, we write
$\wt_A(\gamma)$, $\Gamma(A)$, $\Delta(A)$, $c_A\Delta(A)$ for the objects
defined above for $G(A)$. For a $G(A)$-cycle $\gamma$ of length
$l=l(\gamma)$, we define the \emph{weight-per-symbol} of $\gamma$ to be
$\wps_A(\gamma)=\frac{1}{l}\Log(\wt_A(\gamma))\in\QQ^k$. The rational convex
hull of $\{\wps_A(\gamma):\gamma$ cycle of $G(A)\}$ is the \emph{weight-per-symbol\ 
polytope} $W(A)$ of $A$. For $x_1,\dots,x_k>0$, let $\beta_A(x_1, \dots,
x_k)>0$ be the spectral radius of the nonnegative real-valued matrix $A(x_1,
\dots, x_k)$. Writing $\RR^{++}$ for the positive reals, this
defines the \emph{beta function}
$\beta_A:(\RR^{++})^k\to\RR^{++}$ of $A$.

We write $(X_A, \sigma_A)$ for the shift of finite type defined by $G(A)$
together with the weights-per-symbol assigned to its periodic orbits. We
require
finite-to-one factor maps $\phi:X_A\to X_B$ between such systems to be
\emph{weight-preserving} in that $\wps_B(\phi(\gamma))=\wps_A(\gamma)$ for
every periodic orbit $\gamma$ of $(X_A, \sigma_A)$. The (clearly necessary)
\emph{factor periodic point condition} for $A, B$ is the requirement that,
for each periodic orbit $\gamma$ of $(X_A, \sigma_A)$,
there exist in $(X_B, \sigma_B)$ a periodic orbit of the same weight-per-symbol\  whose
period divides that of $\gamma$.

Applying the above to $p\in R^+_k$ by viewing it as a $1\times 1$ matrix,
note that there is a slight clash with the definitions of $\Gamma(p)$,
$\Delta(p)$, $c_p\Delta(p)$ given in section 2, resulting from confusing
monomials and their exponents.

Markov chains are traditionally defined by stochastic matrices. Given an
irreducible stochastic matrix $M$, we construct a graph $G(M)$ taking
weights in $\RR^{++}$: The vertices of $G(M)$ are given by the indexing set
of $M$, and there is an edge of weight $M(I, J)$ from $I$ to $J$ whenever
$M(I, J)>0$. The shift of finite type $(X_M, \sigma_M)$ defined by $G(M)$
and the Markov measure $\mu_M$ defined by $M$ give us the \emph{Markov
chain} $(X_M, \sigma_M, \mu_M)$. We will write $\wt_M(\gamma)$,
$\Gamma(M)$, $\Delta(M)$, $c_M\Delta(M)$ for the objects defined for the
weighted graph $G(M)$. For $t\in\RR$, let $\beta_M(t)$ be the spectral
radius of the matrix $M^{(t)}$ with
\[
M^{(t)}(I, J) = \left\{\begin{array}{ll}
0 &\hbox{if }M(I, J)=0,\\
M(I, J)^t &\hbox{if }M(I, J)>0.
\end{array}\right.
\]
This defines the \emph{beta function} $\beta_M:\RR\to\RR^{++}$ of $M$.

Letting $Q$ also be an irreducible stochastic matrix, we require factor maps
between $(X_M, \sigma_M, \mu_M)$ and $(X_Q, \sigma_Q, \mu_Q)$ to be
measure-preserving. In particular, $(X_Q, \sigma_Q, \mu_Q)$ is a
\emph{right-closing factor} of $(X_M, \sigma_M, \mu_M)$ if there exists a
right-closing map $\phi$ of the shift of finite type $(X_M, \sigma_M)$ onto
$(X_Q,\sigma_Q)$ such that $\mu_M\circ\phi^{-1}=\mu_Q$. The Markov chain
$(X_Q, \sigma_Q, \mu_Q)$ is a \emph{right-closing eventual factor} of $(X_M,
\sigma_M, \mu_M)$ if $(X_Q, \sigma^n_Q, \mu_Q)$ is a right-closing factor of
$(X_M, \sigma^n_M, \mu_M)$ for all large $n$.

Suppose the rows of $Q$ are identical, so that $(X_Q, \sigma_Q, \mu_Q)$ is a
\emph{Bernoulli shift}. Also suppose $\beta_M=\beta_Q$, since this equality
is necessary for the coding problems under consideration. Then, by
(6.1) of \cite{MT1}, $\Gamma(M)\subset\Gamma(Q)$. Pick a basis $a_1, \dots,
a_k$ of the finitely generated Abelian subgroup $\Gamma(Q)$ of $\RR^{++}$.
Upon conjugating $M, Q$ by suitable diagonal matrices, we obtain matrices
whose entries lie in $\Gamma(Q)$. Hence, each nonzero entry of $M, Q$ can be
uniquely expressed as a product of integral powers of $a_1, \dots, a_k$.
Replacing each $a_i$ by an indeterminate $x_i$, we get from $M, Q$
irreducible matrices $A, B$ over $R^+_k$. A finite-to-one factor map $\phi$
of the shift of finite type $(X_M,\sigma_M)$ onto $(X_Q, \sigma_Q)$
satisfies $\mu_M\circ\phi^{-1}=\mu_Q$ if and only if $\phi$
is a (weight-preserving) factor map of $(X_A, \sigma_A)$ onto
$(X_B, \sigma_B)$. (See section 2 of \cite{T} for details and credits.)
Moreover, since the rows of $Q$ are identical, we can put
$p=\mathop{\sum}_{J}B(I, J)$ for any row $I$ to identify $(X_B,
\sigma_B)$ with $(X_p, \sigma_p)$.

Thus, we are in the position of having $p\in R^+_k$
and an irreducible $R^+_k$-matrix $A$ with $\beta_A=p$ and
studying weight-preserving maps of
$(X_A, \sigma^n_A)$ onto $(X_p, \sigma^n_p)$. The equality $\beta_A=p$
implies that $W(A)=W(p)$, the Newton polyhedron of $p$. Consider
$F\in\cF(p)$. Define a subgraph of $G(A)$ by retaining an edge $e$ of $G(A)$
(and its weight $\wt_A(e)$) if and only if there exists a $G(A)$-cycle
$\gamma$ which contains $e$ and has $\wps_A(\gamma)\in F$. The resulting
subgraph is nonwandering; that is, it consists only of irreducible
components, which we call the \emph{$F$-components} of $A$. The beta
function of an $F$-component either equals $p_F$ or it is strictly less than
$p_F$ on all of $(\RR^{++})^k$; the $F$-components in the former category
are said to be \emph{principal}. (See \cite{MT1,T} for the details.)
$F$-components of $A$ will be central to our solutions of (1)--(3) of the
introduction. Note that when
$F=W(p)$, we have a single (principal) $W(p)$-component, namely, $A$ itself.

\section{The coding results}
To formulate the conditions that will feature in the solutions of
(1)--(3), let $p\in R^+_k$ and let $F$ be a proper face of
$W(p)$. A polynomial $q\in R_k$ will be said to \emph{$F$-conform} to $p$ if
there exists $n\in\NN$ so that for some $u\in\ZZ^k$ we have
\[
\Log(q)+u\subset\Log(p^n)\hbox{ and }(\Log(q)+u)\cap\Log(p^n_F)\ne\emptyset;
\]
in this case we will put $\Log_F(q)\!=\!\Log(q)\cap (\Log(p^n_F)-u)$ and
$q_F \!=\!
\mathop{\sum}_{w\in \Log_F(q)}\,q_w x^w$. Roughly speaking, $F$-conformity
asks that, at and near $F$, both the ``shape'' and the ``gap structure'' of
$\Log(q)$ be subordinate to $\Log(p^n)$.
For a group $\Delta$ of monomials in $R_k$, we put $R(\Delta)=\{q\in
R_k:\Log(q)\subset\Log(\Delta)\}$.

Let $A$ be an irreducible $R^+_k$-matrix with $\beta_A=p$. By a
\emph{right eigenvector} of $A$ we will mean a nontrivial vector $r$ over
$R_k$ such that $Ar=pr$. Our results will require a right eigenvector which
satisfies three conditions. The first two are:
\begin{enumerate}
\item[\textbf{(a)}]The entries of $r$ lie in $R^+_k$.
\item[\textbf{(b)}]For each proper face $F$ of $W(p)$ and each state $I$ that
belongs
to an $F$-component of $A$, the entry $r(I)$ $F$-conforms to $p$.
\end{enumerate}

The existence of a right eigenvector satisfying (a) was proved in
\cite{MT3}. For the description of the third condition, let $F\in\cF(p)$,
let $\cC$ be a principal $F$-component of $A$, and let $A_\cC$ be the matrix
representing $\cC$. Using (b), let $r_\cC$ be the vector indexed by the
states of $\cC$ and having $r_\cC(I)=r(I)_F$ for $I\in\cC$. We then find a
monomial $m$ and a diagonal matrix $D$ with monomials for its diagonal
entries such that $\widetilde p_F=mp_F\in R(\Delta(p_F))$, $\widetilde
A_\cC=mDA_\cC D^{-1}$ is over $R(\Delta(A_\cC))\subset R(\Delta(p_F))$,
$\widetilde r_\cC=Dr_\cC$ is over $R(\Delta(p_F))$ and $\widetilde
A_\cC\widetilde r_\cC=\widetilde p_F\widetilde r_\cC$. Put
$R_{p_F}=R(\Delta(p_F))[\frac{1}{\widetilde p}]$, the ring obtained upon
adjoining $ \frac{1}{\widetilde p}$ to $R(\Delta(p_F))$.
Letting $d$ denote the period of $\cC$, we have
the subring $R_{A_\cC}=R(\Delta(A_\cC))[\frac{1}{\widetilde p{}^d}]$ of
$R_{p_F}$. View $R_{p_F}$ as an $R_{A_\cC}$-module. For a period class $C$
of $\cC$, let $\widetilde r_C$ be the restriction of $\widetilde r_\cC$ to $C$
and consider the $R_{A_\cC}$-submodule $\langle r_C\rangle$ of $R_{p_F}$
generated by the entries of $\widetilde r_C$. Our third requirement is that
$\lan r_C\ran$ equal $R_{p_F}$:
\begin{enumerate}
\item[\textbf{(c)}]If $F\in\cF(p)$ and $C$ is a period class of a principal
$F$-component $\cC$ of $A$, then the $R_{A_\cC}$-module $\lan r_C\ran$
equals $R_{p_F}$.
\end{enumerate}

The following results answer (1)--(3) of the introduction.

\begin{theorem}\label{thm4.1}
Let $(X_M,\s_M,\mu_M)$ be a Markov chain and $(X_Q,\s_Q,\mu_Q)$
a Bernoulli shift. Then $(X_Q,\s_Q,\mu_Q)$ is a right-closing eventual
factor of $(X_M,\s_M,\mu_M)$ if and only if $\myb_M=\myb_Q$ and, considering the
$R^+_k$-matrix $A$ and polynomial $p\in R^+_k$ associated with $M,Q$, there
exists a right eigenvector $r$ of $A$ satisfying (a)--(c).
\end{theorem}

\begin{theorem}\label{thm4.2}
Let $(X_M,\s_M,\mu_M)$ be a Markov chain and
$(X_Q,\s_Q,\mu_Q)$ a Bernoulli shift. Then $(X_Q,\s_Q,\mu_Q)$ is a
right-closing factor of $(X_M,\s_M,\mu_M)$ if and only if $\myb_M=\myb_Q$, and,
considering the $R^+_k$-matrix $A$ and polynomial $p\in R^+_k$ associated
with $M,Q$, there exists a right eigenvector $r$ of $A$ satisfying (a)--(c)
and the factor periodic point condition holds for $A,p$. Moreover,
$(X_Q,\s_Q,\mu_Q)$ is a factor of $(X_M,\s_M,\mu_M)$ by a right-closing map
of degree $1$ if and only if, in addition, $M$ is aperiodic, $\myD(M)=\myD(Q)$ and
$c_M\myD(M)=c_Q\myD(Q)$.
\end{theorem}

The \emph{past $\sigma$-algebra} $\cA_M$
of $(X_M, \sigma_M, \mu_M)$ is generated by
the cylinder sets
\[
[e_0, e_1, \dots, e_l]_h = \{x=(x_n)\in X_M:x_h=e_0, x_{h+1}=e_1,\dots,
x_{h+l}=e_l\}
\]
with $l \in \ZZ^+$, $h\in \ZZ$ and $h+l\le 0$.
Markov chains $(X_M, \sigma_M, \mu_M)$ and $(X_Q,\sigma_Q, \mu_Q)$
are said to be \emph{regularly isomorphic} if there exists a
measure-theoretic isomorphism $\Phi:X_M\to X_Q$ such that
$\Phi^{-1}(\cA_Q)\subset\sigma^{-N}_M(\cA_M)$ and
$\Phi(\cA_M)\subset\sigma_Q^{-N}(\cA_Q)$ for some
nonnegative integer $N$.

\begin{theorem}\label{thm4.3}
Let $(X_M,\s_M,\mu_M)$ be a Markov chain and
$(X_Q,\s_Q,\mu_Q)$ a Bernoulli shift.
The following are equivalent.
\begin{enumerate}
\item[(i)]$(X_M,\s_M,\mu_M)$ and $(X_Q,\s_Q,\mu_Q)$ are regularly
isomorphic.
\item[(ii)]There exists a Markov chain $(X_R,\s_R,\mu_R)$ and right-closing
factor maps $\p:(X_R,\s_R,
\mu_R)\to(X_M,\s_M,\mu_M)$ and
$\ps:(X_R,\s_R,\mu_R)\to(X_Q,\s_Q,\mu_Q)$ of degree $1$.
\item[(iii)]$M$ is aperiodic, $\myb_M=\myb_Q$, $\myD(M)=\myD(Q)$,
$c_M\myD(M)=c_Q\myD(Q)$ and, considering the $R^+_k$-matrix $A$ and polynomial
$p\in R^+_k$ associated with $M,Q$, there exists a right eigenvector $r$ of
$A$ satisfying (a)--(c).
\end{enumerate}
\end{theorem}

The equivalence of (i) and (ii) of (\ref{thm4.3}) is a special case of the
main result of \cite{BT}. The equivalence of (ii) and (iii) is deduced from
(\ref{thm4.2}) with the aid of discrete geometry and techniques adapted from
symbolic dynamics.

\section{Combinatorial formulation}
We have explained that (\ref{thm4.1}) and (\ref{thm4.2}) may be regarded as
statements on right-closing maps of $(X_A, \sigma^n_A)$ onto $(X_p,
\sigma^n_p)$. Taking our cues from \cite{BMT,PT}, we formulate such maps in
terms of state-splittings. (See \cite{LM} for more on state-splittings, which
were first employed by Williams.)

Consider an $R^+_k$-matrix $B$. A \emph{state-splitting} of $(X_B,
\sigma_B)$ results from a collection of partitions: For every state $I$ of
$G(B)$, the set of edges starting at $I$ is partitioned into sets $(I, 1),
(I, 2), \dots, (I, \rho(I))$. For each $(I, i)$ form a vector
$\alpha^{(I, i)}$ indexed by the states of $G(B)$
by letting the $J$th entry $\alpha^{(I, i)}(J)$ be given by
 the sum of the weights $\wt_B(e)$ of the edges $e$
that belong to $(I, i)$ and terminate at $J$. The sum
$\mathop{\sum}^{\rho(I)}_{i=1}\,\alpha^{(I, i)}$ then equals the $I$th
row of $B$. State-splittings of $(X_B, \sigma_B)$ correspond in this way to
partitions of rows of $B$ into vectors over $R^+_k$, leading us to also
speak of \emph{(state-)splitting} $B$. Putting $\widehat B((I, i), (J,
j))=\alpha^{(I, i)}(J)$, the partition elements index a matrix
$\widehat B$ such that $(X_{\widehat B}, \sigma_{\widehat B})$ is block
isomorphic to $(X_B, \sigma_B)$.

Fix $p\in R^+_k$ and an irreducible $R^+_k$-matrix $A$ with $\beta_A=p$.
When $Ar=pr$ and the vector $r$ is over $R^+_k$, we will seek
state-splittings of a particular form: Writing each entry $r(I)$ as a sum of
monomials
\[
r(I)=\sum^{\rho(I)}_{k=1}x^{w(I, i)},
\]
we will seek to partition the $I$th row of $A^n$ into $\rho(I)$ vectors
$\alpha^{(I, i)}$, $1\le i\le \rho(I)$, such that $\alpha^{(I, i)}\cdot
r=x^{w(I, i)}p^n$. When we have been able to do this, we say that we have a
\emph{splitting of $A^n$ according to $r$}. This notion derives its
significance from the following.

\begin{theorem}\label{thm5.1}
Let $A$ be an irreducible $R^+_k$-matrix with $\myb_A=p\in R^+_k$. The
following are equivalent.
\begin{enumerate}
\item[(i)]$(X_{p^n},\s_{p^n})$ is a right-closing factor of $(X_{A^n},
\s_{A^n})$ for some $n\in\NN$.
\item[(ii)] $A$ has a right eigenvector $\,r$ over $R^+_k$ such that,
for some $N\in\NN$, the matrix $A^N$ can be split according to $r$.
\item[(iii)] $A$ has a right eigenvector $\,r$ over $R^+_k$ such that
$A^n$ can be split according to $r$ for all large $n$.
\item[(iv)]$(X_p,\s_p)$ is a right-closing eventual factor of $(X_A,\s_A)$.
\end{enumerate}
\end{theorem}

With both (\ref{thm4.1}) and (\ref{thm4.2}), the necessity of the conditions
is quickly established with the aid of (\ref{thm5.1}). Theorem
(\ref{thm5.1}) also enables us to use \cite{A} to deduce from (\ref{thm4.1})
the sufficiency of the conditions of (\ref{thm4.2}): By (\ref{thm4.1}) and
(\ref{thm5.1}), the conditions of (\ref{thm4.2}) provide splittings of $A^n$
according to $r$ for all large $n$. In \cite{A} Ashley shows how to use
analogous splittings and the related factor periodic point condition to
produce right-closing maps (of the first powers) in the case of shifts of
finite type. A right-closing map of $(X_A, \sigma_A)$ onto $(X_p,
\sigma_p)$ is constructed by going through the argument of \cite{A} with our
factor periodic point condition and splittings of $A^n$.

Thus, (\ref{thm4.1})--(\ref{thm4.3}) reduce to the construction of a
state-splitting of $A^n$ according to $r$. This construction takes up much
of \cite{MT5} (in the preprint version, 43 Latex pages out of 72). We provide
an outline of it.

The right eigenvector $r$ is said to \emph{totally conform to $p$} if, in
addition to satisfying (a)--(c), it has the property that every entry $r(I)$
$F$-conforms to $p$ for every proper face $F$ of $W(p)$.

The construction actually employs two state splittings. The first uses (b) and
(\ref{thm2.1}) to prove:

\begin{prop}\label{prop5.2}
For $n$ large enough, $A^n$ may be state-split in such a way that the
resulting matrix $\widehat{A^n}$ has a right eigenvector $\widehat r$ which
totally conforms to $p$.
\end{prop}

This is followed by the main splitting, outlined in the next section and
showing that if a matrix has a totally conforming right eigenvector, then
large powers of the matrix can be split according to that eigenvector.

\section{The main state-splitting}
By (\ref{thm5.1}) and (\ref{prop5.2}), we may now replace $A$ by a suitable
power to assume that $r$ totally conforms to $p$ and that every $F$-component
of $A$ is aperiodic for every $F\in\cF(p)$. Using (a)--(c) and total
conformity, pick $L\in\ZZ^+$, $u_{F, J}\in\ZZ^k$ and, for each principal
component $\cC$ and coset $x^u\Delta(A_\cC)\in\Delta(p_F)/\Delta(A_\cC)$,
pick $c_\cC\in\Delta(p_F)$, $D_{F, J}\in\Log(\Delta(p_F))$ and polynomials
$q^{(F, u)}(J)\in R(\Delta(A_\cC))$ such that:
\begin{enumerate}
\item[(1)]$\Log(r(J))+u_{F,J}\subset\Log(p^L)$ and $\Log(r(J)_F)+u_{F,J}\subset
\Log(p^L_F)$ for every $J\in S$;
\item[(2)]for each principal $F$-component $\cC$, the matrix $\widetilde A_\cC$
indexed by (the states of) $\cC$ and with
\[
\widetilde A_\cC(J, J')=A_\cC(J, J')\, \frac{x^{u_{F,J}}\,x^{D_{F,J}}}{c_\cC\,
c_{p_F}\,x^{u_{F,J'}}\,x^{D_{F,J'}}}
\]
is over $R(\Delta(A_\cC))$;
\item[(3)] $\sum_{J\in\cC}q^{(F,u)}(J)\,x^{u_{F,J}}x^{D_{F,J}}r(J
)_F=
x^up^L_F\,$ for every $F\in\cF(p)$, principal $F$-component $\cC$ and
$x^u\Delta(A_\cC)\in\Delta(p_F)/\Delta(A_\cC)$.
\end{enumerate}

Denote the starting and terminal states of a $G(A)$-path $\gamma$ by
$s(\gamma)$ and $t(\gamma)$. Let $W_n(I)$ be the set of $G(A)$-paths
$\gamma$ of length $n$ and with $s(\gamma)=I$. Let $W_n(I, J)$ be the set of
$\gamma\in W_n(I)$ with $t(\gamma)=J$; and $W_n(I, J, w)$ the set of
$\gamma\in W_n(I, J)$ with $\Log(\wt(\gamma))=w$. For $a\in\Log(r(I)p^n)$,
let $\pi(n,a)$ denote the probability vector of length $\rho(I)$ whose
$i$th entry equals $\pi(n, a, i)=(x^{w(I, i)}p^n)_a/(r(I)p^n)_a$. The
following lemmas make use of (\ref{prop2.3}) and
(\ref{prop2.4}).

\begin{lemma}\label{lem6.1}
Let $\theta, \bar\epsilon_F>0$ and $D, l\in\ZZ^+$. There exist
$\epsilon_F>0$ and $N\in\NN$ such that
\[
|\pi(n+l, a+lc_F+b, i)/\pi(n, a, i)-1|<\theta
\]
whenever $n\ge N$, $\frac{a}{n}\in B(F, \epsilon_F)\backslash B(\partial F,
\bar\epsilon_F)$, $(p^n)_a\ne 0$, $b\in\Log(\Delta(p_F))$ and $\|b\|\le D$.
\end{lemma}

\begin{lemma}\label{lem6.2}
Let $F\in\cF(p)$, $\bar\epsilon_F>0$ and $\bar D\in\NN$. There exist
$\epsilon_F>0$ and $N,\bar K\in\NN$ such that, for every $n\ge N$ and
$a\in\ZZ^k$ with $\frac{a}{n}\in B(F, \epsilon_F)\backslash B(\partial
F,\bar\epsilon_F)$, we can find a principal $F$-component $\cC$, $J_1\in\cC$
and $x^u\Delta(A_\cC)\in \Delta(p_F)/\Delta(A_\cC)$ with
\[
|W_n(I,J_1, a-u+b-Lc_F+u_{F,J_1}+D_{F,J_1})|\ge \frac{1}{\bar K}(r(I)p^n)_a
\]
whenever $b\in\Log(\Delta(A_\cC))$ and $\|b\|\le\bar D$.
\end{lemma}

Define the \emph{mass} of $\gamma\in W_n(I)$ to be
$\mass(\gamma)=\wt(\gamma)\,r(t(\gamma))$. For $W\subset W_n(I)$, let
$\mass(W)$ equal the sum of $\mass(\gamma)$ over $\gamma\in W$. Our goal is
to partition $W_n(I)$ into sets $(I, i)$, $1\le i\le\rho(I)$, so that
$\mass((I, i))=x^{w(I, i)}p^n$. We will speak of allocating the elements of
$W_n(I, J, w)$ according to $\pi(n, w+a)$, where $a\in\Log(r(J))$: What we
mean by this is that the number of elements placed in the $i$th set differs
from (the possibly nonintegral) number $\pi(n, w+a, i)|W_n(I, J, w)|$ by
less than 1. Condition (1) guarantees that, any time we assign paths from
$W_n(I, J, w)$ to the $i$th set, we have
$w+\Log(r(J))\subset\Log(r(I)p^n)$.

For the sake of simplicity, we restrict our attention to the case $k=2$.

For each $F\in\cF(p)$ and $J$, fix $a_{F, J}\in\Log(r(J)_F)$. Write
$a_J=a_{W(p), J}$. For $F\in\cF(p)$, also fix $v_F\in\ZZ^k$ with coprime
entries which exposes $F$ by having $F\cdot v_F=\min\{W(p)\cdot v_F\}$.
Write $\delta_F=\min\{W(p)\cdot v_F\}=\min\{\Log(p)\cdot v_F\}$ and
$\delta_F(J)=\min\{r(J)\cdot v_F\}$. For $F\in\cF(p)$ and $\lambda\in\ZZ$,
let
\[
\cN_n(F, \lambda)=\{a\in\Log(r(I)p^n):a\cdot v_F\le\delta_F(I)+n\delta_F+
\lambda\}.
\]
Recalling $k=2$, define $\cN_n(\lambda_0)$ to be the union of
$\cN_n(F_0,\lambda_0)$ over all vertices $F_0$ of $W(p)$ and define
$\cN_n(\lambda_0,
\lambda_1)=\cN_n(\lambda_0)\cup\bigcup_{F_1}\cN_n(F_1,
\lambda_1),$
where the last union is over all edges $F_1$ of $W(p)$. Let
$W_n(F, \lambda)$, $W_n(\lambda_0)$, $W_n(\lambda_0, \lambda_1)$ respectively
denote the union of the sets $W_n(I, J, w)$ over all $(J, w)$ such that
$w+\Log(r(J))$ intersects $\cN_n(F, \lambda), \cN_n(\lambda_0),
\cN_n(\lambda_0, \lambda_1)$. We drop the subscript from our notation when
the length is clear from the context.

Consider $\xi$, $D\ge 0$ and a partition of $W_n(\lambda_0, \lambda_1)$ into
sets $P(i)$, $1\le i\le \rho(I)$, satisfying two conditions:
\begin{enumerate}
\item[(i)]For every $a\in\cN_n(\lambda_0, \lambda_1)$ we have
$\mass(P(i))_a=(x^{w(I, i)} p^n)_a$.
\item[(ii)]If $W_n(I, J, w)\subset W_n(\lambda_0, \lambda_1)\bs
W_n(\lambda_0-D, \lambda_1-D)$, then
\[
1-\xi\le \frac{|W_n(I, J, w)\cap P(i)|}{\pi(n, w+a_J, i)|W_n(I, J, w)|}\le
1+\xi.
\]
\end{enumerate}
For a suitable choice of the constant $D$, we have:

\begin{lemma}\label{lem6.3}
For every small $\epsilon>0$ there exist $\xi\ge 0$ and $N\in\NN$ such
that, for any $n\ge N$ and $\lambda_0, \lambda_1>n\epsilon$, the existence
of a partition of $W_n(\lambda_0, \lambda_1)$ into $\rho(I)$ sets $P(i)$
satisfying (i) and (ii) implies the existence of a partition of $W_{n+L}(I)$
into $\rho(I)$ sets $(I, i)$ such that $\mass((I, i))=x^{w(I, i)}p^{n+L}$.
\end{lemma}

\begin{proof}[Sketch of proof] If $W_n(I, J, w)$ is not contained in
$W_n(\lambda_0, \lambda_1)$, allocate it according to $\pi(n, w+a_J)$. Let
$P'(i)$ be the set containing these allocations and $P(i)$. Let $\widetilde
P(i)\subset W_{n+L}(I)$ be obtained by extending the paths in $P'(i)$:
\[
\widetilde P(i)=\{\gamma\eta:\gamma\in P'(i), \eta\in W_L(t(\gamma))\}.
\]
Then $\mass(\widetilde P(i))=\mass(P'(i))p^L$, and $\mass(P'(i))_a=(x^{w(I,
i)}p^n)_a$ for all $a\in W_n(\lambda_0, \lambda_1)$. Consider
$a\in\Log(p^nr(I))\bs W_n(\lambda_0, \lambda_1)$. Taking $F=W(p)$,
$x^u\Delta(A) = x^a\Delta(A)$ in (3), writing $q^{(u)}(J)=q^{(W(p),u)}(J)$
and multiplying by $x^{a-u}$,
\[
\sum_J \,x^{a-u+u_{W(p),J}+D_{W(p),J}}q^{(u)}(J)\,r(J)=x^ap^L.
\]
Consider moving, for each $b\in\Log(q^{(u)}(J))$, exactly $q^{(u)}(J)_b$
elements of
$W_{n+L}(I, J,\\mya-u+u_{W(p),J}+D_{W(p),J}+b)$
from $\widetilde
P(j)$ to $\widetilde P(i)$. (If $q^{(u)}(J)_b<0$, we move the paths from
$\widetilde P(i)$ to $\widetilde P(j)$.) By the above equation, this adds
$x^ap^L$ to $\mass(\widetilde P(i))$ and subtracts $x^ap^L$ from
$\mass(\widetilde P(j))$. To complete the proof, one uses (ii),
(\ref{lem6.1}) and (\ref{lem6.2}) to verify that, for small $\xi$ and large
$n$, the sets $\widetilde P(j)$ contain the paths required to repeat this
``correction'' $(x^{w(I, i)}p^n)_a-\mass(P'(i))_a$ times.
\end{proof}

A partition to which (\ref{lem6.3}) applies is constructed by induction.
For ease of exposition, we assume $L=0$. This enables us
to avoid having, as we did in the
sketch of the proof of (\ref{lem6.3}), to extend paths by $L$ each time we
use (3) to make corrections. For small $\epsilon_0>\epsilon_1>0$, the
induction will have $\epsilon_0n+\epsilon_1n$ stages. (The choices of
$\epsilon_0$, $\epsilon_1$ are indicated below.) For $\lambda\in\{1, \dots,
\epsilon_0n+\epsilon_1n\}$, we will describe the sets $P(\lambda, i)$,
$1\le i\le\rho(I)$, we have at the end of stage $\lambda$.

For $\lambda\in\{1, \dots, \epsilon_0n\}$, we only make allocations near
vertices of $W(p^n)$: We start the $\lambda$th stage having partitioned
$W(\lambda-2)=W_n(\lambda-2)$ into sets $P(\lambda-1,i)$ with
$\mass(P(\lambda-1,i))_a=(x^{w(I, i)}p^n)_a$ for all $a\in\cN(\lambda-2)$.
Then, for each vertex $F_0$, allocate according to $\pi(n, w+a_{F_0,J})$
each $W(I, J, w)$ contained in $W(F_0, \lambda-1)\bs W(\lambda-2)$.
According to (\ref{prop2.2}), by picking $\epsilon_0$ small and $n$ large,
we can be sure that for $a\in\cN(F_0, \lambda-1)\bs\cN(\lambda-2)$ the
coefficient $\mass(P(\lambda-1, i))_a$ will be an arbitrarily small fraction
of $(x^{w(I, i)}p^n)_a$. Combining this with (\ref{lem6.2}), we are assured
of the supply of paths needed to use (3) to make corrections and obtain
$P(\lambda, i)$ with $\mass(P(\lambda, i))_a=(x^{w(I, i)}p^n)_a$ for all
$a\in\cN(\lambda-1)$.

From $\lambda=\epsilon_0n+1$, we allocate paths near the edges of $W(p^n)$
as well. For $\lambda\in\{\epsilon_0n+1, \dots, \epsilon_0n+\epsilon_1n\}$
the $\lambda$th stage consists of $d$ steps. (The choice of $d$ will become
clear in a minute.) We start the $\lambda$th stage having partitioned
$W(\lambda-2, \lambda-\epsilon_0n-2)$ into sets $P(\lambda-1,i)$ with
$\mass(P(\lambda-1,i))_a=(x^{w(I, i)}p^n)_a$ for all $a\in\cN(\lambda-2,
\lambda-\epsilon_0n-2)$. In step 1, we allocate and correct near edges: For
each edge $F_1$, allocate according to $\pi(n, w+a_{F_1,J})$ each $W(I, J,
w)$ contained in $W(F_1, \lambda-\epsilon_0n-1)\bs W(\lambda-2,
\lambda-\epsilon_0n-2)$. Then use (3) to correct: We employ (\ref{prop2.2})
and (\ref{lem6.2}) as before, this time applying them to edges. In addition,
we use (\ref{lem6.1}) to see that errors due to the choice of $a_{F_1,J}$
may be corrected. While getting the coefficients correct for $a\in\cN(F_1,
\lambda-\epsilon_0n-1)$, step 1 may perturb those of boundedly many
$a\in\cN(\lambda-2)\bs \cN(\lambda-d)$. Steps 2 to $d-1$ make up for the
perturbations. (Step $\mu\in\{2, \dots, d-1\}$ gets $\cN(\lambda-d+\mu-1)$
correct.) Applying (\ref{prop2.2}) to edges, for small $\epsilon_1$
and large $n$, the perturbations will be small enough for us to
correct them by employing (3) near vertices. Finally, step $d$ allocates
and corrects at $a\in\cN(\lambda-1)\bs\cN(\lambda-2, \lambda-\epsilon_0n-1)$
to yield $P(\lambda, i)$ with $\mass(P(\lambda, i))_a = (x^{w(I, i)}p^n)_a$
for all $a\in\cN(\lambda-1, \lambda-\epsilon_0n-1)$.

\begin{thebibliography}{MT1}

\bibitem[A]{A}J. Ashley, Resolving factor maps for shifts of finite type
with equal entropy, \emph{Ergod.\ Th.\ and Dynam.\ Sys.} \textbf{ 11} (1991),
219--240. \MR{92d:58056}
\bibitem[AMT]{AMT}J. Ashley, B. Marcus and S. Tuncel, The classification
of one-sided Markov chains, \emph{Ergod.\ Th.\ and Dynam.\ Sys.} \textbf{ 17}
(1997), 269--295. \MR{98k:28021}
\bibitem[BMT]{BMT}M. Boyle, B. Marcus and P. Trow, Resolving maps and the
dimension group for shifts  of finite type, \emph{Mem.\ Amer.\ Math.\ Soc.}
\textbf{ 377} (1987). \MR{89c:28019}
\bibitem[BT]{BT}M. Boyle and S. Tuncel, Regular isomorphism of Markov
chains is almost topological, \emph{Ergod.\ Th.\ and Dynam.\ Sys.} \textbf{ 10}
(1990), 89--100. \MR{92i:28021}
\bibitem[H]{H}D. Handelman, Positive polynomials and product type actions
of compact groups, \emph{Mem.\ Amer.\ Math.\ Soc.}
\textbf{ 320} (1985). \MR{86h:46091}
\bibitem[LM]{LM}D. Lind and B. Marcus, \emph{An Introduction to Symbolic
Dynamics and Coding}, Cambridge Univ.\ Press, Cambridge, 1995. \MR{97a:58050}
\bibitem[M]{M}B. Marcus, Factors and extensions of full shifts,
\emph{Monatshefte  Math.} \textbf{ 88} (1979), 239--247. \MR{81g:28023}
\bibitem[MT1]{MT1}B. Marcus and S. Tuncel, The weight-per-symbol polytope
and scaffolds of invariants associated with Markov chains, \emph{Ergod.\
Th.\ and Dynam.\ Sys.} \textbf{ 11} (1991), 129--180. \MR{92g:28038}
\bibitem[MT2]{MT2}B. Marcus and S. Tuncel, Entropy at a weight-per-symbol
and embeddings of Markov chains, \emph{Invent.\ Math.} \textbf{ 102} (1990),
235--266. \MR{91k:28023}
\bibitem[MT3]{MT3}B. Marcus and S. Tuncel, Matrices of polynomials,
positivity, and finite equivalence of Markov chains, \emph{J.\ Amer.\
Math.\ Soc.} \textbf{ 6} (1993), 131--147. \MR{93e:28022}
\bibitem[MT4]{MT4}B. Marcus and S. Tuncel, On large powers of positive
polynomials in several variables, preprint.
\bibitem[MT5]{MT5}B. Marcus and S. Tuncel, Resolving Markov chains onto
Bernoulli shifts, preprint.
\bibitem[O]{O}D. Ornstein, \emph{Ergodic Theory, Randomness and Dynamical
Systems}, Yale Univ.\ Press, New Haven, 1974. \MR{56:5836}
\bibitem[PS]{PS}W. Parry and K. Schmidt, Natural coefficients and
invariants for Markov shifts, 
\emph{Invent.\ Math.} \textbf{ 76} (1984), 15--32. \MR{86b:28022a}
\bibitem[PT]{PT}W. Parry and S. Tuncel, On the stochastic and
topological structure of Markov chains, \emph{Bull.\ London Math.\ Soc.}
\textbf{ 14} (1982), 16--27. \MR{84i:28024}
\bibitem[T]{T}S. Tuncel, Faces of Markov chains and matrices of
polynomials, \emph{Contemp.\ Math.}, Vol.\ 135, Amer.\ Math.\ Soc.,
Providence, 1992, pp.\ 391--422. \MR{94m:28034}
\end{thebibliography}
\end{document}