On the Structure of Covers of Sofic Shifts

Rune Johansen

Received: June 6, 2010 Revised: March 1, 2011

Communicated by Joachim Cuntz

Abstract. A canonical cover generalizing the left Fischer cover to arbitrary sofic shifts is introduced and used to prove that the left Krieger cover and the past set cover of a sofic shift can be divided into natural layers. These results are used to find the range of a flow-invariant and to investigate the ideal structure of the universal C^{∗}-algebra associated to a sofic shift space.

2010 Mathematics Subject Classification: Primary: 37B10; Secondary: 46L05 Keywords and Phrases: shift space, sofic shift, Krieger cover, Fischer cover

1 Introduction

Shifts of finite type have been completely classified up to flow equivalence by Boyle and Huang [4, 6, 15], but very little is known about the classification of the class of sofic shift spaces introduced by Weiss [38], even though they are a natural first generalization of shifts of finite type. The purpose of this paper is to investigate the structure of - and relationships between - various standard presentations (the Fischer cover, the Krieger cover, and the past set cover) of sofic shift spaces. These results are used to find the range of the flow-invariant introduced in [1], and to investigate the ideal structure of the C^{∗}-algebras associated to sofic shifts. In this way, the present paper can be seen as a continuation of the strategy applied in [10, 11, 30], where invariants for shift spaces are extracted from the associated C^{∗}-algebras. Section 2 recalls the definitions of shift spaces, labelled graphs, and covers to make the paper self contained. Section 3 introduces a canonical and flowinvariant cover generalizing the left Fischer cover to arbitrary sofic shifts.

Section 4 introduces the concept of a foundation of a cover, which is used to prove that the left Krieger cover and the past set cover can be divided into natural layers and to show that the left Krieger cover of an arbitrary sofic shift can be identified with a subgraph of the past set cover. In Section 5, the structure of the layers of the left Krieger cover of an irreducible sofic shift is used to find the range of the flow-invariant introduced in [1]. Section 6 uses the results about the structure of covers of sofic shifts to investigate ideal lattices of the associated C^{∗}-algebras. Additionally, it is proved that Condition (∗) introduced by Carlsen and Matsumoto [12] holds if and only if the left Krieger cover is the maximal essential subgraph of the past set cover. Acknowledgements. This work was supported by the Danish National Research Foundation (DNRF) through the Centre for Symmetry and Deformation. The author would like to thank David Pask, Toke Meier Carlsen, and Søren Eilers for interesting discussions and helpful comments. The author would also like to thank the anonymous referee for useful comments improving the exposition and to thank the University of Wollongong, Australia and the University of Tokyo, Japan where parts of the research for this paper were carried out during visits funded by Rejselegat for Matematikere.

2 Background

Shift spaces. Here, a short introduction to the definition and properties of shift spaces is given to make the present paper self-contained; for a thorough treatment of shift spaces see [21]. Let A be a finite set with the discrete topology. The full shift over A consists of the space A^{ℤ} endowed with the product topology and the shift map σ: A^{ℤ} → A^{ℤ} defined by σ(x)_{i} = x_{i+1} for all i ∈ ℤ. Let A^{∗} be the collection of finite words (also known as blocks) over A. A subset X ⊆ A^{ℤ} is called a shift space if it is invariant under the shift map and closed. For each F ⊆ A^{∗}, define X_{F} to be the set of bi-infinite sequences in A^{ℤ} which do not contain any of the forbidden words from F. A subset X ⊆ A^{ℤ} is a shift space if and only if there exists F ⊆ A^{∗} such that X = X_{F} (cf. [21, Proposition 1.3.4]). X is said to be a shift of finite type (SFT) if this is possible for a finite set F. The language of a shift space X is defined to be the set of all words which occur in at least one x ∈ X, and it is denoted B(X). X is said to be irreducible if there for every u, w ∈ B(X) exists v ∈ B(X) such that uvw ∈ B(X). For each x ∈ X, define the left-ray of x to be x^{−} = ⋯ x_{−2}x_{−1} and define the right-ray of x to be x^{+} = x_{0}x_{1}x_{2} · · ·. The sets of all left-rays and all right-rays are, respectively, denoted X^{−} and X^{+}. A bijective, continuous, and shift commuting map between two shift spaces is called a conjugacy, and when such a map exists, the two shift spaces are said to be conjugate. Shift spaces (X, σ_{X}) and (Y, σ_{Y}) are said to be flow equivalent if the corresponding suspension flows SX and SY are topologically equivalent. Flow equivalence is generated by conjugacy and symbol expansion [35].

Graphs. For countable sets E^{0} and E^{1}, and maps r, s: E^{1} → E^{0} the quadruple E = (E^{0}, E^{1}, r, s) is called a directed graph. The elements of E^{0} and E^{1} are, respectively, the vertices and the edges of the graph. For each edge e ∈ E^{1}, s(e) is the vertex where e starts, and r(e) is the vertex where e ends. A path λ = e_{1} ⋯ e_{n} is a sequence of edges such that r(e_{i}) = s(e_{i+1}) for all i ∈ {1, … n − 1}. For each n ∈ ℕ_{0}, the set of paths of length n is denoted E^{n}, and the set of all finite paths is denoted E^{∗}. Extend the maps r and s to E^{∗} by defining s(e_{1} ⋯ e_{n}) = s(e_{1}) and r(e_{1} ⋯ e_{n}) = r(e_{n}). A circuit is a path λ with r(λ) = s(λ) and |λ| > 0. For u, v ∈ E^{0}, u is said to be connected to v if there is a path λ ∈ E^{∗} such that s(λ) = u and r(λ) = v, and this is denoted by u ≥ v [21, Section 4.4]. A vertex is said to be maximal, if it is connected to all other vertices. E is said to be irreducible if all vertices are maximal. If E has a unique maximal vertex, this vertex is said to be the root of E. E is said to be essential if every vertex emits and receives an edge. For a finite essential directed graph E, the edge shift (X_{E}, σ_{E}) is defined by

X_{E} = {x ∈ (E^{1})^{ℤ} | r(x_{i}) = s(x_{i+1}) for all i ∈ ℤ} .

A labelled graph (E, L) over an alphabet A consists of a directed graph E and a surjective labelling map L: E^{1} → A. Extend the labelling map to L: E^{∗} → A^{∗} by defining L(e_{1} ⋯ e_{n}) = L(e_{1}) ⋯ L(e_{n}) ∈ A^{∗}. For a finite essential labelled graph (E, L), define the shift space (X_{(E,L)}, σ) by

X_{(E,L)} = {(L(x_{i}))_{i} ∈ A^{ℤ} | x ∈ X_{E}} .

The labelled graph (E, L) is said to be a presentation of the shift space X_{(E,L)}, and a representative of a word w ∈ B(X_{(E,L)}) is a path λ ∈ E^{∗} such that L(λ) = w. Representatives of rays are defined analogously. If H ⊆ E^{0} then the subgraph of (E, L) induced by H is the labelled subgraph of (E, L) with vertices H and edges {e ∈ E^{1} | s(e), r(e) ∈ H}. Sofic shifts. A function π: X_{1} → X_{2} between shift spaces X_{1} and X_{2} is said to be a factor map if it is continuous, surjective, and shift commuting. A shift space is called sofic [38] if it is the image of an SFT under a factor map. A shift space is sofic if and only if it can be presented by a finite labelled graph [14]. A sofic shift space is irreducible if and only if it can be presented by an irreducible labelled graph (see [21, Section 3.1]). Let (E, L) be a finite labelled graph and let π_{L}: X_{E} → X_{(E,L)} be the factor map induced by the labelling map L: E^{1} → A then the SFT X_{E} is called a cover of the sofic shift X_{(E,L)}, and π_{L} is called the covering map. A presentation (E, L) of a sofic shift space X is said to be left-resolving if no vertex in E^{0} receives two edges with the same label. Fischer proved [14] that, up to labelled graph isomorphism, every irreducible sofic shift has a unique left-resolving presentation with fewer vertices than any other left-resolving presentation. This is called the left Fischer cover of X, and it is denoted (F, L_{F}). An irreducible sofic shift is said to have almost finite type (AFT) [22, 33] if the left Fischer cover is right-closing (see e.g. [21, Definition 5.1.4]).

For x ∈ B(X) ∪ X^{+}, define the predecessor set of x to be the set of left-rays which may precede x in X (see [17, Sections I and III] and [21, Exercise 3.2.8]). The follower set of a left-ray or word is defined analogously. Let (E, L) be a labelled graph presenting X and let v ∈ E^{0}. Define the predecessor set of v to be the set of left-rays in X which have a presentation terminating at v. This is denoted P_{∞}^{E}(v), or just P_{∞}(v) when (E, L) is understood from the context. The presentation (E, L) is said to be predecessor-separated if P_{∞}^{E}(u) ≠ P_{∞}^{E}(v) when u, v ∈ E^{0} and u ≠ v. The left Krieger cover of the shift space X is the labelled graph (K, L_{K}) where K^{0} = {P_{∞}(x^{+}) | x^{+} ∈ X^{+}}, and where there is an edge labelled a ∈ A from P ∈ K^{0} to P′ ∈ K^{0} if and only if there exists x^{+} ∈ X^{+} such that P = P_{∞}(ax^{+}) and P′ = P_{∞}(x^{+}). The past set cover of the shift space X is the labelled graph (W, L_{W}) where W^{0} = {P_{∞}(w) | w ∈ B(X)} and where the edges and labels are constructed as in the Krieger cover. A shift space is sofic if and only if the number of predecessor sets is finite [19, §2], so the left Krieger cover is finite exactly when the shift space is sofic. The left Fischer cover, the left Krieger cover, and the past set cover are left-resolving and predecessorseparated presentations of X. The right Krieger cover and the future set cover are right-resolving and followerseparated covers defined analogously to the left Krieger cover and the past set cover, respectively. Every result developed for left-resolving covers in the following has an analogue for the corresponding right-resolving cover. These results can easily be obtained by considering the transposed shift space X^{T} (see e.g. [21, p. 39]).

3 Generalizing the Fischer cover

Jonoska [16] proved that a reducible sofic shift does not necessarily have a unique minimal left-resolving presentation. The aim of this section is to define a generalization of the left Fischer cover as the subgraph of the left Krieger cover induced by a certain subset of vertices. Let X be a sofic shift space, and let (K, L_{K}) be the left Krieger cover of X. A predecessor set P ∈ K^{0} is said to be non-decomposable if V ⊆ K^{0} and P = ⋃_{Q∈V} Q implies that P ∈ V.

Lemma 3.1. If P ∈ K^{0} is non-decomposable then the subgraph of (K, L_{K}) induced by K^{0} \ {P } is not a presentation of X.

Proof. Let E be the subgraph of K induced by K^{0} \ {P }. Choose x^{+} ∈ X^{+} such that P = P_{∞}(x^{+}). Let V ⊆ K^{0} \ {P } be the set of vertices where a presentation of x^{+} can start. Then Q ⊆ P_{∞}(x^{+}) = P for each Q ∈ V, and by assumption, there exists y^{−} ∈ P \ ⋃_{Q∈V} Q. Hence, there is no presentation of y^{−}x^{+} in (E, L_{K}|_{E}).

Lemma 3.1 shows that a subgraph of the left Krieger cover which presents the same shift must contain all the non-decomposable vertices. The next example shows that this subgraph is not always large enough.

P_{1}

P′

P  P_{2}

f c d e b b a a g h i d e b a j

k

Figure 1: Left Krieger cover of the shift considered in Example 3.2. Note that the labelled graph is no longer a presentation of the same shift if the decomposable predecessor set P = P_{1} ∪ P_{2} is removed.

Example 3.2. It is easy to check that the labelled graph in Figure 1 is the left Krieger cover of a reducible sofic shift X. Note that the predecessor set P is decomposable since P = P_{1} ∪ P_{2}, and that the graph obtained by removing the vertex P and all edges starting at or terminating at P is not a presentation of the same sofic shift since there is no presentation of f^{∞}dbjk^{∞} in this graph. Note that there is a path from P to the vertex P′ which is non-decomposable. Together with Lemma 3.1, this example motivates the following definition.

Definition 3.3. The generalized left Fischer cover (G, L_{G}) of a sofic shift X is defined to be the subgraph of the left Krieger cover induced by G^{0} = {P ∈ K^{0} | P ≥ P′, P′ non-decomposable}.

The following proposition justifies the term generalized left Fischer cover.

Proposition 3.4.

(i) The generalized left Fischer cover of a sofic shift X is a left-resolving and predecessor-separated presentation of X.

(ii) If X is an irreducible sofic shift then the generalized left Fischer cover is isomorphic to the left Fischer cover.

(iii) If X_{1}, X_{2} are sofic shifts with disjoint alphabets then the generalized left Fischer cover of X_{1}∪X_{2} is the disjoint union of the generalized left Fischer covers of X_{1} and X_{2}.

Proof. Given y^{−} ∈ X^{−}, choose x^{+} ∈ X^{+} such that y^{−} ∈ P_{∞}(x^{+}) = P. By definition of the generalized left Fischer cover, there exist vertices P_{1}, …, P_{n} ∈ G^{0} such that P = ⋃_{i=1}^{n} P_{i}. Choose i such that y^{−} ∈ P_{i}. By construction, the left Krieger cover contains a path labelled y^{−} terminating at P_{i}. Since P_{i} ∈ G^{0}, this is also a path in the generalized left Fischer cover. This proves that the generalized left Fischer cover is a presentation of X^{−}, and hence also a presentation of X. Since the left Krieger cover is left-resolving and predecessorseparated, so is the generalized left Fischer cover. Let X be an irreducible sofic shift, and identify the left Fischer cover (F, L_{F}) with the top irreducible component of the left Krieger cover (K, L_{K}) [19, Lemma 2.7]. By the construction of the generalized left Fischer cover, it follows that the left Fischer cover is a subgraph of the generalized left Fischer cover. Let x^{+} ∈ X^{+} such that P = P_{∞}(x^{+}) is non-decomposable. Let S ⊆ F^{0} be the set of vertices where a presentation of x^{+} in (F, L_{F}) can start. Then P = ⋃_{v∈S} P_{∞}(v), so P ∈ S ⊆ F^{0} by assumption. Since X_{1} and X_{2} have no letters in common, the left Krieger cover of X_{1} ∪X_{2} is just the disjoint union of the left Krieger covers of X_{1} and X_{2}. The generalized left Fischer cover inherits this property from the left Krieger cover.

The shift consisting of two non-interacting copies of the even shift is a simple example where the generalized left Fischer cover is a proper subgraph of the left Krieger cover.

Lemma 3.5. Let X be a sofic shift with left Krieger cover (K, L_{K}). If there is an edge labelled a from a non-decomposable P ∈ K^{0} to a decomposable Q ∈ K^{0} then there exists a non-decomposable Q′ ∈ K^{0} and an edge labelled a from P to Q′.

Proof. Choose x^{+} ∈ X^{+} such that P = P_{∞}(ax^{+}) and Q = P_{∞}(x^{+}). Since Q is decomposable, there exist n > 1 and non-decomposable Q_{1}, …, Q_{n} ∈ K^{0} \{Q} such that Q = Q_{1} ∪ ⋯ ∪ Q_{n}. Let S be the set of predecessor sets P′ ∈ K^{0} for which there is an edge labelled a from P′ to Q_{j} for some 1 ≤ j ≤ n. Given y^{−} ∈ P, y^{−}ax^{+} ∈ X, so y^{−}a ∈ Q. Choose 1 ≤ i ≤ n such that y^{−}a ∈ Q_{i}. By construction, there exists P′ ∈ S such that y^{−} ∈ P′. Reversely, if y^{−} ∈ P′ ∈ S then there is an edge labelled a from P′ to Q_{i} for some 1 ≤ i ≤ n, so y^{−}a ∈ Q_{i} ⊆ Q. This implies that y^{−}ax^{+} ∈ X, so y^{−} ∈ P. Thus P = ⋃_{P′∈S} P′, but P is non-decomposable, so this means that P ∈ S. Hence, there is an edge labelled a from P to Q_{i} for som i, and Q_{i} is nondecomposable.

The following proposition is an immediate consequence of this result and the definition of the generalized left Fischer cover.

Proposition 3.6. The generalized left Fischer cover is essential.

The left Fischer cover of an irreducible sofic shift X is minimal in the sense that no other left-resolving presentation of X has fewer vertices. This is not always the case for the generalized left Fischer cover. Canonical. Krieger proved that a conjugacy Φ: X_{1} → X_{2} between sofic shifts with left Krieger covers (K_{1}, L_{1}) and (K_{2}, L_{2}), respectively, induces a conjugacy φ: X_{K_{1}} → X_{K_{2}} such that Φ ∘ π_{1} = π_{2} ∘ φ when π_{i}: X_{K_{i}} → X_{i} is the covering map of the left Krieger cover of X_{i} [19]. A cover with this property is said to be canonical. The next goal is to prove that the generalized left Fischer cover is canonical. This will be done by using results and methods used by Nasu [34] to prove that the left Krieger cover is canonical.

Definition 3.7 (Bipartite code). When A, C, D are alphabets, an injective map f: A → CD is called a bipartite expression. If X_{1}, X_{2} are shift spaces with alphabets A_{1} and A_{2}, respectively, and if f_{1} : A_{1} → CD is a bipartite expression then a map Φ: X_{1} → X_{2} is said to be a bipartite code induced by f_{1} if there exists a bipartite expression f_{2} : A_{2} → DC such that one of the following two conditions is satisfied:

(i) If x ∈ X_{1}, y = Φ(x), and f_{1}(x_{i}) = c_{i}d_{i} with c_{i} ∈ C and d_{i} ∈ D for all i ∈ ℤ then f_{2}(y_{i}) = d_{i}c_{i+1} for all i ∈ ℤ.

(ii) If x ∈ X_{1}, y = Φ(x), and f_{1}(x_{i}) = c_{i}d_{i} with c_{i} ∈ C and d_{i} ∈ D for all i ∈ ℤ then f_{2}(y_{i}) = d_{i−1}c_{i} for all i ∈ ℤ.

A mapping Φ: X_{1} → X_{2} is called a bipartite code, if it is the bipartite code induced by some bipartite expression.

It is clear that a bipartite code is a conjugacy and that the inverse of a bipartite code is a bipartite code.

Theorem 3.8 (Nasu [34, Thm. 2.4]). Any conjugacy between shift spaces can be decomposed into a product of bipartite codes.

Let Φ: X_{1} → X_{2} be a bipartite code corresponding to bipartite expressions f_{1} : A_{1} → CD and f_{2} : A_{2} → DC, and use the bipartite expressions to recode X_{1} and X_{2} to

X̂_{1} = {(f_{1}(x_{i}))_{i} | x ∈ X_{1}} ⊆ (CD)^{ℤ}
X̂_{2} = {(f_{2}(x_{i}))_{i} | x ∈ X_{2}} ⊆ (DC)^{ℤ}.

For i ∈ {1, 2}, f_{i} induces a one-block conjugacy from X_{i} to X̂_{i}, and Φ induces a bipartite code Φ̂: X̂_{1} → X̂_{2} which commutes with these conjugacies. If Φ satisfies condition (i) in the definition of a bipartite code then (Φ̂(x̂))_{i} = d_{i}c_{i+1} when x̂ = (c_{i}d_{i})_{i∈ℤ} ∈ X̂_{1}. If it satisfies condition (ii) then (Φ̂(x̂))_{i} = d_{i−1}c_{i} when x̂ = (c_{i}d_{i})_{i∈ℤ} ∈ X̂_{1}. The shifts X̂_{1} and X̂_{2} will be called the recoded shifts of the bipartite code, and Φ̂ will be called the recoded bipartite code. A labelled graph (G, L) is said to be bipartite if G is a bipartite graph (i.e. the vertex set can be partitioned into two sets (G^{0})_{1} and (G^{0})_{2} such that no edge has its range and source in the same set). When (G, L) is a bipartite labelled graph over an alphabet A, define two graphs G_{1} and G_{2} as follows: For i ∈ {1, 2}, the vertex set of G_{i} is (G^{0})_{i}, the edge set is the set of paths of length 2 in (G, L) for which both range and source are in (G^{0})_{i}, and the range and source maps are inherited from G. For i ∈ {1, 2}, define L_{i}: G_{i}^{1} → A^{2} by L_{i}(ef) = L(e)L(f). The pair (G_{1}, L_{1}), (G_{2}, L_{2}) is called the induced pair of labelled graphs of (G, L). This decomposition is not necessarily unique, but whenever a bipartite labelled graph is mentioned, it will be assumed that the induced graphs are specified. Remark 3.9 (Nasu [34, Remark 4.2]). Let (G, L) be a bipartite labelled graph for which the induced pair of labelled graphs is (G_{1}, L_{1}), (G_{2}, L_{2}). Let X_{1} and X_{2} be the sofic shifts presented by these graphs, and let X_{G_{1}}, X_{G_{2}} be the edge shifts generated by G_{1}, G_{2}. The natural embedding f: G_{1}^{1} → (G^{1})^{2} is a bipartite expression which induces two bipartite codes φ_{±}: X_{G_{1}} → X_{G_{2}} such that (φ_{+}(x))_{i} = f_{i}e_{i+1} and (φ_{−}(x))_{i} = f_{i−1}e_{i} when x = (e_{i}f_{i})_{i∈ℤ} ∈ X_{G_{1}}. Similarly, the embedding F: L_{1}(G_{1}^{1}) → (L(G^{1}))^{2} is a bipartite expression which induces bipartite codes Φ_{±}: X_{1} → X_{2} such that (Φ_{+}(x))_{i} = b_{i}a_{i+1} and (Φ_{−}(x))_{i} = b_{i−1}a_{i} when x = (a_{i}b_{i})_{i∈ℤ} ∈ X_{1}. By definition, Φ_{±} ∘ π_{1} = π_{2} ∘ φ_{±} when π_{1} : X_{G_{1}} → X_{1}, π_{2} : X_{G_{2}} → X_{2} are the covering maps. The bipartite codes φ_{±} and Φ_{±} are called the standard bipartite codes induced by (G, L).

Lemma 3.10 (Nasu [34, Cor. 4.6 (1)]). Let Φ: X_{1} → X_{2} be a bipartite code between sofic shifts X_{1} and X_{2}. Let X̂_{1} and X̂_{2} be the recoded shifts of X_{1} and X_{2} respectively, and let (K_{1}, L_{1}) and (K_{2}, L_{2}) be the left Krieger covers of X̂_{1} and X̂_{2} respectively. Then there exists a sofic shift X̂ for which the left Krieger cover is a bipartite labelled graph such that the induced pair of labelled graphs is (K_{1}, L_{1}), (K_{2}, L_{2}) and such that the recoded bipartite code Φ̂: X̂_{1} → X̂_{2} of Φ is one of the standard bipartite codes Φ_{±} induced by the left Krieger cover of X̂ as defined in Remark 3.9.

The proof of the following theorem is very similar to the proof of the corresponding result by Nasu [34, Thm. 3.3] for the left Krieger cover.

Theorem 3.11. The generalized left Fischer cover is canonical.

Proof. Let Φ: X_{1} → X_{2} be a bipartite code. Let X̂_{1}, X̂_{2} be the recoded shifts, let (K_{1}, L_{1}), (K_{2}, L_{2}) be the corresponding left Krieger covers, and let Φ̂: X̂_{1} → X̂_{2} be the recoded bipartite code. Use Lemma 3.10 to find a sofic shift X̂ such that the left Krieger cover (K, L) of X̂ is a bipartite labelled graph for which the induced pair of labelled graphs is (K_{1}, L_{1}), (K_{2}, L_{2}). Let (G_{1}, L_{1}), (G_{2}, L_{2}), and (G, L) be the generalized left Fischer covers of respectively X̂_{1}, X̂_{2}, and X̂. The labelled graph (G, L) is bipartite since G is a subgraph of K. Note that a predecessor set P in K_{1}^{0} or K_{2}^{0} is decomposable if and only if the corresponding predecessor set in K^{0} is decomposable. If i ∈ {1, 2} and Q ∈ G_{i}^{0} ⊆ K_{i}^{0} then there is a path in K_{i} from Q to a non-decomposable P ∈ K_{i}^{0}. By considering the corresponding path in K, it is clear that the vertex in K^{0} corresponding to Q is in G^{0}. Conversely, if Q ∈ G^{0} then there is a path in K from Q to a non-decomposable P ∈ K^{0}. If P and Q belong to the same partition K_{i}^{0} then the vertex in K_{i} corresponding to Q is in G_{i}^{0} by definition. On the other hand, if Q corresponds to a vertex in K_{i} and if P belongs to the other partition then Lemma 3.5 shows that there exists a non-decomposable P′ in the same partition as Q and an edge from P to P′ in K. Hence, there is also a path in K_{i} from the vertex corresponding to Q to the vertex corresponding to P′, so Q ∈ G_{i}^{0}. This proves that the pair of induced labelled graphs of (G, L) is (G_{1}, L_{1}), (G_{2}, L_{2}). Let Ψ̂_{±}: X̂_{1} → X̂_{2} be the standard bipartite codes induced by (G, L). Remark 3.9 shows that there exist bipartite codes ψ̂_{±}: X_{G_{1}} → X_{G_{2}} such that Ψ̂_{±} ∘ π̂_{1}|_{X_{G_{1}}} = π̂_{2}|_{X_{G_{2}}} ∘ ψ̂_{±}. The labelled graph (G, L) presents the same sofic shift as (K, L), so they both induce the same standard bipartite codes from X̂_{1} to X̂_{2}, and by Lemma 3.10, Φ̂ is one of these standard bipartite codes, so Φ̂ = Ψ̂_{+} or Φ̂ = Ψ̂_{−}. In particular, there exists a bipartite code ψ̂: X_{G_{1}} → X_{G_{2}} such that Φ̂ ∘ π̂_{1}|_{X_{G_{1}}} = π̂_{2}|_{X_{G_{2}}} ∘ ψ̂. By recoding X̂_{1} to X_{1} and X̂_{2} to X_{2} via the bipartite expressions inducing Φ, this gives a bipartite code ψ such that Φ ∘ π_{1} = π_{2} ∘ ψ when π_{1}, π_{2} are the covering maps of the generalized left Fischer covers of X_{1} and X_{2} respectively. By Theorem 3.8, any conjugacy can be decomposed as a product of bipartite codes, so this proves that the generalized left Fischer cover is canonical.

Theorem 3.12. For i ∈ {1, 2}, let X_{i} be a sofic shift with generalized left Fischer cover (G_{i}, L_{i}) and covering map π_{i}: X_{G_{i}} → X_{i}. If Φ: SX_{1} → SX_{2} is a flow equivalence then there exists a unique flow equivalence φ: SX_{G_{1}} → SX_{G_{2}} such that Φ ∘ Sπ_{1} = Sπ_{2} ∘ φ.

Proof. In [5] it is proved that the left Krieger cover respects symbol expansion: If X is a sofic shift with alphabet A, a ∈ A, • is some symbol not in A, and if X̂ is obtained from X via a symbol expansion which inserts a • after each a then the left Krieger cover of X̂ is obtained by replacing each edge labelled a in the left Krieger cover of X by two edges in sequence labelled a and • respectively. Clearly, the generalized left Fischer cover inherits this property. By [5], any canonical cover which respects flow equivalence has the desired property, so the result follows from Theorem 3.11.

4 Foundations and layers of covers

Let E = (E, L) be a finite left-resolving and predecessor-separated labelled graph. For each V ⊆ E^{0} and each word w over the alphabet A of L define

wV = {u ∈ E^{0} | u is the source of a path labelled w terminating in V }.

Definition 4.1. Let S be a subset of the power set P(E^{0}), and let ∼ be an equivalence relation on S. The pair (S, ∼) is said to be past closed if

• {v} ∈ S,

• {u} ∼ {v} implies u = v,

• aV ≠ ∅ implies aV ∈ S, and

• U ∼ V and aU ≠ ∅ implies aV ≠ ∅ and aU ∼ aV

for all u, v ∈ E^{0}, U, V ∈ S, and a ∈ A.

Let (S, ∼) be past closed. For each V ∈ S, let [V] denote the equivalence class of V with respect to ∼. When a ∈ A and V ∈ S, [V] is said to receive a if aV ≠ ∅. For each [V] ∈ S/∼, define |[V]| = min_{V ∈[V]}|V |.

Definition 4.2. Define G(E, S, ∼) to be the labelled graph with vertex set S/∼ for which there is an edge labelled a from [aV] to [V] whenever [V] receives a. For each n ∈ ℕ, the nth layer of G(E, S, ∼) is the labelled subgraph induced by S_{n} = {[V] ∈ S/∼ | n = |[V]|}. E is said to be a foundation of any labelled graph isomorphic to G(E, S, ∼).

If a labelled graph H is isomorphic to G(E, S, ∼) then the subgraph of H corresponding to the nth layer of G(E, S, ∼) is be said to be the nth layer of H with respect to E, or simply the nth layer if E is understood from the context.

Proposition 4.3. E and G(E, S, ∼) present the same sofic shift, and E is labelled graph isomorphic to the first layer of G(E, S, ∼).

Proof. By assumption, there is a bijection between E^{0} and the set of vertices in the first layer of G(E, S, ∼). By construction, there is an edge labelled a from u to v in E if and only if there is an edge labelled a from [{u}] to [{v}] in G(E, S, ∼). Every finite word presented by G(E, S, ∼) is also presented by E, so they present the same sofic shift.

The following proposition motivates the use of the term layer by showing that edges can never go from higher to lower layers.

Proposition 4.4. If [V] ∈ S/∼ receives a ∈ A then |[aV]| ≤ |[V]|. If G(E, S, ∼) has an edge from a vertex in the mth layer to a vertex in the nth layer then m ≤ n.

Proof. Choose V ∈ [V] such that |V | = |[V]|. Each u ∈ aV emits at least one edge labelled a terminating in V, and E is left-resolving, so |[aV]| ≤ |aV | ≤ |V | = |[V]|. The second statement follows from the definition of G(E, S, ∼).

Example 4.5. Let (F, L_{F}) be the left Fischer cover of an irreducible sofic shift X. For each x^{+} ∈ X^{+}, define s(x^{+}) ⊆ F^{0} to be the set of vertices where a presentation of x^{+} can start. S = {s(x^{+}) | x^{+} ∈ X^{+}} ⊆ P(F^{0}) is past closed since each vertex in the left Fischer cover is the predecessor set of an intrinsically synchronizing right-ray, so the multiplicity set cover of X can be defined to be G((F, L_{F}), S, =). An analogous cover can be defined by considering the vertices where presentations of finite words can start. Thomsen [37] constructs the derived shift space ∂X of X using right-resolving graphs, but an analogous construction works for left-resolving graphs. The procedure from [37, Example 6.10] shows that this ∂X is presented by the labelled graph obtained by removing the left Fischer cover from the multiplicity set cover.

Let X be a sofic shift, and let (K, L_{K}) be the left Krieger cover of X. In order to use the preceding results to investigate the structure of the left Krieger cover and the past set cover, define an equivalence relation on P(K^{0}) by U ∼_{∪} V if and only if ⋃_{P ∈U} P = ⋃_{Q∈V} Q. Clearly, {P } ∼_{∪} {Q} if and only if P = Q. If U, V ⊆ K^{0}, a ∈ A, aV ≠ ∅, and U ∼_{∪} V then aU ∼_{∪} aV by the definition of the left Krieger cover.

Theorem 4.6. For a sofic shift X, the generalized left Fischer cover (G, L_{G}) is a foundation of the left Krieger cover (K, L_{K}), and no smaller subgraph is a foundation.

Proof. Define S = {V ⊆ G^{0} | ∃x^{+} ∈ X^{+} such that P_{∞}(x^{+}) = ⋃_{P ∈V} P }. Note that {P } ∈ S for every P ∈ G^{0}. If x^{+} ∈ X^{+} with P_{∞}(x^{+}) = ⋃_{P ∈V} P and if aV ≠ ∅ for some a ∈ A then ax^{+} ∈ X^{+} and P_{∞}(ax^{+}) = ⋃_{P ∈aV} P. This proves that the pair (S, ∼_{∪}) is past closed, so G((G, L_{G}), S, ∼_{∪}) is well defined. Since (G, L_{G}) is a presentation of X, there is a bijection φ: S/∼_{∪} → K^{0} defined by φ([V]) = ⋃_{P ∈V} P. By construction, there is an edge labelled a from [U] to [V] in G((G, L_{G}), S, ∼_{∪}) if and only if there exists x^{+} ∈ X^{+} such that P_{∞}(ax^{+}) = ⋃_{P ∈U} P and P_{∞}(x^{+}) = ⋃_{Q∈V} Q, so G((G, L_{G}), S, ∼_{∪}) is isomorphic to (K, L_{K}). It follows from Lemma 3.1 that no proper subgraph of (G, L_{G}) can be a foundation of the left Krieger cover.

The example from [12, Section 4] shows that the left Krieger cover can be a proper subgraph of the past set cover. The following lemma will be used to further investigate this relationship.

Lemma 4.7. Let X be a sofic shift. For every right-ray x^{+} = x_{1}x_{2}x_{3} … ∈ X^{+} there exists n ∈ ℕ such that P_{∞}(x^{+}) = P_{∞}(x_{1}x_{2} … x_{k}) for all k ≥ n.

Proof. It is clear that P_{∞}(x_{1}) ⊇ P_{∞}(x_{1}x_{2}) ⊇ ⋯ ⊇ P_{∞}(x^{+}). Since X is sofic, there are only finitely many different predecessor sets of words, so there must exist n ∈ ℕ such that P_{∞}(x_{1}x_{2} … x_{k}) = P_{∞}(x_{1}x_{2} … x_{n}) for all k ≥ n. If y^{−} ∈ P_{∞}(x_{1}x_{2} … x_{n}) is given, then y^{−}x_{1}x_{2} … x_{k} ∈ X for all k ≥ n, so y^{−}x^{+} contains no forbidden words, and therefore y^{−} ∈ P_{∞}(x^{+}). Since y^{−} was arbitrary, P_{∞}(x^{+}) = P_{∞}(x_{1}x_{2} … x_{n}).

Theorem 4.8. For a sofic shift X, the generalized left Fischer cover (G, L_{G}) and the left Krieger cover (K, L_{K}) are both foundations of the past set cover (W, L_{W}).

Proof. Define S = {V ⊆ G^{0} | ∃w ∈ B(X) such that P_{∞}(w) = ⋃_{P ∈V} P }, and use Lemma 4.7 to conclude that S contains {P } for every P ∈ G^{0}. By arguments analogous to the ones used in the proof of Theorem 4.6, it follows that G((G, L_{G}), S, ∼_{∪}) is isomorphic to (W, L_{W}). To see that (K, L_{K}) is also a foundation, define T = {V ⊆ K^{0} | ∃w ∈ B(X) such that P_{∞}(w) = ⋃_{P ∈V} P }, and apply arguments analogous to the ones used above to prove that (W, L_{W}) is isomorphic to G((K, L_{K}), T, ∼_{∪}).

\begin{matrix}u \\ v \\ w \\ x \\ + \\ + \\ + \\ − \\ − \\ − \end{matrix}

Figure 2: Left Fischer cover of the 3-charge constrained shift.

P_{∞}(u) P_{∞}(v) P_{∞}(w) P_{∞}(x) P_{∞}(u) ∪ P_{∞}(v) P_{∞}(v) ∪ P_{∞}(w) P_{∞}(w) ∪ P_{∞}(x) P_{∞}(u) ∪ P_{∞}(v) ∪ P_{∞}(w) P_{∞}(v) ∪ P_{∞}(w) ∪ P_{∞}(x) + + + − − − + − + + − − + − + −

Figure 3: Left Krieger cover of the 3-charge constrained shift.

In the following, the nth layer of the left Krieger cover (past set cover) will always refer to the nth layer with respect to the generalized left Fischer cover (G, L_{G}). For a right-ray (word) x, P_{∞}(x) is a vertex in the nth layer of the left Kriger cover (past set cover) for some n ∈ ℕ, and such an x is said to be 1/n-synchronizing. Note that x is 1/n-synchronizing if and only if n is the smallest number such that there exist P_{1}, …, P_{n} ∈ G^{0} with ⋃_{i=1}^{n} P_{i} = P_{∞}(x). In an irreducible sofic shift with left Fischer cover (F, L_{F}), this happens if and only if n is the smallest number such that there exist u_{1}, …, u_{n} ∈ F^{0} with ⋃_{i=1}^{n} P_{∞}(u_{i}) = P_{∞}(x). Example 4.9. Figures 2 and 3 show, respectively, the left Fischer and the left Krieger cover of the 3-charge constrained shift (see e.g. [21, Example 1.2.7] for the definition of charge constrained shifts). There are 3 vertices in the second layer of the left Krieger cover and two in the third. Note how the left Fischer cover can be identified with the first layer of the left Krieger cover.

Corollary 4.10. If the left Krieger cover of a sofic shift is reducible then so is the past set cover.

Proof. This follows from Proposition 4.4 and Theorem 4.8.

5 The range of a flow invariant

Let E be a directed graph. Vertices u, v ∈ E^{0} properly communicate [1] if there are paths μ, λ ∈ E^{∗} of length greater than or equal to 1 such that s(μ) = u, r(μ) = v, s(λ) = v, and r(λ) = u. This relation is used to construct maximal disjoint subsets of E^{0}, called proper communication sets of vertices, such that u, v ∈ E^{0} properly communicate if and only if they belong to the same subset. The proper communication graph P C(E) is defined to be the directed graph for which the vertices are the proper communication sets of vertices of E and for which there is an edge from one proper communication set to another if and only if there is a path from a vertex in the first set to a vertex in the second. The proper communication graph of the left Krieger cover of a sofic shift space is a flow-invariant [1]. Let X be an irreducible sofic shift with left Fischer cover (F, L_{F}) and left Krieger cover (K, L_{K}), and let E be the proper communication graph of K. By construction, E is finite and contains no circuit. The left Fischer cover is isomorphic to an irreducible subgraph of (K, L_{K}) corresponding to a root r ∈ E^{0} [19, Lemma 2.7], and by definition, there is an edge from u ∈ E^{0} to v ∈ E^{0} whenever u > v. The following proposition gives the range of the flow-invariant by proving that all such graphs can occur.

Proposition 5.1. Let E be a finite directed graph with a root and without circuits. E is the proper communication graph of the left Krieger cover of an AFT shift if there is an edge from u ∈ E^{0} to v ∈ E^{0} whenever u > v.

Proof. Let E be an arbitrary finite directed graph which contains no circuit and which has a root r, and let Ẽ be the directed graph obtained from E by adding an edge from u ∈ E^{0} to v ∈ E^{0} whenever u > v. The goal is to construct a labelled graph (F, L_{F}) which is the left Fischer cover of an irreducible sofic shift with the desired properties. For each v ∈ E^{0}, let l(v) be the length of the longest path from r to v. This is well-defined since E does not contain any circuits. For each v ∈ E^{0}, define n(v) = 2^{l(v)} vertices v_{1}, …, v_{n(v)} ∈ F^{0}. The single vertex corresponding to the root r ∈ E^{0} is denoted r_{1}. For each v ∈ E^{0}, draw a loop of length 1 labelled a_{v} at each of the vertices v_{1}, …, v_{n(v)} ∈ F^{0}. If there is an edge from u ∈ E^{0} to v ∈ E^{0} then l(v) > l(u). From each vertex u_{1}, …, u_{n(u)} draw n(u, v) = n(v)/n(u) = 2^{l(v)−l(u)} ≥ 2 edges labelled a_{u,v}^{1}, …, a_{u,v}^{n(u,v)} such that every vertex v_{1}, …, v_{n(v)} receives exactly one of these edges. For each sink v ∈ E^{0} draw a uniquely labelled edge from each vertex v_{1}, …, v_{n(v)} to r_{1}. This finishes the construction of (F, L_{F}). By construction, F is irreducible, right-resolving, and left-resolving. Additionally, it is predecessor-separated because there is a uniquely labelled path to every vertex in F^{0} from r_{1}. Thus, (F, L_{F}) is the left Fischer cover of an AFT shift X. Let (K, L_{K}) be the left Krieger cover of X. For every v ∈ E^{0}, P_{∞}(a_{v}^{∞}) = ⋃_{i=1}^{n(v)} P_{∞}(v_{i}) and no smaller set of vertices has this property, so P_{∞}(a_{v}^{∞}) is a vertex in the n(v)th layer of the left Krieger cover. There is clearly a loop labelled a_{v} at the vertex P_{∞}(a_{v}^{∞}), so it belongs

\begin{matrix}r \\ x \\ y \\ z \end{matrix}

Figure 4: A directed graph with root r and without circuits.

r_{1} x_{1} x_{2} y_{1} y_{2} z_{1} z_{2} z_{3} z_{4} r_{1} a_{r,x}^{1} a_{r,x}^{2} a_{r,y}^{1} a_{r,y}^{2} a_{r,z}^{1} a_{r,z}^{2} a_{r,z}^{3} a_{r,z}^{4} a_{y,z}^{1} a_{y,z}^{2} a_{y,z}^{1} a_{y,z}^{2} a_{x} a_{x} a_{y} a_{y} a_{z} a_{z} a_{z} a_{z}

Figure 5: Left Fischer cover of the sofic shift X considered in Example 5.2.

to a proper communication set of vertices. Furthermore, ba_{v}^{∞} ∈ X^{+} if and only if b = a_{v} or b = a_{u,v}^{i} for some u ∈ E^{0} and 1 ≤ i ≤ n(u, v). By construction, P_{∞}(a_{u,v}^{i}a_{v}^{∞}) = ⋃_{i=1}^{n(u)} P_{∞}(u_{i}) = P_{∞}(a_{u}^{∞}), so there is an edge from P_{∞}(a_{u}^{∞}) to P_{∞}(a_{v}^{∞}) if and only if there is an edge from u to v in E. This proves that E, and hence also Ẽ, are subgraphs of the proper communication graph of K. Since the edges which terminate at r_{1} are uniquely labelled, any x^{+} ∈ X^{+} which contains one of these letters must be intrinsically synchronizing. If x^{+} ∈ X^{+} does not contain any of these letters then x^{+} must be eventually periodic with x^{+} = wa_{v}^{∞} for some v ∈ E^{0} and w ∈ B(X). Thus, K only has the vertices described above, and therefore the proper communication graph of K is Ẽ.

Example 5.2. To illustrate the construction used in the proof of Proposition 5.1, let E be the directed graph drawn in Figure 4. E has a unique maximal vertex r and contains no circuit, so it is the proper communication graph of

(F, L_{F}) r_{1} P_{∞}(a_{x}^{∞}) P_{∞}(a_{y}^{∞}) P_{∞}(a_{z}^{∞}) a_{r,x}^{1} a_{r,x}^{2} a_{r,y}^{1} a_{r,y}^{2} a_{r,z}^{1}, a_{r,z}^{2}, a_{r,z}^{3}, a_{r,z}^{4} a_{y,z}^{1} a_{y,z}^{2} a_{x} a_{y} a_{z}

Figure 6: Left Krieger cover of the shift space X considered in Example 5.2. The structure of the irreducible component corresponding to the left Fischer cover has been suppressed.

the left Krieger cover of an irreducible sofic shift. Note that l(x) = l(y) = 1 and that l(z) = 2. Figure 5 shows the left Fischer cover of a sofic shift X constructed using the method from the proof of Proposition 5.1. Note that the top and bottom vertices should be identified, and that the labelling of the edges terminating at r_{1} has been suppressed. Figure 6 shows the left Krieger cover of X, but the structure of the irreducible component corresponding to the left Fischer cover has been suppressed to emphasize the structure of the higher layers.

In [1], it was also remarked that an invariant analogous to the one discussed in Proposition 5.1 is obtained by considering the proper communication graph of the right Krieger cover. The following example shows that the two invariants may carry different information.

Example 5.3. The labelled graph in Figure 7 is left-resolving, irreducible, and predecessor-separated, so it is the left Fischer cover of an irreducible sofic shift. Similarly, the labelled graph in Figure 8 is irreducible, right-resolving and follower-separated, so it is the right Fischer cover of an irreducible sofic shift. By considering the edges labelled d, it is easy to see that the two graphs present the same sofic shift space X. Every right-ray which contains a letter different from a or a′ is intrinsically synchronizing, so consider a right-ray x^{+} ∈ X^{+} such that (x^{+})_{i} ∈ {a, a′} for all i ∈ ℕ. By considering Figure 7, it is clear that P_{∞}(x^{+}) = P_{∞}(u) ∪ P_{∞}(v) ∪ P_{∞}(y) = P_{∞}(y), so P (x^{+}) is also in the first layer of the left Krieger cover. Hence, the proper communication graph has only one vertex and no edges. Every left-ray containing a letter different from a or a′ is intrinsically synchronizing, so consider the left-ray a^{∞} ∈ X^{−}. Figure 8 shows that F_{∞}(a^{∞}) =

\begin{aligned}& u \\ v & w & x \\ & y \end{aligned} a′ a a a a′ a′ bfgecd fb

Figure 7: Left Fischer cover of the irreducible sofic shift X discussed in Example 5.3.

\begin{aligned}& u′ \\ v′ & w′ & x′ \end{aligned} a′ a a a′ bfged d c

Figure 8: Right Fischer cover of the irreducible sofic shift X discussed in Example 5.3.

F_{∞}(u′) ∪ F_{∞}(v′) and that no single vertex y′ in the right Fischer cover has F_{∞}(y′) = F_{∞}(a^{∞}), so there is a vertex in the second layer of the right Krieger cover. In particular, the corresponding proper communication graph is nontrivial.

6 C^{∗}-Algebras associated to sofic shift spaces

Cuntz and Krieger [13] introduced a class of C^{∗}-algebras which can naturally be viewed as the universal C^{∗}-algebras associated to shifts of finite type. This was generalized by Matsumoto [23] who associated two C^{∗}-algebras O_{X} and O_{X^{∗}} to every shift space X, and these Matsumoto algebras have been studied intensely [8, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]. The two Matsumoto algebras O_{X} and O_{X^{∗}} are generated by elements satisfying the same relations, but they are not isomorphic in general [12]. This paper will follow the approach of Carlsen in [9] where a universal C^{∗}-algebra OX̃ is associated to every onesided shift space X̃. This also gives a way to associate C^{∗}-algebras to every two-sided shift since a two-sided shift X corresponds to two one-sided shifts X^{+} and X^{−}. Ideal lattices. Let X be a sofic shift space and let O_{X^{+}} be the universal C^{∗}-algebra associated to the one-sided shift X^{+} as defined in [9]. Carlsen proved that O_{X^{+}} is isomorphic to the Cuntz-Krieger algebra of the left Krieger cover of X [8], so the lattice of gauge invariant ideals in O_{X^{+}} is given by the proper communication graph of the left Krieger cover of X [3, 20], and all ideals are given in this way if the left Krieger cover satisfies Condition (K) [36, Theorem 4.9]. Hence, Proposition 4.4 and Theorem 4.6 can be used to investigate the ideal lattice of O_{X^{+}}. For a reducible sofic shift, a part of the ideal lattice is given by the structure of the generalized left Fischer cover, which is reducible, but if X is an irreducible sofic shift, and the left Krieger cover of X satisfies Condition (K) then the fact that the left Krieger cover has a unique top component implies that O_{X^{+}} will always have a unique maximal ideal. The following proposition shows that all these lattices can be realized.

Proposition 6.1. Any finite lattice of ideals with a unique maximal ideal is the ideal lattice of the universal C^{∗}-algebra O_{X^{+}} associated to an AFT shift X.

Proof. Let E be a finite directed graph whitout circuits and with a unique maximal vertex. Consider the following slight modification of the algorithm from the proof of Proposition 5.1. For each v ∈ E, draw two loops of length 1 at each vertex v_{1}, …, v_{n(v)} associated to v: One labelled a_{v} and one labelled a′_{v}. The rest of the construction is as before. Let (K, L_{K}) be the left Krieger cover of the corresponding sofic shift. As before, the proper communication graph of K is given by E, and now (K, L_{K}) satisfies Condition (K), so there is a bijective correspondence between the hereditary subsets of E^{0} and the ideals of C^{∗}(K) ≅ O_{X^{+}}. Since E was arbitrary, any finite ideal lattice with a unique maximal ideal can be obtained in this way.

The C^{∗}-algebras O_{X^{+}} and O_{X^{−}}. Every two-sided shift space X corresponds to two one-sided shift spaces X^{+} and X^{−}, and this gives two natural ways to associate a universal C^{∗}-algebra to X. The next goal is to show that these two C^{∗}-algebras may carry different information about the shift space. Let O_{X^{−}} be the universal C^{∗}-algebra associated to the one-sided shift space (X^{T})^{+} as defined in [9]. The left Krieger cover of X^{T} is the transpose of the right Krieger cover of X, so by [8], O_{X^{−}} is isomorphic to the Cuntz-Krieger algebra of the transpose of the right Krieger cover of X. Example 6.2. Let X be the sofic shift from Example 5.3. Note that the left and right Krieger covers of X both satisfy Condition (K) from [36], so the corresponding proper communication graphs completely determine the ideal lattices of O_{X^{+}} and O_{X^{−}}. The proper communication graph of the left Krieger cover (K, L_{K}) of X is trivial, so O_{X^{+}} is simple, while there are precisely two vertices in the proper communication graph of the right Krieger cover of X, so there is exactly one non-trivial ideal in O_{X^{−}}. In particular, O_{X^{+}} and O_{X^{−}} are not isomorphic. Consider the edge shift Y = X_{K}. This is an SFT, and the left and right Krieger covers of Y are both (K, L_{Id}), where L_{Id} is the identity map on the edge set K^{1}. By [8], O_{X^{+}} and O_{Y^{+}} are isomophic to C^{∗}(K). Similarly, O_{Y^{−}} is isomorphic to C^{∗}(K^{T}) and K^{T} is an irreducible graph satisfying Condition (K), so O_{Y^{−}} is simple. In particular, O_{Y^{−}} is not isomophic to O_{X^{−}}. This shows that the C^{∗}-algebras associated to X^{+} and X^{−} are not always isomorphic, and that there can exist a shift space Y such that O_{Y^{+}} is isomorphic to O_{X^{+}} while O_{Y^{−}} is not isomorphic to O_{X^{−}}. An investigation of Condition (∗). In [12], two C^{∗}-algebras O_{X} and O_{X^{∗}} are associated to every two-sided shift space X. The C^{∗}-algebras O_{X}, O_{X^{∗}}, and O_{X^{+}} are generated by partial isometries satisfying the same relations, but O_{X^{+}} is always universal unlike O_{X} [9]. In [12], it is proved that O_{X} and O_{X^{∗}} are isomorphic when X satisifies a condition called Condition (∗). The example from [12, Section 4] shows that not all sofic shift spaces satisfy this condition by constructing a sofic shift where the left Krieger cover and the past set cover are not isomorphic. The relationship between Condition (∗) and the structure of the left Krieger cover and the past set cover is further clarified by the final main result. For each l ∈ ℕ and w ∈ B(X) define P_{l}(w) = {v ∈ B(X) | vw ∈ B(X), |v| ≤ l}. Two words v, w ∈ B(X) are said to be l-past equivalent if P_{l}(v) = P_{l}(w). For x^{+} ∈ X^{+}, P_{l}(x^{+}) and l-past equivalence are defined analogously. Condition (∗). For every l ∈ ℕ and every infinite F ⊆ B(X) such that P_{l}(u) = P_{l}(v) for all u, v ∈ F there exists x^{+} ∈ X^{+} such that P_{l}(w) = P_{l}(x^{+}) for all w ∈ F.

Lemma 6.3. A vertex P in the past set cover of a sofic shift X is in an essential subgraph if and only if there exist infinitely many w ∈ B(X) such that P_{∞}(w) = P.

Proof. Let P be a vertex in an essential subgraph of the past set cover of X, and let x^{+} ∈ X^{+} be a right ray with a presentation starting at P. Given n ∈ ℕ, there exists w_{n} ∈ B(X) such that P = P_{∞}(x_{1}x_{2} … x_{n}w_{n}). To prove the converse, let P be a vertex in the past set cover for which there exist infinitely many w ∈ B(X) such that P = P_{∞}(w). For each w, there is a path labelled w_{[1,|w|−1]} starting at P. There are no sources in the past set cover, so this implies that P is not stranded.

Proposition 6.4. A sofic shift X satisfies Condition (∗) if and only if the left Krieger cover is the maximal essential subgraph of the past set cover.

Proof. Assume that X satisfies Condition (∗). Let P be a vertex in an essential subgraph of the past set cover and define F = {w ∈ B(X) | P_{∞}(w) = P }. Choose m ∈ ℕ such that for all x, y ∈ B(X) ∪ X^{+}, P_{∞}(x) = P_{∞}(y) if and only if P_{m}(x) = P_{m}(y). By Lemma 6.3, F is an infinite set, so Condition (∗) can be used to choose x^{+} ∈ X^{+} such that P_{m}(x^{+}) = P_{m}(w) for all w ∈ F. By the choice of m, this means that P_{∞}(x^{+}) = P_{∞}(w) = P for all w ∈ F, so P is a vertex in the left Krieger cover. To prove the other implication, assume that the left Krieger cover is the maximal essential subgraph of the past set cover. Let l ∈ ℕ be given, and consider an infinite set F ⊆ B(X) for which P_{l}(u) = P_{l}(v) for all u, v ∈ F. Since X is sofic, there are only finitely many different predecessor sets, so there must exist w ∈ F such that P_{∞}(w) = P_{∞}(v) for infinitely many v ∈ F. By Lemma 6.3, this proves that P = P_{∞}(w) is a vertex in the maximal essential subgraph of the past set cover. By assumption, this means that it is a vertex in the left Krieger cover, so there exists x^{+} ∈ X^{+} such that P_{∞}(w) = P_{∞}(x^{+}). In particular, P_{l}(x^{+}) = P_{l}(w) = P_{l}(v) for all v ∈ F, so Condition (∗) is satisfied.

In [2], it was proved that O_{X^{∗}} is isomorphic to the Cuntz-Krieger algebra of the past set cover of X when X satisfies a condition called Condition (I). According to Carlsen [7], a proof similar to the proof which shows that O_{X^{+}} is isomorphic to the Cuntz-Krieger algebra of the left Krieger cover of X should prove that O_{X^{∗}} is isomorphic to the Cuntz-Krieger algebra of the subgraph of the past set cover of X induced by the vertices P for which there exist infinitely many words w such that P_{∞}(w) = P. Using Lemma 6.3, this shows that O_{X^{∗}} is always isomorphic to the Cuntz-Krieger algebra of the maximal essential subgraph of the past set cover of X.

References

[1] T. Bates, S. Eilers, and D. Pask. Reducibility of covers of AFT shifts. Israel J. Math., 2011 (in press).

[2] T. Bates and D. Pask. C^{∗}-algebras of labelled graphs. J. Operator Theory, 57(1):207–226, 2007.

[3] T. Bates, D. Pask, I. Raeburn, and W. Szymański. The C^{∗}-algebras of row-finite graphs. New York J. Math., 6:307–324 (electronic), 2000.

[4] M. Boyle. Flow equivalence of shifts of finite type via positive factorizations. Pacific J. Math., 204(2):273–317, 2002.

[5] M. Boyle, T. M. Carlsen, and S. Eilers. Flow equivalence of sofic shifts. In preparation.

[6] M. Boyle and D. Huang. Poset block equivalence of integral matrices. Trans. Amer. Math. Soc., 355(10):3861–3886 (electronic), 2003.

[7] T. M. Carlsen. Personal communication.

[8] T. M. Carlsen. On C^{∗}-algebras associated with sofic shifts. J. Operator Theory, 49(1):203–212, 2003.

[9] T. M. Carlsen. Cuntz-Pimsner C^{∗}-algebras associated with subshifts. Internat. J. Math., 19(1):47–70, 2008.

[10] T. M. Carlsen and S. Eilers. Augmenting dimension group invariants for substitution dynamics. Ergodic Theory Dynam. Systems, 24(4):1015–1039, 2004.

[11] T. M. Carlsen and S. Eilers. Matsumoto K-groups associated to certain shift spaces. Doc. Math., 9:639–671 (electronic), 2004.

[12] T. M. Carlsen and K. Matsumoto. Some remarks on the C^{∗}-algebras associated with subshifts. Math. Scand., 95(1):145–160, 2004.

[13] J. Cuntz and W. Krieger. A class of C^{∗}-algebras and topological Markov chains. Invent. Math., 56(3):251–268, 1980.

[14] R. Fischer. Sofic systems and graphs. Monatsh. Math., 80(3):179–186, 1975.

[15] D. Huang. Flow equivalence of reducible shifts of finite type. Ergodic Theory Dynam. Systems, 14(4):695–720, 1994.

[16] N. Jonoska. Sofic shifts with synchronizing presentations. Theoret. Comput. Sci., 158(1-2):81–115, 1996.

[17] N. Jonoska and B. Marcus. Minimal presentations for irreducible sofic shifts. IEEE Trans. Inform. Theory, 40(6):1818–1825, 1994.

[18] Y. Katayama, K. Matsumoto, and Y. Watatani. Simple C^{∗}-algebras arising from β-expansion of real numbers. Ergodic Theory Dynam. Systems, 18(4):937–962, 1998.

[19] W. Krieger. On sofic systems. I. Israel J. Math., 48(4):305–330, 1984.

[20] A. Kumjian, D. Pask, I. Raeburn, and J. Renault. Graphs, groupoids, and Cuntz-Krieger algebras. J. Funct. Anal., 144(2):505–541, 1997.

[21] D. Lind and B. Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995.

[22] B. Marcus. Sofic systems and encoding data. IEEE Trans. Inform. Theory, 31(3):366–377, 1985.

[23] K. Matsumoto. On C^{∗}-algebras associated with subshifts. Internat. J. Math., 8(3):357–374, 1997.

[24] K. Matsumoto. K-theory for C^{∗}-algebras associated with subshifts. Math. Scand., 82(2):237–255, 1998.

[25] K. Matsumoto. Dimension groups for subshifts and simplicity of the associated C^{∗}-algebras. J. Math. Soc. Japan, 51(3):679–698, 1999.

[26] K. Matsumoto. Relations among generators of C^{∗}-algebras associated with subshifts. Internat. J. Math., 10(3):385–405, 1999.

[27] K. Matsumoto. A simple C^{∗}-algebra arising from a certain subshift. J. Operator Theory, 42(2):351–370, 1999.

[28] K. Matsumoto. On automorphisms of C^{∗}-algebras associated with subshifts. J. Operator Theory, 44(1):91–112, 2000.

[29] K. Matsumoto. Stabilized C^{∗}-algebras constructed from symbolic dynamical systems. Ergodic Theory Dynam. Systems, 20(3):821–841, 2000.

[30] K. Matsumoto. Bowen-Franks groups for subshifts and Ext-groups for C^{∗}-algebras. K-Theory, 23(1):67–104, 2001.

[31] K. Matsumoto. C^{∗}-algebras associated with presentations of subshifts. Doc. Math., 7:1–30 (electronic), 2002.

[32] K. Matsumoto, Y. Watatani, and M. Yoshida. KMS states for gauge actions on C^{∗}-algebras associated with subshifts. Math. Z., 228(3):489– 509, 1998.

[33] M. Nasu. An invariant for bounded-to-one factor maps between transitive sofic subshifts. Ergodic Theory Dynam. Systems, 5(1):89–105, 1985.

[34] M. Nasu. Topological conjugacy for sofic systems. Ergodic Theory Dynam. Systems, 6(2):265–280, 1986.

[35] B. Parry and D. Sullivan. A topological invariant of flows on 1-dimensional spaces. Topology, 14(4):297–299, 1975.

[36] I. Raeburn. Graph algebras, volume 103 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2005.

[37] K. Thomsen. On the structure of a sofic shift space. Trans. Amer. Math. Soc., 356(9):3557–3619 (electronic), 2004.

[38] B. Weiss. Subshifts of finite type and sofic systems. Monatsh. Math., 77:462–474, 1973.

Rune Johansen Department of Mathematical Sciences University of Copenhagen Universitetsparken 5 2100 København Ø Denmark 132

Documenta Mathematica 16 (2011)