---
abstract: |
    We study one-sided Markov shifts, corresponding to positively recurrent Markov chains with countable (finite or infinite) state spaces. The following classification problem is considered: when two one-sided Markov shifts are isomorphic up to a measure preserving isomorphism ? In this paper we solve the problem for the class of $\rho$-uniform (or finitely $\rho$-Bernoulli) one-sided Markov shifts considered in .

    We show that every ergodic $\rho$-uniform Markov shift $T$ can be represented in a canonical form $T = T_G $ by means of a canonical (uniquely determined by $T$) stochastic graph $G$. In the canonical form, two such shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic if and only if their canonical stochastic graphs $G_1$ and $G_2$ are isomorphic.
address:
- 'Address: [*Ben Zion Rubshtein, Dept. of Mathematics, Ben-Gurion University of the Negev, Beer-Sheva, 84105, Israel.*]{}'
- ' E-mail: [*benzion@math.bgu.ac.il*]{}'
author:
- 'Ben-Zion Rubshtein'
title: ' On a class of one-sided Markov shifts'
---

Introduction {#Intro}
============

In this paper we consider the classification problem for one-sided Markov shifts with respect to measure preserving isomorphism. Let $G$ be a finite or countable stochastic graph, i.e. a directed graph, whose edges $g \in G$ are equipped with positive weights $p(g)$. The weights $p(g)$ determine transition probabilities of a Markov chain on the discrete state space $G$. The corresponding one-sided Markov shift $T_G$ acts on the space $(X_G,m_G)$, where $ X_G = G^{{\mathbb{N}}}$ and $m_G$ is a stationary (probability) Markov measure on $X_G$. We deal only with irreducible positively recurrent Markov chains, so that such a Markov measure exists and the shift $T_G$ is an ergodic endomorphism of the Lebesgue space $(X_G,m_G)$. The problem under consideration is : When for given two stochastic graphs $G_1$ and $G_2$, does there exist an isomorphism $\; \Phi { : }X_{G_1} {\rightarrow}X_{G_2} \;$ such that $\; m_{G_2} = m_{G_1} \circ \Phi^{-1} \;$ and $\; \Phi \circ T_{G_1} \;=\; T_{G_2} \circ \Phi \;$.

It is obvious, that any (weight preserving) graph isomorphism $\phi { : }G_1 {\rightarrow}G_2$ generates such an isomorphism $\Phi = \Phi_\phi$, but nonisomorphic graphs can generate the same shift $T_G$.

Recently J. Ashley, B. Marcus and S. Tuncel [@AsMaTu] solved the classification problem for one-sided Markov shifts corresponding to [**finite**]{} Markov chains. They used an approach which is based on the following important fact: Two one-sided Markov shifts $T_{G_1}$ and $T_{G_2}$ (on finite state spaces) are isomorphic iff there exists a common extension $G$ of $G_1$ and $G_2$ by right resolving graph homomorphisms of degree $1$. The result was proved implicitly in [@BoTu], where regular isomorphisms and right closing maps for two-sided Markov shifts were studied (See also [@As], [@KiMaTr], [@Tr], [@Ki] and references cited there)

It should be noted that the classification problem for two-sided shifts is quite different from the one-sided case. Namely, any mixing two-sided Markov shift is isomorphic to the Bernoulli shift with the same entropy [@FrOr] and two-sided Bernoulli shifts are isomorphic iff they have the same entropy by the Sinai-Ornstein theorem [@Si]-[@Or].

On the other hand, let $T_\rho$ be the one-sided Bernoulli shift with a discrete state space $(I,\rho)$, where $I$ is a finite or countable set, $1 < |I| \leq \infty$, and $\rho = \{\rho_i\}_{i
\in I}$, $\sum_{i} \rho_i = 1$, $\rho_i > 0$. The endomorphism $T_\rho$ acts as the one-sided shift on the product space $(X_\rho , m_\rho) = \prod_{n=1}^{\infty} (I, \rho)$. Consider the measurable partition $T_\rho^{-1} {\varepsilon}= \{ T_\rho^{-1} x \;,\; x \in X_\rho \}$ generated by $T_\rho$ on $X_\rho$. The partition admits an independent complement ${\delta}$, which is not unique in general, but necessarily has the distribution $\rho$. This implies that one-sided Bernoulli shifts $T_{\rho_1}$ and $T_{\rho_2}$ are isomorphic iff the distributions $\rho_1$ and $\rho_2$ coincide.

This simple observation motivates the following definition. An endomorphism $T$ of a Lebesgue space $(X, m)$ is called ${\boldsymbol{\rho}}$[**-uniform**]{} (or [**finitely**]{} ${\boldsymbol{\rho}}$[**-Bernoulli**]{} according to ) if the measurable partition $T^{-1} {\varepsilon}= \{ T^{-1} x \;,\;\; x \in X \}$ admits an independent complement ${\delta}$ with $distr \; {\delta}= \rho$. We denote by ${\mathcal {UE}(\rho)}$ the class of all $\rho$-uniform endomorphisms.

Recall that the cofiltration $\xi (T)$ generated by an endomorphism $T$ is the decreasing sequence $\{\xi_n\}_{n=1}^{\infty}$ of the measurable partitions $\xi_n = T^{-n} {\varepsilon}$ of the space $X$ onto inverse images $T^{-n}x$. If two endomorphisms $T_1$ and $T_2$ are isomorphic, i.e. there exists an isomorphism $\Phi$ such that $\; \Phi \circ T_1 = T_2 \circ \Phi \;$, then $\; \Phi (T_1^{-n}x) = T_2^{-n} (\Phi x) \;$ for almost all $x \in X$, i.e. $\Phi (T_1^{-n} {\varepsilon}) = T_2^{-n} {\varepsilon}$ for all $n$. This means that the cofiltrations $\xi(T_1)$ and $\xi(T_2)$ are isomorphic.

If $T \in {\mathcal {UE}(\rho)}$, the cofiltration $\xi(T)$ is not necessarily isomorphic to the [**standard**]{} cofiltration $\xi(T_\rho)$, generated by the Bernoulli shift $T_\rho$. However, it is [**finitely isomorphic**]{} to $\xi(T_\rho)$, i.e. for every $n \in {{\mathbb{N}}}$ there exists an isomorphism $\Phi_n$ such that $\Phi_n (T^{-k} {\varepsilon}) =T_\rho^{-k} {\varepsilon}$ for all $1 \leq k
\leq n$.

The isomorphism problem for $\rho$-uniform endomorphisms is decomposed into the following two parts: When are the cofiltrations $\xi(T_1)$ and $\xi(T_2)$ isomorphic? When are $T_1$ and $T_2$ isomorphic provided that $\xi(T_1) = \xi(T_2)$?

In particular, for given $ T \in {\mathcal {UE}(\rho)}$: When is the cofiltration $\xi(T)$ standard, i.e. isomorphic to $\xi(T_\rho)$ ? When are $T_1$ and $T_2$ isomorphic provided that $\xi(T_1) = \xi(T_2)$ ?

All these problems are quite nontrivial even in the dyadic case $\rho = (\frac{1}{2},\frac{1}{2})$. Various classes of decreasing sequences of measurable partitions were considered by A.M. Vershik -, V.G. Vinokurov [@Vi], A.M. Stepin

[@St] and by author ,,-. A new remarkable progress in the theory is due to J. Feldman, D.J. Rudolph, D. Heicklen and Ch. Hoffman (See [@FeR], [@HeHo], [@HeHoR], [@Ho], [@HoR]). Note also that, as it was shown in , a $\rho$-uniform one-sided Markov shift $T_G$ is isomorphic to the Bernoulli shift $T_\rho$ iff the cofiltration $\xi(T_G)$ is isomorphic to standard cofiltration $\xi(T_\rho)$.

The purpose of this paper is to classify the $\rho$-uniform one-sided Markov shifts. We show that every ergodic $\rho$-uniform Markov shift $T$ can be represented in a [**canonical form**]{} $T = T_G $ by means of a [**canonical**]{} (uniquely determined by $T$) stochastic graph $G$. In the canonical form, two such shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic if and only if their canonical stochastic graphs $G_1$ and $G_2$ are isomorphic.

First we consider (Section \[s2\]) general $\rho$-uniform endomorphisms and use the following results from . Any ergodic $T \in {\mathcal {UE}(\rho)}$ can be represented as a skew product over $T_\rho$ on the space $X_\rho \times Y_d$, $d \in {{\mathbb{N}}}\cup \{\infty\} $, where $Y_d$ consists of $d$ atoms of equal measure $\frac{1}{d}$ for $d < \infty$ and $Y_\infty$ is a Lebesgue space with no atoms, (see Section \[ss2.2\] below). According to we introduce the [**minimal index**]{} $d(T)$ of $T \in {\mathcal {UE}(\rho)}$ as the minimal possible $d$ in the above skew product representation of $T$. The index $d(T)$ is an invariant of the endomorphism $T$ and $d(T) = 1$ iff $T$ is isomorphic to the Bernoulli shift $T_\rho$.

Other important invariants of $T \in {\mathcal {UE}(\rho)}$ (introduced also in ) are the [**partitions**]{} ${\boldsymbol{\gamma}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$, ${\boldsymbol{\beta}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$ and the [**index**]{} ${\mathbf{d}}_{{\boldsymbol{\gamma}}{ : }{\boldsymbol{\beta}}}
{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$. The partition ${\gamma}(T)$ is the smallest (i.e. having the most coarse elements) measurable partition of $X$ such that almost all elements of the partition $\; {\beta}_n := {\gamma}(T) \vee
T^{-n} {\varepsilon}\;$ have homogeneous conditional measures for all $n$. The corresponding tail partition is defined by $\; {\beta}(T) =
\bigwedge_{n=1}^{\infty} {\beta}_n  \geq {\gamma}(T) \;$. and the index $d_{{\gamma}{ : }{\beta}}(T) $ is the number of elements of ${\beta}(T)$ in typical elements of the partition ${\gamma}(T)$ (Proposition \[gga:gb\]).

It was proved in that $\; d(T) = d_{{\gamma}{ : }{\beta}}
(T) < \infty \;$ for any $\rho$-uniform one-sided Markov shift $T
= T_G$. This result implies, in particular, that $T_G$ is [**simple**]{} in the sence of Definition \[def SUE\]. The classification of general simple $\rho$-uniform endomorphisms is reduced to a description of equivalent $d$-extensions of the Bernoulli shift $T_\rho$ (Theorem \[simple\]).

Next we turn to $\rho$-uniform one-sided Markov shifts.

It is easy to see that a Markov shift $T_G$ is $\rho$-uniform iff the graph $G$ satisfies the following condition: For any vertex $u$ the set $G_u$ of all edges starting in $u$, equipped with the corresponding weights $\; p(g) \;,\; g \in G_u \;$, is isomorphic to $(I,\rho)$. This means that the transition probabilities of the Markov chain (starting from any fixed state) coincide with $\;
\rho(i) \;,\; i \in I \;$, up to a permutation. We call these graphs and Markov chains ${\boldsymbol{\rho}}$[**-uniform.**]{} In particular, $(I,\rho)$ itself is considered as a $\rho$-uniform graph having a single vertex. The corresponding Markov shift is the Bernoulli shift $T_\rho$.

Following [@AsMaTu] we use in the sequel graph homomorphisms of the form $\; \phi { : }G_1 {\rightarrow}G_2 \;$, which are assumed to be [**weight preserving**]{} and [**deterministic**]{}, i.e. right resolving in the terminology of [@AsMaTu], (see Definition \[hom\] for details). Thus a stochastic graph $G$ is $\rho$-uniform iff there exists a homomorphisms $\; \phi { : }G {\rightarrow}I \;$.

Two particular kinds of homomorphisms are of special interest in our explanation, they are homomorphisms of [**degree 1**]{} and [**d-extensions**]{}. A homomorphism $\; \phi { : }G_1 {\rightarrow}G_2 \;$ has degree $1$, $\; d(\phi) = 1\;$, if the corresponding factor map $\; \Phi_\phi { : }X_{G_1} {\rightarrow}X_{G_2} \;$ is an isomorphism. So that $\; \Phi_\phi \circ T_{G_1} \;=\; T_{G_2}
\circ \Phi_\phi \;$, i.e. $T_{G_1}$ and $T_{G_2}$ are isomorphic.

The d-extensions homomorphism are defined in Section \[ss3.2\] by the condition: $\; |\phi^{-1}g| = d \;,\; g \in G \;$. They can be described (up to equivalence) by the [**graph skew products**]{}, (see Example \[GSP\] and Definition \[def GSP\] in Section \[ss3.2\]).

As the first step to the construction of the canonical graph we show (Theorem \[phi bar\]) that any homomorphism $\; \phi { : }G {\rightarrow}I \;$ can be extended to a $d$-extension ${{\bar \phi}}$ by homomorphisms of degree $1$ (See Diagram \[diag phi bar\]). To this end we consider a ${\mathbf{d}}$[**-contractive**]{} semigroup ${{\mathcal S}}(\phi)$, associated with the homomorphism $\phi$, and the corresponding [**persistent**]{} sets (Section \[ss4.4\]). Thus we reduce the classification problem to the study of diagrams of the form $$\label{pipsi}
(\pi,\psi) \;{ : }\;
\xymatrix{ {{\bar H}}\ar[r]^{\pi} & H \ar[r]^{\psi} & I}$$ where ${{\bar H}}$ is a $d$-extension, $\psi$ is a degree $1$ homomorphism and the shift $T_{{\bar H}}$ is isomorphic to the shift $T_G$.

The second step is to minimize $d$ in the above Diagram \[pipsi\]. We show (Theorem \[phi bar d(T)\]) that, passing possibally to a “$n$-stringing” graph $G{^{(n)}}$, one can choose the minimal $ d = d(T)$. Note that the result is based on .

The third final step is to reduce the homomorphism $\psi$ in Diagram \[pipsi\] as much as possible. Let ${{\mathcal Ext}^d(I,\rho)}$ denotes the set of all $d$-extensions of the Bernoulli graph $(I,\rho)$ of the form (\[pipsi\]). We show that ${{\mathcal Ext}^d(I,\rho)}$ can be equipped with a natural [**partial order**]{} “$\preceq$” and [**equivalence relation**]{} “$\sim$” (Definition \[partial order\]). The minimal elements of ${{\mathcal Ext}^d(I,\rho)}$ with respect to the order are called [**irreducible**]{} (Definition \[irreduc\]). We describe these irreducible $(\pi,\psi)$-extensions by means of the persistent $d$-partitions, associated with elements of ${{\mathcal Ext}^d(I,\rho)}$ (Theorem \[reduc part\]).

Now we can formulate the main result of the paper (Theorems \[canon form\] and \[classification\]).

-   [*Let $T_G$ be a $\rho$-uniform ergodic one-sided Markov shift. A stochastic graph ${{\bar H}}= {{\bar H}}(G)$ is said to be a canonical graph for the shift $T$ if there exists an irreducible $(\pi,\psi)$-extension (\[pipsi\]) from ${{\mathcal Ext}^d(I,\rho)}$ with $\; d = d(T) \;$ such that the shift $T_{{\bar H}}$ is isomorphic to $T_G$.*]{}

-   [*Any $\rho$-uniform ergodic one-sided Markov shift can be represented in the canonical form $T = T_{{\bar H}}$ by a canonic graph ${{\bar H}}= {{\bar H}}(G)$.*]{}

-   [*In this canonical form, two shifts $T_{{{\bar H}}_!}$ and $T_{{{\bar H}}_2}$ are isomorphic iff the canonical graphs ${{\bar H}}_1$ and ${{\bar H}}_1$ are isomorphic, and iff the corresponding irreducible $(\pi,\psi)$-extensions are equivalent.*]{}

The paper is organized as follows.

In Section \[s2\] we study general $\rho$-uniform endomorphisms (class ${\mathcal {UE}(\rho)}$) and [**simple**]{} $\rho$-uniform endomorphisms (subclass ${\mathcal {SUE}(\rho)}$). Following , we introduce the [**partitions**]{} ${\boldsymbol{\gamma}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$, ${\boldsymbol{\beta}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$ and the [**index**]{} ${\mathbf{d}}_{{\boldsymbol{\gamma}}{ : }{\boldsymbol{\beta}}} {{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$. Two main conclusions of the section are Theorem \[simple\] (classification of simple $\rho$-uniform endomorphisms) and Theorem \[simp mar\], which states that every ergodic $\rho$-uniform one-sided Markov shift $T_G$ is simple and $\;
d(T_G) \;=\; d_{{\gamma}{ : }{\beta}}(T_G) \;<\; \infty  \;$.

In Section \[s3\] we consider general properties of stochastic graphs and their homomorphisms. In particular, we define ${\boldsymbol{\rho}}$[**-uniform** ]{} graphs corresponding to $\rho$-uniform Markov shifts. We prove that the index $d(T_G)$ of any ergodic $\rho$-uniform Markov shift $T_G$ is finite (Theorem \[zet del\]). This follows from the finiteness of the degree $d(\phi)$ of any homomorphism $\phi { : }G {\rightarrow}I$ from any $\rho$-uniform graph $G$ onto the standard Bernoulli graph $(I,\rho)$. The degree $d(\phi)$, in turn, can be computed by means a special [**d-contractive**]{} semigroup ${{\mathcal S}}(\phi)$, induced by $\phi$ (Theorem \[d(phi)\]).

Section \[s4\] contains some essential stages of the proof of Main Theorems \[canon form\] and \[classification\]. Homomorphisms of degree $1$ and extensions of the Bernoulli graph are considered in Sections \[ss4.1\] and \[ss4.2\]. Theorem \[Equ ext\] (Section \[ss4.3\]) reduces the classification of skew product over Markov shifts $T_H$ to the classification of the corresponding graph skew product over $H$. In Sections \[ss4.4\] and \[ss4.5\], we study the set ${{\mathcal Ext}^d(I,\rho)}$ of all $(\pi,\psi)$-pairs of the form (\[pipsi\]). The main result of Section \[s4\] is Theorem \[reduc ext\], which claims the existence and uniqueness of the irreducible $(\pi,\psi)$-pair $(\pi_*,\psi_*)$, majorized by a given $(\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$.

In Section \[s5\] we prove Main Theorems \[canon form\] and \[classification\] and give some consequences and examples. As a consequence we prove also (Theorem \[common exten 1\]) that two shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic iff the graphs $G_1$ and $G_2$ have a common extension of degree $1$.

We do not study here the classification problem for general, not necessarily $\rho$-uniform, one-sided Markov shifts as well as the classification problem of the cofiltrations, generated by the shifts. Our approach seems to be a good tool to this end and we hope to deal with these two problems in another paper.

We do not also consider the classification problem of one-sided Markov shifts with infinite invariant measure, in particular, of null-recurrent one-sided Markov shifts. One can find a good introduction to the topic and more references in [@Aar Chapters 4 and 5].

 Class of $\rho$-uniform endomorphisms  {#s2}
=======================================

 Lebesgue spaces and their measurable partitions  {#ss2.1}
-------------------------------------------------

We use terminology and results of the Rokhlin’s theory of Lebesgue spaces and their measurable partitions (See , ). An improved and more detailed explanation can be found in [@ViRuFed]. We fix the terms “homomorphism , isomorphism, endomorphism” only for [**measure preserving**]{} maps of Lebesgue spaces.

Let $(X, {{\mathcal F}}, m)$ be a Lebesgue space with $ mX=1$. The space $X$ is called [**homogeneous** ]{} if it is non-atomic or if it consists of $d$ points of measure $\; \frac{1}{d} \;,\; d
\in {{\mathbb{N}}}\;$.

Let $ {\zeta}$ be a partition of $X$ onto mutually disjoint sets $ C
\in {\zeta}$. The element of $ {\zeta}$ containing a point $ x $ is denoted by $ C_{\zeta}(x) $. The partition $ {\zeta}$ is measurable iff there exists a measurable function $ f { : }X {\rightarrow}{{\mathbb{R}}}$ such that $$x \stackrel{{\zeta}}{\sim} y \Longleftrightarrow
 C_{\zeta}(x) = C_{\zeta}(y) \Longleftrightarrow  f(x)=f(y) \;,\; x,y \in X$$ Elements of $ {\zeta}$ are considered as Lebesgue spaces $\; (C, {{\mathcal F}}^C , m^C) \;,\; C \in {\zeta}\;$, with canonical system of conditional measures $\; m^C \;,\;C \in {\zeta}\;$. We shall denote also by $ m(A|C)$ the conditional measures $\; m^C(A \cap C) \;$ of a measurable set $ A \in {{\mathcal F}}$ in the element $ C$ of $ {\zeta}$.

Two measurable partitions ${\zeta}_1$ and ${\zeta}_2$ are said to be [**independent** ]{} (${\zeta}_1 \perp {\zeta}_2 $) if the corresponding ${\sigma}$-algebras $ {{\mathcal F}}({\zeta}_1) $ and $ {{\mathcal F}}({\zeta}_2)$ are independent , where ${{\mathcal F}}({\zeta})$ denotes the $m$-completion of the ${\sigma}$-algebra of all measurable ${\zeta}$-sets. We shall write also $\; {\zeta}_1 \perp {\zeta}_2 \pmod {\zeta}\;$ if the partitions ${\zeta}_1$ and $ {\zeta}_2 $ are [**conditionally independent**]{} with respect to the third measurable partition ${\zeta}$. This means that $$m(A \cap B \;|\; C_{\zeta}(x)) =
 m(A|C_{\zeta}(x)) \cdot m(B \;|\; C_{\zeta}(x))$$ for all $ A \in {{\mathcal F}}({\zeta}_1), B \in {{\mathcal F}}({\zeta}_2) $ and a.a. $ x \in X $.

We denote by $ {\varepsilon}= {\varepsilon}_X $ the partition of $X$ onto separate points and by $\nu = \nu_X$ the trivial partition of $X$.

An [**independent complement**]{} of ${\delta}$ is a measurable partition $ \eta $ such that $\; {\zeta}\perp \eta \;$ and $\; {\zeta}\vee \eta =
{\varepsilon}\;$. The partition ${\zeta}$ admits an independent complement iff almost all elements $ (C,m^C) $ of ${\zeta}$ are mutually isomorphic. The collection of all independent complements of ${\zeta}$ is denoted by $IC({\zeta})$.

We shall use induced endomorphisms, which are defined as follows. Let $ A \in {{\mathcal F}}$ , $ mA > 0$ and $T$ be an endomorphism of $(X,m)$. Then the return function $$\label{ret fun}
  {\varphi}_A(x) := min \{ n \geq 1 { : }T^{n}x \in A \}
  \;\;,\;\; x \in A$$ is finite a.e. on $A$. The [**induced endomorphism**]{} $T_A$ on $A$ is defined now by $\; T_Ax = T^{{\varphi}_A(x)}x \;$. It is an endomorphism of $ (A,{{\mathcal F}}\cap A, m{|}_A) $ and it is ergodic if $T$ is ergodic .

$|E|$ denotes the cardinality of the set $E$

Classes ${\mathcal UE} {\boldsymbol{(}}{\boldsymbol{\rho}}{\boldsymbol{)}}$ and index ${\mathbf{d}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$. {#ss2.2}
---------------------------------------------------------------------------------------------------------------------------------------------------

Let $(I,\rho)$ be a finite or countable state space $$\rho = \{ \rho(i) \;,\; i \in I \} \;,\;\; \rho (i) > 0
  \;\;,\;\; \sum_{i \in I}{\rho(i)} = 1 .$$

\[def rho Bern\] An endomorphism $T$ of a Lebesgue space $(X,m)$ is said to be ${\boldsymbol{\rho}}$[**-unform**]{} or [**finitely**]{} ${\boldsymbol{\rho}}$[**-Bernoulli**]{} endomorphism $\; (T \in {\mathcal {UE}(\rho)}\;$, if there exists a discrete measurable partition ${\delta}$ of $X$, which satisfies the following condition:

1.  $\; distr \; {\delta}= \rho \;$, i.e. $\; {\delta}= \{ B(i) \}_{i \in I}$ with $\;\;m(B(i)) = \rho (i), \;\; i \in I $,

2.  $\; {\delta}\in IC (T^{-1} {\varepsilon}) $ , i.e.    ${\delta}\perp T^{-1} {\varepsilon}\;$ and $\; {\delta}\vee T^{-1}{\varepsilon}= {\varepsilon}$.

So $ {\mathcal {UE}(\rho)}$ denotes the class of all $\rho$-unform endomorphisms. Denote by ${\Delta}_{\rho}(T)$ the set of all partitions ${\delta}$ satisfying the condition $(i)$ and $(ii)$. Then $T \in {\mathcal {UE}(\rho)}$ means ${\Delta}_\rho(T) \neq\emptyset $.

For $T \in {\mathcal {UE}(\rho)}$ and ${\delta}\in {\Delta}_{\rho}(T)$ define $$\label{delta n}
     {\delta}{^{(n)}}= T^{-n+1} {\delta}\;\;,\;\;\;
     {\delta}{^{(n)}}= \{ T^{-n+1}B(i) \}_{i \in I }  \;\;,\;\;   n \in {{\mathbb{N}}}$$ Then $\; distr \;{\delta}_n = \rho \;$ and the partitions $ \; {\delta}_1 \;,\; {\delta}_2 \;,\;{\delta}_3 \;,\; \ldots \; $ are independent.

The partitions $$\label{delta (n)}
  {\delta}{^{(n)}}= \bigvee_{k=1}^{n} {\delta}_{k} \;\;,\;\;\;
  {\delta}^{(\infty)} = \bigvee_{k=1}^{\infty} {\delta}_k$$ satisfy for all $n$ the conditions $${\delta}{^{(n)}}\in IC(T^{-n} {\varepsilon}) \;\;,\;\;
 {\delta}{^{(\infty)}}\perp T^{-n} {\varepsilon}\pmod { {\delta}{^{(\infty)}}\wedge T^{-n} {\varepsilon}}$$ and $${\delta}{^{(\infty)}}\vee T^{-n} {\varepsilon}= {\varepsilon}\;\;,\;\;
  {\delta}{^{(\infty)}}\wedge T^{-n} {\varepsilon}\;=\; T^{-n} {\delta}{^{(\infty)}}\;.$$ In particular, let $ T=T_\rho$ be a Bernoulli endomorphism, which acts on the space $$(X_\rho, m_\rho) = \prod_{n=1}^{\infty} (I,\rho)$$ as the one-sided shift $$T_{\rho} x = \{ x_{n+1}\}_{n=1}^{\infty} \;\; , \;\;\;
  x = \{ x_n \}_{n=1}^{\infty} \in X_\rho \;\;.$$ We can set $$\label{delta rho}
  {\delta}_\rho = \{ B_\rho(i) \}_{i \in I} \;\;,\;\; B_\rho(i) =
  \{ x = \{ x_{n}\}_{n=1}^{\infty} \in X_{\rho}
  \;\; { : }\;\; x_1=i \} \;.$$ Then $\; {\delta}_\rho \in {\Delta}_\rho (T_\rho )$ and ${\delta}_{\rho}$ is an one-sided Bernoulli generator of $T_\rho$, that is $${\delta}_{\rho}^{(\infty)} = \bigvee_{n=1}^{\infty} T^{-n+1}{\delta}_{\rho}
  = {\varepsilon}_{X_{\rho}} \;.$$

In general case, for $T \in {\mathcal {UE}(\rho)}$ and ${\delta}\in {\Delta}_\rho(T)$, the partition ${\delta}^{(\infty)}$ does not equal ${\varepsilon}$, but we can define the canonical factor map $$\Phi_{{\delta}} { : }X \ni x {\rightarrow}\Phi_{{\delta}} (x) = \{i_{n} (x) \}_{n=1}^{\infty} \in X_{\rho} \;,$$ where $i_{n}(x) \in I$ is uniquely defined by the inclusion $ T^{n}x \in B(i_{n}(x)) \in {\delta}$.

The homomorphism $\Phi_{{\delta}}$ satisfies $\; \Phi_{{\delta}} \circ T = T_{\rho} \circ \Phi_{{\delta}} \;$ and it determines the following representation of $T$ by a skew product over $ T_{\rho} $ (See ).

\[T decompos\] Let $T \in {\mathcal {UE}(\rho)}$ be an endomorphism of $(X,m)$ and ${\delta}\in {\Delta}_\rho(T)$. Then

1.  There exists an independent complement ${\sigma}$ of the partition ${\delta}{^{(\infty)}}$.

2.  The pair $\; ({\delta}{^{(\infty)}}, {\sigma}) \;$ induces decomposition of the space $(X,m)$ into the direct product $\; (X_\rho \times Y \;,\; m_{X_\rho} \times m_{Y})$ such that the factor map $\Phi_{\delta}$ coincides under the decomposition with the canonical projection $$\pi \; { : }\; X_\rho \times Y \ni (x,y) {\rightarrow}x \in X_\rho$$ and $${\delta}= \pi^{-1} {\delta}_{\rho}
        \;\;, \;\; {\delta}{^{(\infty)}}= \pi^{-1} {\varepsilon}_{X_\rho}
        = {\varepsilon}_{X_\rho} \times \nu_Y
        \;\;,\;\; {\sigma}= \nu_{X_\rho} \times {\varepsilon}_Y$$

3.  The endomorphism $T$ is identified with the following skew product over $ T_\rho $ $$\label{skew1}
        {{\bar T}}(x,y) = ( T_\rho x , A(x) y)
        \;\;,\;\; (x,y) \in X_{\rho} \times Y$$ where $\; \{ A(x), x \in X_\rho \} \;$ is a measurable family of automorphisms of $Y$.

4.  If $T$ is ergodic, $Y$ is a homogeneous Lebesgue space.

Every homogeneous Lebesgue space $Y$ is isomorphic to $\; Y_d
\;.\;d \in {{\mathbb{N}}}\cup \{\infty\} \;$, where $\; Y_{\infty} \;$ is the Lebesgue space with a continuous measure and $\; Y_d \;$,$\;d \in
{{\mathbb{N}}}\;$, consists of $d$ points of measure $\frac{1}{d}$. Thus for any ergodic $T$ endomorphism $\; T \in {\mathcal {UE}(\rho)}\;$ and $\; {\delta}\in
{\Delta}_{\rho} (T) \;$ there exists $\; d = d(T,{\delta}) \in {{\mathbb{N}}}\cup
\{\infty\} \;$ such that $$u_{{\delta}^{(\infty)}}(x)
 := m^{C_{{\delta}^{(\infty)}} (x)}(\{x\}) = \frac{1}{d}$$ for a.a. $x \in X $.

\[def d(T)\]

1.  The number $\; d(T,{\delta}) \;$ will be called the [**index**]{} of $T \in {\mathcal {UE}(\rho)}$ with respect to $\; {\delta}\in {\Delta}_{\rho}(T) \;$.

2.  The [**minimal index**]{} $d(T)$ of $T$ is defined as $$\label{d(T)}
        d(T) \;=\; min \; \{\; d(T,{\delta}) \;,\; {\delta}\in {\Delta}_{\rho} (T)\}$$

Note that an ergodic endomorphism $T$ is isomorphic to the Bernoulli shift $T_\rho$ iff $T \in {\mathcal {UE}(\rho)}$, and $d(T) = 1$, that is, there exists ${\delta}\in {\Delta}_\rho(T)$ such that $d(T,{\delta}) = 1$, i.e. ${\delta}{^{(\infty)}}= {\varepsilon}$.

Partitions ${\boldsymbol{\alpha}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$, ${\boldsymbol{\beta}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$, ${\boldsymbol{\gamma}}{{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$ and indices ${\mathbf{d}}_{{\boldsymbol{\alpha}}} {{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$, ${\mathbf{d}}_{{\boldsymbol{\gamma}}{ : }{\boldsymbol{\beta}}} {{\boldsymbol{(}}{\mathbf{T}}{\boldsymbol{)}}}$ {#ss2.3}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Let $T$ be an endomorphism of $(X,m)$ and let $ \{ \xi_n
\}_{n=1}^{\infty} $ be the decreasing sequence of measurable partitions $\; \xi_n := T^{-n}{\varepsilon}\;$, generated by $T$. The element of $\xi_n$ , containing a point $x \in X$, has the form $\; C_{\xi_n}(x) = T^{-n}(T^n x) \;$,

In order to introduce the partitions ${\gamma}(T)$ and ${\beta}(T)$, consider the measurable functions $$u_n(x) = m^{C_{\xi_n}(x)} (C_{\xi_{n-1}}(x)) \;\;\;,
\; n \in {{\mathbb{N}}}\;\;\; , \; x \in X  \;,$$ where $\xi_0 := {\varepsilon}$. With these $\; u_n { : }X {\rightarrow}[0,1]
\;$ we can consider the measurable partitions $${\gamma}_n = \bigvee_{k=1}^{n}u_{k}^{-1} {\varepsilon}_{[0,1]}
  \;\; ,\;\; n \in {{\mathbb{N}}}\;,$$ generated by $\;u_k\;,\; k \leq n \;$, and also $$\label{gga gbn gb}
 {\gamma}= \bigvee_{n=1}^{\infty} {\gamma}_n \;\;,\;\;
 {\beta}_n = {\gamma}\vee T^{-n}{\varepsilon}\;\;,\;\;
 {\beta}= \bigwedge_{n=1}^{\infty} {\beta}_n$$ We shall write $\; {\gamma}_n(T) \;,\; {\gamma}(T)\;,\; {\beta}_n(T)\;,\;
{\beta}(T) \;$ to indicate $T$, if it will be necessary.

\[gga:gb\] Suppose that $T\in {\mathcal {UE}(\rho)}$ and T is ergodic. Then there exists $d \in {{\mathbb{N}}}\cup \{\infty\}$ such that $$m^{C_{{\gamma}}(x)}(C_{{\beta}}(x))=\frac{1}{d}$$ for a.a. $x\in X$.

We may define now the index $\; d_{{\gamma}{ : }{\beta}}(T) \;$ of an ergodic endomorphism $T \in {\mathcal {UE}(\rho)}$ as the number $d$ constructed in Proposition \[gga:gb\], i.e. $$d_{{\gamma}{ : }{\beta}}(T) := (m^{C_{\gamma}(x)}(C_{\beta}(x)))^{-1}$$ for a.e. $x \in X$.

We shall use the following properties of the partitions (\[gga gbn gb\])

\[gga gd d(T)\] Suppose that $\; T \in {\mathcal {UE}(\rho)}\;$, let $\; {\delta}\in {\Delta}_\rho(T) \;$ and the partitions $\; {\delta}_n \;,\; {\delta}{^{(n)}}\;,\; {\delta}{^{(\infty)}}\;$ defined by (\[delta n\]) and (\[delta (n)\]). Then

1.  $\; {\gamma}{^{(n)}}\le {\delta}_n
       \;\;,\;\; {\beta}_n  \perp {\delta}{^{(n)}}\pmod {{\gamma}_n}
       \;\;,\;\; n \in {{\mathbb{N}}}\;.$

2.  ${\gamma}\le {\delta}{^{(\infty)}}\;\;,\;\; {\beta}\perp {\delta}{^{(\infty)}}\pmod {{\gamma}} \;.$

3.  $\; d_{{\gamma}{ : }{\beta}}(T) \; \leq \; d(T) \;$

We shall also use the [**tail**]{} measurable partition $\; {\alpha}(T) := \bigwedge_{n=1}^{\infty} T^{-n} {\varepsilon}\;$. An endomorphism $T$ is called [**exact**]{} if ${\alpha}(T) = \nu$. The [**tail index**]{} $d_{\alpha}(T)$ (which is, in fact, the [**period** ]{} of $T$) is defined as follows: $d_{\alpha}(T)= \infty$ if $
X{/}_{{\alpha}(T)}$ is a continuous Lebesgue space and $d_{{\alpha}}(T) = d$ if $ X {/}_{{\alpha}((T)}$ consists of $d$ atoms of measure $\frac{1}{d}$. So that $d_{\alpha}(T) \in {{\mathbb{N}}}\cup \{\infty\}$.

It is easily to see, that $$\label{ga gb gga}
  T^{-1} {\alpha}= {\alpha}\;\;,\;\;  {\alpha}\vee {\gamma}\le {\beta}\;\;,\;\;
  T^{-1} {\gamma}\le {\gamma}\;\;,\;\;  T^{-1} {\beta}\le {\beta}$$ and $\; {\alpha}\perp {\delta}{^{(\infty)}}\;$ for any $ {\delta}\in {\Delta}_{\rho}(T) $.

Turning to the canonical projection $\Phi_{\delta}$ we have

\[ga(T rho)\]

1.  $ {\alpha}(T_\rho) = \nu
      \;\;,\;\; {\beta}(T_\rho) = {\gamma}(T_{\rho}) \;$.

2.  $ {\gamma}_n(T)   = \Phi_{{\delta}}^{-1}{\gamma}_n(T_\rho)
       \;\;,\;\; {\gamma}(T)   = \Phi_{{\delta}}^{-1}{\gamma}(T_\rho) \;$.

The stated above propositions were proved in .

Simple ${\boldsymbol{\rho}}$-uniform endomorphisms {#ss2.4}
--------------------------------------------------

We use now the partitions ${\gamma}(T)$ and $ {\beta}(T)$ to introduce an important subclass of the class ${\mathcal {UE}(\rho)}$

\[def SUE\] An endomorphism $T \in {\mathcal {UE}(\rho)}$ of a Lebesgue space $(X,m)$ is said to be a [**simple**]{} $\rho$-uniform endomorphism $(T \in {\mathcal {SUE}(\rho)})$, if there exists partition ${\delta}\in {\Delta}_\rho(T)= IC (T^{-1} {\varepsilon})$ such that $$\label{SUE1}
  {\delta}^{(\infty)} \vee {\beta}(T)= {\varepsilon}$$

We denote by ${\mathcal {SUE}(\rho)}$ the class of all simple $\rho$-uniform endomorphisms.

The Bernoulli endomorphism (one-sided Bernoulli shift) $T=T_{\rho}$ belongs to ${\mathcal {SUE}(\rho)}$. In this case there exists a partition $ {\delta}= {\delta}_{\rho} \in {\Delta}_{\rho}(T)$ such that $
{\delta}{^{(\infty)}}= {\varepsilon}$ and hence $ {\beta}(T) \vee {\delta}{^{(\infty)}}= {\varepsilon}$

\[rem SUE\] It is easily to show that the condition (\[SUE1\]) holds iff there exists an independent complement ${\sigma}\in IC({\delta}^{(\infty)}) $ of ${\delta}^{(\infty)}$ that satisfies $$\label{SUE2}
   {\sigma}\vee {\gamma}(T) = {\beta}(T)    \;\;,\;\;
   {\sigma}\in IC ({\delta}^{(\infty)})  \;\;,\;\;
   {\delta}\in {\Delta}_\rho(T)= IC (T^{-1} {\varepsilon})$$

\[simple1\] Suppose $\;T \in {\mathcal {UE}(\rho)}\;$ is ergodic and $\; d(T) < \infty \;$. Then $T$ is simple iff $\; d(T) = d_{{\gamma}{ : }{\beta}}(T) \;$.

Since $\; d(T) < \infty \;$ we have, by Proposition \[gga gd d(T)\] (iii), that $\; d_{{\gamma}{ : }{\beta}}(T) \leq d(T)
< \infty \;$. Definition of the index $d_{{\gamma}{ : }{\beta}}(T)$ (Proposition \[gga:gb\]) means that $\; m^{C_{\gamma}(x)}(C_{\beta}(x)) = d^{-1} \;$ for a.a. $x \in X$ and $\; d = d_{{\gamma}{ : }{\beta}}(T) \in {{\mathbb{N}}}\;$. Almost every element of ${\gamma}(T)$ consists precisely of $d$ elements of the partition ${\beta}(T)$. On the other hand there exists ${\delta}\in {\Delta}_\rho(T)$ such that almost every element of the corresponding partition ${\delta}{^{(\infty)}}$ consists precisely of $d(T)$ points, $d \leq d(T)$. By Proposition \[gga gd d(T)\] (ii) we have $${\beta}(T) \perp {\delta}{^{(\infty)}}\pmod {{\gamma}(T)} \;\;,\;\;
 {\beta}(T) \wedge {\delta}{^{(\infty)}}= {\gamma}(T) \;.$$ Whence, the condition \[SUE1\] holds iff $\; d(T) = d \;$.

Let $\; T \in {\mathcal {SUE}(\rho)}\;$. By Proposition \[T decompos\] any choice of the partition ${\sigma}$ in the equality (\[SUE2\]) determines a skew product representation (\[skew1\]) of $T={{\bar T}}$ over $T_\rho$. Herewith, all statements of Proposition \[T decompos\] hold and we have also by (\[SUE2\]) and Proposition \[ga(T rho)\]) $$\label{SUE3}
 {\beta}(T_\rho)={\gamma}(T_\rho)
 \;\;,\;\; {\gamma}({{\bar T}}) = {\gamma}(T_\rho) \times \nu_Y
 \;\;,\;\; {\beta}({{\bar T}}) = {\gamma}(T_\rho) \times {\varepsilon}_Y$$ These arguments imply the following

\[simple\] Let $T$ be a $\rho$-uniform simple endomorphism, $\; T \in {\mathcal {SUE}(\rho)}\;$.

1.  $T$ can be represented in the skew product form (\[skew1\]) $T={{\bar T}}$ over $T_\rho$ $$\label{Tbar}
        {{\bar T}}(x,y) = ( T_\rho x , A(x) y)
        \;\;,\;\; (x,y) \in X_{\rho} \times Y$$ with a measurable family $\; \{ A(x) \;,\; x \in X_\rho \} \;$ of automorphisms of $Y$ such that $\; {\beta}({{\bar T}}) = {\gamma}(T_\rho) \times {\varepsilon}_Y \;$.

2.  Two such skew product endomorphisms ${{\bar T}}_k$, $k=1,2,$ $$\label{Tbar 1,2}
        {{\bar T}}_k (x,y) = ( T_\rho x , A_k(x) y)
        \;\;,\;\; (x,y) \in X_{\rho} \times Y$$ are isomorphic iff the corresponding families $\; A_1(x) \;$ and $\; A_2(x) \;$ are cohomologous, i.e. $$\label{A2W=WA1}
         A_2(x) W(x) = W(T_\rho x) A_1(x) \;\;,\;\; x \in X_\rho$$ for a measurable family of $\; \{ W(x) \;,\; x \in X_\rho \} \;$ of automorphisms of $Y$.

Part (i) follows from Proposition \[T decompos\] with (\[SUE3\]).

Let ${{\bar T}}_1$ and ${{\bar T}}_2$ be two skew product endomorphisms of the form (\[Tbar 1,2\]). Denote $\; {{\tilde{W}}}(x,y):=(x,W(x)y) \;$. Then (\[A2W=WA1\]) implies $ {{\bar T}}_2 \circ S = S \circ {{\bar T}}_1 $ if we use the automorphism $S = {{\tilde{W}}}$.

Conversely, suppose there exists an automorphism $S$ such that $ {{\bar T}}_2 \circ S = S \circ {{\bar T}}_1 $. Then the partitrions $${{\bar {\gamma}}}:= {\gamma}({{\bar T}}_1) = {\gamma}({{\bar T}}_2) = {\gamma}(T_\rho) \times \nu_Y$$ and $${{\bar {\beta}}}:= {\beta}({{\bar T}}_1) = {\beta}({{\bar T}}_2) = {\gamma}(T_\rho) \times {\varepsilon}_Y$$ are invariant with respect to $S$. Moreover, ${{\bar {\gamma}}}$ is element-wise invariant with respect to $S$. Hence, $S {|}_C
({{\bar {\beta}}}{|}_C) = {{\bar {\beta}}}{|}_C $ for almost every element $C \in {{\bar {\gamma}}}$. The restriction $S{|}_C$ induces a factor automorphism $W_C$ on the factor space $ C{/}_{{{\bar {\beta}}}{|}_C} \cong Y $. We obtain a measurable family $\; W(x) := W_{C(x)} \;,\; x \in
X_\rho  \;$, of automorphisms of $Y$. Since the partition $\;
{{\bar {\gamma}}}= {\gamma}(T_\rho) \times \nu_Y \;$ is ${{\bar T}}_1)$- and ${{\bar T}}_2$-invariant, the functions $ A_1(x) $ and $ A_2(x) $ (as well as $W(x)$) are constant on elements of ${\gamma}(T_\rho)$. Therefore the equality $ {{\bar T}}_2 \circ S = S \circ {{\bar T}}_1 $ implies $
{{\bar T}}_2 \circ {{\tilde{W}}} = {{\tilde{W}}} \circ {{\bar T}}_1 $ and (\[A2W=WA1\]) holds.

Consider two special cases.

[**Absolutely non-homogeneous ${\boldsymbol{\rho}}$.**]{} The distribution $\; \rho = \{\rho(i) \}_{i \in I} \;$ is called absolutely non-homogeneous if $\; \rho(i) \neq \rho(j) \;$ for all $\;i \neq j\;$.

In this case we have $\; {\gamma}_1(T) \vee T^{-1}{\varepsilon}= {\varepsilon}\;$. On the other hand $\; {\gamma}_1(T) \perp T^{-1}{\varepsilon}\;$. Thus $\; {\Delta}_\rho(T) \;$ consists of the only partition, which is $\; {\delta}= {\gamma}_1(T) \;$. Hence $${\delta}{^{(\infty)}}= {\gamma}(T) \;\;,\;\;
  {\beta}_n(T) = {\gamma}_n(T) \vee T^{-n}{\varepsilon}= {\varepsilon}\;,$$ $${\beta}(T) = \bigwedge_{n=1}^{\infty} {\beta}_n(T) = {\varepsilon}\;\;,\;\;
  {\beta}(T) \vee {\delta}{^{(\infty)}}= {\varepsilon}$$ Thus we have

Every $\rho$-uniform endomorphisms with absolutely non-homogeneous $\;\rho \;$ is simple.

[**Homogeneous ${\boldsymbol{\rho}}$.**]{} We have another extremal case if $\;\rho \;$ is homogeneous, i.e. if for some $\; l \in {{\mathbb{N}}}\;$,$\; I = \{1,2, \ldots ,l\;\} \;$ and $\; \rho(i) = l^{-1} \;$ for all $\; i \in I  \;.$

All the functions $ \;u_n \;$, which generate the partitions $\; {\gamma}_n(T) \;$, are constant, $$u_n(x) \;=\; m^{C_{\xi_n }(x)} (C_{\xi_{n-1}}(x))
  \;=\; l^{-1} \;,\; n \in {{\mathbb{N}}}\;,\; x \in X$$ We have $\; {\gamma}(T) = {\gamma}_n(T) = \nu \;,$ and $\; {\beta}_n(T) =
T^{-n}{\varepsilon}\;$, whence, $\; {\beta}(T) = \bigwedge_{n=1}^{\infty}
T^{-n}{\varepsilon}= {\alpha}(T) \;$. Therefore, for any $\;{\delta}\in {\Delta}_{\rho}(T)\;$ the equality (\[SUE1\]) is equivalent to $\; {\delta}{^{(\infty)}}\vee {\alpha}(T) = {\varepsilon}\;$. On the other hand $\; {\delta}{^{(\infty)}}\perp {\alpha}(T) \;$ for every $\;{\delta}\in {\Delta}_{\rho}(T)\;$.

Thus we have for $ T \in {\mathcal {UE}(\rho)}$ with homogeneous $\rho$

Let $ T \in {\mathcal {UE}(\rho)}$ with homogeneous $\rho$. Then

1.  $T$ is simple iff there exists $\;{\delta}\in {\Delta}_{\rho}(T)\;$ such that $ {\delta}{^{(\infty)}}\in IC({\alpha}(T)) $.

2.  The skew product decomposition in Theorem \[simple\] is a direct product $\; T_\rho \times S \;$ with $ S = T {/}_{{\alpha}(T)} $.

3.  Two such direct products $\; T_\rho \times S_1 \;$ and $\; T_\rho \times S_2 \;$ are isomorphic iff the automorphisms $ S_1 $ and $ S_2 $ are isomorphic.

4.  If, in addition, $T$ is exact, i.e. $\;{\alpha}(T) = \nu \;$, then $T$ is simple iff $T$ is isomorphic to $\; T_\rho \;$.

It is easily to construct a skew product $T$ over $T_\rho$, which is exact and has entropy $\; h(T) > h(T_\rho) = \log l \;$. Every such endomorphism is $\rho$-uniform, $\; T \in {\mathcal {UE}(\rho)}\;$, but it is not isomorphic to $T_\rho$, whence, it is not simple. See also [@FeR], [@HeHo], [@HeHoR], [@Ho], [@HoR]), for more interesting examples of such kind of endomorphisms.

It can be shown that there exist non-simple exact endomorphisms in each class $\; {\mathcal {UE}(\rho)}\;$ in the case, when $\rho$ is not absolutely non-homogeneous, i.e. $\; \rho(i) = \rho(j)\;$ for some $\;i,j \in I\;$.

The following result plays an important role in present paper.

\[simp mar\] Every ergodic $\rho$-uniform one-sided Markov shift $T_G$, corresponding to a positively recurrent Markov chain on a finite or countable state space, is simple and $$\label{d=dg:b}
  d(T_G) \;=\; d_{{\gamma}{ : }{\beta}}(T_G) \;<\; \infty  \;.$$

The last statement \[d=dg:b\] was proved in . It implies that $T_G$ is simple by Proposition \[simple1\].

 Stochastic graphs and their homomorphisms.  {#s3}
============================================

Stochastic graphs and Markov shifts {#ss3.1}
-----------------------------------

We need some terminology concerning stochastic graphs and their homomorphisms.

Consider a directed graph with countable (finite or infinite) set $G$ of edges. Denote by $G{^{(0)}}$ the set of all vertices of the graph. We also denote by $s(g)$ the starting vertex and by $t(g)$ the terminal vertex of an edge $g \in G$ $$\xymatrix{   t(g) & s(g) \ar[l]_{g} }$$ The maps $$s \; { : }\; G \ni g \; {\rightarrow}\; s(g) \in G{^{(0)}} \;\; \;,\; \;\;
 t \; { : }\; G \ni g \; {\rightarrow}\; t(g) \in G{^{(0)}}$$ completely determine the structure of the graph $G$,

In the sequel we assume that both the sets $$_vG = \{ g \in G \;{ : }\; t(g) = v \} \;\;\;,\;\;\;
 G_u = \{ g \in G \;{ : }\; s(g)= u \}$$ are not empty for all vertices $ \;u\;,v\;\in G{^{(0)}} $.

Denote by $\; G{^{(n)}}\;$ the set of all paths of length $n$ in $G$ , i.e. $$\label{G(n)}
  G{^{(n)}}= \{ g_1 g_2 \ldots g_n \in G^n \;{ : }\;
  s(g_1)=t(g_2) , \ldots , s(g_{n-1})=t(g_n) \}$$ A graph $G$ is said to be [**irreducible**]{} if for every pair of vertices $ \;u\;,v\;\in G{^{(0)}} $ there exists a finite $G$-path $ \;g_1g_2 \ldots g_n \in G{^{(n)}}\;$ such that $\; u=s(g_n) \;$ and $\; v=t(g_1) \;$.

Take into account that we use here and in the sequel the notation $\; g_1 \; g_2\; \ldots \; g_n \;$ for [**backward**]{} paths $$\xymatrix{
    t(g_1)  &  s(g_1) = t(g_2) \ar[l]_-{g_1}
            &  s(g_2) = t(g_3) \ar[l]_-{g_2}
            &                  \ar[l]_-{g_3}    }
               \;\;\dots\;\;
 \xymatrix{ &  s(g_n)          \ar[l]_-{g_n}    }$$ A graph $G$ is called [**stochastic**]{} if its edges $g$ are equipped with positive numbers $ p(g) $ such that $\; \sum_{g \in
G_u}\;p(g) \;=\; 1 \;$ for all $\; u \; \in G{^{(0)}} \; $. The weights $\; p(g) \;,\; g \in G \;$, determine the backward transition probabilities of the Markov chain induced by $G$.

We shall assume in the sequel that there exist stationary probabilities $ p{^{(0)}}(u) > 0 $ on $ G{^{(0)}}$ such that $$\label{PR}
 \sum_{u \in G{^{(0)}}}\;p{^{(0)}}(u) \;=\; 1 \;\;\;,\;\;\;
 \sum_{g \in _vG} p(g) p{^{(0)}} (s(g)) \;=\; p{^{(0)}} (v)$$ for all vertices $ \;u\;,v\;\in G{^{(0)}} $.

It is known that the stationary probabilities on $G{^{(0)}}$ exist iff the corresponding to $G$ Markov chain is positively recurrent. If, in addition, the irreducibility condition hold, the stationary probabilities $\;p{^{(0)}}(u) \;,\; u \in G{^{(0)}} \;$ on the vertices are uniquely determined by the transition probabilities $\;
p(g)\;,\;g \in G\;$ on the edges.

Thus any stochastic graph $(G,p)$ induces a Markov chain on the state space $G$ with the transition probabilities matrix $\; P
\;=\;{(P(g,h))}_{g\in G , h \in G} \;$, where $$P(g,h) \;=\;
\left\{
 \begin{array}{ll}
  p(h) \;, & if \;\; t(g)=s(h) \; \\
  0  \;\;, & otherwise.
 \end{array}
\right.$$ In the sequel we mainly deal with stochastic graphs, which induce irreducible positively recurrent Markov chains.

The one-sided Markov shift $ T_G $, induced by the stochastic graph $ G $ , is defined as follows. Let $$X_G = \{x={\{g_{n}\}}_{n=1}^{\infty} \in G^{{{\mathbb{N}}}} \;{ : }\;
 s(g_1)=t(g_2)\;,\; s(g_2)=t(g_3) \;,\;  \dots \; \}$$ and the Markov measure $m_G$ on $ X_G $ is given by $$p(g_{1}) \; p(g_{2}) \; \ldots \; p(g_n) \; p{^{(0)}}(s(g_n))$$ on the cylindric sets of the form $$A(g_1\;g_2\; \ldots \;g_n)
 \;:=\; \{x={\{x_k\}}_{k=1}^{\infty} \in X_G
 \;{ : }\; x_1=g_1 \;,\; \ldots \;,\; x_n=g_n \;\}$$ where $\; g_1\;g_2\; \ldots \;g_n) \; \in \; G{^{(n)}}\;$ is a $G$-path of length $n$ in $G$.

The one-sided shift $T_G$ acts on the probability space $\;( X_G , m_G) \; $ by $$T_G({\{x_n\}}_{n=1}^{\infty}\;) \;=\; {\{x_{n+1}\}}_{n=1}^{\infty}$$ and $T_G$ preserves the Markov measure $m_G$. The shift $T_G$ is ergodic iff the graph $G$ is irreducible. Under the irreducibility condition, the stationary probabilities $p{^{(0)}}$ on $G{^{(0)}}$ and, hence, the $T_G$-invariant Markov measure $m_G$ are uniquely determined by the stochastic graph $\; (G,p) \;$.

The coordinate functions $$Z_n \;{ : }\; X_G \ni x={\{x_k\}}_{k=1}^{\infty}\; {\rightarrow}\; x_n
 \in G \;\;,\;\;n \in {{\mathbb{N}}}$$ form a stationary Markov chain on $ ( X_G , m_G) $ with the backward transition probabilities $$P(g,h) \;=\;m_G\{\; Z_n = h \;|\; Z_{n+1} = g \;\} \;=\; p(h)
\;\;,\;\; n \in {{\mathbb{N}}}$$ for all $\; (h,g) \in G^{(2)} \;$.

Consider now the partitions $${\zeta}_n = {Z_n}^{-1}{\varepsilon}_G =
 T_G^{-n+1}{\zeta}_1 = \{ T_G^{-n+1}A(g) \}_{g \in G}
 \;\;,\;\; n \in {{\mathbb{N}}}\;,$$ generated by $Z_n$ on $ X_G$, where $$A(g) \;=\;
 \{\; x={\{x_k\}}_{k=1}^{\infty} \in X_G \;{ : }\; x_1=g \;\}$$ Setting $ {\zeta}= {\zeta}_1 $ and $ T = T_G $, we have $$\label{gen par}
 \bigvee^{\infty}_{n=1}T^{-n+1}{\zeta}= {\varepsilon}$$ $$\label{Mar par}
  {\zeta}\perp  \bigvee^{\infty}_{n=1}T^{-n}{\zeta}\pmod { T^{-1}{\zeta}}$$

Recall that a measurable partition ${\zeta}$ of $(X,m)$ is said to be a [**one-sided Markov generator**]{} or [**one-sided Markov generating partition**]{} for an endomorphism T of $(X,m)$, if the above conditions (\[gen par\]) and (\[Mar par\]) hold.

The partition $ {\zeta}_G $ will be called the [**standard**]{} one-sided Markov generator of the one-sided Markov shift $T_G$ on $ X_G $.

\[Bern graph\] Let $(I,\rho)$ be a finite or countable alphabet and $$\rho = \{ \rho(i) \;,\; i \in I \} \;,\;\; \rho (i) > 0
  \;\;,\;\; \sum_{i \in I}{\rho(i)} = 1 .$$ be a probability on $I$. We shall consider $(I,\rho)$ as a stochastic graph, which has the set of edges $i \in I$ with weights $\; \rho(i) \;$ and a single vertex, denoted by$\;"o"\;$. So $G{^{(0)}} = \{o\}$ is a singleton and $ s(i) = t(i) = o $ for all $i \in I$. We shall say that $(I,\rho)$ is the [**standard Bernoulli graph.**]{}

For instance, $\; \xymatrix{ o \ar@(ul,dl) []_{p} \ar@(dr,ur) []_{q} } \;$ if $\; |I| = 2 \;$ and $\; \rho = (p,q) \;$.

The corresponding to $(I,\rho)$ one-sided Markov shift $T_I$ coincides with the Bernoulli shift $ T_I = T_\rho $. The generating partition $ {\zeta}_I$ coincides with the standard Bernoulli generator $\; {\delta}_\rho = \{ B_\rho(i) \}_{i \in I} \;$, defined by (\[delta rho\]).

[**Induced shift**]{} $\; {\mathbf{T}}_{\mathbf{u}}\;$. For any $\; u \in G{^{(0)}} \;$, denote $$D(u) \;:=\; \{\; x={\{x_k\}}_{k=1}^{\infty} \in
 X_G \;{ : }\; t(x_1)=u \;\} \;\;,\;\; u \in G{^{(0)}} \;.$$ and consider the partition $\; {\zeta}{^{(0)}} := {\{ D(u) \}}_{u \in G{^{(0)}}} \;$ on the space $X_G$. The partition ${\zeta}{^{(0)}}$ is a Markov partition with respect to shift $T_G$ , i.e. $$\label{Mar par 0}
  {\zeta}{^{(0)}}  \perp  T_G^{-1} {\varepsilon}_{X_G} \pmod { T_G^{-1}{\zeta}{^{(0)}} } \;,$$ but it is not a one-sided generator for $T_G$, in general.

We shall use in the sequel the endomorphisms $ T_u := (T_G)_{D(u)} $, induced by the shift $T_G$ on elements $ D(u) $ of ${\zeta}{^{(0)}}$, $\; u \in G{^{(0)}} \;$. The Markov property (\[Mar par 0\]) provides that for every $u \in G{^{(0)}} $ the induced endomorphism $ T_u $ is a Bernoulli shift. More exactly, in accordance with the general definition of return functions (\[ret fun\]) we have $${\varphi}_u(x)={\varphi}_{D(u)}(x) := min \{ n \geq 1 { : }T_G^{n}x \in D(u) \}
 \;\;,\;\; x \in D(u)$$ and $$T_u x \;=\; T_G^{{\varphi}_u(x)} x \;\;,\;\; x \in X_G \;.$$ Take $\; I_u = \bigcup_{n=1}^\infty I_{u,n} \;$, where $I_{u,n}$ be the set of all $ g_1g_2 \ldots g_n \in G{^{(n)}}$ such that $$\label{I u n}
 t(g_1) = s(g_n) = u \;\;,\;\;
 s(g_k) = t(g_{k+1}) \neq u \;,\; k = 1,2, \ldots ,n-1 \;.$$ Define also $\; \rho_u = \{\rho_u(i)\}_{i \in I_u} \;$ by $$\label{rho u}
\rho_u(i) = p(g_1)  p(g_2) \ldots  p(g_n) \;\;,\;\;
        i = g_1g_2 \ldots g_n \in I_{u,n} \;.\; n \in {{\mathbb{N}}}\;.$$ For any $\; i = g_1g_2 \ldots g_n \in I_{u,n} \;$ we set $ B_u(i) := A(g_1g_2 \dots g_n)$ and consider the partition $\; {\zeta}_u = \{ B_u(i)\}_{i \in I_u} \;$, whose elements are enumerated by the alphabet $I_u$. The Markov property (\[Mar par 0\]) implies that the partitions $\; T_u^{-n} {\zeta}_u \;,\; n \in {{\mathbb{N}}}\;$ are independent. Thus

\[Tu\] The induced endomorphism $T_u$ is isomorphic to the Bernoulli shift $T_{\rho_u}$ and $ {\zeta}_u $ is a one-sided Bernoulli generator of$T_u$.

Graph homomorphisms and skew products {#ss3.2}
-------------------------------------

Now we want to establish the class of graph homomorphisms that we shall use.

\[hom\] Let $\; G \;$ and $\; H \;$ be two stochastic graphs.

1.  A map $\; \phi { : }G {\rightarrow}H \;$ is a [**graph homomorphism**]{} if there exists a map $\; \phi{^{(0)}} : G{^{(0)}} {\rightarrow}H{^{(0)}} \;$ such that $$s(\phi (g)) = \phi{^{(0)}} (s(g)) \;\;\;,\;\;\;
        t(\phi (g)) = \phi{^{(0)}} (t(g))$$ for all $\; g \in G \;$. (Note that, if the map $\; \phi{^{(0)}} \;$ exists it is unique.)

2.  A graph homomorphism $\;\phi { : }G {\rightarrow}H \;$ is [**deterministic**]{} if $\; \phi{^{(0)}} (G{^{(0)}}) = H{^{(0)}} \;$ and for every $\; u \in G{^{(0)}} \;$ the restriction of $\phi $ on $ G_u$ $$\phi {|}_{G_u} \;{ : }\; G_{u} \; \rightarrow \;H_{\phi{^{(0)}} (u)}$$ is a bijection of this set onto $\; H_{\phi{^{(0)}} (u)} \;$.

3.  A graph homomorphism is [**weight preserving**]{} or ${\mathbf{p}}$[**-preserving**]{} if $\; p(\phi (g)) \;=\; p(g) \;$ for all $\; g \in G \;$.

Two edges $g_1$ and $g_2$ are said to be [**congruent**]{} if $$s(g_1)=s(g_2) \;\;,\;\; t(g_1)=t(g_2) \;\;,\;\; p(g_1)=p(g_2) \;.$$ The map $ \phi{^{(0)}} $ in the above definition is uniquely determined by $ \phi $, but $ \phi{^{(0)}} $ does not determines $
\phi$ if $G$ has congruent edges.

Anyway one can use a more explicit notation $$( \phi , \phi{^{(0)}} ) \;{ : }\; (G , G{^{(0)}}) \; {\rightarrow}\; (H , H{^{(0)}} )$$ for the homomorphism $\;\phi { : }G {\rightarrow}H \;$.

We shall denote by $\; {{\mathcal Hom}}(G,H) \;$ the set of all weight preserving deterministic graph) homomorphisms $\;\phi { : }G
{\rightarrow}H \;$. In the sequel the term “homomorphism” always means just [**weight preserving deterministic graph homomorphism**]{}.

\[factor map\] Let $\; \phi { : }G {\rightarrow}H\;$ be a map.

1.  If $ \phi $ is a graph homomorphism, it induces a factor map $$\Phi_\phi \;{ : }\; X_G  {\rightarrow}X_H \;\;,\;\;
       \Phi_\phi ( {\{x_n\}}_{n=1}^{\infty} ) \;=\;
       {\{ \phi ( x_n ) \}}_{n=1}^{\infty}$$ such that $\; \Phi_\phi \circ T_G \;=\; T_H \circ {\Phi}_{\phi}\;.$

2.  If, in addition, $\phi $ is weight preserving, the factor map $ \Phi_\phi $ is measure preserving, $\; ( m_H = m_G \circ {\Phi_\phi}^{-1} ) $.

3.  If $\;\phi\;$ is also deterministic, the shift $T_G$ can be represented as a skew product $$\label{skew prod}
       {{\bar T}}(x,y) = ( T_H x \;,\; A(x) y) \;\;,\;\; (x,y) \in X_H \times Y$$ where $\; \{ A(x) \;,\; x \in X_H \} \;$ is a measurable family of automorphisms of $Y$.

4.  If $T_G$ is ergodic, $Y$ is a homogeneous Lebesgue space.

Parts (i) and (ii) follow directly from Definition \[hom\]. Part (iii) and (iv) can be proved by analogy with Proposition \[T decompos\]

Moreover

\[fin ind\] Let $\phi \in  {{\mathcal Hom}}(G,H) $ and suppose that the shift $ T_G $ is ergodic. Then there exists $\;d \in {{\mathbb{N}}}\;$ such that $\; | \Phi_\phi^{-1}(x) | \;=\; d \;$ for almost all $\; x \in X_H \;$. That is, in the skew product (\[skew prod\]) the space $Y$ is finite, $\; |Y| = d \;$.

Note that Theorem \[fin ind\] claims the finiteness of $d$ even in the case, when the graph $G$ is not finite, i.e. $ |G| = \infty
$. This is a consequence of positive recurrence of the corresponding to $G$ Markov chain. The skew product decomposition (\[skew prod\]) of $T_G$ over $T_H$ is a $d$-extension.

Theorem \[fin ind\] was proved earlier in a particular case, when $H$ is a Bernoulli graph, i.e. when $ H{^{(0)}} = \{ o \} $ is a singleton (See Theorem 3.3 and Corollary 3.4 from , and also Theorem \[zet del\] below).

We omit the proof of Theorem \[fin ind\] in general case , since only the pointed out particular case is considered in this paper.

\[def d(phi)\]. The integer $d$ in Theorem \[fin ind\], i.e. the degree of the factor map $\Phi_\phi$ will be called the [**degree**]{} of the homomorphism $\phi$.

Denoting the degree by $\; d(\phi) \;$, we have $\; d(\phi) = |\Phi_\phi^{-1}(x)| \;$ for a.a. $ x \in X_H $.

The following construction plays a central role in our explanation.

\[GSP\]

Let $\;d \in {{\mathbb{N}}}\;$ and let $\; Y_d = \{ 1,2, \ldots , d \} \;$ consists of $d$ points of measure $\frac{1}{d}$. Denote by $\; {{\mathcal A}_d}= {\mathcal A}(Y_d) \;$ the full group of all permutations of $Y_d$.

Given a stochastic graph $ H $, equipped with a function $\; a { : }H \ni h {\rightarrow}a(h) \in {{\mathcal A}_d}\;$, we construct a stochastic graph $ {{\bar H}}_a $ and a homomorphism $\; \pi_H { : }{{\bar H}}_a  {\rightarrow}H \;$ by $${{\bar H}}_a \;=\; H \;\times \; Y_d  \;\; , \;\;
  {{{\bar H}}_a}{^{(0)}} \;=\; H{^{(0)}} \; \times \; Y_d \; ,$$ with $$s({{\bar h}}) = (s(h),y)     \;\;,\;\;
  t({{\bar h}}) = (t(h),a(h)y) \;\;,\;\;  p({{\bar h}}) = p(h)$$ for $\; {{\bar h}}= (h,y) \in {{\bar H}}_a = H \times Y_d \;$ and also $$p{^{(0)}}({{\bar u}}) = p{^{(0)}}(u) \;\;,\;\;
  {{\bar u}}= (u,y) \in {{{\bar H}}_a}{^{(0)}} = H{^{(0)}} \times Y_d$$. The natural projection $$\pi_H { : }{{\bar H}}_a = H \times Y_d {\rightarrow}H \;\;,\;\;
 {\pi_H}{^{(0)}} { : }{{\bar H}}_a^{(0)} = H{^{(0)}} \times Y_d {\rightarrow}H{^{(0)}}$$ is a homomorphism.

\[def GSP\] We shall say that the graph $ {{\bar H}}_a $ is a [**skew product**]{} over $H$ and the homomorphism $\;\pi_H { : }{{\bar H}}_a {\rightarrow}H \;$ is a [**graph skew product**]{} (or [**GSP**]{}) $d$-extension of $H$ .

In the above construction we have $\; | {\pi_H}^{-1} (h) | = d \;$ for all $\; h \in H \;$ and this is, in fact, a characteristic property of the graph skew product $d$-extension in the following sense

\[hom equi\] Two homomorphisms $\; \phi_k { : }G_k {\rightarrow}H \;,\; k = 1,2 \;$ are said to be [**equivalent**]{} if $\; \phi_2 = {\kappa}\circ \phi_1 \;$ for an appropriate isomorphism $\; {\kappa}{ : }G_1 {\rightarrow}G_2 \;$.

\[d-uniform\] Let $\; d \in {{\mathbb{N}}}\;$. A homomorphism $\; \phi \in {{\mathcal Hom}}(G,H) \;$ is called a [**$d$-extension**]{} if $$\label{phi-1=d}
  |{\phi}^{-1} (h)| = d \;\;,\;\; h \in H \;.$$

\[d-unif=GSP\] Any $d$-extension $ \phi { : }G {\rightarrow}H $ is equivalent to a GSP $d$-extension $\; \pi_H { : }{{\bar H}}_a {\rightarrow}H \;$.

Let $\; \phi \in {{\mathcal Hom}}(G,H) \;$ is a $d$-extension. Since $\phi$ is deterministic the restrictions $\; \phi{|}_{G_u}
\;$ are bijections between $G_u$ and $ H_{\phi{^{(0)}}(u)} $ for all $
u \in H{^{(0)}} $. Hence the condition (\[phi-1=d\]) is equivalent to $$|{\phi{^{(0)}}}^{-1}(u)| = d \;,\; u \in H{^{(0)}} \;.$$ For each $u \in H{^{(0)}}$ we can choose a bijection $ w_u $ of $ {\phi{^{(0)}}}^{-1} (u) $ onto $ Y_d $. With any fixed choice of these bijections we set $$H \ni h {\rightarrow}a(h) = w_{t(h)} \circ {w_{s(h)}}^{-1} \in {{\mathcal A}_d}\;,$$ and consider the corresponding skew product graph $ {{\bar H}}_a $. The bijections $ w_u $ uniquely determine an isomorphism $\; {\kappa}{ : }G {\rightarrow}{{\bar H}}_a \;$ such that $\; \phi =\pi_H \circ {\kappa}\;$.

\[re GSP shift\] The Markov shift $T_{{{\bar H}}_a}$ corresponding to a graph skew product $ {{\bar H}}_a $ can be identified with the skew product endomorphism $ {{\bar T}}_{H,a} $, defined by $${{\bar T}}_{H,a} (x,y) = (T_H x , {a(x_1)}^{-1}y) \;\;,\;\;
  x ={\{ x_n \}}_{n=1}^{\infty} \in X_H \;,\; y \in Y_d \;.$$ and thus any $d$-extension is a homomorphism of degree $d$.

Indeed, the shift $T_{{{\bar H}}_a}$ acts on the space $$X_{{{\bar H}}_a} = \{ {\{ (x_n,y_n) \}}_{n=1}^{\infty} \;{ : }\;
 x = {\{ x_n \}}_{n=1}^{\infty} \in X_H \;,\;
 y_n = a(x_n)y_{n+1} \in Y_d \}$$ and the map $$\Psi \;{ : }\; X_{{{\bar H}}_a} \ni {\{ x_n \}}_{n=1}^{\infty} {\rightarrow}({\{ x_n \}}_{n=1}^{\infty},y_1)  \in X_H \times Y_d$$ realizes the identification, that is, $\; m_H \otimes m_{Y_d} = m_{{{\bar H}}_a} \circ \Psi^{-1} \;$ and $\; {{\bar T}}_{H,a} \circ \Psi = \Psi \circ T_{{{\bar H}}_a} \;$. Note also that $$\label{Psi gz}
 \Psi \; {\zeta}_{{{\bar H}}_a} \;=\; {\zeta}_H \times {\varepsilon}_{Y_d} \;\;,\;\;
 \Psi \; {\zeta}_{{{\bar H}}_a}{^{(0)}}  \;=\; {\zeta}_H
{^{(0)}} \times {\varepsilon}_{Y_d} \;.$$

Consider now two skew product endomorphisms $\; {{\bar T}}_{H,a_k} \;$, corresponding to graph skew products $ {{\bar H}}_{a_k} $ with two functions $\; a_k { : }H {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$.

\[cohom\]

1.  Two functions $\; a_k { : }H {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$, are said to be [**cohomologous**]{} with respect to $H$ if there exists a map $\; w { : }H{^{(0)}} {\rightarrow}{{\mathcal A}_d}\;$ such that $$\label{a cohom}
         a_2(h) w(s(h)) = w(t(h)) a_1(h) \;,\; h \in H$$

2.  Two measurable functions $\; A_k { : }X_H {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$ are said to be [ **cohomologous**]{} with respect to $T_H$ if there exists a measurable map $\; W { : }X_H {\rightarrow}{{\mathcal A}_d}\;$ such that $$\label{A cohom}
        A_2(x) W(x) = W(T_H x) A_1(x) \;,\; x \in X_H$$

In accordance with Definitions \[hom equi\] and \[cohom\] we can say now that the homomorphisms $\;\pi_H { : }{{\bar H}}_{a_k} {\rightarrow}H $ are equivalent iff the functions $\; a_k : H {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$ are cohomologous with respect to $H$.

The equality (\[a cohom\]) is equivalent to (\[A cohom\]) if we take $$A_k(x) = {a_k(x_1)}^{-1} \;,\; k=1,2 \;\;,\;\; W(x) = w(t(x_1))$$ for $\; x = {\{ x_n \}}_{n=1}^{\infty} \in X_H \;$ and given $a_k$ and $w$. Hence if $a_1$ and $a_2$ are cohomologous with respect to $H$, then $A_1$ and $A_2$ cohomologous with respect to $T_H$.

We shall show in Section \[ss4.3\] that the inverse is also true.

\[triv exten\] Let $\chi { : }H {\rightarrow}H_1 $ be a homomorphism and $ \pi_1 : {{\bar H}}_1 {\rightarrow}H_1 $ be a $d$-extension of $H_1$ generated by a function $a_1 : H_1 {\rightarrow}{{\mathcal A}_d}$. Setting $ a(h) :=
a_1(\chi(h)) $ we obtain a $d$-extension $ \pi { : }{{\bar H}}:= {{\bar H}}_a
{\rightarrow}H $ of $H$. The map $ {{\bar \chi}}(h,y) := ({\kappa}(h),y) \;,\; (h,y)
\in {{\bar H}}$ is a homomorphism and the diagram $$\label{diag ext}
   \xymatrix{
    {{\bar H}}\ar[d]^{\pi} \ar[r]^{{{\bar \chi}}} & {{\bar H}}_1 \ar[d]^{\pi_1} \\
        H \ar[r]^{\chi}                    &  H_1 }$$ commutes. The homomorphism $ {{\bar \chi}}$ is called a [**trivial**]{} extension of ${{\bar \chi}}$. If, in addition, $ d(\chi) = 1 $, then $ d({{\bar \chi}}) = 1 $ and hence the corresponding endomorphisms ${{\bar T}}_{H,a}$ and ${{\bar T}}_{H_1,a_1}$ are isomorphic.

Stochastic ${\boldsymbol{\rho}}$-unform graphs {#ss3.3}
----------------------------------------------

We continue to consider $\;(I,\rho)\;$ as the standard Bernoulli stochastic graph, (Example \[Bern graph\])

\[rho uni\] A stochastic graph $ (G,p) $ is called ${\boldsymbol{\rho}}$[**-uniform**]{} if there exists a homomorphism $\; \phi \in {{\mathcal Hom}}(G,I) \;$.

For any such homomorphism $\phi$ and for every $ u \in G{^{(0)}} $ $$\phi \;{|}_{G_u} \;{ : }\;
  ( G_u \;,\; p \;{|}_{G_u} )\; {\rightarrow}\; (I,\rho)$$ is a weight preserving bijection. Thus the atomic probability spaces $\; ( G_u , p {|}_{G_u} ) \;$ are isomorphic to $(I,\rho)$ for every $ u \in G{^{(0)}} $.

\[p3.4\] $\; T_G \in {\mathcal {UE}(\rho)}\;$ iff $G$ is $\rho$-uniform.

Consider the partition $\; \xi_1 := T_{G}^{-1} {{\varepsilon}}_{X_G} \;$ generated by the shift $T_G$. The Markov property of the measure $m_G$ on $X_G$ implies $$m^{C_{\xi_1}(x)}(\{x\}) \;=\; m_G \{\; Z_1=x_1 \;|\; Z_2=x_2 \;\}
  \;=\; p(x_1)$$ for a.a. $\; x={\{x_{n}\}}_{n=1}^{\infty} \in X_G \;$, Here $\; m^{C_{\xi_1}(x)}(\{x\}) \;$ is the conditional measure of the point $x$ in the element $C_{\xi_1}(x) = T_G^{-1}T_Gx $ of the partition $ \xi_1 $. Hence for every $ u \in G{^{(0)}} $ almost all elements $(C,m_C)$ of the partition $ \xi_1 $ are isomorphic to $\; ( G_u , p {|}_{G_u})
\;$ on the set $\; \{ x={\{x_n\}}_{n=1}^{\infty} \in X_G
\;{ : }\; s(x_1) = u \} \;$. But $\;T_G \in {\mathcal {UE}(\rho)}\;$ iff a.a. elements $(C,m_C)$ are isomorphic to $(I,\rho)$. Hence $\;T_G \in
{\mathcal {UE}(\rho)}\;$ iff $\;( G_u , p{|}_{G_u})\;$ are isomorphic to $(I,\rho)$ for every $ u \in G{^{(0)}} $.

Let $G$ be a $\rho$-uniform graph and $\; \phi \in {{\mathcal Hom}}(G,I) \;$. Consider the partition $\; \phi^{-1} {\varepsilon}_I = \{ \phi^{-1} (i) \;,\; i \in I \;\}$ of $G$. The first coordinate function $$Z_1 \;{ : }\; X_G \ni x={\{x_k\}}_{k=1}^{\infty}
 \; {\rightarrow}\; x_1 \in G$$ generates the following partition $${\delta}_\phi \;=\; Z_1^{-1} ( \phi^{-1} {\varepsilon}_I )$$ of the space $ X_G  $. Elements of $\; {{\delta}}_{\phi} \;$ have the form $$B(i) = Z_{1}^{-1} ( \phi^{-1} (i) ) =
   \{ x={\{x_{k}\}}_{k=1}^{\infty} \in X_G  \;{ : }\;
   {\phi}(g) = i \} \;,\; i \in I$$ Using the standard Markov generator $${\zeta}_G = Z_{1}^{-1}{\varepsilon}_G = {\{A(g)\}}_{g \in G} \;\;,\;\;
 A(g) = Z_{1}^{-1}(g)$$ of $T_G$, we have $$B(i) = {\bigcup}_{g \in {\phi}^{-1}(i)} A(g)$$ and $$m_G(B(i)) = {\sum}_{g \in {\phi}^{-1}(i)} p(g)  p{^{(0)}}(s(g))
           = \rho(i) {\sum}_{u \in G{^{(0)}}} p{^{(0)}}(u) = \rho(i)$$ for $\; i \in I \;$. Hence for $\; {\delta}\;=\; {\delta}_\phi \;$ we have $$\label{del phi}
 {\delta}\in IC (\; T_{G}^{-1} {\varepsilon}_{X_G} \;) =
 {\Delta}_\rho( T_G )  \;\;,\;\;   {\delta}\leq {\zeta}_G$$ Denoting by $\; {\Delta}_\rho(T_G , {\zeta}_G) \;$ the set of all $ {\delta}$ that satisfy (\[del phi\]), we have also

\[d(T,zeta)\] $\; {\Delta}_\rho(T_G , {\zeta}_G) \;$ is precisely the set of all $ {\delta}$ of the form $\; {\delta}\;=\; {\delta}_\phi \;$.

Now we introduce a semigroup $\; {{\mathcal S}}(\phi) \;$ of maps $\; f { : }G{^{(0)}} {\rightarrow}G{^{(0)}} \;$ induced by the homomorphism $\phi$.

Let $\; i \in I \;$. Since $\; \phi \;$ is deterministic the restriction $\; \phi {|}_{G_u} \;{ : }\; G_u \; {\rightarrow}I \;$ is a bijection of $G_u$ onto $I$ for every $u \in G{^{(0)}}$. Hence for any pair $(i,u)$ there exists an unique $\; g_{i,u} \;$ such that $\; \phi (
g_{i,u} ) = i \;$ and $\; s( g_{u,i} ) = u \;$. Putting $\; f_iu =
g_{i,u} \;$, we get a map $\; f_i { : }G{^{(0)}} {\rightarrow}G{^{(0)}} \;$. Let $\; {{\mathcal S}}(\phi) \;$ be the semigroup generated by the maps $\;
\{ f_i \;,\; i \in I \} \;$.

Let $ {{\mathcal F}}{{\mathcal S}}(I) $ be the set of all finite words $\; i_1i_2
\dots i_n \;$ in the alphabet $I$. We shall consider $ {{\mathcal F}}{{\mathcal S}}(I) $ as a free semigroup with the generating set $I$ and with juxtaposition multiplication: $$i_1i_2 \dots i_m \cdot j_1j_2 \dots j_n
 \;=\; i_1i_2 \dots i_mj_1j_2 \dots j_n$$ and set $$f_{i_1i_2 \dots i_n} \;=\; f_{i_1} \circ f_{i_2} \circ \; \dots \;
  \circ f_{i_{n}} \;\;,\;\; i_1i_2 \dots i_n \; \in \; I^n$$ Then $\; i_1i_2 \dots i_n {\rightarrow}f_{i_1i_2 \dots i_n} \;$ is a homomorphism from the semigroup $ {{\mathcal F}}{{\mathcal S}}(I) $ onto the semigroup $${{\mathcal S}}(\phi) = \{ f_{i_1i_2 \dots i_n} \;,\;i_1i_2 \dots i_n
\in {{\mathcal F}}{{\mathcal S}}(I) \} \;,$$ generated by $\; \{ f_i \;,\; i \in I \} \;$.

Now we can describe the partitions $${\delta}_\phi = \{ B(i) \}_{i \in I} \;\;,\;\;
 {\delta}_\phi{^{(n)}}\;=\; \bigvee_{k=1}^{n} T_{G}^{-k+1} {\delta}_\phi
 \;,\; n \in {{\mathbb{N}}}$$ as follows.

First recall that the partition $\; {\zeta}{^{(0)}}$ consists of the atoms $D(u) = Z^{-1}(_uG) \;,\;u \in G{^{(0)}} \;$ and rename the elements $\; A(g) \;,\; g \in G \;$ of the partition ${\zeta}_G $ by $$D(i,u) := A(g_{i,u}) \;\;,\;\; u \in G{^{(0)}} \;,\; i \in I \;.$$ Then for all $i \in I$ and $u \in G{^{(0)}}$ we have $\; D(i,u) = B(i) \cap T_{G}^{-1}D(u) \;$, $$D(i,u) = \{ x={ \{ x_n \} }_{n=1}^{\infty} \in X_G
 \;{ : }\; t(x_1) = u \;,\; \phi(x_1) = i \}$$ and $$\label{Bi Diu}
 B(i) = \bigcup_{u \in G{^{(0)}}} D(i,u) \;\;\;,\;\;\;
 D(u) = \bigcup_{v { : }f_i(v)=u} D(i,v) \;.$$ Further for any $\; g_1g_2 \dots g_n  \in  G{^{(n)}}\;$ there exists a unique pair $\; (i_1i_2 \dots i_n,u) \in I^n \times G{^{(0)}} \;$ such that $$\label{u i t}
 u = s(g_n) \;,\; i_k = \phi (g_k) \;,\; t(g_k) = f_{i_k} (s(g_k))
 \;,\; k = 1,2, \dots ,n$$ Hence any atom $\; A(g_1g_2\; \dots \,g_n) \;$ of the partition $\; {\zeta}_G{^{(n)}}= \bigvee_{k=1}^{n} T^{-k+1} {\zeta}_G \;$ can be renamed by $\;D(i_1i_2 \dots i_n,u) = A(g_1g_2\; \dots \,g_{n}) \;$, where the pair $\; (i_1i_2 \dots i_n,u) \;$ satisfies (\[u i t\]). By (\[Bi Diu\]) any atom $\; B(i_1i_2\; \dots \;i_n) \;$ of the partition $\; {\delta}_\phi{^{(n)}}= \bigvee_{k=1}^{n} T_{G}^{-k+1}
{\delta}_\phi \;$ has the form $$B(i_1i_2\; \dots \;i_n)
 \;=\; \bigcup_{u \in G{^{(0)}}} D(i_1i_2 \dots i_n,u)$$ and since $$D(i_1i_2...i_n,u) \;=\; B(i_1i_2\; \dots \;i_n) \cap T^{-n} D(u)$$ we have $$m_G(B(i_1i_2\; \dots \;i_n)) \;=\;
 \rho (i_1) \rho (i_2) \; \dots \; \rho (i_n),$$ $$m_G( D(i_1i_2 \dots i_n,u) ) \;=\;
 \rho (i_1) \rho (i_2) \; \dots \; \rho (i_{n})p{^{(0)}}(u).$$ Any ${\zeta}_G{^{(0)}}$-set has the form $$D(E) = \{ x={ \{ x_n \} }_{n=1}^{\infty} \in X_G
 \;{ : }\; t( x_1 ) \in E \}.$$ for a subset $\; E \subseteq G{^{(0)}} \;$. Then for any $ i_1i_2 \; \dots \; i_n \in I^n $ $$D(E) \cap B(i_1i_2\; \dots \;i_n) \;=\;
 \bigcup_{u { : }f_{i_1i_2 \;\dots\; i_n} (u) \in E }
 D(i_1i_2 \dots i_n,u).$$ Hence $$\label{D(E)}
 m_G ( D(E) \; | \; B(i_1i_2 \; \dots \; i_n) ) \;=\;
 p{^{(0)}} ( f^{-1}_{i_1i_2\; \dots \; i_n} (E) ).$$ Next theorem is basic for our explanation. Let $${\delta}_{\phi}^{(\infty)} \;=\; \bigvee_{n=1}^{\infty} {\delta}_\phi{^{(n)}}\;=\; \bigvee_{n=1}^{\infty} T_{G}^{-n+1} {\delta}_\phi$$

\[zet del\] Let $\; \phi \in {{\mathcal Hom}}(G,I) \;$. Then

1.  $\; {\zeta}_G \; \vee \; {\delta}_{\phi}^{(\infty)}
      \;=\; {\varepsilon}_{X_G} \;.$

2.  $\; d(T_G) \;\leq\; d(T_G,{\delta}_{\phi}) \;=\;
       d(\phi) \;<\; \infty \;$

It was proved in that if ${\zeta}$ is a one-sided Markov generator of $T$ and $$T \in  {\mathcal {UE}(\rho)}\;,\; {\delta}\in {\Delta}_\rho(T) \;,\; {\delta}\; \leq \; {\zeta}\; ,$$ then $\; {\zeta}\vee  {\delta}^{(\infty)} = {\varepsilon}\;$. Hence (i) follows by putting $ {\delta}= {\delta}_\phi $ and $ {\zeta}= {\zeta}_G $ .

Since the partition $ {\zeta}_G $ is finite or countable the equality (i) implies that almost all elements $(C,m_C)$ of the partition ${\delta}_{\phi}^{(\infty)}$ are atomic. Taking in to account the ergodicity of $T_G$, we see that almost all elements of ${\delta}_{\phi}^{(\infty)}$ consist of $d$ atoms of measure $\frac{1}{d}$ for an natural $d$. Herewith by Definitions \[def d(T)\] and \[def d(phi)\] we have $\; d =
d(T_G,{\delta}_{\phi}) = d(\phi)$ and, whence, (ii) follows.

We need the following sharp version of Part (i) of Theorem \[zet del\]

\[zet0 del\] $\;  {\zeta}{^{(0)}}_G \; \vee \; {\delta}_{\phi}^{(\infty)} \;=\; {\varepsilon}_{X_G} \;$

Choose an increasing sequence of positive numbers $c_n > 0$ and an increasing sequence of finite subsets $E_n$ of $G{^{(0)}}$ such that $$\label{zet0 del1}
  \bigcup_{n=1}^\infty E_n = G{^{(0)}} \;\;\;.\;\;\;
  \sum_{n=1}^\infty(1-c_n) < \infty \;\;\;.\;\;\; p{^{(0)}}(E_n)>c_n \;.$$ Since $|E_n|<\infty$ there exist $\; i{^{(n)}}_1i{^{(n)}}_2 \dots i{^{(n)}}_{k_n} \in I^{k_n} \;$ and $\; f_n := f_{i{^{(n)}}_1i{^{(n)}}_2 \dots i{^{(n)}}_{k_n}} \in {{\mathcal S}}(\phi) \;$ such that $$|f_n(E_n)| \;=\; \min \{ |f(E_n)| \;{ : }\; f \in {{\mathcal S}}(\phi) \}.$$ The choice of $f_n$ provides that all restrictions $\; f{|}_{f_n(E_n)} \;,\; f \in {{\mathcal S}}(\phi) \;$ are bijections.

Consider the sets $$\begin{split}
 & B_n := B(i{^{(n)}}_1i{^{(n)}}_2 \dots i{^{(n)}}_{k_n}) \;\;,\;\; \\
 & B'_n := B_n \bigcap T_G^{-k_n}D(E_n) \;=\;
   \bigcup_{u \in E_n}D(i{^{(n)}}_1i{^{(n)}}_2 \dots i{^{(n)}}_{k_n},u)
\end{split}$$ and also $$F_n \;:=\; \{ x \in X_G \;{ : }\;
 T^{{\omega}_n(x)+n}x \in B^\prime _n  \} \;,$$ where $${\omega}_n(x) \;:=\; \min \{k \geq 0 \;{ : }\; T^{n+k}x \in B_n  \}$$ Then it is not hard to see that $$m_G(F_n) \;=\; m_G(B'_n \;|\; B_n) \;=\; p{^{(0)}}(E_n) \;>\; c_n \;.$$ Set $\; F \;:=\; \liminf_{n {\rightarrow}\infty}F_n \;$. Then we have $\; m_G(F)=1 \;$, since $\;\sum(1-c_n) < \infty \;$. By constructing, the set $F$ has the following property. Suppose $\; x={\{x_k\}}_{k=1}^{\infty} \;$ and $\;y={\{y_k\}}_{k=1}^{\infty} \;$ belong to $F$ and $$\; \Phi_{{\delta}_\phi}(x) \;=\; \Phi_{{\delta}_\phi}(y)
 \;=\; {\{i_k\}}_{k=1}^{\infty}
 \;\in \; X_\rho \;.$$ If $\; s(x_m)  \neq s(y_m) \;$ for some $m \geq 1 $, then $$t(x_k) = f_{i_k}s(x_k) \neq t(y_k) = f_{i_k}s(y_k) \;\;,\;\;
 k \;=\; 1,\,2,\;\dots \;m \;.$$ In other words, if $t(x_1) = t(y_1)$ and $\; \Phi_{{\delta}_\phi}(x) \;=\; \Phi_{{\delta}_\phi}(y) \;$ then $x=y$. Thus $\; {\zeta}{^{(0)}}_G \; \vee \; {\delta}_{\phi}^{(\infty)} \;=\;
{\varepsilon}_{X_G} \;$ on the set $F$ of measure $1$.

Semigroup $ {{\mathcal S}}({\boldsymbol{\phi}})$ and persistent ${\mathbf{d}}$-sets. {#ss3.4}
------------------------------------------------------------------------------------

Let $U$ be a finite or countable set.

\[L set\] Let $ {{\mathcal S}}$ be a semigroup of maps $\;f \;{ : }\; U \;{\rightarrow}\; U\;$ on $U$ and let $\; d \in {{\mathbb{N}}}\;$. Call the semigroup ${{\mathcal S}}$ ${\mathbf{d}}$[**-contractive**]{} if there exists a subset $\; L\; \subseteq U \;$ such that

1.  $ |f(L)| \;=\; |L| \;=\; d \;$ for all $\; f \in {{\mathcal S}}\;.$

2.  For every finite subset $\; E \subset U \;$ there exists $\; f \in {{\mathcal S}}\;$ with $\; f(E) \subseteq L \;$.

The sets $L$, satisfying (i) and (ii), will be called [**persistent ${\mathbf{d}}$-sets**]{} with respect to $ {{\mathcal S}}$.

Denote by $\; {{\mathcal L}}({{\mathcal S}}) \; $ the set of all such $L$. We have directly from the definition:

-   For $\; L \in {{\mathcal L}}({{\mathcal S}}) \;$ and $\; f \in {{\mathcal S}}\;$ the restriction $\; f {|}_{L} \;{ : }\; L \;{\rightarrow}\; f(L) \;$ is a bijection and $\; f(L) \; \in \; {{\mathcal L}}( {{\mathcal S}}) \;$.

-   The semigroup $ {{\mathcal S}}$ acts transitively on $ {{\mathcal L}}( {{\mathcal S}}) $, i.e. for every pair $\; L_1 \;,\;L_2\; \in \; {{\mathcal L}}({{\mathcal S}}) \;$ there exists $\; f \in {{\mathcal S}}\;$ such that $\; f(L_1) \;=\; L_2 \;$.

-   The integer $d$ is equal to $$\label{d(G)}
        d( {{\mathcal S}}) \; := \; \sup_{E \subseteq U \;{ : }\; |E| < \infty}
       \;\;  \min_{ f \in {{\mathcal S}}} \;\; |f(E)| \; .$$ and $\; d({{\mathcal S}}) \;=\; \min_{ f \in {{\mathcal S}}} \;\; |f(U)| \;$ if $\; |U| \;<\; \infty \;$.

Let $G$ be a $\rho$-uniform stochastic graph and $ \phi \in  {{\mathcal Hom}}(G,I) $ be a homomorphism $ \phi { : }G {\rightarrow}I $.

Return to the semigroup $\; {{\mathcal S}}(\phi) \;$ which acts on $\; U = G{^{(0)}} \;$ .

\[d(phi)\] Let $T_G$ be an ergodic one-sided Markov shift corresponding to a $\rho$-uniform stochastic graph $G$ and let $ \phi \in {{\mathcal Hom}}(G,I)$. Then the semigroup $ {{\mathcal S}}(\phi)$ is $d$-contractive on $G{^{(0)}} $ and $$\label{d=d(G)}
  d \;=\; d({{\mathcal S}}(\phi)) \;=\; d(T_G , {\delta}_\phi) \;=\; d(\phi)$$

To prove the theorem we shall use the partition ${\zeta}{^{(0)}}_G$ on $G{^{(0)}}$. Recall that ${\zeta}{^{(0)}}_G$ consists of all atoms of the form $\; D(u) = Z_1^{-1} (_uG) \;,\; u \in G{^{(0)}}. \;$. For any subset $E$ of $G{^{(0)}} $ we denote $$D(E) = \{ x={\{x_{n}\}}_{n=1}^{\infty} \in X_G  \;{ : }\;
 t( x_1 ) \in E \} = \bigcup_{u \in E} D(u) \;,$$ i.e. $ D(E) $ is a $ {\zeta}{^{(0)}}_G$-set corresponding to $E$ in the space $X_G$.

It follows from Theorem \[zet del\] Part (ii) that almost all elements $(C,m_C)$ of the partition ${\delta}_{\phi}^{(\infty)}$ are isomorphic to $Y_d$, where $\; d = d(T_G,{\delta}_{\phi}) \in {{\mathbb{N}}}\;$. Hence $$m( \{x\} \;|\; C_{{\delta}_{\phi}^{(\infty)}}(x)) \;=\; \frac{1}{d}$$ for a.e. $x \in X_G$. Then Lemma \[zet0 del\] implies that there exists a measurable family $\; \{ l(x) \;,\; x \in X \} \;$ of subsets $\; l(x) \subseteq G{^{(0)}} \;$ such that $$\label{l(x)=d}
 m ( D(l(x)) \;|\; C_{{\delta}_{\phi}^{(\infty)}} (x) ) \;=\; 1
 \;\;,\;\;  |l(x)| \;=\; d$$ almost everywhere on $ X_G $.

For any $ L \subseteq G{^{(0)}} $ denote $$\check{L} \;:=\; \{ x \in X_G \;{ : }\; l(x) = L \} \;\;,\;\;
 {{\mathcal L}}\;:=\; \{ L \subseteq G{^{(0)}} \;:\; m_G ( \check{L} ) > 0 \} \;,$$ i.e. ${{\mathcal L}}$ is the (finite or countable) set of all essential values of the function $\;x \;{\rightarrow}\; l(x) \;$. We show that $\; {{\mathcal L}}\subseteq {{\mathcal L}}({{\mathcal S}}(\phi)) \;$, i.e. that every $\; L \in {{\mathcal L}}\;$ satisfies the conditions (i) and (ii) of Definition \[L set\].

Take any finite subset $E \subseteq G{^{(0)}}$ and choose $\; c > 0
\;$ such that $ \; c  \;<\; \min_{u \in E}p{^{(0)}}(u) \;$. For $\; L \in {{\mathcal L}}\;$ and almost all $\; x={\{x_{n}\}}_{n=1}^{\infty} \in \check{L} \;$ we have by (\[D(E)\]) $$lim_{n {\rightarrow}\infty} m(D(L) \;|\; C_{{\delta}_\phi{^{(n)}}}(x) \}
 \;=\; m_G (D(l(x)) \;|\; C_{{\delta}_\phi{^{(\infty)}}} (x)\} \;=\; 1$$ and by (\[D(E)\]) $$m(D(L) \;|\; C_{{\delta}_\phi{^{(n)}}} (x)\} \;=\;
 p{^{(0)}}( f^{-1}_{x_1x_2\; \ldots \;x_n} (L)).$$ Hence we can choose $n$ and $\; (x_1x_2\; \ldots \;x_{n}) \in G{^{(n)}}\;$ such that $$m(B(x_1x_2\; \dots \;x_n) \cap \check{L} ) > 0$$ and then $$p{^{(0)}} (f^{-1}_{x_1x_2\; \dots \;x_{n}} (L)) \;>\; 1-c$$ The choice of $c$ provides $\; f^{-1}_{x_1x_2\; \ldots \;x_n}(E) \supseteq L \;$ and thus Part (ii) of Definition \[L set\] holds. Part (i) follows from the equalities $$\label{f l(x)}
 f_{x_1x_2\; \dots \;x_{n}} l(T_G^nx) \;=\; l(x) \;\;,\;\; |l(x)| = d
 \;\;,\;\; x \in X_G$$ by the definition of $l(x)$ . We have proved the inclusion $\; {{\mathcal L}}\subseteq {{\mathcal L}}({{\mathcal S}}(\phi)) \;$ , which implies that the semigroup ${{\mathcal S}}$ is $d$-contractive with $\; d = d(T_G , {\delta}_\phi) $

\[L=L(phi)\] $\; {{\mathcal L}}= {{\mathcal L}}({{\mathcal S}}(\phi)) \;$,

It was proved above that $\; {{\mathcal L}}\subseteq {{\mathcal L}}({{\mathcal S}}(\phi)) \;$. Take $ M \in {{\mathcal L}}({{\mathcal S}}(\phi)) $ and $ L \in {{\mathcal L}}$. Since also $ L \in {{\mathcal L}}({{\mathcal S}}(\phi))$, there exists $i_1i_2 \dots
i_{n} \in I^n $ such that $$\; f_{x_1x_2\;...\;x_{n}} (M) \;=\; L
\;=\; l(x) \;,\; x \in \check{L} \;$$ Then the equality (\[f l(x)\]) implies $\; M = l(T^{n}x) \;$ on a set of positive measure in $X$ and hence $\; M \in {{\mathcal L}}\;$. Thus $\; {{\mathcal L}}\supseteq {{\mathcal L}}({{\mathcal S}}(\phi)) \;$.

Note that the notion of $d$-contractive semigroup was introduced in , where an analog of Theorem \[d(phi)\] was also proved. Definition \[L set\] is a generalization of what is called “point collapsing” by M. Rosenblatt , in the case $ |U| < \infty $ and $ d=1 $ . The case , when $ |U| = \infty $ and $ d=1 $, was considered in [@KuMuTo].

 Graph skew product representation. {#ss3.5}
-----------------------------------

From now on let $G$ be a $\rho$-uniform stochastic graph, which is irreducible and satisfies the positive recurrence condition.

\[phi bar\] Let $\; \phi \in {{\mathcal Hom}}(G,I) \;$ be a homomorphism of degree $\; d = d(\phi) \;$. Then there exists a commutative diagram $$\label{diag phi bar}
 \xymatrix{  {{\bar H}}\ar[d]^{{{\bar \phi}}}  \ar[r]^{{{\bar \psi}}} & G \ar[d]^{\phi} \\
                                H \ar[r]^{\psi} & I }$$ where the graph $ {{\bar H}}= {{\bar H}}_a $ is a graph skew product over $H$, generated by a function $\; a { : }H \ni h {\rightarrow}a(h) \in {{\mathcal A}_d}\;$, the homomorphism $ {{\bar \phi}}$ coincides with the natural projection $\pi_H$, and both the homomorphisms $\; {{\bar \psi}}\in {{\mathcal Hom}}({{\bar H}},G) \;$ and $\; \psi \in {{\mathcal Hom}}(H,I)\;$ are of degree 1. In particular, $\; ({{\bar \phi}},\psi) \in {{\mathcal Ext}^d(I,\rho)}\;$

We construct a commutative diagram $$\label{diag phi hat}
 \xymatrix{
  {{\hat H}}\ar[d]^{{{\hat \phi}}} \ar[r]^{{{\hat \psi}}} & G \ar[d]^{\phi} \\
                    H \ar[r]^{\psi} & I }$$ such that the homomorphism $\; {{\hat \phi}}\in {{\mathcal Hom}}({{\hat H}},H) \;$ is a $d$-extension (See Definition \[d-uniform\]) and both homomorphisms $\; {{\hat \psi}}\in {{\mathcal Hom}}({{\hat H}},G) \;$ and $\; \psi \in {{\mathcal Hom}}(H,I) \;$ are of degree 1 .

We shall use the persistent $d$-sets $ {{\mathcal L}}= {{\mathcal L}}({{\mathcal S}}(\phi)) $ of the semigroup $ {{\mathcal S}}(\phi) $, described in Theorem \[d(phi)\] (Section\[ss3.4\]). Since $ {{\mathcal L}}$ is finite or countable we can enumerate the set by an alphabet $J$, setting $ {{\mathcal L}}= \{ L_j \;,\; j \in J \} $.

Recall that the semigroup $ {{\mathcal S}}(\phi) $ is $d$-contractive with $ d = d({{\mathcal S}}(\phi)) $ (Theorem \[d(phi)\]). For any pair $\; i \in I \;,\; j \in J \;$ we have $\; |f_i(L_j)|
= |L_j| =d \;$ and the restrictions $\; f_i {|}_{L_j} \;$ is a bijection of $\; L_j \;$ onto $\;f_i(L_j) \;$, whence, $\;f_i(L_j)
\in {{\mathcal L}}\;$ for all $i$ and $j$. For any $\;i \in I \;$ denote by $f_i^J$ the map $\; J {\rightarrow}J \;$, which is defined by $\; f_i^J j
= j' \;$, where $\; f_i(L_j) = L_{j'} \;$.

To construct Diagram \[diag phi hat\] define first $\; \psi { : }H {\rightarrow}I \;$ with $ \; H := I \times J \;$,$\; H{^{(0)}} := J \;$, where $$s(i,j) = j \;\;,\;\; t(i,j) = f_i^J j \;\;,\;\; p(i,j) = \rho(i)
 \;\;,\;\; \psi (i,j) = i \;.$$ Next set $${{\hat H}}{^{(0)}} \;:=\;
 \{ (j,u) \in J \times G{^{(0)}} \;{ : }\; j \in J \;,\; u \in L_j \}
 \;\;,\;\; {{\hat H}}\;:=\; I \times {{\hat H}}{^{(0)}}$$ with $$s(i,j,u) = (j,u) \;\;,\;\; t(i,j,u) = (f_i^J j , f_i u) \;\;,\;\;
 p(i,j,u) = \rho(i) \;.$$ Finally, we define the maps ${{\hat \psi}}$ and ${{\hat \phi}}$ by $${{\hat \phi}}{ : }{{\hat H}}\ni (i,j,u) {\rightarrow}(i,j) \in H \;\;,\;\;
 {{\hat \psi}}{ : }{{\hat H}}\ni (i,j,u) {\rightarrow}g_{i,u} \in G \;.$$ where $g_{i,u}$ is uniquely determined by the conditions $s(g) =
u$ and $\phi(g) = i$.

It follows directly from this constructing that $H$ and ${{\hat H}}$ are stochastic graphs, and that ${{\hat \phi}}$ , ${{\hat \psi}}$ and $\psi$ are homomorphisms, and that Diagram \[diag phi hat\] commutes. Point out only that ${{\hat \phi}}$ is a $d$-extension, since $ |L_j| = d $ for all $j$ and hence ${{\hat \phi}}$ is of degree $d$. This implies that $\hat{\psi}$ and $\psi$ are of degree 1 , since $\phi$ is of degree $d$.

It remains to apply Proposition \[d-unif=GSP\] to the homomorphism $\; {{\hat \phi}}{ : }{{\hat H}}{\rightarrow}H \;$.

Next we construct d-extensions with a minimal possible $d$. Let $G$ as above be a $\rho$-uniform stochastic graph. Recall that $G{^{(n)}}$ denotes the set of all $n$-paths in $G$, see (\[G(n)\]). We shall consider $G{^{(n)}}$ as a stochastic graph with the set of vertices $G^{(n-1)}$, where for any $\; g{^{(n)}}=
g_1\;g_2\; \ldots \;g_n \;$ $$s(g{^{(n)}}) \;=\; g_2\;g_3\; \ldots \;g_n \;\;,\;\;
 t(g{^{(n)}}) \;=\; g_1\;g_2\; \ldots \;g_{n-1}$$ and $\; p(g{^{(n)}}) \;=\; p(g_1) p(g_2) \ldots p(g_n) \;$. If $G$ is $\rho$-uniform, the “$n$-stringing” graph $G{^{(n)}}$ is also $\rho$-uniform. The natural projection $$\pi{^{(n)}}{ : }G{^{(n)}}\ni g{^{(n)}}=(g_1\;g_2\;
 \ldots \;g_n) {\rightarrow}g_1 \in G$$ is a homomorphism and $\; \phi \circ \pi{^{(n)}}\in {{\mathcal Hom}}(G{^{(n)}},I) \;$ for any $\; \phi \in {{\mathcal Hom}}(G,I) \;$. However, if $(I,\rho)$ has congruent edges there exist $\; \phi_1 \in {{\mathcal Hom}}(G{^{(n)}},I) \;$, which are not of the above form $\; \phi_1 = \phi \circ \pi{^{(n)}}\;$. It is an obvious fact, that $d(\pi{^{(n)}}) = 1$, i.e. $\;
\Phi_{\pi{^{(n)}}} : X_{G{^{(n)}}} {\rightarrow}X_G$ is an isomorphism. We use the index $d(T,{\delta})$ and the minimal index $d(T)$, which were defined by Definition \[def d(T)\].

\[phi bar d(T)\] Let $G$ be a $\rho$-uniform stochastic graph, which is irreducible and satisfies the positive recurrence condition. Then there exist an integer $n \in {{\mathbb{N}}}$, a homomorphism $\; \phi
\in {{\mathcal Hom}}(G{^{(n)}},I) \;$ and a commutative diagram $$\label{diag bar H Gn}
 \xymatrix{
 {{\bar H}}\ar[d]^{{{\bar \phi}}} \ar[r]^{{{\bar \psi}}} & G{^{(n)}}\ar[d]^{\phi} \\
                               H \ar[r]^{\psi} & I   }$$ such that

1.  The graph ${{\bar H}}= {{\bar H}}_a $ is a skew product over a graph $H$, generated by a function $\; a { : }H \ni h {\rightarrow}a(h) \in {{\mathcal A}_d}\;\;,\;\;d \in {{\mathbb{N}}}\;$, and the homomorphism $ {{\bar \phi}}$ coincides with the natural projection $\pi_H$ of ${{\bar H}}$ onto $H$,

2.  $\; d = d(\phi) = d(T_G) \;$,

3.  The homomorphisms $\; {{\bar \psi}}\in {{\mathcal Hom}}({{\bar H}},G) \;$ and $\; \psi \in {{\mathcal Hom}}(H,I) \;$ are of degree 1 .

Let ${\zeta}= {\zeta}_G $ be the standard Markov generator of the shift $T_G$. It was proved in that there exist $ n \in {{\mathbb{N}}}$ and $ {\delta}\in {\Delta}_\rho(T_G) $ such that $${\delta}\leq  {\zeta}{^{(n)}}:= \bigvee_{k=1}^{n} T^{-k+1} {\zeta}\;\;,\;\; d(T,{\delta}) = d(T) \;.$$ Take ${\zeta}{^{(n)}}$ and $G{^{(n)}}$ instead ${\zeta}$ and $G$ in Proposition \[d(T,zeta)\]. Then we obtain $\; \phi \in {{\mathcal Hom}}(G{^{(n)}},I) \;$ with $\; {\delta}= {\delta}_\phi \;$ and thus, by using Corollary \[phi bar\], we complete the proof.

Homomorphisms and finite extensions. {#s4}
====================================

Homomorphisms of degree 1 {#ss4.1}
-------------------------

Let $H$ be a $\rho$-uniform graph and consider a homomorphism $\; \psi { : }H {\rightarrow}I \;$. Suppose that $\psi$ is of degree 1. By Theorem \[d(phi)\] the semigroup ${{\mathcal S}}(\psi)$, generated by $\; f_i = f_i^\psi \;,\; i \in I \;$, is $1$-contractive and all its persistent sets are singletons. Using $\psi$ we can identify the graph $H$ with $I \times J$, where $\; J = H{^{(0)}} \;$ and for any $ h = (i,j) \in H $ $$\psi (h)=i \;,\; s(h)=j \;\;,\;\; t(h)= f_i j
 \;\;,\;\; p(h)=\rho (i)$$ Since $d(\psi)=1$ the partition ${\delta}_\psi$ is a one-sided Bernoulli generator for the Markov shift $T_H$. The factor map $\; \Phi_{{\delta}_\psi} \;{ : }\; X_H {\rightarrow}X_\rho \;$ is an isomorphism, $\; \Phi_{{\delta}_\psi} \;\circ\; T_H = T_{\rho}
\;\circ\; \Phi_{{\delta}_\psi}$ and we can consider the Markov partitions $\; {\zeta}_\rho := \Phi_{{\delta}_\psi}({\zeta}_H) \;$ and $\;
{\zeta}{^{(0)}}_\rho := \Phi_{{\delta}_\psi}({\zeta}_H{^{(0)}}) \;$ for $T_\rho$ on $X_\rho$, which correspond to the Markov partitions ${\zeta}_H$ and ${\zeta}_H{^{(0)}}$ for $T_H$ on $X_H$. The partition ${\delta}_\rho = \Phi_{{\delta}_\psi}({\delta}_H) $ coincides with the standard Bernoulli generator of the Bernoulli shift $T_\rho$.

Thus we have, with the notations from Section \[ss3.3\], $${\delta}_\rho = \{ B_\rho (i) \}_{i \in I} \;\;,\;\;
 {\zeta}_\rho = \{ D_\rho (i,j) \}_{ (i,j) \in I\times J} \;\;,\;\;
 {\zeta}{^{(0)}}_\rho = \{ D_\rho (j) \}_{ j \in J}$$ where $$D_\rho (i,f_i(j)) = B_\rho (i) \cap T_\rho^{-1} D_\rho (j)
 \;\;,\;\;  (i,j) \in I\times J$$ Hence the homomorphism $\psi$ is determined by the partitions $\;
{\delta}_\rho \;,\; {\zeta}_\rho \;,\; {\zeta}{^{(0)}}_\rho \;$ uniquely up to equivalence (see Definition \[hom equi\]).

Our aim now is to construct a [**common extension of degree 1**]{} for two homomorphisms of degree 1.

\[degree 1\] Let $\;  \psi_1 { : }H_1 {\rightarrow}I  \;,\; \psi_2 { : }H_2 {\rightarrow}I
\;$ be two homomorphisms of $\rho$-uniform graphs $H_1$ and $H'_2$ onto the Bernoulli graph $ (I,\rho) $ and suppose that $ \psi_1 $ and $ \psi_2 $ are of degree 1. Then there exist a $\rho$-uniform graph $H$ and homomorphisms $\psi$, $\chi_1$ and $\chi_2 $ of degree 1, for which the following diagram commutes: $$\label{diag degree 1}
 \xymatrix{
  & H_2  \ar[rr]^{\psi_2} & &  I \\
  H \ar[ur]^{\chi_2} \ar[urrr]^{\psi} \ar[rr]_{\chi_1} & &
  H_1 \ar[ur]_{\psi_1} &  }$$

The homomorphism $\psi$ will be called a [**common extension**]{} of $\psi_1$ and $\psi_2$ of degree $1$. Denote by $ ({\zeta}_1 ,
{\zeta}{^{(0)}}_1) $ and $ ({\zeta}_2 , {\zeta}{^{(0)}}_2) $ the pairs of Markov partitions of the space $X_\rho$, which correspond to the homomorphisms $\psi_1$ and $\psi_2$. Here we omit the subscript “$\rho$” and mark the partitions and their elements by subscripts “$1$” and “$2$”, respectively.

We have to construct the desired $H$ and $\; \psi { : }H {\rightarrow}I
\;$ by means of the partitions $${\zeta}:= {\zeta}_1 \vee {\zeta}_2 \;\;,\;\;
 {\zeta}{^{(0)}} := {\zeta}_1^{(0)} \vee {\zeta}_2^{(0)} \;.$$ By the identification $H_1= I \times J_1$ and $H_2= I \times J_2$, we have $${\zeta}_1 = \{ D_1 (i,j_1) \}_{ (i,j_1) \in I \times J_1} \;\;,\;\;
 {\zeta}_1^{(0)} = \{ D_1 (j_1) \}_{ j_1 \in J_1}  \;\;,$$ $${\zeta}_2 = \{ D_2 (i,j_2) \}_{ (i,j_2) \in I \times J_2} \;\;,\;\;
 {\zeta}_2^{(0)} = \{ D_2 (j_2) \}_{ j_2 \in J_2}  \;\;,$$ and then the partition $ {\zeta}{^{(0)}} $ consists of all elements $$D(j) = D_1 (j_1) \cap D_2 (j_2) \;\;,\;\; j=(j_1,j_2) \in J \;.$$ where the set $J$ is defined by $$\label{eq J}
 J := \{ j=(j_1,j_2) \;{ : }\; p{^{(0)}} (j) :=
 m_\rho ( D_1 (j_1) \cap D_2(j_2)) >0 \} \subset J_1 \times J_2 \;.$$ For any $i \in I$ and $ j=(j_1,j_2) \in J $ we set $ f_i j := (f_{1,i}  j_1 ,f_{1,i} j_2 )$. Then $$\begin{split}
   D(f_i j) :=
 & D_1 (f_{1,i} j_1 ) \cap D _2(f_{2,i} j_2)
     \supseteq  D_1(i,j_1) \cap D_2(i,j_2)  =      \\
 & B(i) \cap T_\rho^{-1} (D_1 ( j_1) \cap D_2( j_2)) =
   B(i) \cap T_\rho^{-1} D(j)
\end{split}$$ Since $ {\delta}$ and $ T_\rho^{-1} {\varepsilon}$ are independent, this implies $$p{^{(0)}} (f_i j) = m_\rho ( D(f_i j)) \geq
 m_\rho(B(i) \cap T_\rho^{-1} D(j)) = \rho(i) p{^{(0)}} (j) \;.$$ Hence $f_i j \in J$ for all $j \in J$ and $ i \in I $ .

Thus we are able to define a stochastic graph $H := I \times J $ with $H{^{(0)}} := J$ such that for any $j \in H{^{(0)}} $ and $h=(i,j) \in H $ $$s(h) := j \;,\; t(h)
 := f_i (j) \;,\; p(h) := \rho (i) \;,\; \psi (h) := i \;.$$ The construction provides that $H$ is a $\rho$-uniform graph , $p{^{(0)}}$ is a stationary probability on $H{^{(0)}} $ and $\psi { : }H
{\rightarrow}I $ is a homomorphism of index $1$. Moreover, if we set $$\chi_1(h) := (i,j_1) \;,\; \chi_2(h) := (i,j_2) \;\;,\;\;
  h=(i,j_1,j_2) \in H= I \times J_1 \times J_2 \;,$$ then $\chi_1 { : }H {\rightarrow}H_1$ and $\chi_2 : H {\rightarrow}H_2$ are homomorphisms and Diagram \[diag degree 1\] commutes.

We shall use also the following sharpening of the previous theorem, which can be proved in a similar way.

\[degree 1 sharp\] Let $${\kappa}_1 { : }H_1 {\rightarrow}H_0  \;\;,\;\; {\kappa}_2 { : }H_2 {\rightarrow}H_0
   \;\;,\;\; \psi_0 { : }H_0 {\rightarrow}I$$ be homomorphisms of $\rho$-uniform graphs $H_1 \;,\; H_2$ and $H_0$ and suppose they are of degree 1. Then there exist a $\rho$-uniform graph $H$ and homomorphisms $\chi$, $\chi_1$ and $\chi_2 $ of degree 1, for which the following diagram commutes $$\label{diag degree 1 sharp}
 \xymatrix{
 & H_2  \ar[rr]^{{\kappa}_2} & & H_0 \ar[rr]^{\psi_0} & & I \\
 H \ar[ur]^{\chi_2} \ar[urrr]^{\chi} \ar[rr]_{\chi_1} & &
   H_1 \ar[ur]_{{\kappa}_1} & & & }$$

Note that this theorem holds without adding of homomorphism $\psi_0$ i.e. for graphs, which are not necessary $\rho$-uniform, but we do not use the fact in this paper.

 Extensions of Bernoulli graphs. {#ss4.2}
--------------------------------

Consider a very special case of the graph skew product construction ${{\bar H}}_a$ (see Example \[GSP\]), when the graph $H$ is the standard Bernoulli graph $(I,\rho)$. Let $ d \in {{\mathbb{N}}}$ and let $\; a { : }I {\rightarrow}{{\mathcal A}_d}\;$ be a function on $I$ with the values $\; a(i) , i \in I , \;$ in the group ${{\mathcal A}_d}$ of all permutations of $\; Y_d = \{1,2, \ldots ,d \} \;$. According to the general GSP-construction we have $\; {{\bar I}}_a = I
\times  Y_d \;$ , $\; {{{\bar I}}_a}{^{(0)}} = Y_d \;$ and $\; \pi { : }{{\bar I}}_a {\rightarrow}I \;$, where for any $ {{\bar h}}= (i,y) \in {{\bar I}}_a $ $$s({{\bar h}}) = y \;,\; t({{\bar h}}) = a(i)y \;,\; \pi ({{\bar h}}) = i \;,\;
 p({{\bar h}}) = \rho(i) \;,\, p{^{(0)}} (y) = d^{-1} \;.$$ The stochastic graph ${{\bar I}}_a$ is $\rho$-uniform and it is irreducible iff the group ${\Gamma}(a) $, generated by $\; \{ a(i) , i
\in I \} \subseteq {{\mathcal A}_d}\;$, is transitive on $Y_d$.

As it was noted in Section \[ss3.2\] (see Remark \[re GSP shift\]) the Markov shift $T_{{{\bar I}}_a} $ is isomorphic to the skew product ${{\bar T}}_{\rho,a}$ , which acts on $X_\rho \times Y_d$ by $$\label{bT rho a}
  {{\bar T}}_{\rho,a} (x,y) = (T_\rho x , {a(x_1)}^{-1} y) \;\;,\;\;
  x ={\{ x_n \}}_{n=1}^{\infty} \in X_\rho \;,\; y \in Y_d \;.$$

\[th rho cohom\] Let $\; \pi_k \;{ : }\; {{\bar I}}_{a_k} {\rightarrow}I \;,\; k = 1,2, \;$ be two $d$-extensions of the Bernoulli graph $(I,\rho)$, generated by functions $ a_k { : }I {\rightarrow}{{\mathcal A}_d}$, respectively. Let the functions $\; A_k { : }X_\rho {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2, \;$ are defined by $$\label{Am(x)}
 A_k(x) := {a_k(x_1)}^{-1}  \;\;,\;\; x
 ={\{x_n\}}_{n=1}^{\infty} \in X_\rho \;.$$ If there exists a measurable function $ W { : }X_\rho {\rightarrow}{{\mathcal A}_d}$ such that $$\label{eq rho cohom}
 A_2(x) \cdot W(x) = W(T_\rho x) \cdot A_1(x) \;\;,\;\; x \in X_\rho$$ then $W(x)$ does not depend on $x$ , i.e. $W(x) = w_0 \in {{\mathcal A}_d}$ a.e. on $X_\rho$. Thus $A_1$ and $A_2$ are cohomologous with respect to $T_\rho$ iff $a_1$ and $a_2$ are conjugate in ${{\mathcal A}_d}$, i.e. $\; a_2(i) \cdot w_0 = w_0 \cdot a_1(i) \;,\; i \in I \;$.

Note that the last equality means the equivalence of $a_1$ and $a_2$ in the sense of Definition \[cohom\] , since $I{^{(0)}} = \{ o
\}$.

To proof the theorem we need the following simple lemma.

\[le ext Ber\] Let ${\Gamma}$ be a finite group with the identity element $e$. For any $ b { : }I {\rightarrow}{\Gamma}$ denote $$\label{be(x)}
  B{^{(n)}}(x) \;:=\; b(x_1) \cdot b(x_2) \cdot \ldots \cdot b(x_n)
  \;\;,\;\;  x ={\{x_n\}}_{n=1}^{\infty} \in X_\rho$$ and $$\label{gwb(x)}
 {\omega}_b(x) \;:=\; min \{ n \in {{\mathbb{N}}}\;{ : }\; B{^{(n)}}(x) = e \}
 \;\;,\;\; x \in X_\rho  \;.$$ Then the transformation $T_\rho^{{\omega}_b}$, defined by $$X_\rho \ni x {\rightarrow}T_\rho^{{\omega}_b} x := {T_\rho}^{{\omega}_b(x)}x \in
X_\rho \;,$$ is an ergodic endomorphism of $X_\rho$, which is in fact a one-sided Bernoulli shift.

Consider the ${\Gamma}$-extension of the graph $(I,\rho)$ generated by $b$.

Namely, set $\; {{\tilde{I}}}_b :=  \; I \times  {\Gamma}\;$ and $\; {{{\tilde{I}}}_b}{^{(0)}} := {\Gamma}\;$ with $$s({\tilde{i}}) = (s(i) , {\gamma}) \;,\; t({\tilde{i}}) = (t(i) , b(i) \cdot {\gamma})
 \;,\; p({\tilde{i}}) = \rho(i)  \;,\; p{^{(0)}} ({\gamma}) = {|{\Gamma}|}^{-1}$$ The skew product endomorphism $ {{\tilde{T}}}_{\rho,b} $ corresponding to the stochastic graph $ {{\tilde{I}}}_b$, acts on the space $X_\rho \times {\Gamma}$ by $${{\tilde{T}}}_{\rho,b} (x , {\gamma}) = (T_\rho x \;,\; B(x) \cdot {\gamma})
  \;\;,\;\; x ={\{ x_n \}}_{n=1}^{\infty} \in X_\rho
  \;,\; {\gamma}\in {\Gamma}\;.$$ where $\; B(x) := {b(x_1)}^{-1} \;$. The skew product $ {{\tilde{T}}}_{\rho,b} $ can be identified with the Markov shift $T_{{{\tilde{I}}}_b}$ (see Remark \[re GSP shift\] ). Under this identification the partition ${\zeta}^{(0)}_{{{\tilde{I}}}_b}$ coincides with the partition $${\zeta}{^{(0)}} = \nu_{X_\rho} \times {\varepsilon}_{{\Gamma}} =
 \{{\tilde{E}}({\gamma}) \}_{{\gamma}\in {\Gamma}} \;,$$ where $${\tilde{E}}({\gamma}) :=
 X_\rho \times \{{\gamma}\} \subseteq  X_\rho \times {\Gamma}\;\;.\;\; {\gamma}\in {\Gamma}\;.$$ For any ${\gamma}\in {\Gamma}$ consider the endomorphism $ ({{\tilde{T}}}_{\rho,b})_{{\tilde{E}}({\gamma})} $ induced by $ {{\tilde{T}}}_{\rho,b} $ on the set $ {\tilde{E}}({\gamma}) $. Let $${\varphi}_{{\tilde{E}}({\gamma})} \;{ : }\; {\tilde{E}}({\gamma}) \ni (x,{\gamma}) {\rightarrow}{\varphi}_{{\tilde{E}}({\gamma})}(x,{\gamma}) \in {{\mathbb{N}}}$$ be the corresponding return functions (\[ret fun\]).

Since we use the left shifts on ${\Gamma}$ in the definition of the skew product $ {\tilde{T}}_b $ and they commute with the right shifts, we have $${\varphi}_{{\tilde{E}}({\gamma})}(x,{\gamma}) =
 {\varphi}_{{\tilde{E}}({\gamma}\cdot {\beta})}(x,{\gamma}\cdot {\beta})
 \;,\; {\gamma},{\beta}\in {\Gamma}\;,\; x \in X_\rho \;.$$ Hence with (\[gwb(x)\]) and (\[be(x)\]) we have $${\omega}^b(x) = {\varphi}_{{\tilde{E}}({\gamma})}(x,{\gamma}) \;\;,\;\;$$ and $${{{\tilde{T}}}_b}^{{\omega}^b(x)}(x,{\gamma}) = (T^{{\omega}^b(x)}x,{\gamma})
 \;.\; {\gamma}\in {\Gamma}\;,\; x \in X_\rho \;,$$ Thus $T^{{\omega}^b}$ is isomorphic to the endomorphisms $(T_{{{\tilde{I}}}_b})_{D({\gamma})}$ induced by the Markov shift $T_{{{\tilde{I}}}_b}$ on elements $D({\gamma})$ of the partition $ {{\zeta}^{(0)}_{{{\tilde{I}}}_b}}$. So that $T^{{\omega}^b}$ is a Bernoulli shift by Proposition \[Tu\].

[**Proof of Theorem \[th rho cohom\]** ]{} For given two functions $a_1$ an $a_2$ put $$b { : }I \ni i {\rightarrow}b(i) :=
 (a_1(i),a_2(i)) \in {\Gamma}:= {{\mathcal A}_d}\times {{\mathcal A}_d}\;.$$ and denote for $k=1,2$ $$A_k^{{\omega}_b}(x) :=
 A_k(T_\rho^{{\omega}_b(x)-1}x) \cdot \ldots \cdot A_k(T_\rho x)
 \cdot A_k(x)   \;\;,\;\; k=1,2$$ with $A_1$ and $A_2$ defined by (\[Am(x)\]). Then by definition of $b$ and ${\omega}_b$ we have $$A_2^{{\omega}_b}(x) := A_1^{{\omega}_b}(x) = e  \;\;,\;\; x \in X_\rho \;,$$ where $e$ is the identity of ${{\mathcal A}_d}$. The equality (\[eq rho cohom\]) implies $$A_2^{{\omega}_b}(x) \cdot W(x) = W(T_\rho^{{\omega}_b} x) \cdot A_1^{{\omega}_b}(x)$$ and then $\; W(T_\rho^{{\omega}_b} (x) = W(x) \;$ a.e. on $X_\rho$. By Lemma \[le ext Ber\] $\; T_\rho^{{\omega}_b} $ is ergodic and hence $W(x)$ is constant a.e. on $X_\rho$.

Equivalent extensions. {#ss4.3}
----------------------

Let $d \in {{\mathbb{N}}}$, and $H$ be an irreducible positively recurrent stochastic graph. Given a function $\; a { : }H \ni h {\rightarrow}a(h)
\in {{\mathcal A}_d}\;$ consider the graph skew product $d$-extension ${{\bar H}}_a$ of $H$ generated by the function $a$ (See Example \[GSP\]). Recall that the skew product endomorphism $ {{\bar T}}_{H,a} $, corresponding to $ {{\bar H}}_a $, acts on the space $X_H \times Y_d $ by $${{\bar T}}_{H,a} (x,y) = (T_H x , A(x) y)
  \;\;,\;\; x ={\{ x_n \}}_{n=1}^{\infty} \in X_H \;,\; y \in Y_d \;.$$ where $\; A(x) := {a(x_1)}^{-1} \;$. We shall use Definition \[cohom\]

\[Equ ext\] Let $\; \pi_k { : }{{\bar H}}_{a_k}  {\rightarrow}H \;,\; k = 1,2 \;$, be two $d$-extensions of $H$ generated by functions $a_1$ and $a_2$, respectively, and let the functions $\; A_k { : }X_H {\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$ are defined by $$\label{Ak = ak -1}
  A_k(x) := a_k(x_1)^{-1}
  \;\;,\;\; x ={\{ x_n \}}_{n=1}^{\infty} \in X_H \;.$$ Then the following two conditions are equivalent

1.  $A_1$ and $A_2$ cohomologous with respect to $T_H$, i.e. there exists a measurable map $\; W { : }X_H {\rightarrow}{{\mathcal A}_d}\;$ such that $$\label{A coho}
        A_2(x) \cdot W(x) = W(Tx) \cdot A_1(x) \;\;,\;\; x \in X_H \;,$$

2.  $a_1$ and $a_2$ cohomologous with respect to $H$, i.e. there exists a map $\; w { : }H{^{(0)}} {\rightarrow}{{\mathcal A}_d}\;$ such that $$\label{a coho}
        a_2(h) \cdot w(s(h)) = w(t(h)) \cdot a_1(h) \;,\; h \in H$$

It is obvious that (\[a coho\]) implies (\[A coho\]) with $$\label{W(x)}
 W(x) = w(t(x_1)) \;\;,\;\; x ={\{ x_n \}}_{n=1}^{\infty} \in X_H$$ That is (ii) implies (i).

To prove the converse, suppose that (\[A coho\]) holds with a suitable measurable function $\; W { : }X_H {\rightarrow}{{\mathcal A}_d}\;$.

We have to show that the function $W(x)$ necessarily has the form (\[W(x)\]), i.e. $W(x)$ is constant on each element $D(u) =
Z_1^{-1}(_uH)$ of the partition $\; {\zeta}_H{^{(0)}} = \{ D(u) \;,\; u
\in H{^{(0)}} \} \;$.

To this purpose we shall use induced endomorphisms, which are defined as follows.

Fix an atom $D(u)$ of the partition $ {\zeta}_H{^{(0)}} $ and consider the endomorphism $ T_u := (T_H)_{D(u)} $, induced by the shift $T_H$ on $D(u)$, see Section \[ss3.1\]. In accordance with the general definition (\[ret fun\]), the return function $${\varphi}_u(x)={\varphi}_{D(u)}(x) := min \{ n \geq 1 { : }T_H^{n}x \in D(u) \}
 \;\;,\;\; x \in D(u)$$ induces $T_u$ by $\; T_ux = T_H^{{\varphi}_u(x)}x \;$. By Proposition \[Tu\] the induced endomorphism $T_u$ is isomorphic to the Bernoulli shift $T_{\rho_u}$, where $\; I_u= \bigcup_{n=1}^\infty
I_{u,n} \;$, and $\; \rho_u =  \{\rho_u(i)\}_{i \in I_u} \;$ are defined by (\[I u n\]) and (\[rho u\]). That is, $I_{u,n}$ consists of all $\; h_1h_2 \ldots h_n \in H{^{(n)}}\;$ such that $$t(h_1) = s(h_n) = u \;\;,\;\; s(h_m) = t(h_{m+1}) \neq u \;,\;
  m = 1,2, \ldots ,n-1$$ and $$\rho_u(i) = p(h_1)  p(h_2) \ldots  p(h_n) \;\;,\;\;
        i = h_1h_2 \ldots h_n \in I_{u,n} \;.\; n \in {{\mathbb{N}}}\;.$$ For any $u \in H{^{(0)}}$ and $k=1,2$ set $$A_k^{{\varphi}_u}(x) := A_k(T^{{\varphi}_u(x)-1}x)
  \cdot \ldots \cdot A_k(Tx) \cdot A_k(x)
   \;\;.\;\; x \in D(u)$$ and $$a_k^u (i) := a_k(h_1) \cdot a_k(h_2) \cdot \ldots \cdot a_k(h_n)
 \;\;,\;\;  i = h_1h_2 \ldots h_n \in I_{u,n} \;.$$ Then $$A_k^{{\varphi}_u}(x) = {a_k^u(i)}^{-1} \;\;,\;\;
 x \in B_u(i) \subseteq D(u) \;.\; i \in I_u \;,$$ where $$B_u(i) := \{ x ={\{ x_n \}}_{n=1}^{\infty} \in D(u) \;{ : }\;
   (x_1x_2 \ldots x_n) = i \in I_{u,n} \;.$$ Then the equality (\[A coho\]) implies $$\label{Au cohom}
 A_2^{{\varphi}_u}(x) \cdot W(x) =W(T_u x) \cdot A_1^{{\varphi}_u}(x)
 \;\;.\;\; x \in D(u) \;,$$ i.e. $A_1^{{\varphi}_u}$ and $A_2^{{\varphi}_u}$ are cohomologous on $D(u)$ with respect to $ T_u = T_H^{{\varphi}_u} $.

Since for any fix $u \in D(u)$ the partition $\; {\zeta}_u = \{ B_u(i)
\}_{i \in I_u} \;$ is a one-sided Bernoulli generator for $T_u$, we may apply Theorem \[th rho cohom\] with the Bernoulli shift $
T_u = T_{\rho_u}$ and with the functions $a_k^u \;,\; k=1,2$. Therefore, it follows from (\[Au cohom\]) that there exists $\;
w(u) \in {{\mathcal A}_d}\;$ such that $\; W(x)=w(u) \;$ a.e. on $ D(u) $.

For every $u$ we have now an element $w(u)$ such that $ W(x) =
w(u) = w(t(x_1))$ for a.e. $ x \in D(u) $. Hence $ W(x) $ is of the form (\[W(x)\]), $\; W(T_H x) =
w(s(x_1)) \;$. Thus (\[A coho\]) implies (\[a coho\]).

As a consequence we obtain

\[Equ ext 1\] Let $\; \pi_k { : }{{\bar H}}_{a_k}  {\rightarrow}H \;,\; k = 1,2 \;$, be two $d$-extensions of $H$ generated by functions $a_1$ and $a_2$, respectively. Let also $\psi { : }H {\rightarrow}I $ be an homomorphism of degree $1$. Suppose $ d = d({{\bar T}}_{H,a_1}) =
d({{\bar T}}_{H,a_2}) $. Then the endomorphisms ${{\bar T}}_{H,a_1}$ and ${{\bar T}}_{H,a_2}$ are isomorphic iff $a_1$ and $a_2$ cohomologous with respect to $H$.

Since $d(\psi) = 1$ the factor map $\Psi := \Phi_\psi
{ : }X_H {\rightarrow}X_I$ is an isomorphism. Consider two skew products over the Bernoulli shift $T_\rho$ $${{\bar T}}_k (x,y) = ( T_\rho x , B_k(x) y)
 \;\;,\;\; (x,y) \in X_\rho \times Y_d
 \;\;,\;\; k = 1,2$$ where $ B_k(x) := A_k(\Psi^{-1}x) $ and $A_k$ induced by $a_k$ as above (\[Ak = ak -1\]). Each of the shifts $T_{{{\bar H}}_{a_k}}$ is a simple $\rho$-uniform endomorphism by Theorem \[simp mar\]. The skew products ${{\bar T}}_{H,a_k}$ as well as the shifts $T_{{{\bar H}}_{a_k}}$, are isomorphic to ${{\bar T}}_k$. They are $\rho$-uniform endomorphisms and $d = d({{\bar T}}_1) = d({{\bar T}}_2).$ By Theorem \[simple\] ${{\bar T}}_1$ and ${{\bar T}}_2$ are isomorphic iff the functions $B_1$ and $B_2$ are cohomologous with respect to $T_\rho$. This means that the functions $A_1$ and $A_2$ are cohomologous with respect to $T_H$. Finally, by Theorem \[Equ ext\] the last condition holds iff $a_1$ and $a_2$ cohomologous with respect to $H$.

 ${{\mathbf{G}}{\mathbf{S}}{\mathbf{P}}}$-extensions and persistent ${\mathbf{d}}$-partitions. {#ss4.4}
----------------------------------------------------------------------------------------------

Let $H$ be a stochastic graph and $(I,\rho)$ a standard Bernoulli graph. In this section we study extensions of the form $$\label{pi psi}
(\pi,\psi) \;{ : }\; \xymatrix{ {{\bar H}}\ar[r]^{\pi} & H \ar[r]^{\psi} & I}$$ where the graph $H$ be an extension of the Bernoulli graph $(I,\rho)$ by a homomorphism $\psi$ of degree $ d(\psi) = 1 $ and $ {{\bar H}}= {{\bar H}}_a $ be a graph skew product $d$-extension of $H$ generated by a function $ a { : }H {\rightarrow}{{\mathcal A}_d}$ (See Example \[GSP\]). The diagrams of the above form (\[pi psi\]) will be referred to ${\boldsymbol{(}}{\boldsymbol{\pi}}, {\boldsymbol{\psi}}{\boldsymbol{)}}$[**-extensions**]{}. We assume that the graph $ {{\bar H}}$ is irreducible, i.e. the corresponding Markov shift $T_{{\bar H}}$ and skew product ${{\bar T}}_{H,a} $ are ergodic.

Fixing an extension (\[pi psi\]) and setting $\; J = H{^{(0)}} \;$, we identify $H$ with $ I \times J $ such that $$\psi (h) = i \;,\; s(h) = j \;,\; t(h) = f_i (j)
 \;,\; p(h) = \rho(i)$$ for any $ h = (i,j) \in H = I \times J $. Here the maps $ f_i { : }J {\rightarrow}J $ are uniquely determined by $$f_ij = t(i,j) \;\;,\;\; (i,j) \in  I \times J$$ and the semigroup $ {{\mathcal S}}(\psi) $, generated by $ \{ f_i \;,\; i
\in I \} $ is $1$-contractive, since $ d(\psi) = 1 \;$ (Theorem \[d(phi)\]).

The $d$-extension $ {{\bar H}}= {{\bar H}}_a $ is described now as follows: $$\label{bar H}
 {{\bar H}}= I \times J \times Y_d \;\; , \;\;
 {{\bar H}}{^{(0)}} = H{^{(0)}} \times Y_d = J \times Y_d \;,$$ where for any $ {{\bar h}}= (i,j,y) $ $$\label{stp bar H}
  s({{\bar h}}) = (j,y)   \;,\; t({{\bar h}}) = (f_ij , a(i,j)y) \;,\;
  p({{\bar h}}) = \rho(i) \;,\; a(h) = a(i,j)$$ The homomorphisms $\psi$, $\pi$ and $\phi = \psi \circ \pi $ are defined by $$\pi ({{\bar h}}) = h = (i,j) \;\;,\;\; \pi{^{(0)}} (j,y) = j \;\;,\;\;
 \phi ({{\bar h}}) = \psi (h) = i \;,$$ where $ d(\phi) = d(\pi) = d $ and the diagram $$\label{diag I J Yd}
\xymatrix{
 I \times J \times Y_d \ar[d]^{\pi}  \ar[dr]^{\phi} &   \\
 I \times J \ar[r]^{\psi}                           & I  }$$ commutes. The semigroup ${{\mathcal S}}(\phi)$ can be described now as a $d$-extension ${{\bar {{\mathcal S}}}}= {{\bar {{\mathcal S}}}}(\pi,\psi)$ of the semigroup ${{\mathcal S}}(\psi)$.

Set $$\label{bfi (j,y)}
 {{\bar f}}_i(j,y) := t(i,j,y) = (f_i j \;,\; a(i,j) y)
 \;,\; (j,y) \in J \times Y_d \;,\; i \in I  \;.$$ The maps $ {{\bar f}}_i $ act on $J \times Y_d $.

The semigroup ${{\bar {{\mathcal S}}}}$, generated by $\; {{\bar f}}_i \;,\; i \in I \;$, consists of all maps of the form: $$\{ {{\bar f}}_{i_1i_2 \ldots i_n} \;,\; i_1i_2 \ldots i_n \in I^n \;,\;
   n \in {{\mathbb{N}}}\} \;,$$ where $${{\bar f}}_{i_1i_2 \ldots i_n}(j,y) = (f_{i_1i_2 \ldots i_n} j ,
 a(i_1i_2 \ldots i_n,j) y)$$ and $$a(i_1i_2 \ldots i_n,j) := a(i_1,f_{i_2i_3 \ldots i_n} j )
 \ldots a(i_{n-1},f_{i_n} j ) a(i_n,j) \;.$$ Note that $\; {{\mathcal S}}(\psi) \ni f {\rightarrow}{{\bar f}}\in {{\bar {{\mathcal S}}}}\;$ is an isomorphism between the semigroups.

\[S(phi) bar H\] The semigroup ${{\bar {{\mathcal S}}}}$ is $d$-contractive and its persistent $d$-sets are of the form $${{\mathcal L}}({{\bar {{\mathcal S}}}}) = \{ L_j , j \in J \} \;\;,\;\; L_j := \{ j \} \times Y_d  \;.$$

By Theorem \[d(phi)\] the semigroup $ {{\bar {{\mathcal S}}}}$ is $d$-contractive and ${{\mathcal S}}(\psi)$ is $1$-contractive, since $ d(\phi) = d $ and $ d(\psi) = 1 $.

For any finite set $ F \subseteq J \times Y_d $ the set $ E :=
\pi{^{(0)}} (F) \subseteq J $ is also finite. Since the semigroup ${{\mathcal S}}(\psi)$ is $1$-contractive there exist $ i_1i_2 \ldots i_n \in
I^n $ and $j \in J$ such that $\; f_{i_1i_2 \ldots i_n}(E) = \{j\}
\;$ and hence $\; {{\bar f}}_{i_1i_2 \ldots i_n}(F) \subseteq L_j \;$. On the other hand $ d = |L_j| = |{{\bar f}}_i(L_j)| $ for all $i \in I ,
j \in J$. Thus the sets $L_j$ and only they are persistent sets for the semigroup ${{\bar {{\mathcal S}}}}$.

For every $E \subseteq J$ set $ {{\bar E}}:= {\pi{^{(0)}}}^{-1}E = E \times
Y_d $.

\[pers part\] Let the semigroup ${{\bar {{\mathcal S}}}}$ be as above.

1.  A subset $ R $ of $ {{\bar H}}{^{(0)}} = J \times Y_d $ will be called [**transversal**]{} with respect to $\pi{^{(0)}}$ if $ \pi{^{(0)}} (R) = H{^{(0)}} = J $ and the restriction $ \pi{^{(0)}} {|}_R { : }R {\rightarrow}J $ is a bijection. A partition $\; r = \{ R_1,R_2, \ldots ,R_d \} \;$ will be called [**transversal**]{} with respect to $\pi{^{(0)}}$ if all the set $R_1,R_2, \ldots ,R_d$ are transversal.

2.  A transversal partition $r$ will be called [ **persistent**]{} with respect to semigroup $ {{\bar {{\mathcal S}}}}$, if for every transversal partition $r_1$ and every finite subset $E \subseteq J$ there exists $ {{\bar f}}\in {{\bar {{\mathcal S}}}}$ such that $\; {{\bar f}}^{-1}r_1 \;{|}_{{\bar E}}= r \;{|}_{{\bar E}}\;.$

Denote by ${{\mathcal R}}$ the set of all transversal partitions and by ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ the set of all persistent partitions for the semigroup ${{\bar {{\mathcal S}}}}$.

If a set $R$ is transversal then for any $i \in I$ the set ${{\bar f}}^{-1}R$ is transversal. Hence for any $r = \{ R_1,R_2, \ldots
,R_d \} \in {{\mathcal R}}$ and $ {{\bar f}}\in {{\bar {{\mathcal S}}}}$ we have $${{\bar f}}^{-1} r := \{ \; {{\bar f}}^{-1}R_1 , {{\bar f}}^{-1}R_2, \ldots ,
 {{\bar f}}^{-1}R_d \; \} \in {{\mathcal R}}\;.$$ Further we shall use this action $${{\mathcal R}}\ni r \; {\rightarrow}\;  {{\bar f}}^{-1} r \in {{\mathcal R}}\;\;,\;\; {{\bar f}}\in {{\bar {{\mathcal S}}}}$$ of the semigroup ${{\bar {{\mathcal S}}}}$ on ${{\mathcal R}}$. The following lemma shows that $ {{\mathcal R}}({{\bar {{\mathcal S}}}})$ is an attracting set for ${{\mathcal R}}$ with respect to the action in a natural sense.

\[gL(phi)\]

1.  The set ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ is not empty.

2.  ${{\bar f}}^{-1} {{\mathcal R}}({{\bar {{\mathcal S}}}}) \subseteq  {{\mathcal R}}({{\bar {{\mathcal S}}}})$ for all ${{\bar f}}\in {{\bar {{\mathcal S}}}}$

3.  ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ is the least subset of ${{\mathcal R}}$ with the property (ii).

Consider a subset ${{\mathcal R}}_0 ({{\bar {{\mathcal S}}}})$ of ${{\mathcal R}}$ consisting of all $r \in {{\mathcal R}}$ having the following property:

1.  For any finite subset $E \subseteq J $ there exists $\; f \in {{\mathcal S}}(\psi) $ such that $f(E)$ is a singleton, i.e. $|f(E)|=1$, and $ r \;{|}_{{\bar E}}=  {{\bar f}}^{-1}{\varepsilon}\;{|}_{{\bar E}}\;$, where $ {{\bar E}}:= E \times Y_d $ and $ {\varepsilon}= {\varepsilon}_{J \times Y_d} $.

We show that ${{\mathcal R}}({{\bar {{\mathcal S}}}}) = {{\mathcal R}}_0({{\bar {{\mathcal S}}}}) \neq \emptyset$.

Take a sequence $\; E_n \nearrow J \;,\; |E_n| < \infty \;$. Since $d({{\mathcal S}}(\psi)) = 1 \;$ we can find a sequence $g_n \in {{\mathcal S}}(\psi)$ such that for all $n \in {{\mathbb{N}}}$ and $ f_n := g_n \cdot \ldots \cdot g_2 \cdot g_1$, the set $f_n (E_n)$ is single-point, i.e. $|f_n (E_n)|=1$. Using the decreasing sequence of partitions $${\varepsilon}\geq {{\bar f}}_1^{-1} {\varepsilon}\geq {{\bar f}}_2^{-1} {\varepsilon}\geq \; \ldots \;
 \geq {{\bar f}}_n^{-1} {\varepsilon}\geq \ldots$$ set $\; r_0 := \bigwedge_{n=1}^{\infty} {{{\bar f}}_n}^{-1}{\varepsilon}\;$. Since $|f_n (E_n)|=1$ the restriction $r_0 \;{|}_{{{\bar E}}_n} $ consists of $d$ sets, whose projections on $J$ are $E_n$. Hence $
r_0 \in {{\mathcal R}}$ and $r_0 \;{|}_{{{\bar E}}_n} = {{\bar f}}_n^{-1}{\varepsilon}\;{|}_{{{\bar E}}_n} $. We see that $r_0 \in {{\mathcal R}}_0({{\bar {{\mathcal S}}}})$, i.e. ${{\mathcal R}}_0$ is not empty,

Let $r \in {{\mathcal R}}_0({{\bar {{\mathcal S}}}})$ and $r_1 \in {{\mathcal R}}$. For any finite subset $E \subseteq J$ there exists ${{\bar f}}\in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ such that $ r
\;{|}_{{\bar E}}=  {{\bar f}}^{-1}{\varepsilon}\;{|}_{{\bar E}}\;$. Then $${{\bar f}}^{-1}r_1 \;{|}_{{\bar E}}\leq {{\bar f}}^{-1}{\varepsilon}\;{|}_{{\bar E}}= r \;{|}_{{\bar E}}\;,$$ Since each of the partitions consists of $d$ elements, we have also ${{\bar f}}^{-1}r_1 \;{|}_{{\bar E}}= r \;{|}_{{\bar E}}$. Hence $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$.

Conversely, let $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ and $E$ be a finite subset of $J$. There are exist ${{\bar f}}\in {{\bar {{\mathcal S}}}}$ and $r_1 \in {{\mathcal R}}$ such that $
r_1 \;{|}_{{\bar E}}= {{\bar f}}^{-1}{\varepsilon}\;{|}_{{\bar E}}\;$. On the other hand, since $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$, we can choose ${{\bar f}}_1
\in {{\bar {{\mathcal S}}}}$ for which $ {{\bar f}}_1^{-1}r_1 \;{|}_{{\bar E}}= r \;{|}_{{\bar E}}$. Hence $$r \;{|}_{{\bar E}}= {{\bar f}}_1^{-1}r_1 = {{\bar f}}_1^{-1}{{\bar f}}^{-1}{\varepsilon}\;{|}_{{\bar E}}= ({{\bar f}}^{-1}{{\bar f}}_1)^{-1}{\varepsilon}\;{|}_{{\bar E}}.$$ We see that $r \in {{\mathcal R}}_0({{\bar {{\mathcal S}}}})$ and thus ${{\mathcal R}}({{\bar {{\mathcal S}}}}) = {{\mathcal R}}_0$ and Part $(i)$ follows.

Parts $(ii)$ and $(iii)$ follow in the same manner by the definition of ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ and by the equality ${{\mathcal R}}({{\bar {{\mathcal S}}}}) =
{{\mathcal R}}_0({{\bar {{\mathcal S}}}})$.

 Irreducible ${\mathbf{d}}$-extensions. {#ss4.5}
---------------------------------------

In this section we continue to study $(\pi,\psi)$-extensions of the form (\[pi psi\]) $$(\pi,\psi) \;{ : }\; \xymatrix{
 {{\bar H}}\ar[r]^{\pi} & H \ar[r]^{\psi} & I } \;,$$ where the graph $H$ is an extension of the Bernoulli graph $(I,\rho)$ by a homomorphism $\psi$ of degree $ 1 $ and $ {{\bar H}}=
{{\bar H}}_a $ be a GSP $d$-extension of $H$, generated by a function $ a
{ : }H {\rightarrow}{{\mathcal A}_d}$.

Fix $d$ and $(I,\rho)$ and consider the set $\; {{\mathcal Ext}^d(I,\rho)}\;$ of all $(\pi,\psi)$-extensions of the form (\[pi psi\]). This set is equipped with a natural partial order and with an equivalence relation as follows

\[partial order\] Let $\; (\pi,\psi) { : }\xymatrix{ {{\bar H}}\ar[r]^{\pi} & H \ar[r]^{\psi} & I } \;$ and $\; (\pi_1,\psi_1) { : }\xymatrix{{{\bar H}}_1 \ar[r]^{\pi_1} & H_1 \ar[r]^{\psi_1} & I } \;$ be two $(\pi,\psi)$-extensions from ${{\mathcal Ext}^d(I,\rho)}$. Let $a$ and $a_1$ be the functions, which generate the extensions ${{\bar H}}$ and ${{\bar H}}_1$, respectively.

1.  A homomorphism $\; {{\bar {\kappa}}}{ : }{{\bar H}}{\rightarrow}{{\bar H}}_1 \;$ is said to be a [**trivializable**]{} $d$-extension of a homomorphism $\; {\kappa}{ : }H {\rightarrow}H_1 \;$, if the square part of Diagram \[diag order\] ( below ) commutes and the functions

    $a_1 \circ \chi$ and $a$ are cohomologous with respect to $H$.

2.  We shall say that $$(\pi_1,\psi_1) \; \preceq \; (\pi,\psi)$$ if there is a commutative diagram $$\label{diag order}
       \xymatrix{
        {{\bar H}}\ar[d]^{{{\bar {\kappa}}}} \ar[r]^{\pi}
      & H \ar[d]^{{\kappa}} \ar[dr]^{\psi} & \\
        {{\bar H}}_1 \ar[r]^{\pi_1}
      & H_1 \ar[r]^{\psi_1}           & I }\;,$$ where $\; {{\bar {\kappa}}}\in {{\mathcal Hom}}({{\bar H}},{{\bar H}}_1) \;$ is a trivializable $d$-extension of $\; {\kappa}\in {{\mathcal Hom}}(H,H_1) \;$.

3.  We shall say that $$(\pi_1,\psi_1) \; \sim \; (\pi,\psi) \;$$ if there is commutative Diagram \[diag order\], where both $\; {\kappa}\;{ : }\; H {\rightarrow}H_1 \;$ and its $d$-extension $\; {{\bar {\kappa}}}\;{ : }\; {{\bar H}}{\rightarrow}{{\bar H}}_1 \;$ are isomorphisms.

In connection with Part (i) of the definition, note that an extension $\; {{\bar {\kappa}}}\;{ : }\; {{\bar H}}{\rightarrow}{{\bar H}}_1 \;$ is trivializable iff it is equivalent to a trivial extension of $\; {\kappa}\;:\; H
{\rightarrow}H_1 \;$ (see Remark \[triv exten\]).

It can be checked also that $\; (\pi_1,\psi_1) \preceq (\pi,\psi)
\;$ and $\; (\pi,\psi) \preceq (\pi_1,\psi_1) \;$ imply $\;
(\pi_1,\psi_1) \sim (\pi,\psi) \;$, but we do not use the fact in this paper.

Our aim now is to describe “minimal” elements of $\; (\; {{\mathcal Ext}^d(I,\rho)}\;,\; \preceq \;) \;$.

\[irreduc\] An extension $(\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$ is called [**irreducible**]{} if $(\pi_1,\psi_1) \sim (\pi,\psi)$ as soon as $ (\pi_1,\psi_1) \in
{{\mathcal Ext}^d(I,\rho)}$ and $(\pi_1,\psi_1) \preceq (\pi,\psi)$.

\[reduc ext\] For any $\; (\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}\;$ there exists a unique up to equivalence irreducible $(\pi,\psi)$-extension $\; (\pi_*,\psi_*) \in {{\mathcal Ext}^d(I,\rho)}\;$ such that $\; (\pi_*,\psi_*) \preceq (\pi,\psi) \;$.

To prove the theorem we fix a pair $(\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$ and again use the identification (\[bar H\]). Namely, $$\label{diagr I J Yd}
 (\pi, \psi) \;\;:\;\;
 \xymatrix{
   {{\bar H}}= I \times J \times Y_d \ar[r]^-\pi
 & H = I \times J \ar[r]^-\psi & I }$$ where $H{^{(0)}} = J$ and ${{\bar H}}{^{(0)}} = H{^{(0)}} \times Y_d = J \times Y_d $ as in Section \[ss4.4\].

We construct the desired irreducible $(\pi_*,\psi_*)$-extension and a corresponding commutative diagram $$\label{diag reduc ext}
 \xymatrix{
    {{\bar H}}\ar[d]^{{{\bar {\kappa}}}_*} \ar[r]^{\pi}
  & H \ar[d]^{{\kappa}_*} \ar[dr]^{\psi} &   \\
    {{\bar H}}_* \ar[r]^{\pi_*}
  & H_* \ar[r]^{\psi_*}             & I  }$$ by means of the semigroup $ {{\bar {{\mathcal S}}}}= {{\bar {{\mathcal S}}}}(\pi,\psi) $ and its persistent partitions ${{\mathcal R}}({{\bar {{\mathcal S}}}})$.

\[reduc part\] A partition $\xi$ of $J=H{^{(0)}}$ is called [**reducing**]{} partition if the following two conditions hold

1.  $f^{-1}\xi \leq \xi$ for all $f \in {{\mathcal S}}(\psi)$, i.e. $\xi$ is ${{\mathcal S}}(\psi)$-invariant

2.  For any element $C \in \xi$ denote ${{\bar C}}:= \pi^{-1}C$ and let $r {|}_{{\bar C}}$ be the restriction of the partition $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ on the set ${{\bar C}}$. Then all the partitions $\; r {|}_{{\bar C}}\;,\; r \in {{\mathcal R}}({{\bar {{\mathcal S}}}}) \;$ coincide with each other.

Consider the set $\Xi$ of all reducing partitions $\xi$ on $H{^{(0)}}$.

For any $\xi \in \Xi$ we have $\; {\pi{^{(0)}}}^{-1}\xi = \xi \times \nu_{Y_d} \;$ and the partition $\; {\pi{^{(0)}}}^{-1}\xi \vee r \;$ does not depend on the choice of $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$. So that we may set $$\label{bxi}
  {{\bar \xi}}:= {\pi{^{(0)}}}^{-1}\xi \vee r \;\;,\;\; \xi \in \Xi$$ and ${{\bar \Xi}}:= \{{{\bar \xi}}\;{ : }\; \xi \in \Xi \}$ on ${{\bar H}}{^{(0)}}$.

Since $\xi$ is ${{\mathcal S}}(\psi)$-invariant and ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ is ${{\bar {{\mathcal S}}}}$-invariant by Lemma \[gL(phi)\], the partition ${{\bar \xi}}$ is also ${{\bar {{\mathcal S}}}}$-invariant.

Therefore we may introduce the [**factor pair**]{} $$\label{factor pair}
 \xymatrix{
   {{\bar H}}{/}_{{\bar \xi}}\ar[r]^{\pi{/}_\xi}
 & H{/}_\xi \ar[r]^{\psi{/}_\xi} & I }$$ Namely, we set $$H{/}_\xi := I \times J{/}_\xi \;\;,\;\;
 {{\bar H}}{/}_{{\bar \xi}}:= I \times J{/}_\xi \times Y_d$$ Any element of ${{\bar \xi}}$ consists of $d$ elements of the form $\;
R_y^C \;,\; y \in Y_d \;$, where $C \in \xi$ and $\pi{^{(0)}}(R_y^C) =
C$. Hence. by possibly passing to an equivalent extension, we may assume that $R_y^C = C \times \{y\}$, i.e. ${{\bar \xi}}= \xi \times
{\varepsilon}_{Y_d}$. This means that the function $a = a(i,j)$, generating the extension ${{\bar H}}= {{\bar H}}_a$, does not depend on $j$ on the elements of $\xi$. Hence the equalities (\[stp bar H\]) and (\[bfi (j,y)\]) well define $a{/}_\xi$ and $ {{\bar H}}{/}_{{\bar \xi}}:=
(H{/}_\xi)_{a{/}_\xi}$. Thus we have shown

\[natur proj\] For any $\xi \in \Xi$ the natural projections $${\pi_{{\bar \xi}}}{^{(0)}} { : }{{\bar H}}{^{(0)}} {\rightarrow}{{\bar H}}{^{(0)}}{/}_{{\bar \xi}}\;\;,\;\;
 {\pi_\xi}{^{(0)}} { : }H{^{(0)}} {\rightarrow}H{^{(0)}}{/}_\xi$$ uniquely determine $(\pi{/}_\xi,\psi{/}_\xi) \in {{\mathcal Ext}^d(I,\rho)}$ such that $ (\pi{/}_\xi,\psi{/}_\xi) \preceq (\pi,\psi) $ with the coresponding commutative diagram $$\label{diag /xi}
  \xymatrix{
     {{\bar H}}\ar[d]^{\pi_{{\bar \xi}}} \ar[r]^{\pi}
  & H \ar[d]^{\pi_\xi} \ar[dr]^{\psi} &  \\
     {{\bar H}}{/}_{{\bar \xi}}\ar[r]^{\pi{/}_\xi}
  & H{/}_\xi \ar[r]^{\psi{/}_\xi}     & I }$$

Conversely

\[convers\] For any $\; (\pi_1,\psi_1) \; \preceq \; (\pi,\psi) \;$ there exists $\xi \in \Xi$ such that $(\pi{/}_\xi,\psi{/}_\xi) \sim (\pi_1,\psi_1)$

Take the map $ {\kappa}{^{(0)}} { : }H{^{(0)}} {\rightarrow}{H_1}{^{(0)}} $ induced by homomorphism $ {\kappa}{ : }H {\rightarrow}H_1 $ from Diagram \[diag ext\] and set $\xi := {{\kappa}{^{(0)}}}^{-1}{\varepsilon}_{{H_1}{^{(0)}}}$. Then $\xi \in \Xi$ and it is desired

[**Proof of Theorem \[reduc ext\].**]{} It is easily to see that $\Xi$ is a lattice, i.e. $ \xi_1 \vee \xi_2 \in \Xi $ and $ \xi_1
\wedge \xi_2 \in \Xi $ for all $\xi_1 , \xi_2 \;\in\;\Xi $. Herewith, $\Xi$ has the least element. Denote the least element by $\xi_* $ and let $ {{\bar \xi}}_* := \overline{(\xi_*)}$ be the corresponding partition of ${{\bar H}}{^{(0)}}$. Note that $ {{\bar \xi}}_*$ is the least element of ${{\bar \Xi}}$. Herewith $ {{\bar \xi}}_*$ is the least partition of ${{\bar H}}{^{(0)}}$ such that for all $r \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ and every $C \in \xi$ the restriction $r \;{|}_{{\bar C}}$ consists precisely of $d$ elements.

Putting $\xi = \xi_*$ in Diagram \[diag /xi\] (Proposition \[natur proj\]) we obtain Diagram \[diag reduc ext\] with $$H_* =   H{/}_{\xi_*}    \;\;,\;\; {{\bar H}}_* = {{\bar H}}{/}_{{{\bar \xi}}_*}
 \;\;,\;\; \pi_* = \pi{/}_{\xi_*}   \;\;,\;\; \psi_* =
 \psi{/}_{\xi_*} \;.$$ and $ (\pi_*,\psi_*) \preceq (\pi,\psi) $.

Using by the above propositions and Lemma \[gL(phi)\], we see that the pair $(\pi_*,\psi_*)$ is irreducible and that it is the only (up to equivalence) irreducible pair majorized by $
(\pi,\psi) $.

\[irred ext\] The above arguments show that a pair $ (\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$ is irreducible iff $ (\pi_*,\psi_*) = (\pi,\psi) $, i.e. iff $ \xi_*
= {\varepsilon}_{H{^{(0)}}}$. The last equality means that the persistent partitions $ {{\mathcal R}}({{\bar {{\mathcal S}}}}) $ separate the points of $H{^{(0)}}$ in the following sense: for every pair $ u_1,u_2 \in H{^{(0)}} $ there exist $R_1 \in r_1 \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ and $R_2 \in r_2 \in {{\mathcal R}}({{\bar {{\mathcal S}}}})$ such that $${\pi{^{(0)}}}^{-1}(u_1) \cap R_1 \cap R_2 \neq \emptyset \;\;,\;\;
 {\pi{^{(0)}}}^{-1}(u_2) \cap R_1 \cap R_2 = \emptyset \;.$$

Canonical form and classification. {#s5}
==================================

 Main Theorems. {#ss5.1}
---------------

The following two theorems claim the existence and uniqueness of the canonical form of $\rho$-uniform one-sided Markov shifts.

\[canon form\] Let $G$ be a $\rho$-uniform stochastic graph, which is irreducible and positively recurrent. Then there exists a $(\pi,\psi)$-extension $$\label{pi,psi}
 (\pi,\psi) \;{ : }\;
 \xymatrix{ {{\bar H}}\ar[r]^{\pi} & H \ar[r]^{\psi} & I }$$ such that

1.  The shifts $T_G$ and $T_{{\bar H}}$ are isomorphic,

2.  $(\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$, where $d = d(T_G)$ is the minimal index of the shift $T_G$,

3.  The extension $(\pi,\psi) $ is irreducible.

Combining the results of Theorems \[reduc ext\] and \[phi bar d(T)\] we obtain from Diagrams \[diag reduc ext\] and \[diag bar H Gn\] the following commuting diagram $$\label{diag main}
   \xymatrix{
          {{\bar H}}\ar[dd]^{{{\bar {\kappa}}}} \ar[rd]^{\pi} \ar[rr]^{{{\bar \psi}}}
     &&   G{^{(n)}}\ar[dd]^{\phi} \ar[rr]^{\pi{^{(n)}}}
     &&   G  \\
     &    H \ar[d]^{{\kappa}} \ar[dr]^{\psi}       &    &&     \\
          {{\bar H}}_* \ar[r]^{\pi_*}
     &    H_* \ar[r]^{\psi_*}        &  I &&      }$$ Here, $\pi$, $\pi_*$ and $\phi$ are homomorphisms of degree $d = d(T_G)$, all other homomorphisms are of degree $1$, and the extension $(\pi_*,\psi_*) \in {{\mathcal Ext}^d(I,\rho)}$ is irreducible.

Since $G$ and $ {{\bar H}}_* $ have a common extension ${{\bar H}}$ of degree $1$, the shifts $T_G$ and $T_{{{\bar H}}_*}$ are isomorphic. Thus the the extension $(\pi_*,\psi_*) $ is desired.

\[def canon form\] We shall say that $T_{{\bar H}}$ is a [**canonical form**]{} of the shift $T_G$, if there exists an extension (\[pi,psi\]) satisfying the conditions of Theorem \[canon form\]. Herewith the graph ${{\bar H}}$ is said to be the [**canonical graph**]{} for $T_G$.

Theorem \[canon form\] states the existence of the canonical form. Turn to the uniqueness.

\[classification\] Let $G_1$ and $G_2$ be two $\rho$-uniform stochastic graphs, which are irreducible and satisfy the positive recurrence condition. Suppose the shifts $T_{G_1}$ and $T_{G_1}$ are represented in the canonical form $T_{{{\bar H}}_1}$ and $T_{{{\bar H}}_2}$, respectively, and let $$\label{pi12,psi12}
  (\pi_k,\psi_k) \;{ : }\;
     \xymatrix{
     {{\bar H}}_k \ar[r]^{\pi_k} & H \ar[r]^{\psi_k} & I }  \;\;,\;\; k=1,2$$ be corresponding canonical $(\pi,\psi) $-extensions.

Then the following conditions are equivalent

1.  The shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic, $(T_{G_1} \sim T_{G_2})$.

2.  The graphs ${{\bar H}}_1$ and ${{\bar H}}_2$ are isomorphic, $({{\bar H}}_1 \sim {{\bar H}}_2)$.

3.  The extensions $(\pi_1,\psi_1) $ and $(\pi_1,\psi_1) $

    are equivalent,$ ( (\pi_1,\psi_1) \sim (\pi_2,\psi_2) ) $.

By the definition we have $T_{G_1} \sim T_{{{\bar H}}_1}$ , $T_{G_2} \sim T_{{{\bar H}}_2}$ and $$(\pi_1,\psi_1) \sim (\pi_2,\psi_2) \;\; {\Longrightarrow}\;\; {{\bar H}}_1 \sim {{\bar H}}_2
 \;\; {\Longrightarrow}\;\; T_{{{\bar H}}_1} \sim T_{{{\bar H}}_2}$$ Thus we need to prove only $$\label{RRaro}
 T_{{{\bar H}}_1} \sim T_{{{\bar H}}_2} \;\; {\Longrightarrow}\;\; (\pi_1,\psi_1) \sim (\pi_2,\psi_2)$$ Suppose $T_{{{\bar H}}_1} \sim T_{{{\bar H}}_2} $ and let $\; a_k { : }H_k
{\rightarrow}{{\mathcal A}_d}\;,\; k=1,2 \;$, be the functions generating ${{\bar H}}_k$, where $\; d = d(T_{{{\bar H}}_1}) = d(T_{{{\bar H}}_2}) \;$.

Since both of $ \psi_1 { : }H_1 {\rightarrow}I $ and $ \psi_2 : H_2
{\rightarrow}I $ are of degree $1$, we can apply Theorem \[degree 1\] and to construct a common extension $H$ of $H_1$ and $H_2$. Herewith, the corresponding Diagram \[diag degree 1\] commutes and the homomorphisms $\; \psi { : }H {\rightarrow}I \;$ , $\; \chi_1
{ : }H {\rightarrow}H_1 \;$ and $\; \chi_2 { : }H {\rightarrow}H_2 \;$ are of degree $1$.

By Remark \[triv exten\] each of homomorphisms $\; \chi_k { : }H_{b_k} {\rightarrow}H_k \;,\; k = 1,2 \;$ admits the trivial extension $\; {{\bar \chi}}_k { : }{{\bar H}}_{b_k} {\rightarrow}{{\bar H}}_k \;$ with the commuting diagram $$\label{diag ext k=1,2}
   \xymatrix{
      {{\bar H}}_{b_k} \ar[d]^{\pi_{b_k}} \ar[r]^{{{\bar \chi}}_k}
    & {{\bar H}}_k \ar[d]^{\pi_k} \\
        H \ar[r]^{\chi_k}           &  H_k }$$ Here ${{\bar \chi}}_k$ is of degree $1$ and $b_k := a_k \circ \chi_k $ for $k = 1,2$. Since $ d({{\bar \chi}}_1) = d({{\bar \chi}}_2) = 1 $ we have $T_{{{\bar H}}_1} \sim T_{{{\bar H}}_{b_1}} $ and $T_{{{\bar H}}_2} \sim T_{{{\bar H}}_{b_2}}
$. Therefore $T_{{{\bar H}}_1} \sim T_{{{\bar H}}_2} $ implies that the skew products ${{\bar T}}_{H,b_1}$ and ${{\bar T}}_{H,b_2}$ are isomorphic.

Thus we have two GSP $d$-extensions $\; \pi_{b_k} { : }{{\bar H}}_{b_k} {\rightarrow}H \;,\; k = 1,2 \;,\;$ of $H$ and a homomorphism $\psi : H {\rightarrow}I $ of degree $1$. Herewith, the number $d$ is the minimal index of ${{\bar T}}_{H,b_1}$ and ${{\bar T}}_{H,b_2}$. By Theorem \[Equ ext 1\] the functions $b_1$ and $b_2$ are cohomologous with respect to $H$. Hence two constructed $(\pi,\psi)$-extensions $$(\pi_{b_k},\psi) \;{ : }\;
    \xymatrix{ {{\bar H}}_{b_k} \ar[r]^{\pi}
       & H \ar[r]^{\psi} & I } \;\;,\;\; k=1,2$$ are equivalent, $\; (\pi_{b_1},\psi) \sim (\pi_{b_2},\psi) \;$.

On the other hand by constructing both two diagrams $$\xymatrix{
   {{\bar H}}_{b_k} \ar[d]^{{{\bar {\kappa}}}_k} \ar[r]^{\pi_{b_k}}
 & H \ar[d]^{{\kappa}} \ar[dr]^{\psi} & \\
   {{\bar H}}_k \ar[r]^{\pi_k}
 & H_k \ar[r]^{\psi_k}    & I } \;\;,\;\; k=1,2$$ commute. This means that $\; (\pi_1,\psi_1) \; \preceq \;
(\pi_{b_1},\psi) \;$ and $\; (\pi_2,\psi_2) \; \preceq \;
(\pi_{b_2},\psi) \;$.

The pairs $(\pi_1,\psi_1)$ and $(\pi_2,\psi_2)$ are irreducible and they are majorized by equivalent pairs. Hence they are equivalent.

We have shown (\[RRaro\]).

As a consequence we have also

\[common exten 1\] Under conditions of Theorem \[classification\] the shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic iff the graphs $G_1$ and $G_2$ have a common extension of degree $1$, i.e. there exists a diagram $$\label{diag com ext 1}
   \xymatrix{
    G_!  &  G \ar[l]_{\phi_1} \ar[r]^{\phi_2}  &  G_2  }$$ where homomorphisms $\phi_1$ and $\phi_2$ are of degree $1$.

By Theorem \[phi bar d(T)\] we have two diagram of homomorphisms $$\label{diag com ext 2}
 \xymatrix{
 G_k & G_k{^{(n)}}\ar[l]_{\pi{^{(n)}}}
 &  {{\bar H}}_k \ar[l]_{{{\bar \psi}}_k} \ar[r]^{\pi_k}
 & H_k \ar[r]^{\psi_k} & I   }  \;\;\;\; k=1,2$$ where $d(\pi{^{(n)}}) = d({{\bar \psi}}_k) = d(\psi_k) = 1 $ and $\pi_k$ is a $d$-extension. So that $(\pi_k,\psi_k) \in {{\mathcal Ext}^d(I,\rho)}$.

By Theorem \[reduc ext\] each pair $(\pi_k,\psi_k) \;,\; k=1,2
\;$ majorizes an irreducible pair from $ {{\mathcal Ext}^d(I,\rho)}$. If the the shifts $T_{G_1}$ and $T_{G_2}$ are isomorphic the irreducible pairs are equivalent (Theorem \[classification\]) and we may assume without loss of generality that they coincide with each other.

Thus there exists $(\pi_0,\psi_0) \in {{\mathcal Ext}^d(I,\rho)}$ with two commuting diagrams $$\label{diag reduc ext k=1,2}
 \xymatrix{
    {{\bar H}}_k \ar[d]^{{{\bar {\kappa}}}_k} \ar[r]^{\pi_k}
  & H_k \ar[d]^{{\kappa}_k} \ar[dr]^{\psi_k} &  \\
    {{\bar H}}_0 \ar[r]^{\pi_0}
  & H_0 \ar[r]^{\psi_0}    & I  } \;\;\;\; k=1,2$$ Passing possibly to equivalent extensions we may also assume that ${{\bar {\kappa}}}_1$ and ${{\bar {\kappa}}}_2$ are trivial extensions of ${\kappa}_1$ and ${\kappa}_2$.

By Theorem \[degree 1 sharp\] and Remark \[triv exten\] we find a common extension of degree 1 $$\label{diag com ext 3}
   \xymatrix{  H_1  &  H \ar[l]_{\chi_1} \ar[r]^{\chi_2}  &  H_2  }$$ of $H_1$ and $H_2$ with the trivial extensions $$\label{diag com ext 4}
   \xymatrix{
   {{\bar H}}_!  &  {{\bar H}}\ar[l]_{{{\bar \chi}}_1} \ar[r]^{{{\bar \chi}}_2}  &  {{\bar H}}_2  }$$ of $\chi_1$ and $\chi_2$ such that the corresponding diagram $$\label{diag com ext 5}
   \xymatrix{
 & {{\bar H}}_2 \ar[dd]_(.75){\pi_2} \ar[rr]^{{{\bar {\kappa}}}_2}&
 & {{\bar H}}_0 \ar[dd]^{\pi_0} \ar[drrrr]^{{{\bar \psi}}_0}   & &&& \\
   {{\bar H}}\ar[dd]_{\pi} \ar[ur]^{{{\bar \chi}}_2} \ar[rr]^(.75){{{\bar \chi}}_1}
     \ar[rrru]^{{{\bar \chi}}}
 && {{\bar H}}_1 \ar[ur]_{{{\bar {\kappa}}}_1} \ar[dd]^(.25){\pi_1} &&&&& I \\
 &  H_2 \ar[rr]^(.75){{\kappa}_2}&
 &  H_0  \ar[rrrru]^{\psi_0} &&&& \\
    H \ar[ur]^{\chi_2} \ar[rr]_{\chi_1} \ar[rrru]^{\chi}
         & & H_1 \ar[ur]_{{\kappa}_1} & && && \\  }$$ commutes. Therefore we have $$\label{diag com ext 6}
 \xymatrix{
  G_1 & G_1{^{(n)}}\ar[l]_{\pi{^{(n)}}}  &  {{\bar H}}_1 \ar[l]_{{{\bar \psi}}_1}
  & {{\bar H}}\ar[l]_{{{\bar {\kappa}}}_1} \ar[r]^{{{\bar {\kappa}}}_2} & {{\bar H}}_2 \ar[r]^{\psi_2}
  & G_2{^{(n)}}\ar[r]^{\pi{^{(n)}}} & G_2  }$$ Putting $\; G := {{\bar H}}\;$ and $\; \phi_k := {{\bar {\kappa}}}_k \circ {{\bar \psi}}_k
\circ \pi{^{(n)}}\;$ for $\; k = 1,2 \;$, we obtain the desired common extension of degree $1$ (\[diag com ext 1\]).

Consequences and examples. {#ss5.2}
--------------------------

Consider some particular cases.

[**Extensions of Bernoulli graphs.**]{} Let $(I,\rho)$ be a standard Bernoulli graph and let $ d \in {{\mathbb{N}}}$. Let $\; a { : }I {\rightarrow}{{\mathcal A}_d}\;$ be a function $\; a { : }I {\rightarrow}{{\mathcal A}_d}\;$ on $I$ with the values $\; a(i) \;,\; i \in I  \;,$ in the group ${{\mathcal A}_d}$ of all permutations of $\; Y_d = \{1,2, \ldots ,d \} \;$. Consider a $d$-extension $\; {{\bar I}}_a \;$ generated by the function $a$ (See Section \[ss4.2\]). We assume that the group $ {\Gamma}(a) $, generated by $\; a(i) , i \in
I, \;$ acts transitively on $Y_d$. This provides that the shift $T_{{{\bar I}}_a} $ and the skew product ${{\bar T}}_{I,a}$ are ergodic.

We want to clarify: when is $\; {{\bar I}}_a \;$ the canonical graph for the corresponding Markov shift $T_{{{\bar I}}_a}$ (Definition \[def canon form\]). Let $\pi { : }{{\bar I}}_a {\rightarrow}I$ be the projection and $ (\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$. Since every homomorphism $ \psi { : }I
{\rightarrow}I $ is an automorphism, the pair $(\pi,\psi)$ is irreducible. Therefore $\; {{\bar I}}_a \;$ is a the canonical graph iff $\; d(T_{{{\bar I}}_a}) = d \;$.

\[d = d(T bI a)\] If the function $a$ satisfies the following condition $$\label{modular a}
  \rho(i) = \rho(i') \;\; {\Longrightarrow}\;\; a(i) = a(i')
  \;\;,\;\; i,i' \in I$$ then $\; d(T_{{{\bar I}}_a}) = d \;$.

Suppose the condition (\[modular a\]) holds. The Markov shift $T_{{{\bar I}}_a} $ is isomorphic to the skew product ${{\bar T}}= {{\bar T}}_{\rho,a}$, which acts on $X_\rho \times Y_d$ by (\[bT rho a\]). So that we have $d(T_{{{\bar I}}_a}) = d({{\bar T}}) $ and by Theorem \[simp mar\] $\; d({{\bar T}}) \;=\; d_{{\gamma}{ : }{\beta}}({{\bar T}})
\;$.

A direct computation, using (\[modular a\]), the definition of ${\gamma}(T)$ and ${\beta}({{\bar T}})$ and Proposition \[ga(T rho)\], shows that $${\beta}({{\bar T}}) = {\gamma}(T_\rho) \times {\varepsilon}_{Y_d}  \;\;\;,\;\;\;
 {\gamma}({{\bar T}}) = {\gamma}(T_\rho) \times \nu_{Y_d} \;.$$ This means that any element of ${\gamma}({{\bar T}})$ consists precisely of $d$ elements of the partition ${\beta}({{\bar T}})$. By the definition of the index $ d_{{\gamma}{ : }{\beta}}({{\bar T}}) $ we have $\; d_{{\gamma}{ : }{\beta}}({{\bar T}}) = d \;$. Thus $\; d(T_{{{\bar I}}_a}) = d \;$.

Taking into account Theorem \[th rho cohom\] we have

\[cor modular a\] Let $\; \pi_k { : }{{\bar I}}_{a_k} {\rightarrow}I \;,\; k = 1,2, \;$ be two $d$-extensions of the Bernoulli graph $(I,\rho)$, generated by functions $ a_k { : }I {\rightarrow}{{\mathcal A}_d}$, respectively, and suppose both the functions $\; a_k \;,\;k=1,2 \;$ satisfy the condition \[modular a\]. Then the Markov shifts $T_{{{\bar I}}_{a_1}}$ and $T_{{{\bar I}}_{a_2}}$ are isomorphic iff $ a_1 $ and $ a_2 $ are conjugate in ${{\mathcal A}_d}$, i.e. there exists $w_0 \in {{\mathcal A}_d}$ such that $\; a_2(i) \cdot w_0 = w_0
\cdot a_1(i) \;,\; i \in I \;$.

\[rem modular a\] It can be proved that for $d$-extension ${{\bar I}}_a$, the condition \[modular a\] is equivalent to $\; d(T_{{{\bar I}}_a}) = d \;$.

[**Absolutely non-homogeneous ${\boldsymbol{\rho}}$.**]{} Consider the case , when $\rho$ is absolutely non-homogeneous (see Section \[ss2.4\]). this means that $\; \rho(i) \neq \rho(i') \;$ for all $\;i \neq i' \;$ from $I$, i.e. the Bernoulli graph $(I,\rho)$ has no congruent edges.

In this case for any $\rho$-uniform graph $G$ there exists a [**unique**]{} homomorphism $\; \phi { : }G {\rightarrow}I \;$. Therefore Theorem \[phi bar d(T)\] can be sharpened as follows

\[phi bar d(T) sharp\] Let $G$ be a $\rho$-uniform stochastic graph, which is irreducible and satisfies the positive recurrence condition. Suppose that $\rho$ is absolutely non-homogeneous. Then there exist a unique homomorphism $\; \phi \in {{\mathcal Hom}}(G,I) \;$ and a commutative diagram $$\label{diag bar H G}
 \xymatrix{   {{\bar H}}\ar[d]^{\pi} \ar[r]^{{{\bar \psi}}} & G \ar[d]^{\phi} \\
                               H \ar[r]^{\psi} & I   }$$ such that

1.  The pair $\; (\pi,\psi) \in {{\mathcal Ext}^d(I,\rho)}$ is a $(\pi,\psi)$-extension.

2.  $\; d = d(\phi) = d(T_G) \;$,

A natural question, which is arisen in connection with the previous theorem is:

\[gen road prob\] Does Theorem \[phi bar d(T)\] hold with $n=1$ in general case, when $\rho$ is not necessarily absolutely non-homogeneous, i.e. when $(I,\rho)$ has congruent edges ?

As we know, the problem is open even in the case, when the graph $G$ is finite (See [@AsMaTu] and references therein.)

[**Homogeneous ${\boldsymbol{\rho}}$ and Road Problem** ]{} Consider a special case, when $\rho$ is homogeneous, i.e. $\; \rho(i) =
l^{-1} \;,\; i \in I \;$ with an integer $l = |I| \in {{\mathbb{N}}}$. Theorem \[simp mar\] and arguments adduced in Section \[ss2.4\] imply

\[\] Suppose $\rho$ is homogeneous. Then every ergodic $\rho$-uniform Markov shift $\; T_G \;$ is isomorphic to a direct product $\; T_\rho \times {\sigma}_d \;$ of the Bernoulli shift $T_\rho$ and a cyclic permutation ${\sigma}_d$ of $Y_d$, where $d$ is the period of $ T_G $. If, in addition, $ T_G
$ is exact, then it is isomorphic to the Bernoulli shift $T_\rho$, herewith, there exists $n \in {{\mathbb{N}}}$ and a homomorphism $\; \phi
{ : }G{^{(n)}}{\rightarrow}I \;$ of degree $1$.

The result was proved earlier in for finite $G$ and in for general case.

If $G$ is finite and $\rho$ is homogeneous Question \[gen road prob\] is a reformulation of well-known Road Coloring Problem (See [@Fr], [@O'B], [@AdGoWe], [@Ki]). As we know, the problem is still open.

Some (p,q)-uniform graphs. {#ss5.4}
--------------------------

We construct some simple examples to illustrate the case, when the $\psi$-part in the canonical pair $(\pi,\psi)$ is not trivial.

Let $\; I = \{0,1\}\;$ and $\; \rho = (p,q) \;$, where $\; 0 < p < 1 \;$ and $\; q=1-p \;$. Given $\; n \in {{\mathbb{N}}}\;$ consider the following random walk on $\; J_n := \{ 1,2, \ldots ,n \} \;$ $$\label{FDR}
   \xymatrix@C=3pc{
            1       \ar@(ul,dl) []_{q}   \ar@/_/ [r]_{p}
    &       2       \ar@/_/ [l]_{q}      \ar@/_/ [r]_{p}
    &       \;\;\;\;\hdots\;\;\;\;
                    \ar@/_/ [l]_{q}      \ar@/_/ [r]_{p}
    &       n       \ar@/_/ [l]_{q}      \ar@(dr,ur) []_{p}    } \;,$$ which is known as a [**Finite Drunkard Ruin**]{}. We set here: $\; H:=I \times J_n \;$ , $\; H{^{(0)}} := J_n \;$ and $$s(h) = j \;,\; t(h) = f_ij \;,\; \psi (h) = i
  \;\;,\;\; h = (i,j) \in H \;,$$ where the maps $\; f_i { : }J_n/ {\rightarrow}J_n \;,\; i = 0,1 \;,$ are defined by $$f_1 j = \min{(j+1,n)} \;\;,\;\;  f_0 j = \max{(j-1,1)}
   \;\;\;,\;\;\;  j \in J_n$$ and the weights of edges $\; p(h) \;,\; h \in H \;$ are given according to (\[FDR\]) by $\; p(1,j) = p \;$, $\; p(0,j) = q
\;$.

Then the finite stochastic graph $H$ is irreducible and $\rho$-uniform, $\; \psi \in {{\mathcal Hom}}(H,I) \;$. The semigroup ${{\mathcal S}}(\psi)$, generated by $\{f_0,f_1\}$, is $1$-contractive, since $\;
(f_0)^n (J_n) = \{1\} \;$. Whence, $\; d(\psi) = 1 \;$ and the Markov shift $T_H$ is isomorphic to the Bernoulli shift $T_\psi$.

Given $p$ and $n$ we construct a ${{\mathbb{Z}}}_2$-extension ${{\bar H}}_a$ of the graph $H$, where $a : H {\rightarrow}{{\mathbb{Z}}}_2$ and ${{\mathbb{Z}}}_2 := \{0,1\}$ be the cyclic group of order $2$.

Define $\; a : H=I \times J_n \ni h=(i,j) {\rightarrow}a(h) \in {{\mathbb{Z}}}_2 \;$ by $$\label{a(h)}
a(i,j) \;=\;            \left\{
     \begin{array}{ll}
         1 \;\;,\;\; & if \;\; (i,j)    \;=\;   (1,1) \; \\
         0 \;\;,\;\; & if \;\; (i,j)   \;\neq\; (1,1) \;.
     \end{array}
                        \right.$$ Then the corresponding graph ${{\bar H}}_a$ has the form $$\label{FDR2}
   \xymatrix@C=3pc{
      **[r] 11      \ar@(ul,dl) []_{q}  \ar [rd]_(.75){p}
    &       21      \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
    &       \;\;\;\hdots\;\;\;
                    \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
    & **[l] n1      \ar@/_/ [l]_{q}     \ar@(dr,ur) []_{p}
    &      z=1                                             \\
      **[r] 10      \ar@(dl,ul) []^{q}  \ar [ru]^(.75){p}
    &       20      \ar@/^/ [l]^{q}     \ar@/^/ [r]^{p}
    &       \;\;\;\hdots\;\;\;
                    \ar@/^/ [l]^{q}     \ar@/^/ [r]^{p}
    & **[l] n0      \ar@/^/ [l]^{q}     \ar@(ur,dr) []^{p}
    &      z=0                                             }$$ for $\; n > 2 \;.$ and $$\label{FDR3}
   \xymatrix@C=3pc{
        **[r] 11      \ar@(ul,dl) []_{q}  \ar@/^3pc/ [d]^{p}
    && **[r] 11      \ar@(ul,dl) []_{q}  \ar [rd]_(.75){p}
    &   **[l] 21      \ar@/_/ [l]_{q}     \ar@(dr,ur) []_{p}
    &        z=1                                              \\
        **[r] 10      \ar@(ul,dl) []_{q}  \ar@/_2pc/ [u]^{p}
    && **[r] 10      \ar@(dl,ul) []^{q}  \ar [ru]^(.75){p}
    &   **[l] 20      \ar@/^/ [l]^{q}     \ar@(ur,dr) []^{p}
    &        z=0                                               }$$ for two special cases $\; n = 1,2 \;$

Suppose $\; p \neq q \;$. We claim in this case that for all $n
\in {{\mathbb{N}}}$ the graphs (\[FDR3\]) and (\[FDR2\]) are canonical. Indeed, $\; d(\pi_H) = d(T_{{{\bar H}}_a}) = 2 \;$, since $ \rho = (p,q)
$ is absolutely non-homogeneous. In order to check the irreducibility of the $2$-extension $\; (\pi_H,\psi) { : }{{\bar H}}_a
{\rightarrow}H {\rightarrow}I \;$ consider the semigroup ${{\bar {{\mathcal S}}}}= {{\bar {{\mathcal S}}}}(\pi,\psi)$ and its persistent partitions ${{\mathcal R}}({{\bar {{\mathcal S}}}})$.

The semigroup ${{\bar {{\mathcal S}}}}$ is generated by $\; \{{{\bar f}}_i , i\in I \}$, where $${{\bar f}}_i \; (j\;,\;z) \;=\; (f_i \; j \;,\; z + a(i,j) \pmod 2 ) \;\;,\;\;
       (j,z) \in J_n \times {{\mathbb{Z}}}_2 \;.$$ A direct computation shows that for $\; n = 1,2 \;$ any transversal partition of $J_n \times {{\mathbb{Z}}}_2 $ is persistent in the sense of Definition \[pers part\] , and for $\; n > 2 \;$ there exists a non-persistent transversal partition. Naimly, the partition, consisting of two sets of the following “alternating” form $$\{  (1,0) , (2,1) , (3,0) , (4,1) , \ldots  \}
 \;\;,\;\; \{  (1,1) , (2,0) , (3,1) , (4,0) , \ldots  \} \;,$$ is so. Moreover, this is the only transversal partition, which is not persistent. This implies that for every $ n \in {{\mathbb{N}}}$ the persistent partitions ${{\mathcal R}}({{\bar {{\mathcal S}}}})$ separate points of $ J_n \times
{{\mathbb{Z}}}_2 $ in the sense of Remark \[irred ext\] and the $2$-extension $(\pi_H, \psi)$ is irreducible. Thus

-   For all $n \in {{\mathbb{N}}}$ and $p \neq q$ the graphs ${{\bar H}}_a$ are canonical graphs for the corresponding shifts $T_{{{\bar H}}_a}$.

Just in the same way we can consider the following [**Infinite Drunkard Ruin**]{} $$\label{FDR4}
   \xymatrix@C=3pc{
      **[r] 1      \ar@(ul,dl) []_{q}  \ar@/_/ [r]_{p}
    &       2      \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
    &                   \;\;\;\hdots\;\;\;
                   \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
    &       n      \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
    &              \ar@/_/ [l]_{q}     \;\;\;\hdots      }$$ where $\; H:=I \times {{\mathbb{N}}}\;$ , $\; H{^{(0)}} := {{\mathbb{N}}}\;$.

Suppose $\; p < q \;$. Then the corresponding Markov chain is positively recurrent and the Markov shift $T_H$ is isomorphic to the Bernoulli shift $T\rho$.

Again define the functions $\; a : H=I \times {{\mathbb{N}}}\ni h=(i,j) {\rightarrow}a(h) \in {{\mathbb{Z}}}_2 \;$ by (\[a(h)\]). Then ${{\mathbb{Z}}}_2$-extension ${{\bar H}}_a$ of the graph $H$ (\[FDR5\]) has the form $$\label{FDR5}
   \xymatrix@C=3pc{
      **[r] 11               \ar@(ul,dl) []_{q}  \ar [rd]_(.75){p}
  &         21               \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
  &   \;\;\;\hdots\;\;\; \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
  &         n1               \ar@/_/ [l]_{q}     \ar@/_/ [r]_{p}
  &                          \ar@/_/ [l]_{q}     \;\;\;\hdots      \\
      **[r] 10               \ar@(dl,ul) []^{q}  \ar [ru]^(.75){p}
  &       20                 \ar@/^/ [l]^{q}     \ar@/^/ [r]^{p}
  &   \;\;\;\hdots\;\;\; \ar@/^/ [l]^{q}     \ar@/^/ [r]^{p}
  &       n0                 \ar@/^/ [l]^{q}     \ar@/^/ [r]^{p}
  &                          \ar@/^/ [l]^{q}     \;\;\;\hdots       }$$ It can be shown in this case that any transversal set is persistent. Thus

-   If $p < q$ the graph ${{\bar H}}_a$ (\[FDR5\]) is the canonical graph for the shift $T_{{{\bar H}}_a}$.

Note that the shift $T_{{{\bar H}}_a}$ is a ${{\mathbb{Z}}}_2$-extension of the Bernoulli shift $T_{p,q}$, therefore, $T_{{{\bar H}}_a}$ has a $4$-element one-sided generator. On the other hand the shift is not isomorphic to Markov shifts on finite state spaces. Thus

-   If $p < q$ the one-sided Markov shift $T_{{{\bar H}}_a}$ has no finite one-sided Markov generator.

[9]{}

J. Aaronson. An introduction to infinite ergodic theory. Math. Surveys and Monographs, vol. 50, 1997.

A.L. Adler, L.W. Goodwyn, B. Weiss. Equivalence of topological Markov shifts. Isr. J. Math. 27(1977), 49-63.

J. Ashley. Resolving factor maps for shifts of finite type with equal entropy. Ergod. Th. Dyn. Syst. 11(1991), 219-240.

J. Ashley, B. Marcus, S. Tuncel. The classification of one-sided Markov chains. Ergod. Th. Dyn. Syst. 17(1997), 269-295.

M. Boyle, S. Tuncel. Regular isomorphism of Markov chains is almost topological. Ergod. Th. Dyn. Syst. 10(1990), 89-100.

J. Feldman, D.J. Rudolph. Standardness of sequences of $\sigma$- fields given by certain endomorphisms. Fund. Math. 157(1998), 175-189.

J. Friedman. On the Road Coloring Problem. Proc. AMS 110(1990), 1133-1135.

N. Friedman, D. Ornstein. On the isomorphism of weak Bernoulli transformations. Adv. in Math. 5(1970), 365-394.

D. Heicklen, C. Hoffman. $(T,T^{-1})$ is not standard. Ergod. Th. Dyn. Syst. 18(1998), 875-878.

D. Heicklen, C. Hoffman, D.J. Rudolph. Entropy and dyadic equivalence of random walks on a random scenery. Adv. Math. 156(2000), 157-179.

C. Hoffman. A zero entropy $T$ such that the $(T,Id)$-endomorphism is non standard. Proc. AMS 128(2000), 183-188.

C. Hoffman, D. Rudolph. Uniform endomorphisms which are isomorphic to a Bernoulli shift. Ann, of Math. 156(2002), 79-101.

M. Keane, M. Smorodinsky. Finitary isomorphism of irreducible Markov shifts. Israel J. Math. 34(1979), 281-286.

B.P. Kitchens. Symbolic dynamic. Springer-Verlag, Berlin, 1998.

B.P. Kitchens, B. Marcus, P. Trow. Eventual factor maps and compositions of closing maps. Ergod. Th. Dyn. Syst. 11(1991), 85-113.

W. Krieger. On finitary isomorphism of Markov shifts that have finite expected coding time. Z. Wahr. 65(1983), 323-328.

J. Kubo, H. Murata, H, Totoki. On the isomorphism problem for endomorphisms of Lebesgue space. Publ. RIMS. Kyoto Univ. 9(1974), 285-296.

D. Ornstein. Bernoulli shifts with the same entropy are isomorphic. Adv. Math. 4(1970), 337-352.

O’Brien. The Road Coloring Problem. Isr. J. Math. 39(1981), 145-154.

V. Rokhlin. On the fundamental ideas of the measure theory. Mat. Sbor. 25(1949), 107-150 (Russian), Trans. AMS. 71(1952). 1-54.

V. Rokhlin. Lectures on the entropy theory of transformation with invariant measure. Usp. Mat. Nauk. 22(1967), 3-56 (Russian). Russ. Math. Surveys 22(1967), 1-52.

M. Rosenblatt. Stationary processes as shifts of functions of independent random variables. J. Math. Mech. 8(1959), 665-681.

M. Rosenblatt. Markov processes. Structure and asymptotic behavior. Springer Grundl. Math. 184, Berlin, 1971.

B.Z. Rubshtein. On decreasing sequences of measurable partitions. Sov. Math. Dok. 13(1972), 962-965.

B.Z. Rubshtein. Decreasing sequences of measurable partitions generated by endomorphisms. Ups. Math. Nauk 28(1973), 247-248.

B.Z. Rubshtein. Generating partitions of Markov endomorphism. Func. Anal. Appl. 8(1974), 84-85.

B.Z. Rubshtein. On non homogeneous finitely Bernoulli sequences of measurable partitions. Func. Anal. Appl. 10(1976), 39-44.

B.Z. Rubshtein. Lacunary isomorphism of decreasing sequences of measurable partition. Israel J. Math. 97(1997), 317-345.

B.Z. Rubshtein, On finitely Bernoulli one-sided Markov shifts and their cofiltrations, Ergod. Th. Dyn. Syst, 19(1999), 1527-1524.

Ya. G. Sinai. On weak isomorphism of measurable preserving transformations. Mat. Sb. 63(1964), 23-42, Transl. AMS 57(1966), 123-143.

A.M. Stepin. On entropy invariants of decreasing sequences of measurable partitions. Func. Anal. Appl. 5(1971). 80-84.

P. Trow. Degrees of finite to one factor maps. Israel J. Math. 71(1990), 229-238.

A.M. Vershik. A lacunary isomorphism theorem for monotone sequences of measurable partitions. Func. Anal. Appl. 2(1968). 17-21.

A.M. Vershik. Decreasing sequences of measurable partitions and their applications. Sov. Math. Doc. 11(1970), 1007-1011.

A.M. Vershik. A continuum of pairwise non-isomorphic dyadic sequences. Func. Anal. Appl. 5(1971), 16-18.

A.M. Vershik. Theory of decreasing sequences of measurable partitions. St.Peterburg Math. J. 6 (1995), 705-761.

V.G. Vinokurov. Two non-isomorphic exact endomorphisms of the Lebesgue space with isomorphic sequences of partitions. In “Random processes and related topics”. vol. 1 Tashkent 1970, 43-45 (in Russian).

V. Vinokurov. B. Rubshtein. A. Fedorov. Lebesgue spaces and their measurable partitions. Tashkent Univ. 1985, 75 pp. (in Russian).
