A Lambda-Graph System

for the Dyck Shift and Its K-Groups

Wolfgang Krieger and Kengo Matsumoto

Received: December 12, 2002

Communicated by Joachim Cuntz

Abstract. A property of subshifts is described that allows to associate to the subshift a distinguishied presentation by a compact Shannon graph. For subshifts with this property and for the resulting invariantly associated compact Shannon graphs and their λ-graph systems the term ‘Cantor horizon’ is proposed. The Dyck shifts are Cantor horizon. The C^{∗}-algebras that are obtained from the Cantor horizon λ-graph systems of the Dyck shifts are separable, unital, nuclear, purely infinite and simple with UCT. The K-groups and Bowen-Franks groups of the Cantor horizon λ-graph systems of the Dyck shifts are computed and it is found that the K_{0}-groups are not finitely generated.

2000 Mathematics Subject Classification: Primary 37B10; Secondary 46L35. Keywords and Phrases: subshift, Shannon graph, λ-graph system, Dyck shift, K-groups, C^{∗}-algebra

0. Introduction

Let Σ be a finite alphabet. On the shift space Σ^{ℤ} one has the left-shift that sends a point (σ_{i})_{i∈ℤ} into the point (σ_{i+1})_{i∈ℤ}. In symbolic dynamics one studies the dynamical systems, called subshifts, that are obtained by restricting the shift to a shift invariant closed subset of Σ^{ℤ}. For an introduction to symbolic dynamics see [Ki] or [LM]. A finite word in the symbols of Σ is said to be admissible for the subshift X ⊂ Σ^{ℤ} if it appears somewhere in a point of X. A subshift is uniquely determined by its set of admissible words. Throughout this paper, we denote by ℤ_{+} and ℕ the set of all nonnegative integers and the set of all positive integers respectively. A directed graph G whose edges are labeled by symbols in the finite alphabet Σ is called a Shannon graph if for every vertex u of G and for every α ∈ Σ, G has at most one edge with initial vertex u and label α. We say that a Shannon graph G presents a subshift X if every vertex of G has a predecessor and a successor and if the set of admissible words of X coincides with the set of label sequences of finite paths on G. To a Shannon graph G there is associated a topological Markov chain M(G). The state space of M(G) is the set of pairs (u, α), where u is a vertex of G and α is the label of an edge of G with initial vertex u. Here a transition from state (u, α) to state (v, β) is allowed if and only if v is the final vertex of the edge with initial vertex u and label α. For a vertex u of Shannon graph G we denote the forward context of u by Γ^{+}(u). Γ^{+}(u) is the set of sequences in Σ^{ℕ} that are label sequences of infinite paths in G that start at the vertex u. We say that a Shannon graph G is forward separated if vertices of G, that have the same forward context, are identical. The Shannon graphs that we consider in this paper are forward separated. We always identify the vertices of a forward separated Shannon graph G with their forward contexts, and then use on the vertex set of G the topology that is given by the Hausdorff metric on the set of nonempty compact subsets of Σ^{ℕ}. There is a one-to-one correspondence between forward-separated compact Shannon graphs G such that every vertex has a predecessor and a class of λ-graph systems [KM]. We recall that a λ-graph system is a directed labelled Bratteli diagram with an additional structure. We write the vertex set of a λ-graph system as

V = ⋃_{n∈ℤ_{+}} V_{−n}.

Every edge with initial vertex in V_{−n}, has its final vertex in V_{−n+1}, n ∈ ℕ. It is required that every vertex has a predecessor and every vertex except the vertex in V_{0} has a successor. In this paper we consider λ-graph-systems that are forward separated Shannon graphs. Their additional structure is given by a mapping

ι : ⋃_{n∈ℕ} V_{−n} → V

such that

ι(V_{−n}) = V_{−n+1}, n ∈ ℕ

A Lambda-Graph System for the Dyck Shift … 81

that is compatible with the labeling, that is, if u is the initial vertex of an edge with label α and final vertex v, then ι(u) is the intial vertex of an edge with label α and final vertex ι(v). Given a subshift X ⊂ Σ^{ℤ} there is a one-to-one correspondence between the compact forward separated Shannon graphs that present X, and the forward separated Shannon λ-graph systems that present X. To describe this oneto-one correspondence denote for a vertex v of a Shannon graph by v_{n} the set of initial segments of length n of the sequences in V, n ∈ ℕ. The λ-graph system that corresponds to the forward separated Shannon graph has as its set V_{−n} the set of v_{n}, n ∈ ℤ_{+}, v a vertex of G, and if in G there is an edge with initial vertex u and final vertex v and label α then in the corresponding λ-graph system there is an edge with initial vertex u_{n}, final vertex v_{n−1}, n ∈ ℕ, and label α, the mapping ι of the corresponding λ-graph system deleting last symbols. λ-graph systems can be described by their symbolic matrix systems [Ma]

(M_{−n,−n−1}, I_{−n,−n−1})_{n∈ℤ_{+}}.

Here M_{−n,−n−1} is the symbolic matrix

[M_{−n,−n−1}(u, v)]_{u∈V_{−n},v∈V_{−n−1}}

that is given by setting M_{−n,−n−1}(u, v) equal to α_{1} + ⋯ + α_{k} if in V there is an edge with initial vertex v and final vertex u with label α_{i}, i = 1, …, k and by setting M_{−n,−n−1}(u, v) equal to zero otherwise. I_{−n,−n−1} is the zero-one matrix

[I_{−n,−n−1}(u, v)]_{u∈V_{−n},v∈V_{−n−1}}

that is given by setting I_{−n,−n−1}(u, v) equal to one if ι(v) = u and by setting I_{−n,−n−1}(u, v) equal to zero otherwise. We remark that the time direction considered here is opposite to the time direction in [Ma]. For symbolic matrix systems there is a notion of strong shift equivalence [Ma] that extends the notion of strong shift equivalence for transition matrices of topological Markov shifts [Wi] and of the symbolic matrices of sofic systems [BK,N]. To a symbolic matrix system there are invariantly associated K-groups and Bowen-Franks groups [Ma]. To describe them, let

M_{n,n+1} = [M_{n,n+1}(u, v)]_{u∈V_{−n},v∈V_{−n−1}}

be the nonnegative matrix that is given by setting M_{n,n+1}(u, v) equal to zero if M_{−n,−n−1}(u, v) is zero, and by setting it equal to the number of the symbols whose sum is M_{−n,−n−1}(u, v) otherwise. We let I_{n,n+1}, n ∈ ℤ_{+} be I_{−n,−n−1}. Let m(n) be the cardinal number of the vertex set V_{−n}. Also denote by Ī_{n,n+1}^{t}, n ∈ ℤ_{+} the homomorphism from ℤ^{m(n)}/(M_{n−1,n}^{t} − I_{n−1,n}^{t})ℤ^{m(n−1)} to ℤ^{m(n+1)}/(M_{n,n+1}^{t} − I_{n,n+1}^{t})ℤ^{m(n)} that is induced by I_{n,n+1}^{t}. Then

K_{0}(M, I) = \underrightarrow{lim}_{n}\{ℤ^{m(n+1)}/(M_{n,n+1}^{t} − I_{n,n+1}^{t})ℤ^{m(n)}, Ī_{n,n+1}^{t}\},

K_{1}(M, I) = \underrightarrow{lim}_{n}\{Ker(M_{n,n+1}^{t} − I_{n,n+1}^{t}) in ℤ^{m(n)}, I_{n,n+1}^{t}\}.

Let ℤ_{I} be the group of the projective limit \underrightarrow{lim}_{n}\{ℤ^{m(n)}, I_{n,n+1}\}. The sequence

M_{n,n+1} − I_{n,n+1}, n ∈ ℤ_{+} acts on it as an endomorphism, denoted by M − I. The Bowen-Franks groups BF^{I}(M, I), i = 0, 1 are defined by

BF^{0}(M, I) = ℤ_{I}/(M − I)ℤ_{I}, BF^{1}(M, I) = Ker(M − I) in ℤ_{I}.

Given a subshift X ⊂ Σ^{ℤ} we use for x = (x_{i})_{i∈ℤ} ∈ X notation like

x_{[j,k]} = (x_{i})_{j≤i≤k},

and we set

X_{[j,k]} = {x_{[j,k]} | x ∈ X}, j, k ∈ ℤ, j < k,

using similar notations when indices range is infinite intervals. We denote the forward context of a point x^{−} in X_{(−∞,0]} by Γ^{+}(x^{−}),

Γ^{+}(x^{−}) = {x^{+} ∈ X_{[1,∞)} | (x^{−}, x^{+}) ∈ X}.

The set G(X) = {Γ^{+}(x^{−}) | x^{−} ∈ X_{(−∞,0]}} is the vertex set of a forward separated Shannon graph that presents X. The λ-graph system of its closure was introduced in [KM] as the canonical λ-graph system of the subshift X. It is canonically associated to the subshift in the sense that a topological conjugacy of subshifts induces a strong shift equivalence of their canonical λ-graph systems. For a subshift X ⊂ Σ^{ℤ} that is synchronizing [Kr] (or semisynchronizing [Kr] ) one has an intrinsically defined shift invariant dense subset P_{s}(X) of periodic points of X, and one has associated to X the presenting forward separated Shannon graph whose vertex set is the set of forward contexts Γ^{+}(x), where x is left asymptotic to a point in P_{s}(X). These Shannon graphs are canonically associated to the synchronizing (or semisynchronizing) subshift, in the sense that a topological conjugacy of subshifts induces a block conjugacy of the topological Markov chains of the Shannon graphs and also a strong shift equivalence [Ma] of the λ-graph systems of their closures. Prototype examples of semisynchronizing subshifts are the Dyck shifts that can be defined via the Dyck inverse monoids. The Dyck inverse monoid is the inverse monoid (with zero) with generators α_{n}, β_{n}, 1 ≤ n ≤ N, and relations

α_{n}β_{n} = 1,  1 ≤ n ≤ N,
α_{n}β_{m} = 0,  1 ≤ n, m ≤ N, n ≠ m

and the Dyck shift D_{N} is defined as the subshift D_{N} ⊂ {α_{n}, β_{n} | 1 ≤ n ≤ N}^{ℤ}, whose admissible words (γ_{i})_{0≤i≤I} satisfy the condition

∏_{0≤i≤I} γ_{i} ≠ 0.

In section 1 we introduce another class of subshifts X ⊂ Σ^{ℤ} with an intrinsically defined shift invariant dense set P_{Ch}(X) of periodic points. Again the Dyck shifts serve here as prototypes. In the Dyck shift D_{N} the points in P_{Ch}(D_{N}) are such that during a period there appears an event that has the potential to influence even the most distant future. In other words, a point (x_{i})_{i∈ℤ} in D_{N} with period p is in P_{Ch}(D_{N}) if the normal form of the word (x_{i})_{0≤i<p} is a word in the symbols α_{n}, 1 ≤ n ≤ N. One can view here the record of an infinite sequence of events as a point in a Cantor discontinuum. With this in mind, we call the subshifts in this class Cantor horizon subshifts. The presenting Shannon graph with vertex set the set of forward contexts Γ^{+}(y^{−}), where y^{−} is negatively asymptotic to a point in P_{Ch}(X), is canonically associated to the Cantor horizon subshift X ⊂ Σ^{ℤ}, and so is the λ-graph system of its closure, that we call the Cantor horizon λ-graph system of X. The Cantor horizon λ-graph system of a Cantor horizon subshift is a sub λ-graph system of its canonical λ-graph system. The K-groups and Bowen-Franks groups of the symbolic matrix system (M^{D_{N}} , I^{D_{N}}) for the canonical λ-graph systems of the Dyck shifts D_{N}, N ≥ 2 were computed in [Ma2]. These are

K_{0}(M^{D_{N}} , I^{D_{N}}) ≅ ∑_{n∈ℕ} ℤ,  K_{1}(M^{D_{N}} , I^{D_{N}}) ≅ 0,
BF^{0}(M^{D_{N}} , I^{D_{N}}) ≅ 0,  BF^{1}(M^{D_{N}} , I^{D_{N}}) ≅ ∏_{n∈ℕ} ℤ.

In section 3 we determine the symbolic matrix system (M^{Ch(D_{2})}, I^{Ch(D_{2})}) of the Cantor horizon λ-graph system 𝔏^{Ch(D_{2})} of the Dyck shift D_{2}, and we compute its K-groups. Denoting the group of all ℤ-valued continuous functions on the Cantor discontinuum ℭ by C(ℭ, ℤ) one has

K_{0}(M^{Ch(D_{2})}, I^{Ch(D_{2})}) ≅ ℤ/2ℤ ⊕ C(ℭ, ℤ),

and one has

K_{1}(M^{Ch(D_{2})}, I^{Ch(D_{2})}) ≅ 0.

One can construct simple C^{∗}-algebras from irreducible λ-graph systems [Ma3]. A λ-graph system is said to be irreducible if for a sequence v_{−n} ∈ V_{−n}, n ∈ ℤ_{+} of vertices with ι(v_{−n}) = v_{−n+1} and for a vertex u, there exists an N ∈ ℤ_{+} such that there is a path from v_{−N} to u. It is said to be aperiodic if for a vertex u, there exists an N ∈ ℤ_{+} such that for all v ∈ V_{−N} there exist paths from v to u. The Cantor horizon λ-graph system 𝔏^{Ch(D_{2})} of the Dyck shift D_{2} is irreducible and moreover aperiodic. Hence the resulting C^{∗}-algebra O_{𝔏^{Ch(D_{2})}} is simple and purely infinite whose K_{0}-group and K_{1}-group are the above groups K_{0}(M^{Ch(D_{2})}, I^{Ch(D_{2})}) and K_{1}(M^{Ch(D_{2})}, I^{Ch(D_{2})}) respectively (cf. [Ma3]). In section 4, we compute the Bowen-Franks groups of the symbolic matrix system (M^{Ch(D_{2})}, I^{Ch(D_{2})}). In section 5, we consider the K-groups and Bowen-Franks groups of the Dyck shifts D_{N}, N ≥ 2. Here one has

K_{0}(M^{Ch(D_{N})}, I^{Ch(D_{N})}) ≅ ℤ/Nℤ ⊕ C(ℭ, ℤ),
K_{1}(M^{Ch(D_{N})}, I^{Ch(D_{N})}) ≅ 0.

1. Subshifts with Cantor horizon lambda-graph systems

Denoting for a given subshift X ⊂ Σ^{ℤ}, the right context of an admissible block x_{[i,j]}, x ∈ X, i, j ∈ ℤ, i ≤ j, by Γ^{+}(x_{[i,j]}),

Γ^{+}(x_{[i,j]}) = {y^{+} ∈ X_{(j,∞)} | (x_{[i,j]}, y^{+}) ∈ X_{[i,∞)}}

and its left context by Γ^{−}(x_{[i,j]}),

Γ^{−}(x_{[i,j]}) = {y^{−} ∈ X_{(−∞,i)} | (y^{−}, x_{[i,j]}) ∈ X_{(−∞,j]}},

we set

ω^{+}(x_{[i,j]}) = ⋂_{y^{−}∈Γ^{−}(x_{[i,j]})}{y^{+} ∈ X_{(j,∞)} | (y^{−}, x_{[i,j]}, y^{+}) ∈ X}.

Lemma 1.1. Let X̃ ⊂ Σ̃^{ℤ}, X ⊂ Σ^{ℤ} be subshifts and let ψ : X̃ → X be a topological conjugacy. Let for some L ∈ ℤ_{+} ψ be given by a (2L + 1)-block map Ψ and ψ^{−1} be given by a (2L + 1)-block map Ψ̃. Let Ñ ∈ ℕ, and let x̃ ∈ X̃ be such that

(1.1)  ω^{+}(x̃_{(−L−_{N},−L]}) = ω^{+}(x̃_{(−L−ñ,−L]}),  ñ ≥ Ñ.

Then for x = ψ(x̃) and N = Ñ + 2L,

(1.2)  ω^{+}(x_{(−N,0]}) = ω^{+}(x_{(−n,0]}),  n ≥ N.

Proof. Let n ≥ N, and let

(1.3)  y^{+} ∈ ω^{+}(x_{(−n,0]}).

Let

ỹ^{+} = Ψ̃(x_{[−L,0]}, y^{+}).

One has

(1.4)  ỹ^{+} ∈ ω^{+}(x̃_{(−_{N}−L,−L]}),

which implies that

y^{+} ∈ ω^{+}(x_{(−N,0]}),

confirming (1.2). We note that by (1.1) one has that (1.4) follows from

ỹ^{+} ∈ ω^{+}(x̃_{(−ñ−L,−L]}),

which in turn follows from (1.3). □

Let X ⊂ Σ^{ℤ} be a subshift and P (X) be its set of periodic points. Denote by P_{a}(X) the set of x ∈ P (X) such that there is an N ∈ ℕ such that

ω^{+}(x_{(−N,0]}) = ω^{+}(x_{(−n,0]}), n ≥ N.

Lemma 1.2. Let X̃ ⊂ Σ̃^{ℤ}, X ⊂ Σ^{ℤ} be subshifts and let ψ : X̃ → X be a topological conjugacy. Then

ψ(P_{a}(X̃)) = P_{a}(X).

Proof. Apply Lemma 1.1. □

By Lemma 1.1 the following property of a subshift X ⊂ Σ^{ℤ} is invariant under topological conjugacy : For x ∈ X and N ∈ ℕ such that

ω^{+}(x_{(−N,0]}) = ω^{+}(x_{(−n,0]}), n ≥ N

there exists an M ∈ ℕ such that

ω^{+}(x_{[−M,0)}) = ω^{+}(x_{[−m,0)}), m ≥ M.

For a subshift X ⊂ Σ^{ℤ} with this property we consider the subgraph G_{Ch}(X) of G(X) with vertices Γ^{+}(u^{−}) where u^{−} ∈ X_{(−∞,0]} is negatively asymptotic to a point in P_{Ch}(X) = P (X)\P_{a}(X). If here G_{Ch}(X) presents X then we say that X is a Cantor horizon subshift, and we call the λ-graph system of the closure of G_{Ch}(X) the Cantor horizon λ-graph system of X. By Lemma 1.2 the Cantor horizon property is an invariant of topological conjugacy and the Cantor horizon λ-graph system is invariantly associated to the Cantor horizon subshift.

2. The Dyck shift

We consider the Dyck shift D_{2} with alphabet Σ = Σ^{−} ∪ Σ^{+} where Σ^{−} = {α_{0}, α_{1}}, Σ^{+} = {β_{0}, β_{1}}. A periodic point x of D_{2} with period p is not in P_{a}(D_{2}) precisely if for some i ∈ ℤ the normal form of the word (x_{i+q})_{0≤q<p} is a word in the symbols of Σ^{−}, in other words, if the multiplier of x in the sense of [HI] is negative. We also note that periodic points with negative multipliers give rise to the same irreducible component of G_{Ch}(D_{2}) precisely if they have the same multiplier. We describe the Cantor horizon λ-graph system 𝔏^{Ch(D_{2})} of D_{2}: The vertices at level l are given by the words of length l in the symbols of Σ^{−}. The mapping ι deletes the first symbol of a word. A word (α_{i(n)})_{1≤n≤l} accepts β_{i} precisely if i(l) = i, i = 0, 1, effecting a transition to the word (α_{i(n)})_{1≤n<l}, and it accepts α_{i}, effecting a transition to the word (α_{i(n)})_{2≤n≤l}. The forward context of the word a = (α_{i(n)})_{1≤n≤l} contains precisely all words c = (γ_{n})_{1≤n≤l} in symbols of Σ such that (a, c) is admissible for D_{2}. In describing the Cantor horizon symbolic matrix system (M, I) of the Dyck shift and the resulting nonnegative matrix system (M, I) we use the reverse lexcographic order on the words in the symbols in Σ^{−}, that is, we assign to a word (α_{i(n)})_{1≤n≤l} ∈ Σ^{−}^{[1,l]} the number

∑_{1≤n≤l} i(n)2^{n−1}.

One has then

M_{0,−1} = [β_{0} + α_{0} + α_{1}, β_{1} + α_{0} + α_{1}] = [α_{0} + α_{1} + β_{0}, α_{0} + α_{1} + β_{1}],
I_{0,−1} = [1, 1].

For l ∈ ℤ_{+} and a ∈ {α_{0}, α_{1}, β_{0}, β_{1}}, let I_{l}(a) be the 2^{l} × 2^{l} diagonal matrix with diagonal entries a, and S_{l}(a) be the 2^{l−1} × 2^{l+1} matrix [S_{l}(a)(i, j)]_{1≤i≤2^{l−1},1≤j≤2^{l+1}} where S_{l}(a)(i, j) is a for j = 4i, 4i−1, 4i−2, 4i−3, and is otherwise zero.

Proposition 2.1. For l = 1, 2, …, the matrix M_{−l,−l−1} is a 2^{l} × 2^{l+1} rectangular matrix that is given as the block matrix:

(2.1)  M_{−l,−l−1} = [ \begin{matrix}S_{l}(α_{0}) \\ S_{l}(α_{1}) \end{matrix} ] + [ I_{l}(β_{0}) | I_{l}(β_{1}) ]

and

(2.2)  I_{−l,−l−1}(i, j) = \{ \begin{matrix}1 & (j = 2i − 1, 2i), \\ 0 & elsewhere. \end{matrix}

Proof. The first summand in (2.1) describes the transitions that arise when a vertex accepts a symbol in Σ^{+}. The second summand arises from the transitions that arise when a vertex accepts a symbol in Σ^{−}, the arrangement of the components of the matrix as well as (2.2) being a component of the ordering of the vertices at level l and l − 1. □

We note that the λ-graph systems of the closures of the irreducible components of G_{Ch}(X) are identical.

Proposition 2.2. The λ-graph system 𝔏^{Ch(D_{2})} for (M, I) is irreducible and aperiodic.

Proof. Let V_{−l}, l ∈ ℤ_{+} be the vertex set of the λ-graph system 𝔏^{Ch(D_{2})}. For any vertex u of V_{−l}, there are labeled edges from each of the vertices in V_{−2l} to the vertex u. This implies that (M, I) is aperiodic. □

3. Computation of the K-groups

Let M_{l,l+1} for l ∈ ℤ_{+} be the nonnegative matrix obtained from M_{−l,−l−1} by setting all the symbols of the components of M_{−l,−l−1} equal to 1. The matrix I_{l,l+1} for l ∈ ℤ_{+} is defined to be I_{−l,−l−1}. For l > 1 and 1 ≤ i ≤ 2^{l−2} let a_{i}(l) = [a_{i}(l)_{n}]_{n=1}^{2^{l}} be the vector that is given by

a_{i}(l)_{n} = \{ \begin{matrix}1 & (n = 4i − 3, 4i − 2, 4i − 1, 4i), \\ 0 & elsewhere. \end{matrix}

Define for 1 < l ∈ ℕ E_{l} as the 2^{l} × 2^{l}-matrix whose i−th column vector and whose (2^{l−1} + i)−th column vector are both equal to a_{i}(l), 1 ≤ i ≤ 2^{l−2}, the other column vectors being equal to zero vectors. For l > 1 and 1 ≤ i ≤ 2^{l−1} let b_{i}(l) = [b_{i}(l)_{n}]_{n=1}^{2^{l}} be the vector that is given by

b_{i}(l)_{n} = \{ \begin{matrix}1 & (n = 2i − 1, 2i), \\ 0 & elsewhere. \end{matrix}

Define for 1 < l ∈ ℕ F_{l} as the 2^{l} × 2^{l}-matrix whose i−th column vector is equal to b_{i}(l), 1 ≤ i ≤ 2^{l−1}, the other column vectors being equal to zero vectors. One has

(3.1)  I_{l,l+1}^{t}E_{l} = E_{l+1}I_{l,l+1}^{t},  I_{l,l+1}^{t}F_{l} = F_{l+1}I_{l,l+1}^{t},  l > 1.

Let I_{l} denote the unit matrix of size 2^{l}. Define a 2^{l} × 2^{l−1} matrix H_{l,l−1} by setting

H_{l,l−1} = [ \begin{matrix}I_{l−1} \\ −I_{l−1} \end{matrix} ] , l > 1.

Lemma 3.1. For l > 1 one has

(E_{l} − F_{l})H_{l,l−1} = −I_{l−1,l}^{t}.

Proof. One has

E_{l}H_{l,l−1} = 0, F_{l}H_{l,l−1} = I_{l−1,l}^{t}.

□

Set y_{1}(2) = [ \begin{matrix}1 \\ 1 \\ 1 \\ 1 \end{matrix} ] , y_{2}(2) = [ \begin{matrix}1 \\ 1 \\ 0 \\ 0 \end{matrix} ] , y_{3}(2) = [ \begin{matrix}0 \\ 1 \\ 1 \\ 1 \end{matrix} ] , y_{4}(2) = [ \begin{matrix}0 \\ 0 \\ 0 \\ 1 \end{matrix} ] , and define

inductively for l > 2 vectors y_{i}(l), 1 ≤ i ≤ 2^{l}, where

(3.2)  y_{i}(l) = I_{l−1,l}^{t}y_{i}(l − 1),  1 ≤ i ≤ 2^{l−1}

and

(3.3)  y_{i}(l) = H_{l,l−1}y_{i−2^{l−2}}(l − 1),  2^{l−1} < i ≤ 2^{l−1} + 2^{l−2}

where one defines the vectors

y_{i}(l) = [y_{i}(l)_{n}]_{n=1}^{2^{l}}, 2^{l−1} + 2^{l−2} < i ≤ 2^{l}

by setting (3.4)

y_{2^{l−1}+2^{l−2}+i}(l)_{n} = \{ \begin{matrix}1 & (n = 4i − 1, 4i, 2^{l−1} + 2i), \\ −1 & (n = 2^{l−1} + 4i − 1, 2^{l−1} + 4i), \\ 0 & elsewhere, \end{matrix} 1 ≤ i ≤ 2^{l−3}

and by setting

(3.5) y_{2^{l−1}+2^{l−2}+2^{l−3}+i}(l)_{n} = \{ \begin{matrix}1 & (n = 2^{l−1} + 2^{l−2} + 2i), \\ 0 & elsewhere, \end{matrix}  1 ≤ i ≤ 2^{l−3}.

Define for l > 2, T_{l} as the 2^{l} ×2^{l}-matrix whose column vectors y_{i}(l), 1 ≤ i ≤ 2^{l}. Here y_{1}(l) has all components equal to 1, that is, y_{1}(l) is the eigenvector of E_{l} − F_{l} for the eigenvalue 1. Also the vectors

y_{i}(l), 2^{l−1} + 2^{l−2} < i ≤ 2^{l}

are linearly independent vectors in the kernel of E_{l} − F_{l} and one sees from (3.1), (3.2), (3.3), (3.4) and (3.5) that T_{l} is invertible and that T_{l}^{−1}(E_{l} − F_{l})T_{l} is a matrix that is in a normal form. This normal form is a Jordan form in the sense that by conjugation with a suitable permutation matrix, followed by a conjugation with a suitable diagonal matrix whose entries are 1 or −1, the matrix assumes a Jordan form with Jordan blocks arranged along the diagonal. There will be one Jordan block of length 1 for the eigenvalue 1, and there will be 2^{l−1} Jordan blocks for the eigenvalue 0, and if one lists these by decreasing length then the k−th Jordan block for the eigenvalue 0 has length l − μ(k) where μ(k) be given by 2^{μ(k)−1} < k ≤ 2^{μ(k)}, 1 ≤ k ≤ 2^{l−2}. By an elementary column operation we will mean the addition or subtraction of one column vector from another or the exchange of two column vectors.

Lemma 3.2. Let l ∈ ℕ and let K be a 2^{l} × 2^{l}-matrix with column vectors z_{i}, 1 ≤ i ≤ 2^{l},

z_{i} = b_{i}(l), 1 ≤ i ≤ 2^{l−1},

and column vectors

z_{2^{l−1}+i} = [z_{2^{l−1}+i,n}]_{n=1}^{2^{l}}, 1 ≤ i ≤ 2^{l−1}

such that

z_{2^{l−1}+i,2j−1} = z_{2^{l−1}+i,2j} = 0,  1 ≤ j < i,
z_{2^{l−1}+i,2i−1} = 0,  z_{2^{l−1}+i,2i} = 1,
z_{2^{l−1}+i,2j−1} = 0,  z_{2^{l−1}+i,2j} ∈ {−1, 0, 1},  i < j ≤ 2^{l−1}.

Then K can be converted into the unit matrix by a sequence of elementary column operations.

Proof. Let the vector c_{j} = [c_{j,n}]_{n=1}^{2^{l}}, 1 ≤ j ≤ 2^{l−1}, be given by

c_{j,n} = \{ \begin{matrix}1 & (n = 2j), \\ 0 & elsewhere. \end{matrix}

and denote by K[j], 1 ≤ j ≤ 2^{l−1} the matrix that is obtained by replacing in the matrix K the last j column vectors by the vectors c_{2^{l−1}−i}, j ≥ i ≥ 1. K[1] is equal to K and K[j], 1 < j ≤ 2^{l−1}, can be obtained from K[j − 1] by subtracting from and adding to the (2^{l} − j)-th column appropriate selections of the the (2^{l} − i)-th columns, 1 ≤ i ≤ j. K[2^{l−1}] has as its first 2^{l−1} column vectors the vectors b_{i}(l), 1 ≤ i ≤ 2^{l−1}, and as its last 2^{l−1} column vectors the vectors c_{i}(l), 1 ≤ i ≤ 2^{l−1}, and can be converted into the unit matrix by elementary column operations. □

Lemma 3.3. Let l ∈ ℕ and let K be a 2^{l} × 2^{l}-matrix with column vectors z_{i}, 1 ≤ i ≤ 2^{l},

z_{i} = b_{i}(l), 1 ≤ i ≤ 2^{l−1},

and column vectors

z_{2^{l−1}+i} = [z_{2^{l−1}+i,n}]_{n=1}^{2^{l}}, 1 < i ≤ 2^{l−1}

such that

(z_{2^{l−1}+i,2j−1},z_{2^{l−1}+i,2j}) ∈ {(0, 0), (1, 1)},  1 ≤ j < i,
z_{2^{l−1}+i,2i−1} = 0,  z_{2^{l−1}+i,2i} = 1,
(z_{2^{l−1}+i,2j−1},z_{2^{l−1}+i,2j}) ∈ {(−1, −1), (0, 0), (1, 1), (0, 1), (0, −1)}, i < j < 2^{l−1}.

Then K can be converted into the unit matrix by a sequence of elementary column operations.

Proof. For all i, 2^{l−1} < i ≤ 2^{l}, one subtracts from the i-th column of K and adds to the i-th column of K appropriate selections of the first 2^{l−1} columns of K to obtain a matrix to which Lemma 3.2 applies. □

Proposition 3.4. The matrix T_{l} is unimodular.

Proof. The matrix T_{2} can be converted into the unit matrix by elementary column operations. The proof is by induction on l. Assume that the matrix T_{l−1}, l > 2 can be converted into the unit matrix by a sequence of elementary column operations. Then by (3.2) the matrix T_{l} can be converted by a sequence of elementary column operations into a matrix whose first 2^{l−1} column vectors are the vectors b_{i}(l), 1 ≤ i ≤ 2^{l−1} and whose last 2^{l−1} column vectors are those of the matrix T_{l}, and by (3.2),(3.3) and (3.4) Lemma 3.3 is applicable to this matrix. □

Define a 2^{l} × 2^{l} matrix L_{l} by setting

L_{l} = I_{l} + E_{l} − F_{l}, l > 1.

Denote by 0_{k,l} the 2^{k} × 2^{l} matrix with entries 0’s. Also define permutation matrices P_{l}(i, j), 1 ≤ i, j ≤ 2^{l}, l > 1, by

P_{l}(i, 2^{l} − i + 1) = 1, 1 ≤ i ≤ 2^{l},

and set

B_{l+1} = [ \begin{matrix}L_{l} & 0_{l,l} \\ P_{l}L_{l}P_{l} & 0_{l,l} \end{matrix} ] .

Lemma 3.5. B_{l+1} = [ M_{l,l+1}^{t} − I_{l,l+1}^{t} | 0_{l+1,l}] , l > 1. Proof. This follows from Proposition 2.1. □ Define 2^{l+1} × 2^{l+1} matrices J(l + 1) and U_{l+1} by setting

J(l + 1) = [ \begin{matrix}T_{l}^{−1}L_{l}T_{l} & 0_{l,l} \\ 0_{l,l} & 0_{l,l} \end{matrix} ] , U_{l+1} = [ \begin{matrix}T_{l} & 0_{l,l} \\ P_{l}T_{l} & I_{l} \end{matrix} ] .

Lemma 3.6. U_{l+1} is unimodular and U_{l+1}^{−1}B_{l+1}U_{l+1} = J(l + 1), l > 1.

Proof. One has

U_{l+1}^{−1} = [ \begin{matrix}T_{l}^{−1} & 0_{l,l} \\ −P_{l} & I_{l} \end{matrix} ]

and further

[ \begin{matrix}T_{l}^{−1} & 0_{l,l} \\ −P_{l} & I_{l} \end{matrix} ] [ \begin{matrix}L_{l} & 0_{l,l} \\ P_{l}L_{l}P_{l} & 0_{l,l} \end{matrix} ] [ \begin{matrix}T_{l} & 0_{l,l} \\ P_{l}T_{l} & I_{l} \end{matrix} ] = [ \begin{matrix}T_{l}^{−1}L_{l}T_{l} & 0_{l,l} \\ 0_{l,l} & 0_{l,l} \end{matrix} ] .

□ Define a 2^{l+1} × 2^{l} matrix G_{l+1,l} by setting

G_{l+1,l} = [ \begin{matrix}I_{l} \\ 0_{l,l} \end{matrix} ] , l > 1.

One has

(3.6)  I_{l,l+1}^{t}T_{l} = T_{l+1}G_{l+1,l},
(3.7)  I_{l,l+1}^{t}P_{l}T_{l} = P_{l+1}T_{l+1}G_{l+1,l}.

Define a 2^{l+1} × 2^{l} matrix J_{l+1,l} by setting

J_{l+1,l} = [ \begin{matrix}G_{l,l−1} & 0_{l,l−1} \\ 0_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ] , l > 1.

Lemma 3.7. I_{l,l+1}^{t}U_{l} = U_{l+1}J_{l+1,l}, l > 1. Proof. From (3.6) and (3.7), it follows that

[ \begin{matrix}I_{l−1,l}^{t} & 0_{l,l−1} \\ 0_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ][ \begin{matrix}T_{l−l} & 0_{l,l−1} \\ P_{l−1}T_{l−1} & I_{l−1} \end{matrix} ] = [ \begin{matrix}T_{l}G_{l,l−1} & 0_{l,l−1} \\ P_{l}T_{l}G_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ]

= [ \begin{matrix}T_{l} & 0_{l,l} \\ P_{l}T_{l} & I_{l} \end{matrix} ][ \begin{matrix}G_{l,l−1} & 0_{l,l−1} \\ 0_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ] .

□

A Lambda-Graph System for the Dyck Shift … 91

Lemma 3.8.

J_{l+1,l}J(l) = J(l + 1)J_{l+1,l}, l > 1.

Proof. By (3.1)

I_{l−1,l}^{t}L_{l−1} = L_{l}I_{l−1,l}^{t}

and by (3.6)

T_{l+1}^{−1}I_{l,l+1}^{t}T_{l} = G_{l+1,l}T_{l}^{−1}.

Therefore by (3.6)

G_{l,l−1}T_{l−1}^{−1}L_{l−1}T_{l−1} = T_{l}^{−1}I_{l−1,l}^{t}L_{l−1}T_{l−1}
= T_{l}^{−1}L_{l}I_{l−1,l}^{t}T_{l−1}
= T_{l}^{−1}L_{l}T_{l}G_{l,l−1}

and therefore

[ \begin{matrix}G_{l,l−1} & 0_{l,l−1} \\ 0_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ] [ \begin{matrix}T_{l−1}^{−1}L_{l−1}T_{l−1} & 0_{l,l−1} \\ 0_{l,l−1} & 0_{l,l−1} \end{matrix} ]

= [ \begin{matrix}G_{l,l−1}T_{l−1}^{−1}L_{l−1}T_{l−1} & 0_{l,l−1} \\ 0_{l,l−1} & 0_{l,l−1} \end{matrix} ]

= [ \begin{matrix}T_{l}^{−1}L_{l}T_{l}G_{l,l−1} & 0_{l,l−1} \\ 0_{l,l−1} & 0_{l,l−1} \end{matrix} ]

= [ \begin{matrix}T_{l}^{−1}L_{l}T_{l} & 0_{l,l−1} \\ 0_{l,l−1} & 0_{l,l−1} \end{matrix} ] [ \begin{matrix}G_{l,l−1} & 0_{l,l−1} \\ 0_{l,l−1} & I_{l−1,l}^{t} \end{matrix} ] .

□ By the preceding lemma, the matrix J_{l+1,l} induces a homomorphism

J̄_{l+1,l} : ℤ^{2^{l}}/J(l)ℤ^{2^{l}} → ℤ^{2^{l+1}}/J(l + 1)ℤ^{2^{l+1}}

and by Proposition 3.4 and Lemma 3.6 the matrix U_{l}, as B_{l}ℤ^{2^{l}} = (M_{l−1,l}^{t} − I_{l−1,l}^{t})ℤ^{2^{l−1}}, induces a homomorphism

Ū_{l} : ℤ^{2^{l}}/J(l)ℤ^{2^{l}} → ℤ^{2^{l}}/B_{l}ℤ^{2^{l}}.

Lemma 3.9. The diagram :

ℤ^{2^{l}}/(M_{l−1,l}^{t} − I_{l−1,l}^{t})ℤ^{2^{l−1}} ⟶^{Ī_{l,l+1}^{t}} ℤ^{2^{l+1}}/(M_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2^{l}}
Ū_{l}↑  Ū_{l+1}↑
ℤ^{2^{l}}/J(l)ℤ^{2^{l}}  ⟶^{J̄_{l+1,l}} ℤ^{2^{l+1}}/J(l + 1)ℤ^{2^{l+1}}

Documenta Mathematica 8 (2003) 79–96

92 Wolfgang Krieger and Kengo Matsumoto

is commutative. Proof. Apply Lemma 3.7. □ Define a diagonal matrix D(l) by setting

D(l) = diag(2, \overbrace{1, 1, …, 1}^{2^{l}−1}), l ∈ ℕ.

As J(l+1)ℤ^{2^{l+1}} = D(l)ℤ^{2^{l}} ⊕(\overbrace{0, …, 0}^{2^{l}}) and hence ℤ^{2^{l+1}}/J(l+1)ℤ^{2^{l+1}} ≅ ℤ/2ℤ⊕

ℤ^{2^{l}}, through the map φ_{l} ⊕ id where φ_{l} : ℤ^{2^{l}}/D(l)ℤ^{2^{l}} → ℤ/2ℤ is defined by φ_{l}([(x_{i})_{i=1}^{2^{l}}]) = [x_{1}] (mod 2), we have Proposition 3.10. The following diagram is commutative:

ℤ^{2^{l}}/J(l)ℤ^{2^{l}}  ⟶^{J̄_{l+1,l}} ℤ^{2^{l+1}}/J(l + 1)ℤ^{2^{l+1}}
φ_{l−1}⊕id↓  ^{φ_{l}⊕id}↓
ℤ/2ℤ ⊕ ℤ^{2^{l−1}} ⟶^{id⊕I_{l−1,l}^{t}}  ℤ/2ℤ ⊕ ℤ^{2^{l}}.

Corollary 3.11.

\underrightarrow{lim}_{l}\{ℤ^{2^{l+1}}/(M_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2^{l}}, Ī_{l,l+1}^{t}\} ≅ ℤ/2ℤ ⊕ C(ℭ, ℤ).

Proof. As the group of the inductive limit: \underrightarrow{lim}_{l}\{I_{l,l+1}^{t} : ℤ^{2^{l}} → ℤ^{2^{l+1}}\} is isomorphic to C(ℭ, ℤ), we get the assertion. □ Theorem 3.12.

K_{0}(M, I) ≅ ℤ/2ℤ ⊕ C(ℭ, ℤ), K_{1}(M, I) ≅ 0.

By Proposition 2.2, the Cantor horizon λ-graph system 𝔏^{Ch(D_{2})} of D_{2} is aperiodic so that the C^{∗}-algebra O_{𝔏^{Ch(D_{2})}} associated with the λ-graph system 𝔏^{Ch(D_{2})} is simple and purely infinite ([Ma3;Proposition 4.9]). It satisfies the UCT by [Ma3;Proposition 5.6] (cf.[Bro],[RS]). By [Ma3;Theorem 5.5], the Kgroups K_{i}(O_{𝔏^{Ch(D_{2})}}) are isomorphic to the K-groups K_{i}(M, I) so that we get Corollary 3.13. The C^{∗}-algebra O_{𝔏^{Ch(D_{2})}} associated with the λ-graph system 𝔏^{Ch(D_{2})} is separable, unital, nuclear, simple, purely infinite with UCT such that

K_{0}(O_{𝔏^{Ch(D_{2})}}) ≅ ℤ/2ℤ ⊕ C(ℭ, ℤ), K_{1}(O_{𝔏^{Ch(D_{2})}}) ≅ 0.

4. Computation of the Bowen-Franks groups

We compute next the Bowen-Franks groups BF^{0}(M, I) and BF^{0}(M, I). Lemma 4.1. Ext_{ℤ}^{1}(C(ℭ, ℤ), ℤ) ≅ 0. Proof. From [Ro] (cf.[Sch;Theorem 1.3]) one has that for an inductive sequence {G_{i}} of abelian groups there exists a natural short exact sequence

0 → lim_{⟵}^{1}Hom_{ℤ}(G_{i}, ℤ) → Ext_{ℤ}^{1}(lim_{⟶}G_{i}, ℤ) → lim_{⟵}Ext_{ℤ}^{1}(G_{i}, ℤ) → 0.

The lemma follows therefore from C(ℭ, ℤ) = \underrightarrow{lim}_{l}\{I_{l,l+1}^{t} : ℤ^{2^{l}} → ℤ^{2^{l+1}}\} and Ext_{ℤ}^{1}(ℤ^{2^{l}}, ℤ) = lim_{⟵}^{1}Hom_{ℤ}(ℤ^{2^{l}}, ℤ) = 0. □ As in [Ma;Theorem 9.6], one has the following lemma that provides a universal coefficient type theorem. Lemma 4.2. For i = 0, 1 there exists an exact sequence

0 → Ext_{ℤ}^{1}(K_{i}(M, I), ℤ) → BF^{i}(M, I) → Hom_{ℤ}(K_{i+1}(M, I), ℤ) → 0.

Theorem 4.3.

BF^{0}(M, I) ≅ ℤ/2ℤ.

Proof. By Theorem 3.12 and by Lemma 4.2 one has

BF^{0}(M, I) ≅ Ext_{ℤ}^{1}(ℤ/2ℤ, ℤ) ⊕ Ext_{ℤ}^{1}(C(ℭ, ℤ), ℤ).

As Ext_{ℤ}^{1}(ℤ/2ℤ, ℤ) ≅ ℤ/2ℤ, the theorem follows from Lemma 4.1. □ Theorem 4.4.

BF^{1}(M, I) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

Proof. Hom_{ℤ}(ℤ/2ℤ, ℤ) is trivial. Therefore by Theorem 3.12

Hom_{ℤ}(K_{0}(M, I)) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

Since the group K_{1}(M, I) is trivial, by Lemma 4.2, one gets

BF^{1}(M, I) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

□ As the Bowen-Franks groups BF^{0}(M, I) and BF^{1}(M, I) are isomorphic to the Ext-groups Ext^{1}(O_{𝔏^{Ch(D_{2})}})(= Ext(O_{𝔏^{Ch(D_{2})}})) and Ext^{0}(O_{𝔏^{Ch(D_{2})}})(= Ext(O_{𝔏^{Ch(D_{2})}} ⊗ C_{0}(ℝ)) for the C^{∗}-algebra O_{𝔏^{Ch(D_{2})}} (cf. [Ma3]), we obtain Corollary 4.5.

Ext^{1}(O_{𝔏^{Ch(D_{2})}}) ≅ ℤ/2ℤ, Ext^{0}(O_{𝔏^{Ch(D_{2})}}) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

5. General Dyck shifts

One can extend the preceding results for the Dyck shift D_{2} to the general Dyck shifts D_{N} with 2N symbols α_{n}, β_{n}, 1 ≤ n ≤ N, for N > 2, generalizing the previous discussions for the case of N = 2. We will briefly explain this. We consider the Cantor horizon λ-graph system 𝔏^{Ch(D_{N})} of D_{N} as in the previous case and write its symbolic matrix system (M_{−l,−l−1}^{Ch(D_{N})}, I_{−l,−l−1}^{Ch(D_{N})}) as (M_{l,l+1}, I_{l,l+1}). We define the nonnegative matrices M_{l,l+1}, I_{l,l+1}, l ∈ ℤ_{+} in a similar way. The size of the matrices M_{l,l+1}, I_{l,l+1} is N^{l} ×N^{l+1}. Let I_{l}^{(N)} be the unit matrix with size N^{l}. For l > 1 and 1 ≤ i ≤ N^{l−2} let a_{i}^{(N)}(l) = [a_{i}^{(N)}(l)_{n}]_{n=1}^{N^{l}} be the vector that is given by

a_{i}^{(N)}(l)_{n} = \{ \begin{matrix}1 & (N^{2}(i − 1) + 1 ≤ n ≤ N^{2}i), \\ 0 & elsewhere. \end{matrix}

Define for 1 < l ∈ ℕ E_{l}^{(N)} as the N^{l} × N^{l}-matrix whose i−th, (N^{l−1} + i)−th, (2N^{l−1} + i)−th, …, ((N − 1)N^{l−1} + i)−th column vectors are all equal to a_{i}^{(N)}(l), 1 ≤ i ≤ N^{l−2}, the other column vectors being equal to zero vectors. Let b_{i}^{(N)}(l) = [b_{i}^{(N)}(l)_{n}]_{n=1}^{N^{l}} be the vector that is given by

b_{i}^{(N)}(l)_{n} = \{ \begin{matrix}1 & (N(i − 1) + 1 ≤ n ≤ Ni), \\ 0 & elsewhere. \end{matrix}

Define for 1 < l ∈ ℕ F_{l}^{(N)} as the N^{l} × N^{l}-matrix whose i−th column vector is equal to b_{i}^{(N)}(l), 1 ≤ i ≤ N^{l−1}, the other column vectors being equal to zero vectors. Define a N^{l} × N^{l} matrix by

L_{l}^{(N)} = I_{l}^{(N)} + E_{l}^{(N)} − F_{l}^{(N)}, l ∈ ℕ.

Also define permutation matrices P_{l}^{(N),k}, k = 1, 2, …, N − 1, by

P_{l}^{(N),k}(i, N^{l} − i + 1 − (k − 1)) = 1, 1 ≤ i ≤ N^{l},

where 1 ≤ N^{l} − i + 1 − (k − 1) ≤ N^{l} is taken mod N^{l}. Denote by 0_{k,l} the N^{k} × N^{l} matrix with entries 0’s. We define an N^{l+1} × N^{l+1} matrix B_{l+1}^{(N)} by

B_{l+1}^{(N)} = [M_{l,l+1}^{t} − I_{l,l+1}^{t} | 0_{l+1,l}],

that is written as the block matrix

[ \begin{matrix}L_{l}^{(N)} & 0_{l,l} \\ P_{l}^{(N),1}L_{l}^{(N)}P_{l}^{(N),1} & 0_{l,l} \\ ⋮ & ⋮ \\ P_{l}^{(N),N−1}L_{l}^{(N)}P_{l}^{(N),N−1} & 0_{l,l} \end{matrix} ] .

By an argument that is similar to the one of the previous sections, one can conclude then Theorem 5.1.

K_{0}(M, I) ≅ ℤ/Nℤ ⊕ C(ℭ, ℤ),  K_{1}(M, I) ≅ 0,
BF^{0}(M, I) ≅ ℤ/Nℤ,  BF^{1}(M, I) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

Corollary 5.2. The C^{∗}-algebra O_{𝔏^{Ch(D_{N})}} associated with the Cantor horizon λ-graph system 𝔏^{Ch(D_{N})} of D_{N} is separable, unital, nuclear, simple, purely infinite such that

K_{0}(O_{𝔏^{Ch(D_{N})}}) ≅ ℤ/Nℤ ⊕ C(ℭ, ℤ),  K_{1}(O_{𝔏^{Ch(D_{N})}}) ≅ 0,
Ext^{1}(O_{𝔏^{Ch(D_{N})}}) ≅ ℤ/Nℤ,  Ext^{0}(O_{𝔏^{Ch(D_{N})}}) ≅ Hom_{ℤ}(C(ℭ, ℤ), ℤ).

Acknowledgement : This work was supported by DFG and JSPS.

References

[BK] M. Boyle and W. Krieger, Almost Markov and shift equivalent sofic systems, Proceedings of Maryland Special Year in Dynamics 1986-87, Springer Verlag Lecture Notes in Math. 1342 (1988), 33–93.

[Bro] L. G. Brown, The universal coefficient theorem for Ext and quasidiagonality, Operator Algebras and Group Representation, Pitman Press 17 (1983), 60–64.

[HI] T. Hamachi and K. Inoue, Embedding of shifts of finite type into the Dyck shift, preprint 2002.

[Ki] B.P. Kitchens, Symbolic dynamics, Springer-Verlag, Berlin, Heidelberg and New York, 1998.

[Kr] W. Krieger, On subshifts and topological Markov chains, Numbers, information and complexity (Bielefeld 1998), Kluwer Acad. Publ. Boston MA (2000), 453–472.

[KM] W. Krieger and K. Matsumoto, Shannon graphs, subshifts and lambdagraph systems, J. Math. Soc. Japan 54 (2002), 877–899.

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

[Ma] K. Matsumoto, Presentations of subshifts and their topological conjugacy invariants, Documenta Math. 4 (1999), 285-340.

[Ma2] K. Matsumoto, K-theoretic invariants and conformal measures of the Dyck subshift, preprint, 1999.

[Ma3] K. Matsumoto, C^{∗}-algebras associated with presentations of subshifts, Documenta Math. 7 (2002), 1-30.

[N] M. Nasu, Topological conjugacy for sofic shifts, Ergodic Theory Dynam. Systems 6 (1986), 265–280.

[Ro] J. E. Roos, Sur les dérivés de \underleftarrow{lim}. Applications, C. R. Acad. Sci. Paris 252 (1961), 3702–3704.

[RS] J. Rosenberg and C. Schochet, The Künneth Theorem and the Universal Coefficient Theorem for Kasparov’s generalized K-functor, Duke Math. J. 55 (1987), 431–474.

[Sch] C. Schochet, The UCT, the Milnor sequence, and a canonical decomposition of the Kasparov group, K-Theory 10 (1996), 49–72.

[Wi] R. F. Williams, Classification of subshifts of finite type, Ann. Math. 98 (1973), 120–153, erratum, Ann. Math. 99(1974), 380 − 381.

Wolfgang Krieger Institute for Applied Mathematics University of Heidelberg Im Neuenheimer Feld 294 69120 Heidelberg, Germany krieger@math.uni-heidelberg.de Kengo Matsumoto Department of Mathematical Sciences Yokohama City University 22-2 Seto, Kanazawa-ku Yokohama, 236-0027 Japan kengo@yokohama-cu.ac.jp