C^{∗}-Algebras Associated

with Presentations of Subshifts

Kengo Matsumoto

Received: May 28, 2001 Revised: March 4, 2002

Communicated by Joachim Cuntz

Abstract. A λ-graph system is a labeled Bratteli diagram with an upward shift except the top vertices. We construct a continuous graph in the sense of V. Deaconu from a λ-graph system. It yields a Renault’s groupoid C^{∗}-algebra by following Deaconu’s construction. The class of these C^{∗}-algebras generalize the class of C^{∗}-algebras associated with subshifts and hence the class of Cuntz-Krieger algebras. They are unital, nuclear, unique C^{∗}-algebras subject to operator relations encoded in the structure of the λ-graph systems among generating partial isometries and projections. If the λ-graph systems are irreducible (resp. aperiodic), they are simple (resp. simple and purely infinite). K-theory formulae of these C^{∗}-algebras are presented so that we know an example of a simple and purely infinite C^{∗}-algebra in the class of these C^{∗}-algebras that is not stably isomorphic to any Cuntz-Krieger algebra.

2000 Mathematics Subject Classification: Primary 46L35, Secondary 37B10. Keywords and Phrases: C^{∗}-algebras, subshifts, groupoids, Cuntz-Krieger algebras

1. Introduction

In [CK], J. Cuntz-W. Krieger have presented a class of C^{∗}-algebras associated to finite square matrices with entries in {0, 1}. The C^{∗}-algebras are simple if the matrices satisfy condition (I) and irreducible. They are also purely infinite if the matrices are aperiodic. There are many directions to generalize the Cuntz-Krieger algebras (cf. [An],[De],[De2],[EL],[KPRR],[KPW],[Pi], [Pu],[T], etc.). The Cuntz-Krieger algebras have close relationships to topological Markov shifts by Cuntz-Krieger’s observation in [CK]. Let Σ be a finite set, and let σ be the shift on the infinite product space Σ^{ℤ} defined by σ((x_{n})_{n∈ℤ}) = (x_{n+1})_{n∈ℤ}, (x_{n})_{n∈ℤ} ∈ Σ^{ℤ}. For a closed σ-invariant subset Λ of Σ^{ℤ}, the topological dynamical system Λ with σ is called a subshift. The topological Markov shifts form a class of subshifts. In [Ma], the author has generalized the class of Cuntz-Krieger algebras to a class of C^{∗}-algebras associated with subshifts. He has formulated several topological conjugacy invariants for subshifts by using the K-theory for these C^{∗}-algebras ([Ma5]). He has also introduced presentations of subshifts, that are named symbolic matrix system and λ-graph system ([Ma5]). They are generalized notions of symbolic matrix and λ-graph (= labeled graph) for sofic subshifts respectively. We henceforth denote by ℤ_{+} and ℕ the set of all nonnegative integers and the set of all positive integers respectively. A symbolic matrix system (M, I) over a finite set Σ consists of two sequences of rectangular matrices (M_{l,l+1}, I_{l,l+1}), l ∈ ℤ_{+}. The matrices M_{l,l+1} have their entries in the formal sums of Σ and the matrices I_{l,l+1} have their entries in {0, 1}. They satisfy the following relations

(1.1)  I_{l,l+1}M_{l+1,l+2} = M_{l,l+1}I_{l+1,l+2},  l ∈ ℤ_{+}.

It is assumed for I_{l,l+1} that for i there exists j such that the (i, j)-component I_{l,l+1}(i, j) = 1 and that for j there uniquely exists i such that I_{l,l+1}(i, j) = 1. A λ-graph system 𝔏 = (V, E, λ, ι) consists of a vertex set V = V_{0} ∪ V_{1} ∪ V_{2} ∪ ⋯, an edge set E = E_{0,1} ∪ E_{1,2} ∪ E_{2,3} ∪ ⋯, a labeling map λ : E → Σ and a surjective map ι_{l,l+1} : V_{l+1} → V_{l} for each l ∈ ℤ_{+}. It naturally arises from a symbolic matrix system. For a symbolic matrix system (M, I), a labeled edge from a vertex 𝔳_{i}^{l} ∈ V_{l} to a vertex 𝔳_{j}^{l+1} ∈ V_{l+1} is given by a symbol appearing in the (i, j)-component M_{l,l+1}(i, j) of the matrix M_{l,l+1}. The matrix I_{l,l+1} defines a surjection ι_{l,l+1} from V_{l+1} to V_{l} for each l ∈ ℤ_{+}. The symbolic matrix systems and the λ-graph systems are the same objects. They give rise to subshifts by looking the set of all label sequences appearing in the labeled Bratteli diagram (V, E, λ). A canonical method to construct a symbolic matrix system and a λ-graph system from an arbitrary subshift has been introduced in [Ma5]. The obtained symbolic matrix system and the λ-graph system are said to be canonical for the subshift. For a symbolic matrix system (M, I), let A_{l,l+1} be the nonnegative rectangular matrix obtained from M_{l,l+1} by setting all the symbols equal to 1 for each l ∈ ℤ_{+}. The resulting pair (A, I) satisfies the following relations from (1.1)

(1.2)  I_{l,l+1}A_{l+1,l+2} = A_{l,l+1}I_{l+1,l+2},  l ∈ ℤ_{+}.

C^{∗}-Algebras Associatedwith Presentations of Subshifts 3

We call (A, I) the nonnegative matrix system for (M, I). In the present paper, we introduce C^{∗}-algebras from λ-graph systems. If a λgraph system is the canonical λ-graph system for a subshift Λ, the C^{∗}-algebra coincides with the C^{∗}-algebra O_{Λ} associated with the subshift. Hence the class of the C^{∗}-algebras in this paper generalize the class of Cuntz-Krieger algebras. Let 𝔏 = (V, E, λ, ι) be a λ-graph system over alphabet Σ. We first construct a continuous graph from 𝔏 in the sense of V. Deaconu ([D2],[De3],[De4]). We then define the C^{∗}-algebra O_{𝔏} associated with 𝔏 as the Renault’s C^{∗}-algebra of a groupoid constructed from the continuous graph. For an edge e ∈ E_{l,l+1}, we denote by s(e) ∈ V_{l} and t(e) ∈ V_{l+1} its source vertex and its terminal vertex respectively. Let Λ^{l} be the set of all words of length l of symbols appearing in the labeled Bratteli diagram of 𝔏. We put Λ^{∗} = ∪_{l=0}^{∞}Λ^{l} where Λ^{0} denotes the empty word. Let {𝔳_{1}^{l}, …, 𝔳_{m(l)}^{l}} be the vertex set V_{l}. We denote by Γ_{l}^{−}(𝔳_{i}^{l}) the set of all words in Λ^{l} presented by paths starting at a vertex of V_{0} and terminating at the vertex 𝔳_{i}^{l}. 𝔏 is said to be left-resolving if there are no distinct edges with the same label and the same terminal vertex. 𝔏 is said to be predecessor-separated if Γ_{l}^{−}(𝔳_{i}^{l}) ≠ Γ_{l}^{−}(𝔳_{j}^{l}) for distinct i, j and for all l ∈ ℕ. Assume that 𝔏 is left-resolving and satisfies condition (I), a mild condition generalizing Cuntz-Krieger’s condition (I). We then prove:

Theorem A (Theorem 3.6 and Theorem 4.3). Suppose that a λ-graph system 𝔏 satisfies condition (I). Then the C^{∗}-algebra O_{𝔏} is the universal concrete unique C^{∗}-algebra generated by partial isometries S_{α}, α ∈ Σ and projections E_{i}^{l}, i = 1, 2, …, m(l), l ∈ ℤ_{+} satisfying the following operator relations:

∑_{α∈Σ} S_{α}S_{α}^{∗} = 1, (1.3)

(1.4)  ∑_{i=1}^{m(l)} E_{i}^{l} = 1,  E_{i}^{l} = ∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)E_{j}^{l+1},

S_{α}S_{α}^{∗}E_{i}^{l} = E_{i}^{l}S_{α}S_{α}^{∗}, (1.5)

(1.6)  S_{α}^{∗}E_{i}^{l}S_{α} = ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, α, j)E_{j}^{l+1},

for i = 1, 2, …, m(l), l ∈ ℤ_{+}, α ∈ Σ, where

A_{l,l+1}(i, α, j) = \{ \begin{matrix}1 & if s(e) = 𝔳_{i}^{l}, λ(e) = α, t(e) = 𝔳_{j}^{l+1} for some e ∈ E_{l,l+1}, \\ 0 & otherwise, \end{matrix}
I_{l,l+1}(i, j) = \{ \begin{matrix}1 & if ι_{l,l+1}(𝔳_{j}^{l+1}) = 𝔳_{i}^{l}, \\ 0 & otherwise \end{matrix}

for i = 1, 2, …, m(l), j = 1, 2, …, m(l + 1), α ∈ Σ.

If 𝔏 is predecessor-separated, the following relations:

(1.7)  E_{i}^{l} = ∏_{\begin{matrix}μ,ν∈Λ^{l} \\ μ∈Γ_{l}^{−}(𝔳_{i}^{l}),ν∉Γ_{l}^{−}(𝔳_{i}^{l}) \end{matrix}} S_{μ}^{∗}S_{μ}(1 − S_{ν}^{∗}S_{ν}),  l ∈ ℕ,

E_{i}^{0} = ∑_{α∈Σ} ∑_{j=1}^{m(1)} A_{0,1}(i, α, j)S_{α}E_{j}^{1}S_{α}^{∗}

hold for i = 1, 2, …, m(l), where S_{μ} = S_{μ_{1}} ⋯ S_{μ_{k}} for μ = (μ_{1}, …, μ_{k}), μ_{1}, …, μ_{k} ∈ Σ. In this case, O_{𝔏} is generated by only the partial isometries S_{α}, α ∈ Σ. If 𝔏 comes from a finite directed graph G, the algebra O_{𝔏} becomes the Cuntz-Krieger algebra O_{A_{G}} associated to its adjacency matrix A_{G} with entries in {0, 1}. We generalize irreducibility and aperiodicity for finite directed graphs to λgraph systems. Then simplicity arguments of the Cuntz algebras in [C], the Cuntz-Krieger algebras in [CK] and the C^{∗}-algebras associated with subshifts in [Ma] are generalized to our C^{∗}-algebras O_{𝔏} so that we have

Theorem B (Theorem 4.7 and Proposition 4.9). If 𝔏 satisfies condition (I) and is irreducible, the C^{∗}-algebra O_{𝔏} is simple. In particular if 𝔏 is aperiodic, O_{𝔏} is simple and purely infinite.

There exists an action α_{𝔏} of the torus group 𝕋 = {z ∈ ℂ | |z| = 1} on the algebra O_{𝔏} that is called the gauge action. It satisfies α_{𝔏}_{z}(S_{α}) = zS_{α}, α ∈ Σ for z ∈ 𝕋. The fixed point subalgebra O_{𝔏}^{α_{𝔏}} of O_{𝔏} under α_{𝔏} is an AFalgebra F_{𝔏}, that is stably isomorphic to the crossed product O_{𝔏} ⋊_{α_{𝔏}} 𝕋. Let (A, I) = (A_{l,l+1}, I_{l,l+1})_{l∈ℤ_{+}} be the nonnegative matrix system for the symbolic matrix system corresponding to the λ-graph system 𝔏. In [Ma5], its dimension group (Δ_{(A,I)}, Δ_{(A,I)}^{+}, δ_{(A,I)}), its Bowen-Franks groups BF^{i}(A, I), i = 0, 1 and its K-groups K_{i}(A, I), i = 0, 1 have been formulated. They are related to topological conjugacy invariants of subshifts. The following K-theory formulae are generalizations of the K-theory formulae for the Cuntz-Krieger algebras and the C^{∗}-algebras associated with subshifts ([Ma2],[Ma4],[Ma5],[Ma6], cf.[C2],[C3],[CK]).

Theorem C (Proposition 5.3, Theorem 5.5 and Theorem 5.9).

(K_{0}(F_{𝔏}), K_{0}(F_{𝔏})_{+}, α̂_{𝔏}_{∗}) ≅ (Δ_{(A,I)}, Δ_{(A,I)}^{+}, δ_{(A,I)}),
K_{i}(O_{𝔏}) ≅ K_{i}(A, I),  i = 0, 1,
Ext^{i+1}(O_{𝔏}) ≅ BF^{i}(A, I),  i = 0, 1

where α̂_{𝔏} denotes the dual action of the gauge action α_{𝔏} on O_{𝔏}.

We know that the C^{∗}-algebra O_{𝔏} is nuclear and satisfies the Universal Coefficient Theorem (UCT) in the sense of Rosenberg and Schochet (Proposition 5.7)([RS], cf. [Bro2]). Hence, if 𝔏 is aperiodic, O_{𝔏} is a unital, separable, nuclear, purely infinite, simple C^{∗}-algebra satisfying the UCT, that lives in a classifiable class by K-theory of E. Kirchberg [Kir] and N. C. Phillips [Ph]. By Rørdam’s result [Rø;Proposition 6.7], one sees that O_{𝔏} is isomorphic to the C^{∗}-algebra of an inductive limit of a sequence B_{1} → B_{2} → B_{3} → ⋯ of simple Cuntz-Krieger algebras (Corollary 5.8). We finally present an example of a λ-graph system for which the associated C^{∗}-algebra is not stably isomorphic to any Cuntz-Krieger algebra O_{A} and any Cuntz-algebra O_{n} for n = 2, 3, …, ∞. The example is a λ-graph system 𝔏(S) constructed from a certain Shannon graph S (cf.[KM]). We obtain Theorem D (Theorem 7.7). The C^{∗}-algebra O_{𝔏(S)} is unital, simple, purely infinite, nuclear and generated by five partial isometries with mutually orthogonal ranges. Its K-groups are

K_{0}(O_{𝔏(S)}) = 0, K_{1}(O_{𝔏(S)}) = ℤ.

In [Ma7], among other things, relationships between ideals of O_{𝔏} and sub λgraph systems of 𝔏 are studied so that the class of C^{∗}-algebras associated with λ-graph systems is closed under quotients by its ideals.

Acknowledgments: The author would like to thank Yasuo Watatani for his suggestions on groupoid C^{∗}-algebras and C^{∗}-algebras of Hilbert C^{∗}-bimodules. The author also would like to thank the referee for his valuable suggestions and comments for the presentation of this paper.

2. Continuous graphs constructed from λ-graph systems

We will construct Deaconu’s continuous graphs from λ-graph systems. They yield Renault’s r-discrete groupoid C^{∗}-algebras by Deaconu ([De],[De2],[De3]). Following V. Deaconu in [De3], by a continuous graph we mean a closed subset E of V × Σ × V where V is a compact metric space and Σ is a finite set. If in particular V is zero-dimensional, that is, the set of all clopen sets form a basis of the open sets, we say E to be zero-dimensional or Stonean. Let 𝔏 = (V, E, λ, ι) be a λ-graph system over Σ with vertex set V = ∪_{l∈ℤ_{+}}V_{l} and edge set E = ∪_{l∈ℤ_{+}}E_{l,l+1} that is labeled with symbols in Σ by λ : E → Σ, and that is supplied with surjective maps ι(= ι_{l,l+1}) : V_{l+1} → V_{l} for l ∈ ℤ_{+}. Here the vertex sets V_{l}, l ∈ ℤ_{+} are finite disjoint sets. Also E_{l,l+1}, l ∈ ℤ_{+} are finite disjoint sets. An edge e in E_{l,l+1} has its source vertex s(e) in V_{l} and its terminal vertex t(e) in V_{l+1} respectively. Every vertex in V has a successor and every vertex in V_{l} for l ∈ ℕ has a predecessor. It is then required that there exists an edge in E_{l,l+1} with label α and its terminal is v ∈ V_{l+1} if and only if there exists an edge in E_{l−1,l} with label α and its terminal is ι(v) ∈ V_{l}. For u ∈ V_{l−1} and v ∈ V_{l+1}, we put

E^{ι}(u, v) = {e ∈ E_{l,l+1} | t(e) = v, ι(s(e)) = u},
E_{ι}(u, v) = {e ∈ E_{l−1,l} | s(e) = u, t(e) = ι(v)}.

Then there exists a bijective correspondence between E^{ι}(u, v) and E_{ι}(u, v) that preserves labels for each pair of vertices u, v. We call this property the local property of 𝔏. Let Ω_{𝔏} be the projective limit of the system ι_{l,l+1} : V_{l+1} → V_{l}, l ∈ ℤ_{+}, that is defined by

Ω_{𝔏} = {(v^{l})_{l∈ℤ_{+}} ∈ ∏_{l∈ℤ_{+}} V_{l} | ι_{l,l+1}(v^{l+1}) = v^{l}, l ∈ ℤ_{+}}.

We endow Ω_{𝔏} with the projective limit topology so that it is a compact Hausdorff space. An element v in Ω_{𝔏} is called an ι-orbit or also a vertex. Let E_{𝔏} be the set of all triplets (u, α, v) ∈ Ω_{𝔏} × Σ × Ω_{𝔏} such that for each l ∈ ℤ_{+}, there exists e_{l,l+1} ∈ E_{l,l+1} satisfying

u^{l} = s(e_{l,l+1}), v^{l+1} = t(e_{l,l+1}) and α = λ(e_{l,l+1})

where u = (u^{l})_{l∈ℤ_{+}}, v = (v^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏}.

Proposition 2.1. The set E_{𝔏} ⊂ Ω_{𝔏}×Σ×Ω_{𝔏} is a zero-dimensional continuous graph.

Proof. It suffices to show that E_{𝔏} is closed. For (u, β, v) ∈ Ω_{𝔏} × Σ × Ω_{𝔏} with (u, β, v) ∉ E_{𝔏}, one finds l ∈ ℕ such that there does not exist any edge e in E_{l,l+1} with s(e) = u^{l}, t(e) = v^{l+1} and λ(e) = β. Put

U_{u^{l}} = {(w^{i})_{i∈ℤ_{+}} ∈ Ω_{𝔏} | w^{l} = u^{l}}, U_{v^{l+1}} = {(w^{i})_{i∈ℤ_{+}} ∈ Ω_{𝔏} | w^{l+1} = v^{l+1}}.

They are open sets in Ω_{𝔏}. Hence U_{u^{l}} × {β} × U_{v^{l+1}} is an open neighborhood of (u, β, v) that does not intersect with E_{𝔏} so that E_{𝔏} is closed. □

We denote by {𝔳_{1}^{l}, …, 𝔳_{m(l)}^{l}} the vertex set V_{l}. Put for α ∈ Σ, i = 1, …, m(1)

U_{i}^{1}(α) = {(u, α, v) ∈ E_{𝔏} | v^{1} = 𝔳_{i}^{1} where v = (v^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏}}.

Then U_{i}^{1}(α) is a clopen set in E_{𝔏} such that

∪_{α∈Σ} ∪_{i=1}^{m(1)} U_{i}^{1}(α) = E_{𝔏}, U_{i}^{1}(α) ∩ U_{j}^{1}(β) = ∅ if (i, α) ≠ (j, β).

Put t(u, α, v) = v for (u, α, v) ∈ E_{𝔏}. Suppose that 𝔏 is left-resolving. It is easy to see that if U_{i}^{1}(α) ≠ ∅, the restriction of t to U_{i}^{1}(α) is a homeomorphism onto U_{𝔳_{i}^{1}} = {(v^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏} | v^{1} = 𝔳_{i}^{1}}. Hence t : E_{𝔏} → Ω_{𝔏} is a local homeomorphism. Following Deaconu [De3], we consider the set X_{𝔏} of all one-sided paths of E_{𝔏}:

X_{𝔏} = {(α_{i}, u_{i})_{i=1}^{∞} ∈ ∏_{i=1}^{∞}(Σ × Ω_{𝔏}) | (u_{i}, α_{i+1}, u_{i+1}) ∈ E_{𝔏} for all i ∈ ℕ
and (u_{0}, α_{1}, u_{1}) ∈ E_{𝔏} for some u_{0} ∈ Ω_{𝔏}}.

The set X_{𝔏} has the relative topology from the infinite product topology of Σ × Ω_{𝔏}. It is a zero-dimensional compact Hausdorff space. The shift map σ : (α_{i}, u_{i})_{i=1}^{∞} ∈ X_{𝔏} → (α_{i+1}, u_{i+1})_{i=1}^{∞} ∈ X_{𝔏} is continuous. For v = (v^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏} and α ∈ Σ, the local property of 𝔏 ensures that if there exists e_{0,1} ∈ E_{0,1} satisfying v^{1} = t(e_{0,1}), α = λ(e_{0,1}), there exist e_{l,l+1} ∈ E_{l,l+1} and u = (u^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏} satisfying u^{l} = s(e_{l,l+1}), v^{l+1} = t(e_{l,l+1}), α = λ(e_{l,l+1}) for each l ∈ ℤ_{+}. Hence if 𝔏 is left-resolving, for any x = (α_{i}, v_{i})_{i=1}^{∞} ∈ X_{𝔏}, there uniquely exists v_{0} ∈ Ω_{𝔏} such that (v_{0}, α_{1}, v_{1}) ∈ E_{𝔏}. Denote by v(x)_{0} the unique vertex v_{0} for x ∈ X_{𝔏}.

Lemma 2.2. For a λ-graph system 𝔏, consider the following conditions (i) 𝔏 is left-resolving. (ii) E_{𝔏} is left-resolving, that is, for (u, α, v), (u′, α, v′) ∈ E_{𝔏}, the condition

v = v′ implies u = u′. (iii) σ is a local homeomorphism on X_{𝔏}.

Then we have

(i) ⇔ (ii) ⇒ (iii).

Proof. The implications (i) ⇔ (ii) are direct. We will see that (ii) ⇒ (iii). Suppose that 𝔏 is left-resolving. Let {γ_{1}, …, γ_{m}} = Σ be the list of the alphabet. Put

X_{𝔏}(k) = {(α_{i}, v_{i})_{i=1}^{∞} ∈ X_{𝔏} | α_{1} = γ_{k}}

that is a clopen set of X_{𝔏}. Since the family X_{𝔏}(k), k = 1, …, m is a disjoint covering of X_{𝔏} and the restriction of σ to each of them σ|_{X_{𝔏}(k)} : X_{𝔏}(k) → X_{𝔏} is a homeomorphism, the continuous surjection σ is a local homeomorphism on X_{𝔏}. □

Remark. We will remark that a continuous graph coming from a left-resolving, predecessor-separated λ-graph system is characterized as in the following way. Let E ⊂ V × Σ × V be a continuous graph. Following [KM], we define the l-past context of v ∈ V as follows:

Γ_{l}^{−}(v) = {(α_{1}, …, α_{l}) ∈ Σ^{l} | ∃v_{0}, v_{1}, …, v_{l−1} ∈ V;
(v_{i−1}, α_{i}, v_{i}) ∈ E, i = 1, 2, …, l − 1, (v_{l−1}, α_{l}, v) ∈ E}.

We say E to be predecessor-separated if for two vertices u, v ∈ V, there exists l ∈ ℕ such that Γ_{l}^{−}(u) ≠ Γ_{l}^{−}(v). The following proposition can be directly proved by using an idea of [KM]. Its result will not be used in our further discussions so that we omit its proof.

Proposition 2.3. Let E ⊂ V × Σ × V be a zero-dimensional continuous graph such that E is left-resolving, predecessor-separated. If the map t : E → V defined by t(u, α, v) = v is a surjective open map, there exists a λ-graph system L^{E} over Σ and a homeomorphism Φ from V onto Ω_{𝔏^{E}} such that the map Φ × id × Φ : V × Σ × V → Ω_{𝔏^{E}} × Σ × Ω_{𝔏^{E}} satisfies (Φ × id × Φ)(E) = E_{𝔏^{E}} .

3. The C^{∗}-algebra O_{𝔏}.

In what follows we assume 𝔏 to be left-resolving. Following V. Deaconu [De2],[De3],[De4], one may construct a locally compact r-discrete groupoid from a local homeomorphism σ on X_{𝔏} as in the following way (cf. [An],[Re]). Set

G_{𝔏} = {(x, n, y) ∈ X_{𝔏} × ℤ × X_{𝔏} | ∃k, l ≥ 0; σ^{k}(x) = σ^{l}(y), n = k − l}.

The range map and the domain map are defined by

r(x, n, y) = x, d(x, n, y) = y.

The multiplication and the inverse operation are defined by

(x, n, y)(y, m, z) = (x, n + m, z), (x, n, y)^{−1} = (y, −n, x).

The unit space G_{𝔏}^{0} is defined to be the space X_{𝔏} = {(x, 0, x) ∈ G_{𝔏} | x ∈ X_{𝔏}}. A basis of the open sets for G_{𝔏} is given by

Z(U, V, k, l) = {(x, k − l, (σ^{l}|_{V})^{−1} ∘ (σ^{k}(x)) ∈ G_{𝔏} | x ∈ U}

where U, V are open sets of X_{𝔏}, and k, l ∈ ℕ are such that σ^{k}|_{U} and σ^{l}|_{V} are homeomorphisms with the same open range. Hence we see

Z(U, V, k, l) = {(x, k − l, y) ∈ G_{𝔏} | x ∈ U, y ∈ V, σ^{k}(x) = σ^{l}(y)}.

The groupoid C^{∗}-algebra C^{∗}(G_{𝔏}) for the groupoid G_{𝔏} is defined as in the following way ([Re], cf. [An],[De2],[De3],[De4]). Let C_{c}(G_{𝔏}) be the set of all continuous functions on G_{𝔏} with compact support that has a natural product structure of ∗-algebra given by

(f ∗ g)(s) = ∑_{\begin{matrix}t∈G_{𝔏}, \\ r(t)=r(s) \end{matrix}} f(t)g(t^{−1}s) = ∑_{\begin{matrix}t_{1},t_{2}∈G_{𝔏}, \\ s=t_{1}t_{2} \end{matrix}} f(t_{1})g(t_{2}),

f^{∗}(s) = \overline{f(s^{−1})},  f, g ∈ C_{c}(G_{𝔏}), s ∈ G_{𝔏}.

Let C_{0}(G_{𝔏}^{0}) be the C^{∗}-algebra of all continuous functions on G_{𝔏}^{0} that vanish at infinity. The algebra C_{c}(G_{𝔏}) is a C_{0}(G_{𝔏}^{0})-module, endowed with a C_{0}(G_{𝔏}^{0})- valued inner product by

(ξf)(x, n, y) =ξ(x, n, y)f(y),  ξ ∈ C_{c}(G_{𝔏}), f ∈ C_{0}(G_{𝔏}^{0}), (x, n, y) ∈ G_{𝔏},
< ξ, η > (y) = ∑_{\begin{matrix}x,n \\ (x,n,y)∈G_{𝔏} \end{matrix}} \overline{ξ(x, n, y)}η(x, n, y),  ξ, η ∈ C_{c}(G_{𝔏}), y ∈ X_{𝔏}.

Let us denote by l^{2}(G_{𝔏}) the completion of the inner product C_{0}(G_{𝔏}^{0})-module C_{c}(G_{𝔏}). It is a Hilbert C^{∗}-right module over the commutative C^{∗}-algebra C_{0}(G_{𝔏}^{0}). We denote by B(l^{2}(G_{𝔏})) the C^{∗}-algebra of all bounded adjointable C_{0}(G_{𝔏}^{0})-module maps on l^{2}(G_{𝔏}). Let π be the ∗-homomorphism of C_{c}(G_{𝔏}) into B(l^{2}(G_{𝔏})) defined by π(f)ξ = f ∗ ξ for f, ξ ∈ C_{c}(G_{𝔏}). Then the closure of π(C_{c}(G_{𝔏})) in B(l^{2}(G_{𝔏})) is called the (reduced) C^{∗}-algebra of the groupoid G_{𝔏}, that we denote by C^{∗}(G_{𝔏}).

Definition. The C^{∗}-algebra O_{𝔏} associated with λ-graph system 𝔏 is defined to be the C^{∗}-algebra C^{∗}(G_{𝔏}) of the groupoid G_{𝔏}.

We will study the algebraic structure of the C^{∗}-algebra O_{𝔏}. Recall that Λ^{k} denotes the set of all words of Σ^{k} that appear in 𝔏. For x = (α_{n}, u_{n})_{n=1}^{∞} ∈ X_{𝔏}, we put λ(x)_{n} = α_{n} ∈ Σ, v(x)_{n} = u_{n} ∈ Ω_{𝔏} respectively. The ι-orbit v(x)_{n} is written as v(x)_{n} = (v(x)_{n}^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏} = \underleftarrow{lim} V_{l}. Now 𝔏 is left-resolving so that there uniquely exists v(x)_{0} ∈ Ω_{𝔏} satisfying (v(x)_{0}, α_{1}, u_{1}) ∈ E_{𝔏}. Set for μ = (μ_{1}, …, μ_{k}) ∈ Λ^{k},

U(μ) = {(x, k, y) ∈ G_{𝔏} | σ^{k}(x) = y, λ(x)_{1} = μ_{1}, …, λ(x)_{k} = μ_{k}}

and for 𝔳_{i}^{l} ∈ V_{l},

U(𝔳_{i}^{l}) = {(x, 0, x) ∈ G_{𝔏} | v(x)_{0}^{l} = 𝔳_{i}^{l}}

where v(x)_{0} = (v(x)_{0}^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏}. They are clopen sets of G_{𝔏}. We set

S_{μ} = π(χ_{U(μ)}),  E_{i}^{l} = π(χ_{U(𝔳_{i}^{l})})  in π(C_{c}(G_{𝔏}))

where χ_{F} ∈ C_{c}(G_{𝔏}) denotes the characteristic function of a clopen set F on the space G_{𝔏}. Then it is straightforward to see the following lemmas.

Lemma 3.1.

(i) S_{μ} is a partial isometry satisfying S_{μ} = S_{μ_{1}} ⋯ S_{μ_{k}}, where μ = (μ_{1}, …, μ_{k}) ∈ Λ^{k}.

(ii) ∑_{μ∈Λ^{k}} S_{μ}S_{μ}^{∗} = 1 for k ∈ ℕ. We in particular have

(3.1)  ∑_{α∈Σ} S_{α}S_{α}^{∗} = 1.

(iii) E_{i}^{l} is a projection such that

(3.2)  ∑_{i=1}^{m(l)} E_{i}^{l} = 1,  E_{i}^{l} = ∑_{j=1}^{m(l+1)} I_{l,l+1}(i, j)E_{j}^{l+1},

where I_{l,l+1} is the matrix defined in Theorem A in Section 1, corresponding to the map ι_{l,l+1} : V_{l+1} → V_{l}.

Take μ = (μ_{1}, …, μ_{k}) ∈ Λ^{k}, ν = (ν_{1}, …, ν_{k′}) ∈ Λ^{k′} and 𝔳_{i}^{l} ∈ V_{l} with k, k′ ≤ l such that there exist paths ξ, η in 𝔏 satisfying λ(ξ) = μ, λ(η) = ν and t(ξ) = t(η) = 𝔳_{i}^{l}. We set

U(μ, 𝔳_{i}^{l}, ν) ={(x, k − k′, y) ∈ G_{𝔏} | σ^{k}(x) = σ^{k′}(y), v(x)_{k}^{l} = v(y)_{k′}^{l} = 𝔳_{i}^{l},

λ(x)_{1} = μ_{1}, …, λ(x)_{k} = μ_{k}, λ(y)_{1} = ν_{1}, …, λ(y)_{k′} = ν_{k′} }.

The sets U(μ, 𝔳_{i}^{l}, ν), μ ∈ Λ^{k}, ν ∈ Λ^{k′}, i = 1, …, m(l) are clopen sets and generate the topology of G_{𝔏}.

Lemma 3.2.

S_{μ}E_{i}^{l}S_{ν}^{∗} = π(χ_{U(μ,𝔳_{i}^{l},ν)}) ∈ π(C_{c}(G_{𝔏})).

Hence the C^{∗}-algebra O_{𝔏} is generated by S_{α}, α ∈ Σ and E_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}.

The generators S_{α}, E_{i}^{l} satisfy the following operator relations, that are straightforwardly checked.

Lemma 3.3.

S_{α}S_{α}^{∗}E_{i}^{l} = E_{i}^{l}S_{α}S_{α}^{∗}, (3.3)

(3.4)  S_{α}^{∗}E_{i}^{l}S_{α} = ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, α, j)E_{j}^{l+1},

for α ∈ Σ, i = 1, 2, …, m(l), l ∈ ℤ_{+}, where A_{l,l+1}(i, α, j) is defined in Theorem A in Section 1.

The four operator relations (3.1),(3.2),(3.3),(3.4) are called the relations (𝔏). Let A_{l}, l ∈ ℤ_{+} be the C^{∗}-subalgebra of O_{𝔏} generated by the projections E_{i}^{l}, i = 1, …, m(l), that is,

A_{l} = ℂE_{1}^{l} ⊕ ⋯ ⊕ ℂE_{m(l)}^{l}.

The projections S_{α}^{∗}S_{α}, α ∈ Σ and S_{μ}^{∗}S_{μ}, μ ∈ Λ^{k}, k ≤ l belong to A_{l}, l ∈ ℕ by (3.4) and the first relation of (3.2). Let A_{𝔏} be the C^{∗}-subalgebra of O_{𝔏} generated by all the projections E_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}. By the second relation of (3.2), the algebra A_{l} is naturally embedded in A_{l+1} so that A_{𝔏} is a commutative AF-algebra. We note that there exists an isomorphism between A_{l} and C(V_{l}) for each l ∈ ℤ_{+} that is compatible with the embeddings A_{l} ↪ A_{l+1} and I_{l,l+1}^{t}(= ι_{l,l+1}^{∗}) : C(V_{l}) ↪ C(V_{l+1}). Hence there exists an isomorphism between A_{𝔏} and C(Ω_{𝔏}). Let k, l be natural numbers with k ≤ l. We set

D_{𝔏} =The C^{∗}-subalgebra of O_{𝔏} generated by S_{μ}aS_{μ}^{∗}, μ ∈ Λ^{∗}, a ∈ A_{𝔏}.
F_{k}^{l} =The C^{∗}-subalgebra of O_{𝔏} generated by S_{μ}aS_{ν}^{∗}, μ, ν ∈ Λ^{k}, a ∈ A_{l}.
F_{k}^{∞} =The C^{∗}-subalgebra of O_{𝔏} generated by S_{μ}aS_{ν}^{∗}, μ, ν ∈ Λ^{k}, a ∈ A_{𝔏}.
F_{𝔏} =The C^{∗}-subalgebra of O_{𝔏} generated by S_{μ}aS_{ν}^{∗}, μ, ν ∈ Λ^{∗},

|μ| = |ν|, a ∈ A_{𝔏}.

The algebra D_{𝔏} is isomorphic to C(X_{𝔏}). It is obvious that the algebra F_{k}^{l} is finite dimensional and there exists an embedding ι_{l,l+1} : F_{k}^{l} ↪ F_{k}^{l+1} through the preceding embedding A_{l} ↪ A_{l+1}. Define a homomorphism c : (x, n, y) ∈ G_{𝔏} → n ∈ ℤ. We denote by F_{𝔏} the subgroupoid c^{−1}(0) of G_{𝔏}. Let C^{∗}(F_{𝔏}) be its groupoid C^{∗}-algebra. It is also immediate that the algebra F_{𝔏} is isomorphic to C^{∗}(F_{𝔏}). By (3.1),(3.3),(3.4), the relations:

E_{i}^{l} = ∑_{α∈Σ} ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, α, j)S_{α}E_{j}^{l+1}S_{α}^{∗}, i = 1, 2, …, m(l)

hold. They yield

S_{μ}E_{i}^{l}S_{ν}^{∗} = ∑_{α∈Σ} ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, α, j)S_{μα}E_{j}^{l+1}S_{να}^{∗} for μ, ν ∈ Λ^{k},

that give rise to an embedding F_{k}^{l} ↪ F_{k+1}^{l+1}. It induces an embedding of F_{k}^{∞} into F_{k+1}^{∞} that we denote by λ_{k,k+1}.

Proposition 3.4.

(i) F_{k}^{∞} is an AF-algebra defined by the inductive limit of the embeddings ι_{l,l+1} : F_{k}^{l} ↪ F_{k}^{l+1}, l ∈ ℕ.

(ii) F_{𝔏} is an AF-algebra defined by the inductive limit of the embeddings λ_{k,k+1} : F_{k}^{∞} ↪ F_{k+1}^{∞}, k ∈ ℤ_{+}.

Let U_{z}, z ∈ 𝕋 = {z ∈ ℂ | |z| = 1} be an action of 𝕋 to the unitary group of B(l^{2}(G_{𝔏})) defined by

(U_{z}ξ)(x, n, y) = z^{n}ξ(x, n, y) for ξ ∈ l^{2}(G_{𝔏}), (x, n, y) ∈ G_{𝔏}.

The action Ad(U_{z}) on B(l^{2}(G_{𝔏})) leaves O_{𝔏} globally invariant. It gives rise to an action on O_{𝔏}. We denote it by α_{𝔏} and call it the gauge action. Let E_{𝔏} be the expectation from O_{𝔏} onto the fixed point subalgebra O_{𝔏}^{α_{𝔏}} under α_{𝔏} defined by

(3.5)  E_{𝔏}(X) = ∫_{z∈𝕋} α_{𝔏}_{z}(X)dz,  X ∈ O_{𝔏}.

Let P_{𝔏} be the ∗-algebra generated algebraically by S_{α}, α ∈ Σ and E_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}. For μ = (μ_{1}, …, μ_{k}) ∈ Λ^{k}, it follows that by (3.3), E_{i}^{l}S_{μ_{1}} ⋯ S_{μ_{k}} = S_{μ_{1}}S_{μ_{1}}^{∗}E_{i}^{l}S_{μ_{1}} ⋯ S_{μ_{k}}. As S_{μ_{1}}^{∗}E_{i}^{l}S_{μ_{1}} is a linear combination of E_{j}^{l+1}, j = 1, …, m(l+1) by (3.4), one sees S_{μ_{1}}^{∗}E_{i}^{l}S_{μ_{1}}S_{μ_{2}} = S_{μ_{2}}S_{μ_{2}}^{∗}S_{μ_{1}}^{∗}E_{i}^{l}S_{μ_{1}}S_{μ_{2}} and inductively

(3.6)  E_{i}^{l}S_{μ} = S_{μ}S_{μ}^{∗}E_{i}^{l}S_{μ},  E_{i}^{l}S_{μ}S_{μ}^{∗} = S_{μ}S_{μ}^{∗}E_{i}^{l}.

By the relations (3.6), each element X ∈ P_{𝔏} is expressed as a finite sum

X = ∑_{|ν|≥1} X_{−ν}S_{ν}^{∗} + X_{0} + ∑_{|μ|≥1} S_{μ}X_{μ} for some X_{−ν}, X_{0}, X_{μ} ∈ F_{𝔏}.

Then the following lemma is routine.

Lemma 3.5. The fixed point subalgebra O_{𝔏}^{α_{𝔏}} of O_{𝔏} under α_{𝔏} is the AFalgebra F_{𝔏}.

We can now prove a universal property of O_{𝔏}.

Theorem 3.6. The C^{∗}-algebra O_{𝔏} is the universal C^{∗}-algebra subject to the relations (𝔏).

Proof. Let O_{[𝔏]} be the universal C^{∗}-algebra generated by partial isometries s_{α}, α ∈ Σ and projections e_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+} subject to the operator relations (𝔏). This means that O_{[𝔏]} is generated by s_{α}, α ∈ Σ and e_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}, that have only operator relations (𝔏). The C^{∗}- norm of O_{[𝔏]} is given by the universal C^{∗}-norm. Let us denote by F_{[k]}^{[l]}, F_{[𝔏]} the similarly defined subalgebras of O_{[𝔏]} to F_{k}^{l}, F_{𝔏} respectively. The algebra F_{[k]}^{[l]} as well as F_{k}^{l} is a finite dimensional algebra. Since s_{μ}e_{i}^{l}s_{ν}^{∗} ≠ 0 if and only if S_{μ}E_{i}^{l}S_{ν}^{∗} ≠ 0, the correspondence s_{μ}e_{i}^{l}s_{ν}^{∗} → S_{μ}E_{i}^{l}S_{ν}^{∗}, |μ| = |ν| = k ≤ l yields an isomorphism from F_{[k]}^{[l]} to F_{k}^{l}. It induces an isomorphism from F_{[𝔏]} to F_{𝔏}. By the universality, for z ∈ ℂ, |z| = 1 the correspondence s_{α} → zs_{α}, α ∈ Σ, e_{i}^{l} → e_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+} gives rise to an action of the torus group 𝕋 on O_{[𝔏]}, which we denote by α_{[𝔏]}. Let E_{[𝔏]} be the expectation from O_{[𝔏]} onto the fixed point subalgebra O_{[𝔏]}^{α_{[𝔏]}} under α_{[𝔏]} similarly defined to (3.5). The algebra O_{[𝔏]}^{α_{[𝔏]}} is nothing but the algebra F_{[𝔏]}. By the universality of O_{[𝔏]}, the correspondence s_{α} → S_{α}, α ∈ Σ, e_{i}^{l} → E_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+} extends to a surjective homomorphism from O_{[𝔏]} to O_{𝔏}, which we denote by π_{𝔏}. The restriction of π_{𝔏} to F_{[𝔏]} is the preceding isomorphism. As we see that E_{𝔏} ∘ π_{𝔏} = π_{𝔏} ∘ E_{[𝔏]} and E_{[𝔏]} is faithful, we conclude that π_{𝔏} is isomorphic by a similar argument to [CK; 2.12. Proposition]. □

4. Uniqueness and simplicity

We will prove that O_{𝔏} is the unique C^{∗}-algebra subject to the operator relations (𝔏) under a mild condition on 𝔏, called (I). The condition (I) is a generalization of condition (I) for a finite square matrix with entries in {0, 1} defined by Cuntz-Krieger in [CK] and condition (I) for a subshift defined in [Ma4]. A related condition for a Hilbert C^{∗}-bimodule has been introduced by Kajiwara-Pinzari-Watatani in [KPW]. For an infinite directed graph, such a condition is defined by Kumjian-Pask-Raeburn-Renault in [KPRR]. For a vertex 𝔳_{i}^{l} ∈ V_{l}, let Γ^{+}(𝔳_{i}^{l}) be the set of all label sequences in 𝔏 starting at 𝔳_{i}^{l}. That is,

Γ^{+}(𝔳_{i}^{l}) = {(α_{1}, α_{2}, …,) ∈ Σ^{ℕ} | ∃e_{n,n+1} ∈ E_{n,n+1} for n = l, l + 1, …;
𝔳_{i}^{l} = s(e_{l,l+1}), t(e_{n,n+1}) = s(e_{n+1,n+2}), λ(e_{n,n+1}) = α_{n−l+1}}.

Definition. A λ-graph system 𝔏 satisfies condition (I) if for each 𝔳_{i}^{l} ∈ V, the set Γ^{+}(𝔳_{i}^{l}) contains at least two distinct sequences.

For 𝔳_{i}^{l} ∈ V_{l} set F_{i}^{l} = {x ∈ X_{𝔏} | v(x)_{0}^{l} = 𝔳_{i}^{l}} where v(x)_{0} = (v(x)_{0}^{l})_{l∈ℤ_{+}} ∈ Ω_{𝔏} = \underleftarrow{lim} V_{l} is the unique ι-orbit for x ∈ X_{𝔏} such that (v(x)_{0}, λ(x)_{1}, v(x)_{1}) ∈ E_{𝔏} as in the preceding section. By a similar discussion to [Ma4; Section 5] (cf.[CK; 2.6.Lemma]), we know that if 𝔏 satisfies (I), for l, k ∈ ℕ with l ≥ k, there exists y_{i}^{l} ∈ F_{i}^{l} for each i = 1, 2, …, m(l) such that

σ^{m}(y_{i}^{l}) ≠ y_{j}^{l} for all 1 ≤ i, j ≤ m(l), 1 ≤ m ≤ k.

By the same manner as the proof of [Ma4;Lemma 5.3], we obtain

Lemma 4.1. Suppose that 𝔏 satisfies condition (I). Then for l, k ∈ ℕ with l ≥ k, there exists a projection q_{k}^{l} ∈ D_{𝔏} such that

(i) q_{k}^{l}a ≠ 0 for all nonzero a ∈ A_{l}, (ii) q_{k}^{l}ϕ_{𝔏}^{m}(q_{k}^{l}) = 0 for all m = 1, 2, …, k, where ϕ_{𝔏}^{m}(X) = ∑_{μ∈Λ^{m}} S_{μ}XS_{μ}^{∗}.

Now we put Q_{k}^{l} = ϕ_{𝔏}^{k}(q_{k}^{l}) a projection in D_{𝔏}. Note that each element of D_{𝔏} commutes with elements of A_{𝔏}. As we see S_{μ}ϕ_{𝔏}^{j}(X) = ϕ_{𝔏}^{j+|μ|}(X)S_{μ} for X ∈ D_{𝔏}, j ∈ ℤ_{+}, μ ∈ Λ^{∗}, a similar argument to [CK;2.9.Proposition] leads to the following lemma.

Lemma 4.2.

(i) The correspondence: X ∈ F_{k}^{l} ⟶ Q_{k}^{l}XQ_{k}^{l} ∈ Q_{k}^{l}F_{k}^{l}Q_{k}^{l} extends to an isomorphism from F_{k}^{l} onto Q_{k}^{l}F_{k}^{l}Q_{k}^{l}.

(ii) Q_{k}^{l}X − XQ_{k}^{l} → 0, ∥Q_{k}^{l}X∥ → ∥X∥ as k, l → ∞ for X ∈ F_{𝔏}.

(iii) Q_{k}^{l}S_{μ}Q_{k}^{l}, Q_{k}^{l}S_{μ}^{∗}Q_{k}^{l} → 0 as k, l → ∞ for μ ∈ Λ^{∗}.

We then prove the uniqueness of the algebra O_{𝔏} subject to the relations (𝔏).

Theorem 4.3. Suppose that 𝔏 satisfies condition (I). Let Ŝ_{α}, α ∈ Σ and Ê_{i}^{l}, i = 1, 2, …, m(l), l ∈ ℤ_{+} be another family of nonzero partial isometries and nonzero projections satisfying the relations (𝔏). Then the map S_{α} → Ŝ_{α}, α ∈ Σ, E_{i}^{l} → Ê_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+} extends to an isomorphism from O_{𝔏} onto the C^{∗}-algebra Ô_{𝔏} generated by Ŝ_{α}, α ∈ Σ and Ê_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}.

Proof. We may define C^{∗}-subalgebras D̂_{𝔏}, F̂_{k}^{l}, F̂_{𝔏} of Ô_{𝔏} by using the elements Ŝ_{μ}Ê_{i}^{l}Ŝ_{ν}^{∗} by the same manners as the constructions of the C^{∗}-subalgebras D_{𝔏}, F_{k}^{l}, F_{𝔏} of O_{𝔏} respectively. As in the proof of Theorem 3.6, the map S_{μ}E_{i}^{l}S_{ν}^{∗} ∈ F_{k}^{l} → Ŝ_{μ}Ê_{i}^{l}Ŝ_{ν}^{∗} ∈ F̂_{k}^{l}, |μ| = |ν| = k ≤ l extends to an isomorphism from the AF-algebra F_{𝔏} onto the AF-algebra F̂_{𝔏}. By Theorem 3.6, the algebra O_{𝔏} has a universal property subject to the relations (𝔏) so that there exists a surjective homomorphism π̂ from O_{𝔏} onto Ô_{𝔏} satisfying π̂(S_{α}) = Ŝ_{α} and π̂(E_{i}^{l}) = Ê_{i}^{l}. The restriction of π̂ to F_{𝔏} is the preceding isomorphism onto F̂_{𝔏}. Now 𝔏 satisfies (I). Let Q_{k}^{l} be the sequence of projections as in Lemma 4.2. We put Q̂_{k}^{l} = π̂(Q_{k}^{l}) ∈ D̂_{𝔏} that has the corresponding properties to Lemma 4.2 for the algebra F̂_{𝔏}. Let P̂_{𝔏} be the ∗-algebra generated algebraically by Ŝ_{α}, α ∈ Σ and Ê_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+}. By the relations (𝔏), each element X ∈ P̂_{𝔏} is expressed as a finite sum

X = ∑_{|ν|≥1} X_{−ν} Ŝ_{ν}^{∗} + X_{0} + ∑_{|μ|≥1} Ŝ_{μ}X_{μ} for some X_{−ν}, X_{0}, X_{μ} ∈ F̂_{𝔏}.

By a similar argument to [CK;2.9.Proposition], it follows that the map X ∈ P̂_{𝔏} → X_{0} ∈ F̂_{𝔏} extends to an expectation Ê_{𝔏} from Ô_{𝔏} onto F̂_{𝔏}, that satisfies Ê_{𝔏} ∘ π̂ = π̂ ∘ E_{𝔏}. As E_{𝔏} is faithful, we conclude that π̂ is isomorphic. □

Remark. Let e_{x} be a vector assigned to x ∈ X_{𝔏}. Let ℌ_{𝔏} be the Hilbert space spanned by the vectors e_{x}, x ∈ X_{𝔏} such that the vectors e_{x}, x ∈ X_{𝔏} form its complete orthonormal basis. For x = (α_{i}, v_{i})_{i=1}^{∞} ∈ X_{𝔏}, take v_{0} = v(x)_{0} ∈ Ω_{𝔏}. For a symbol β ∈ Σ, if there exists a vertex v_{−1} ∈ Ω_{𝔏} such that (v_{−1}, β, v_{0}) ∈ E_{𝔏}, we define βx ∈ X_{𝔏}, by putting α_{0} = β, as

βx = (α_{i−1}, v_{i−1})_{i=1}^{∞} ∈ X_{𝔏}.

Put

Γ_{1}^{−}(x) = {γ ∈ Σ | (v_{−1}, γ, v(x)_{0}) ∈ E_{𝔏} for some v_{−1} ∈ Ω_{𝔏}}.

We define the creation operators S̃_{β}, β ∈ Σ on ℌ_{𝔏} by

S̃_{β}e_{x} = \{ \begin{matrix}e_{βx} & if β ∈ Γ_{1}^{−}(x), \\ 0 & if β ∉ Γ_{1}^{−}(x). \end{matrix}

Proposition 4.4. Suppose that 𝔏 satisfies condition (I). If 𝔏 is predecessorseparated, O_{𝔏} is isomorphic to the C^{∗}-algebra C^{∗}(S̃_{β}, β ∈ Σ) generated by the partial isometries S̃_{β}, β ∈ Σ on the Hilbert space ℌ_{𝔏}.

Proof. Suppose that 𝔏 is predecessor-separated. Define a sequence of projections Ẽ_{i}^{l}, i = 1, …, m(l), l ∈ ℕ and Ẽ_{i}^{0}, i = 1, …, m(0) by using the formulae (1.7) from the partial isometries S̃_{β}, β ∈ Σ. It is straightforward to see that Ẽ_{i}^{l}, i = 1, …, m(l), l ∈ ℤ_{+} are nonzero. The partial isometries S̃_{β} and the projections Ẽ_{i}^{l} satisfy the relations (𝔏). □

Let Λ be a subshift and 𝔏^{Λ} its canonical λ-graph system, that is left-resolving and predecessor-separated. It is easy to see that Λ satisfies condition (I) in the sense of [Ma4] if and only if 𝔏^{Λ} satisfies condition (I).

Corollary 4.5(cf.[Ma],[CaM]). The C^{∗}-algebra O_{𝔏^{Λ}} associated with λgraph system 𝔏^{Λ} is canonically isomorphic to the C^{∗}-algebra O_{Λ} associated with subshift Λ.

We next refer simplicity and purely infiniteness of the algebra O_{𝔏}. We introduce the notions of irreducibility and aperiodicity for λ-graph system

Definition.

(i) A λ-graph system 𝔏 is said to be irreducible if for a vertex v ∈ V_{l} and x = (x_{1}, x_{2}, …) ∈ Ω_{𝔏} = lim_{⟵}V_{l}, there exists a path in 𝔏 starting at v and terminating at x_{l+N} for some N ∈ ℕ.

(ii) A λ-graph system 𝔏 is said to be aperiodic if for a vertex v ∈ V_{l} there exists an N ∈ ℕ such that there exist paths in 𝔏 starting at v and terminating at all the vertices of V_{l+N}.

Aperiodicity automatically implies irreducibility. Define a positive operator λ_{𝔏} on A_{𝔏} by

λ_{𝔏}(X) = ∑_{α∈Σ} S_{α}^{∗}XS_{α} for X ∈ A_{𝔏}.

We say that λ_{𝔏} is irreducible if there exists no non-trivial ideal of A_{𝔏} invariant under λ_{𝔏}, and λ_{𝔏} is aperiodic if for a projection E_{i}^{l} ∈ A_{l} there exists N ∈ ℕ such that λ_{𝔏}^{N}(E_{i}^{l}) ≥ 1. The following lemma is easy to prove (cf.[Ma4]).

Lemma 4.6.

(i) A λ-graph system 𝔏 is irreducible if and only if λ_{𝔏} is irreducible.

(ii) A λ-graph system 𝔏 is aperiodic if and only if λ_{𝔏} is aperiodic.

We thus obtain

Theorem 4.7. Suppose that a λ-graph system 𝔏 satisfies condition (I). If 𝔏 is irreducible, O_{𝔏} is simple.

Proof. Suppose that there exists a nonzero ideal I of O_{𝔏}. As 𝔏 satisfies condition (I), by uniqueness of the algebra O_{𝔏}, I must contain a projection E_{i}^{l} for some l, i. Hence I ∩ A_{𝔏} is a nonzero ideal of A_{𝔏} that is invariant under λ_{𝔏}. This leads to I = A_{𝔏} so that O_{𝔏} is simple. □

The above theorem is a generalization of [CK; 2.14.Theorem] and [Ma;Theorem 6.3]. We next see that O_{𝔏} is purely infinite (and simple) if 𝔏 is aperiodic. Assume that the subshift presented by λ-graph system 𝔏 is not a single point. Note that if 𝔏 is aperiodic, it satisfies condition (I). By [Bra;Corollary 3.5], the following lemma is straightforward.

Lemma 4.8. A λ-graph system 𝔏 is aperiodic if and only if the AF-algebra F_{𝔏} is simple.

As in the proof of [C3;1.6 Proposition], we conclude

Proposition 4.9 (cf.[C;1.13 Theorem]). If a λ-graph system 𝔏 is aperiodic, O_{𝔏} is simple and purely infinite.

5. K-Theory

The K-groups for the C^{∗}-algebras associated with subshifts have been computed in [Ma2] by using an analogous idea to the Cuntz’s paper [C3]. The discussion given in [Ma2] well works for our algebras O_{𝔏} associated with λ-graph systems. Let (A, I) be the nonnegative matrix system of the symbolic matrix system for 𝔏. We first study the K_{0}-group for the AF-algebra F_{𝔏}. We denote by Λ^{k}(𝔳_{i}^{l}) the set of words of length k that terminate at the vertex 𝔳_{i}^{l}. Let F_{k}^{l,i} be the C^{∗}-subalgebra of F_{k}^{l} generated by the elements S_{μ}E_{i}^{l}S_{ν}^{∗}, μ, ν ∈ Λ^{k}. It is isomorphic to the full matrix algebra M_{n_{i}^{l}(k)}(ℂ) of size n_{i}^{l}(k) where n_{i}^{l}(k) denotes the number of the set Λ^{k}(𝔳_{i}^{l}), so that one sees

F_{k}^{l} ≅ M_{n_{1}^{l}(k)}(ℂ) ⊕ ⋯ ⊕ M_{n_{m(l)}^{l}(k)}(ℂ).

The map Φ_{k}^{l} : [S_{μ}E_{i}^{l}S_{μ}^{∗}] ∈ K_{0}(F_{k}^{l}) → [E_{i}^{l}] ∈ K_{0}(A_{l}) for i = 1, 2, …, m(l), μ ∈ Λ^{k}(𝔳_{i}^{l}) yields an isomorphism between K_{0}(F_{k}^{l}) and K_{0}(A_{l}) = ℤ^{m(l)} = ∑_{i=1}^{m(l)} ℤ[E_{i}^{l}]. The isomorphisms Φ_{k}^{l}, l ∈ ℕ induce an isomorphism Φ_{k} = \underrightarrow{lim}_{l}Φ_{k}^{l}

from K_{0}(F_{k}^{∞}) = \underrightarrow{lim}_{ι_{l,l+1}_{∗}}K_{0}(F_{k}^{l}) onto K_{0}(A_{𝔏}) = \underrightarrow{lim}_{ι_{l,l+1}_{∗}}K_{0}(A_{l}) in a natural way.

The latter group is denoted by ℤ_{I^{t}}, that is isomorphic to the abelian group \underrightarrow{lim}_{l}\{ℤ^{m(l)}, I_{l,l+1}^{t}\} of the inductive limit of the homomorphisms I_{l,l+1}^{t} : ℤ^{m(l)} ⟶

ℤ^{m(l+1)}, l ∈ ℕ. The embedding λ_{k,k+1} of F_{k}^{∞} into F_{k+1}^{∞} given in Proposition 3.4 (ii) induces a homomorphism λ_{k,k+1}_{∗} from K_{0}(F_{k}^{∞}) to K_{0}(F_{k+1}^{∞}) that satisfies

λ_{k,k+1}_{∗}([S_{μ}E_{i}^{l}S_{μ}^{∗}]) = ∑_{α∈Σ}[S_{μα}S_{α}^{∗}E_{i}^{l}S_{α}S_{μα}^{∗}], μ ∈ Λ^{k}(𝔳_{i}^{l}), i = 1, 2, …, m(l).

Define a homomorphism λ_{l} from K_{0}(A_{l}) to K_{0}(A_{l+1}) by

λ_{l}([E_{i}^{l}]) = ∑_{j=1}^{m(l+1)} A_{l,l+1}(i, j)[E_{j}^{l+1}].

As A_{l,l+1}(i, j) = ∑_{α∈Σ} A_{l,l+1}(i, α, j), we see λ_{l}([E_{i}^{l}]) = ∑_{α∈Σ}[S_{α}^{∗}E_{i}^{l}S_{α}] by (3.4). The homomorphisms λ_{l} : K_{0}(A_{l}) → K_{0}(A_{l+1}), l ∈ ℕ act as the transposes A_{l,l+1}^{t} of the matrices A_{l,l+1} = [A_{l,l+1}(i, j)]_{i,j}, that are compatible with the embeddings ι_{l,l+1}_{∗}(= I_{l,l+1}^{t}) : K_{0}(A_{l}) → K_{0}(A_{l+1}) by (1.2). They define an endomorphism on ℤ_{I^{t}}(≅ K_{0}(A_{𝔏}). We denote it by λ_{(A,I)}. Since the diagram

K_{0}(F_{k}^{∞}) ⟶^{λ_{k,k+1}_{∗}} K_{0}(F_{k+1}^{∞})
Φ_{k}↓  ↓^{Φ_{k+1}}
K_{0}(A_{𝔏}) ⟶_{λ_{(A,I)}} K_{0}(A_{𝔏})

is commutative, one obtains

Proposition 5.1. K_{0}(F_{𝔏}) = lim_{⟶}{ℤ_{I^{t}}, λ_{(A,I)}}.

The group lim_{⟶}{ℤ_{I^{t}}, λ_{(A,I)}} is the dimension group Δ_{(A,I)} for the nonnegative matrix system (A, I) defined in [Ma5]. The dimension group for a nonnegative square finite matrix has been introduced by W. Krieger in [Kr] and [Kr2]. It is realized as the K_{0}-group for the canonical AF-algebra inside the Cuntz-Krieger algebra associated with the matrix ([C2],[C3]). If a λ-graph system 𝔏 is arising from the finite directed graph associated with the matrix, the C^{∗}-algebras O_{𝔏} and F_{𝔏} coincide with the Cuntz-Krieger algebra and the canonical AF-algebra respectively (cf. Section 7). Hence in this case, K_{0}(F_{𝔏}) coincides with the Krieger’s dimension group for the matrix.

Let p_{0} : 𝕋 → O_{𝔏} be the constant function whose value everywhere is the unit 1 of O_{𝔏}. It belongs to the algebra L^{1}(𝕋, O_{𝔏}) and hence to the crossed product O_{Λ} ⋊_{α_{𝔏}} 𝕋. By [Ro], the fixed point subalgebra O_{𝔏}^{α_{𝔏}} is isomorphic to the algebra p_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋)p_{0} through the correspondence : x ∈ O_{𝔏}^{α_{𝔏}} → x̂ ∈ L^{1}(𝕋, O_{𝔏}) ⊂ O_{𝔏} ⋊_{α_{𝔏}} 𝕋 where the function x̂ is defined by x̂(t) = x, t ∈ 𝕋. Then as in [Ma2;Section 4], the projection p_{0} is full in O_{𝔏} ⋊_{α_{𝔏}} 𝕋. Since the AF-algebra F_{𝔏} is realized as O_{𝔏}^{α_{𝔏}}, one sees, by [Bro;Corollary 2.6] Lemma 5.2. O_{𝔏} ⋊_{α_{𝔏}} 𝕋 is stably isomorphic to F_{𝔏}.

The natural inclusion ι : p_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋)p_{0} → O_{𝔏} ⋊_{α_{𝔏}} 𝕋 induces an isomorphism ι_{∗} : K_{0}(p_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋)p_{0}) → K_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋) on K-theory (cf.[Ri;Proposition 2.4]). Denote by α̂_{𝔏} the dual action of α_{𝔏} on O_{𝔏}⋊_{α_{𝔏}} 𝕋. Under the identification between F_{𝔏} and p_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋)p_{0}, we define an automorphism β on K_{0}(F_{𝔏}) by β = ι_{∗}^{−1} ∘ α̂_{𝔏}_{∗} ∘ ι_{∗}. By a similar argument to [Ma2;Lemma 4.5], [Ma2; Lemma 4.6] and [Ma2;Corollary 4.7], the automorphism β^{−1} : K_{0}(F_{𝔏}) → K_{0}(F_{𝔏}) corresponds to the shift σ on lim_{⟶}{ℤ_{I^{t}}, λ_{(A,I)}}. That is, if x = (x_{1}, x_{2}, …) is a

sequence representing an element of lim_{⟶}{ℤ_{I^{t}}, λ_{(A,I)}}, then β^{−1}x is represented by σ(x) = (x_{2}, x_{3}, …). As the dimension automorphism δ_{(A,I)} of Δ_{(A,I)} is defined to be the shift of the inductive limit lim_{⟶}{ℤ_{I^{t}}, λ_{(A,I)}} ([Ma5]), we obtain

Proposition 5.3. (K_{0}(F_{𝔏}), K_{0}(F_{𝔏})_{+}, α̂_{𝔏}_{∗}) ≅ (Δ_{(A,I)}, Δ_{(A,I)}^{+}, δ_{(A,I)}).

We will next present the K-theory formulae for O_{𝔏}. As K_{1}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋) = 0, the Pimsner-Voiculescu’s six term exact sequence of the K-theory for the crossed product (O_{𝔏} ⋊_{α_{𝔏}} 𝕋) ⋊_{α_{𝔏}} ℤ [PV] says the following lemma:

Lemma 5.4.

(i) K_{0}(O_{𝔏}) ≅ K_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋)/(id − α̂_{𝔏}_{∗}^{−1})K_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋).

(ii) K_{1}(O_{𝔏}) ≅ Ker(id − α̂_{𝔏}_{∗}^{−1}) on K_{0}(O_{𝔏} ⋊_{α_{𝔏}} 𝕋).

Therefore we have the K-theory formulae for O_{𝔏} by a similar argument to [C3;3.1.Proposition].

Theorem 5.5.

(i)

K_{0}(O_{𝔏}) ≅ ℤ_{I^{t}}/(id − λ_{(A,I)})ℤ_{I^{t}}

≅ lim_{⟶}{ℤ^{m(l+1)}/(I_{l,l+1}^{t} − A_{l,l+1}^{t})ℤ^{m(l)}; Ī_{l,l+1}^{t}},

(ii)

K_{1}(O_{𝔏}) ≅ Ker(id − λ_{(A,I)}) in ℤ_{I^{t}}

≅ lim_{⟶}{Ker(I_{l,l+1}^{t} − A_{l,l+1}^{t}) in ℤ^{m(l)}; I_{l,l+1}^{t}}

where Ī_{l,l+1}^{t} is the homomorphism from ℤ^{m(l)}/(I_{l−1,l}^{t} − A_{l−1,l}^{t})ℤ^{m(l−1)} to ℤ^{m(l+1)}/(I_{l,l+1}^{t} − A_{l,l+1}^{t})ℤ^{m(l)} induced by I_{l,l+1}^{t}. More precisely, for the minimal projections E_{1}^{l}, …, E_{m(l)}^{l} of A_{l} with ∑_{i=1}^{m(l)} E_{i}^{l} = 1 and the canonical basis e_{1}^{l}, …, e_{m(l)}^{l} of ℤ^{m(l)}, the map [E_{i}^{l}] → e_{i}^{l} extends to an isomorphism from

K_{0}(O_{𝔏}) onto lim_{⟶}{ℤ^{m(l+1)}/(I_{l,l+1}^{t} − A_{l,l+1}^{t})ℤ^{m(l)}; Ī_{l,l+1}^{t}}. Hence we have

K_{i}(O_{𝔏}) ≅ K_{i}(A, I) i = 0, 1.

Since the double crossed product (O_{𝔏} ⋊_{α_{𝔏}} 𝕋)×_{α_{𝔏}} ℤ is stably isomorphic to O_{𝔏}, the following proposition is immediate from Lemma 5.2 (cf.[RS],[Bl;p.287]).

Proposition 5.6. The C^{∗}-algebra O_{𝔏} is nuclear and satisfies the Universal Coefficient Theorem in the sense of Rosenberg and Schochet [RS] (also [Bro2]).

Hence, for an aperiodic λ-graph system 𝔏, O_{𝔏} is a unital, separable, nuclear, purely infinite, simple C^{∗}-algebra satisfying the UCT so that it lives in a classifiable class of nuclear C^{∗}-algebras by Kirchberg [Kir] and Phillips [Ph]. As the K-groups K_{0}(O_{𝔏}), K_{1}(O_{𝔏}) are countable abelian groups with K_{1}(O_{𝔏}) torsion free by Theorem 5.5, Rørdam’s result [Rø;Proposition 6.7] says the following:

Corollary 5.7. For an aperiodic λ-graph system 𝔏, the C^{∗}-algebra O_{𝔏} is isomorphic to the C^{∗}-algebra of an inductive limit of a sequence B_{1} → B_{2} → B_{3} → ⋯ of simple Cuntz-Krieger algebras.

Set the Ext-groups

Ext^{1}(O_{𝔏}) = Ext(O_{𝔏}), Ext^{0}(O_{𝔏}) = Ext(O_{𝔏} ⊗ C_{0}(ℝ)).

As the UCT holds for our algebras as in the lemma below, it is now easy to compute the Ext-groups by using Theorem 5.5.

Lemma 5.8([RS],[Bro2]). There exist short exact sequences

0 ⟶ Ext_{ℤ}^{1}(K_{0}(O_{𝔏}), ℤ) ⟶ Ext^{1}(O_{𝔏}) ⟶ Hom_{ℤ}(K_{1}(O_{𝔏}), ℤ) ⟶ 0,
0 ⟶ Ext_{ℤ}^{1}(K_{1}(O_{𝔏}), ℤ) ⟶ Ext^{0}(O_{𝔏}) ⟶ Hom_{ℤ}(K_{0}(O_{𝔏}), ℤ) ⟶ 0

that split unnaturally.

We denote by ℤ_{I} the abelian group defined by the projective limit \underleftarrow{lim}_{l}\{I_{l,l+1} :

ℤ^{m(l+1)} → ℤ^{m(l)}}. The sequence A_{l,l+1}, l ∈ ℤ_{+} naturally acts on ℤ_{I} as an endomorphism that we denote by A. The identity on ℤ_{I} is denoted by I. Then the cokernel and the kernel of the endomorphism I − A on ℤ_{I} are the Bowen-Franks groups BF^{0}(A, I) and BF^{1}(A, I) for (A, I) respectively ([Ma5]). By [Ma5;Theorem 9.6], there exists a short exact sequence

0 ⟶ Ext_{ℤ}^{1}(K_{0}(A, I), ℤ) ⟶ BF^{0}(A, I) ⟶ Hom_{ℤ}(K_{1}(A, I), ℤ) ⟶ 0

that splits unnaturally. And also

BF^{1}(A, I) ≅ Hom_{ℤ}(K_{0}(A, I), ℤ).

As in the proof of [Ma5;Lemma 9.7], we see that Ext_{ℤ}^{1}(ℤ_{I^{t}}, ℤ) = 0 so that Ext_{ℤ}^{1}(Ker(id − λ_{(A,I)}) in ℤ_{I^{t}}, ℤ) = 0. This means that Ext_{ℤ}^{1}(K_{1}(A, I)), ℤ) = 0. Theorem 5.5 says that K_{i}(A, I) ≅ K_{i}(O_{𝔏}) so that we conclude by Lemma 5.8,

Theorem 5.9.

(i) Ext(O_{𝔏}) = Ext^{1}(O_{𝔏}) ≅ BF^{0}(A, I) = ℤ_{I}/(I − A)ℤ_{I}, (ii) Ext^{0}(O_{𝔏}) ≅ BF^{1}(A, I) = Ker(I − A) in ℤ_{I}.

Theorem 5.9 is a generalization of [CK;5.3 Theorem] and [Ma6].

6. Realizations as endomorphism crossed products and Hilbert C^{∗}-bimodule algebras

Following Deaconu’s discussions in [De2],[De3],[De4], we will realize the algebra O_{𝔏} as an endomorphism crossed product F_{𝔏} ×_{β_{𝔏}} ℕ. Recall that the algebra F_{𝔏} is isomorphic to the C^{∗}-algebra C^{∗}(F_{𝔏}) of the groupoid F_{𝔏}. The groupoid F_{𝔏} is written as

{(x, y) ∈ X_{𝔏} × X_{𝔏} | σ^{k}(x) = σ^{k}(y) for some k ∈ ℤ_{+}}.

Put

β_{𝔏}(f)(x, y) = \frac{1}{\sqrt{p(σ(x))p(σ(y))}}f(σ(x), σ(y)), f ∈ C_{c}(F_{𝔏}), x, y ∈ X_{𝔏}

where p(x) is the number of the paths z such that σ(z) = x, and for (x, n, y) ∈ G_{𝔏}

v(x, n, y) = \{ \begin{matrix}\frac{1}{\sqrt{p(σ(x))}}, & if n = 1 and y = σ(x), \\ 0 & otherwise. \end{matrix}

Regarding C^{∗}(F_{𝔏}) as a subalgebra of C^{∗}(G_{𝔏}), one sees that v is a nonunitary isometry satisfying β_{𝔏}(f) = vfv^{∗} ([De2],[De3],[De4]). Then β_{𝔏} is a proper corner endomorphism of C^{∗}(F_{𝔏}) such that C^{∗}(G_{𝔏}) is isomorphic to the crossed product C^{∗}(F_{𝔏}) ×_{β_{𝔏}} ℕ (cf.[Rø2]). We will write the isometry v in terms of the generators S_{α}, E_{i}^{l}. For l ∈ ℕ, i = 1, …, m(l), we denote by n_{i}^{l} the number of the edges e in E_{l−1,l} such that t(e) = 𝔳_{i}^{l}. As 𝔏 is left-resolving, it is the number of the symbols α ∈ Σ such that S_{α}^{∗}S_{α}E_{i}^{l} ≠ 0. It follows that n_{i}^{l}E_{i}^{l} = ∑_{α∈Σ} S_{α}^{∗}S_{α}E_{i}^{l}. Note that if I_{l,l+1}(i, j) = 1, then n_{i}^{l} = n_{j}^{l+1}. Then one obtains

(6.1)  v = ∑_{i=1}^{m(l)} \frac{1}{\sqrt{n_{i}^{l}}} ∑_{α∈Σ} S_{α}E_{i}^{l}

where the right-hand side does not depend on the choice of l ∈ ℕ. We can immediately see that O_{𝔏} is generated by the C^{∗}-algebra F_{𝔏} and the above isometry v, that satisfies

(6.2)  v^{∗}v = 1, vF_{𝔏}v^{∗} ⊂ F_{𝔏}, v^{∗}F_{𝔏}v ⊂ F_{𝔏}.

The universality (Theorem 3.6) of the algebra O_{𝔏} corresponds to the universality of the crossed product C^{∗}(F_{𝔏})×_{β_{𝔏}}ℕ. It needs however a slightly complicated argument to directly determine the operator relations (𝔏) by using (6.1) and (6.2), as it is possible. There are some merits to realize O_{𝔏} as F_{𝔏} ×_{β_{𝔏}} ℕ. One is the fact that its purely infiniteness is immediately deduced from Rørdam’s result [Rø2;Theorem 3.1] under the condition that F_{𝔏} is simple. The other one is K-theory formulae. Rørdam also in [Rø2; Corollary 2.2] showed that

(i) K_{0}(F_{𝔏} ×_{β_{𝔏}} ℕ) ≅ K_{0}(F_{𝔏})/(id − β_{𝔏}_{∗})K_{0}(F_{𝔏}).

(ii) K_{1}(F_{𝔏} ×_{β_{𝔏}} ℕ) ≅ Ker(id − β_{𝔏}_{∗}) on K_{0}(F_{𝔏})

(cf.Paschke [Pa], Deaconu [De3]). These are precisely the formulae of Lemma 5.4 with Lemma 5.2.

In [De3; Section 3], Deaconu showed that the groupoid C^{∗}-algebras of continuous graphs are realized as C^{∗}-algebras constructed from Hilbert C^{∗}-bimodules defined in [Pi] (see also [Kat]). A special case of continuous graphs was studied in Kajiwara-Watatani [KW]. We identify the algebra C(Ω_{𝔏}) of all continuous functions on Ω_{𝔏} with the commutative C^{∗}-algebra A_{𝔏}. Let X_{A_{𝔏}} be the set C(E_{𝔏}) of all continuous functions on E_{𝔏}, that is identified with ∑_{α∈Σ}^{⊕} ℂS_{α}A_{𝔏}, because 𝔏 is left-resolving. We endow X_{A_{𝔏}} with a Hilbert C^{∗}-bimodule structure over A_{𝔏} defined by

(S_{α}a) · b = S_{α} · ab,  < S_{α}a, S_{β}b >_{A_{𝔏}}= a^{∗}S_{α}^{∗}S_{β}b,
ϕ_{𝔏}(b)S_{α}a = bS_{α}a = S_{α} · S_{α}^{∗}bS_{α}a

for a, b ∈ A_{𝔏}, α, β ∈ Σ. A special case of this construction of the Hilbert C^{∗}-bimodules is seen in the proof of [PWY;Theorem 4.2] for the C^{∗}-algebras associated with subshifts. The above mentioned Deaconu’s result says the following proposition:

Proposition 6.1. The C^{∗}-algebra constructed from the Hilbert C^{∗}-bimodule (ϕ_{𝔏}, X_{A_{𝔏}}) over A_{𝔏} is isomorphic to the C^{∗}-algebra O_{𝔏}.

7. Examples

In this section, we give two kinds of examples of λ-graph systems and study their associated C^{∗}-algebras. The first ones appear as presentations of sofic shifts. The second one is defined by a Shannon graph with countable infinite vertices.

Presentations of sofic shifts come from labeled graphs with finite vertices that are called λ-graphs (cf. [Fi],[Kr4],[Kr5],[LM],[We], …). Let G = (V, E) be a finite directed graph with finite vertex set V and finite edge set E. Let G = (G, λ) be a labeled graph over Σ defined by G and a labeling map λ : E → Σ. Suppose that it is left-resolving and predecessor-separated. Let A_{G} be the adjacency matrix of G, that is defined by

A_{G}(e, f) = \{ \begin{matrix}1 & if t(e) = s(e), \\ 0 & otherwise \end{matrix}

for e, f ∈ E. The matrix A_{G} defines a shift of finite type by regarding its edges as its alphabet. Since the matrix A_{G} is of entries in {0, 1}, we have the Cuntz-Krieger algebra O_{A_{G}} defined by A_{G} ([CK] cf.[KPPR],[Rø]). By putting V_{l}^{G} = V, E_{l,l+1}^{G} = E for l ∈ ℤ_{+}, and λ^{G} = λ, ι^{G} = id, we have a λ-graph system 𝔏_{G} = (V^{G}, E^{G}, λ^{G}, ι^{G}). Then we have Proposition 7.1. The C^{∗}-algebra O_{𝔏_{G}} is isomorphic to the Cuntz-Krieger algebra O_{A_{G}}.

Proof. Let V = {v_{1}, …, v_{m}} be the vertex set of G. Let S_{α}, α ∈ Σ be the canonical generating partial isometries of O_{𝔏_{G}}. We denote by E_{1}, E_{2}, …, E_{m} the set of all minimal projections of A_{l} = A_{𝔏_{G}}, l ∈ ℕ corresponding to the vertices v_{1}, …, v_{m}. As the labeled graph G is predecessor-separated, they are written in terms of S_{α}, α ∈ Σ as in (1.7). Note that in the algebra O_{𝔏_{G}}, S_{α}E_{i} ≠ 0 if and only if there exists an edge e ∈ E satisfying λ(e) = α and t(e) = v_{i}. As G is left-resolving, the correspondence

e ∈ E ⟷ (λ(e), t(e)) ∈ {(α, v_{i}) ∈ Σ × V | S_{α}E_{i} ≠ 0}

is bijective. For e ∈ E, put s_{e} = S_{λ(e)}E_{t(e)} ∈ O_{𝔏_{G}}, where E_{v_{i}} denotes E_{i}. As

E_{t(e)} = s_{e}^{∗}s_{e} for e ∈ E and S_{α} = ∑\begin{matrix}e∈E, \\ λ(e)=α \end{matrix} s_{e} for α ∈ Σ, the algebra O_{𝔏_{G}} is

generated by the partial isometries s_{e}, e ∈ E. It is immediate to see that the following relations hold:

∑_{e∈E} s_{e}s_{e}^{∗} = 1, s_{e}^{∗}s_{e} = ∑_{f∈E} A_{G}(e, f)s_{f}s_{f}^{∗}.

This means that the C^{∗}-algebra generated by s_{e}, e ∈ E is the Cuntz-Krieger algebra O_{A_{G}} defined by the matrix A_{G}. □

If, in particular, a labeled graph G = (G, λ) has different labels for different edges, it defines a shift of finite type. In this case, one may identify the edge set E with the alphabet Σ. Let 𝔏_{G} be the λ-graph system 𝔏_{G} as in the above one. Let S_{α}, α ∈ Σ be the generating partial isometries of O_{𝔏_{G}}. It is obvious that the relations (1.4),(1.5) and (1.6) give rise to the following relations:

S_{α}^{∗}S_{α} = ∑_{β∈E} A_{G}(α, β)S_{β}S_{β}^{∗}, α ∈ Σ.

Remark. While completing this paper, Toke M. Carlsen let the author know his preprint [Ca], where he shows that the C^{∗}-algebra associated with sofic shifts are isomorphic to the Cuntz-Krieger algebras of their left Krieger cover graphs. His result is a special case of the above proposition.

We will next present a λ-graph system for which the associated C^{∗}-algebra is not stably isomorphic to any Cuntz-Krieger algebra and any Cuntz algebra. There is a method introduced in [KM] to construct λ-graph systems from Shannon graphs. By a Shannon graph we mean here a left-resolving labeled directed graph with countable vertices and finite labels. Let us consider a Shannon graph defined as follows: Let V = {v_{1}, v_{2}, …, } be its countable infinite vertex set. Its alphabet Σ consist of the five symbols {α, β, γ, δ, ϵ}. The edges labeled α are from v_{n+1} to v_{n} for n = 1, 2, …. The edges labeled β are from v_{1} to v_{2} and from v_{2n} to v_{2n+2} for n = 1, 2, …. The edges labeled γ are self-loops at v_{n} for n = 2, 3, …. The edge labeled δ is a self-loop at v_{1}. The edges labeled ϵ are from v_{1} to v_{n} for n = 1, 2, …. The resulting labeled graph is left-resolving and hence it is a Shannon graph. We denote it by S. We will construct a λ-graph system 𝔏(S) from the Shannon graph S by a method introduced in [KM] as in the following way. For a vertex v ∈ V and for l ∈ ℕ, let Γ_{l}^{−}(v) be the set of all label sequences of length l terminating at v. Define an equivalence relation v ≈_{(l)} v′ for vertices v, v′ ∈ V by Γ_{l}^{−}(v) = Γ_{l}^{−}(v′). For l = 0, define v ≈_{(l)} v′ for all v, v′ ∈ V. The vertex set V_{l} is then defined by the set of ≈_{(l)}-equivalence classes of V. We denote by V_{l} = {𝔳_{1}^{l}, …, 𝔳_{m(l)}^{l}}. The vertices 𝔳_{i}^{l}, i = 1, …, m(l) of V_{l} may be identified with {Γ_{l}^{−}(v) : v ∈ V }. We define a map ι_{l,l+1} : V_{l+1} → V_{l} by ι_{l,l+1}(𝔳_{j}^{l+1}) = 𝔳_{i}^{l} if 𝔳_{j}^{l+1} ⊂ 𝔳_{i}^{l}. We define an edge labeled ω ∈ Σ from 𝔳_{i}^{l} to 𝔳_{j}^{l+1} if there exists an edge labeled ω in S from a vertex in 𝔳_{i}^{l} to a vertex in 𝔳_{j}^{l+1}. Then the resulting labeled graph with vertex sets V_{l}, labeled edges from V_{l} to V_{l+1} and surjective maps ι_{l,l+1} : V_{l+1} → V_{l} for l ∈ ℤ_{+} defines a λ-graph system over Σ ([KM]). We denote it by 𝔏(S). The vertex sets V_{l}, l ∈ ℤ_{+} are written as in the following way:

V_{0} : 𝔳_{1}^{0} = {v_{n} | n = 1, 2, … }.
V_{1} : 𝔳_{1}^{1} = {v_{1}}, 𝔳_{2}^{1} = {v_{2n} | n = 1, 2, … }, 𝔳_{3}^{1} = {v_{2n+1} | n = 1, 2, … }.
V_{2} : 𝔳_{1}^{2} = {v_{1}}, 𝔳_{2}^{2} = {v_{2}}, 𝔳_{3}^{2} = {v_{2n} | n = 2, 3, … },
𝔳_{4}^{2} = {v_{2n+1} | n = 1, 2, … }.
V_{3} : 𝔳_{1}^{3} = {v_{1}}, 𝔳_{2}^{3} = {v_{2}}, 𝔳_{3}^{3} = {v_{4}}, 𝔳_{4}^{3} = {v_{2n} | n = 3, 4, … },
𝔳_{5}^{3} = {v_{2n+1} | n = 1, 2, … }.
V_{4} : 𝔳_{1}^{4} = {v_{1}}, 𝔳_{2}^{4} = {v_{2}}, 𝔳_{3}^{4} = {v_{4}}, 𝔳_{4}^{4} = {v_{6}}, 𝔳_{5}^{4} = {v_{2n} | n = 4, 5, … },
𝔳_{6}^{4} = {v_{3}}, 𝔳_{7}^{4} = {v_{2n+1} | n = 2, 3, … }.
V_{5} : 𝔳_{1}^{5} = {v_{1}}, 𝔳_{2}^{5} = {v_{2}}, 𝔳_{3}^{5} = {v_{4}}, 𝔳_{4}^{5} = {v_{6}}, 𝔳_{5}^{5} = {v_{8}},
𝔳_{6}^{5} = {v_{2n} | n = 5, 6, … }, 𝔳_{7}^{5} = {v_{3}}, 𝔳_{8}^{5} = {v_{5}},
𝔳_{9}^{5} = {v_{2n+1} | n = 3, 4, … }.
V_{6} : 𝔳_{1}^{6} = {v_{1}}, 𝔳_{2}^{6} = {v_{2}}, 𝔳_{3}^{6} = {v_{4}}, 𝔳_{4}^{6} = {v_{6}}, 𝔳_{5}^{6} = {v_{8}}, 𝔳_{6}^{6} = {v_{10}},
𝔳_{7}^{6} = {v_{2n} | n = 6, 7, … }, 𝔳_{8}^{6} = {v_{3}}, 𝔳_{9}^{6} = {v_{5}}, 𝔳_{10}^{6} = {v_{7}},
𝔳_{11}^{6} = {v_{2n+1} | n = 4, 5, … }.
V_{7} : 𝔳_{1}^{7} = {v_{1}}, 𝔳_{2}^{7} = {v_{2}}, 𝔳_{3}^{7} = {v_{4}}, 𝔳_{4}^{7} = {v_{6}}, 𝔳_{5}^{7} = {v_{8}}, 𝔳_{6}^{7} = {v_{10}},
𝔳_{7}^{7} = {v_{12}}, 𝔳_{8}^{7} = {v_{2n} | n = 7, 8, … }, 𝔳_{9}^{7} = {v_{3}}, 𝔳_{10}^{7} = {v_{5}}, 𝔳_{11}^{7} = {v_{7}},
𝔳_{12}^{7} = {v_{9}}, 𝔳_{13}^{7} = {v_{2n+1} | n = 5, 6, … }.
· · · · · · · · · .

Lemma 7.2. The λ-graph system 𝔏(S) is aperiodic.

Proof. Take and fix an arbitrary vertex 𝔳_{i}^{l} ∈ V_{l}, let k be the minimum number such that v_{k} ∈ 𝔳_{i}^{l}. There exists a path of length k in 𝔏(S) that starts at 𝔳_{i}^{l} and ends at 𝔳_{1}^{l+k} = {v_{1}} ∈ V_{l+k} whose label is (α, α, …, α). There exist edges from 𝔳_{1}^{l+k} to 𝔳_{j}^{l+k+1} for all j = 1, 2, …, m(l + 1) whose labels are ϵ. This means that 𝔏(S) is aperiodic. □

Therefore the associated C^{∗}-algebra O_{𝔏(S)} is simple and purely infinite.

Let us compute its K-groups. We first present the matrices A_{l,l+1}^{t} and I_{l,l+1}^{t} for all l ≥ 5. As in the preceding table, we see that m(l) = 2l − 1 for l ≥ 5. We write the matrices along the ordered basis 𝔳_{1}^{l}, 𝔳_{2}^{l}, …, 𝔳_{m(l)}^{l}, where blanks denote zeros. For l = 5, we have

A_{5,6}^{t} =[ \begin{matrix}2 & 1 \\ 2 & 1 & 1 \\ 1 & & 1 & 1 \\ 1 & 1 & & 1 & 1 \\ 1 & & & & 1 & 1 \\ 1 & & & 1 & & 1 & & 1 \\ 1 & & & & & & 1 & 1 \\ 1 & & & & & 1 & 1 & 1 \\ 1 & & & & & & 1 & 1 & 1 \\ 1 & & & & & & & 1 & 1 \\ 1 & & & & & & & 1 & 2 \end{matrix} ], I_{5,6}^{t} =[ \begin{matrix}1 \\ & 1 \\ & & 1 \\ & & & 1 \\ & & & & 1 \\ & & & & & 1 \\ & & & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & & 1 \\ & & & & & & & 1 \\ & & & & & & & & 1 \end{matrix} ],

so that

A_{5,6}^{t} − I_{5,6}^{t} = [ \begin{matrix}1 & 1 \\ 2 & & 1 \\ 1 & & & 1 \\ 1 & 1 & & & 1 \\ 1 & & & & & 1 \\ 1 & & & 1 & & & & 1 \\ 1 & & & & & & 1 \\ 1 & & & & & 1 & & 1 \\ 1 & & & & & & 1 & 1 \\ 1 & & & & & & & & 1 \\ 1 & & & & & & & 1 & 1 \end{matrix} ] .

For general l ≥ 5, we see

A_{l,l+1}^{t} = [ \begin{matrix}2 & 1 \\ 2 & 1 & 1 \\ 1 & & 1 & 1 \\ 1 & 1 & & 1 & 1 \\ 1 & & & & 1 & 1 \\ 1 & & & 1 & & 1 & 1 \\ 1 & & & & & & 1 & 1 \\ 1 & & & & & 1 & & 1 & 1 \\ ⋮ & & & & & & & & ... & ... \\ ⋮ & & & & & & & ... & & ... & ... \\ 1 & & & & & & & & & & 1 & 1 \\ 1 & & & & & & & & & 1 & & 1 & & 1 \\ 1 & & & & & & & & & & & & 1 & 1 \\ 1 & & & & & & & & & & & 1 & 1 & 1 \\ 1 & & & & & & & & & & & & 1 & 1 & 1 \\ 1 & & & & & & & & & & & & & 1 & 1 \\ 1 & & & & & & & & & & & & & 1 & 2 \end{matrix} ] ,

I_{l,l+1}^{t} = [ \begin{matrix}1 \\ & 1 \\ & & 1 \\ & & & 1 \\ & & & & 1 \\ & & & & & 1 \\ & & & & & & 1 \\ & & & & & & & 1 \\ & & & & & & & & . & . & . \\ & & & & & & & & & & & . & . & . \\ & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & 1 \\ & & & & & & & & & & & & & & & & & & 1 \end{matrix} ] ,

C^{∗}-Algebras Associatedwith Presentations of Subshifts 25 and hence

A_{l,l+1}^{t} − I_{l,l+1}^{t} = [ \begin{matrix}1 & 1 \\ 2 & & 1 \\ 1 & & & 1 \\ 1 & 1 & & & 1 \\ 1 & & & & & 1 \\ 1 & & & 1 & & & 1 \\ 1 & & & & & & & 1 \\ 1 & & & & & 1 & & & 1 \\ ⋮ & & & & & & & & & ... \\ ⋮ & & & & & & & ... & & & ... \\ 1 & & & & & & & & & & & 1 \\ 1 & & & & & & & & & 1 & & & & 1 \\ 1 & & & & & & & & & & & & 1 \\ 1 & & & & & & & & & & & 1 & & 1 \\ 1 & & & & & & & & & & & & 1 & 1 \\ 1 & & & & & & & & & & & & & & 1 \\ 1 & & & & & & & & & & & & & 1 & 1 \end{matrix} ] .

Lemma 7.3. For l ≥ 4 and z = [ z_{1} ; ⋮ ; z_{2l+1} ] ∈ ℤ^{2l+1}, put

φ_{l}([z_{i}]_{i=1}^{2l+1}) = z_{2l−7} − z_{2l−5} − z_{2l−4} + z_{2l−2},
ψ_{l}([z_{i}]_{i=1}^{2l+1}) = z_{2l−7} − z_{2l−4} − z_{2l−3} + z_{2l−1},
ξ_{l}([z_{i}]_{i=1}^{2l+1}) = z_{2l−7} − z_{2l−4} − z_{2l} + z_{2l+1}.

Then there exists x = [ x_{1} ; ⋮ ; x_{2l−1} ] ∈ ℤ^{2l−1} such that

[ z_{1} ; ⋮ ; z_{2l−1} ; z_{2l} ; z_{2l+1} ] = (A_{l,l+1}^{t} − I_{l,l+1}^{t}) [ x_{1} ; ⋮ ; x_{2l−1} ] + [ 0 ; ⋮ ; 0 ; φ_{l}(z) ; ψ_{l}(z) ; 0 ; ξ_{l}(z) ] .

Lemma 7.4. The map z = [z_{i}]_{i=1}^{2l+1} ∈ ℤ^{2l+1} → (φ_{l}(z), ψ_{l}(z), ξ_{l}(z)) ∈ ℤ^{3} induces an isomorphism from ℤ^{2l+1}/(A_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2l−1} onto ℤ^{3}.

Documenta Mathematica 7 (2002) 1–30

Proof. It suffices to show the surjectivity of the induced map z = [z_{i}]_{i=1}^{2l+1} ∈ ℤ^{2l+1}/(A_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2l−1} ⟶ (φ_{l}(z), ψ_{l}(z), ξ_{l}(z)) ∈ ℤ^{3}.

For (m, n, k) ∈ ℤ ⊕ ℤ ⊕ ℤ, put z = [z_{i}]_{i=1}^{2l+1} where

z_{i} = \{ \begin{matrix}0 & for i = 1, 2, …, 2l − 3, 2l, \\ m & for i = 2l − 2, \\ n & for i = 2l − 1, \\ k & for i = 2l + 1. \end{matrix}

Then we see that φ_{l}(z) = m, ψ_{l}(z) = n, ξ_{l}(z) = k. □ We denote by ρ_{l+1} the above isomorphism from ℤ^{2l+1}/(A_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2l−1}

onto ℤ^{3}. Let L be the matrix [ \begin{matrix}−1 & 1 & 0 \\ −1 & 0 & 1 \\ −1 & 0 & 1 \end{matrix} ] . Since the following diagram is

commutative:

ℤ^{2l−1}/(A_{l−1,l}^{t} − I_{l−1,l}^{t})ℤ^{2l−3} ⟶^{I_{l,l+1}^{t}} ℤ^{2l+1}/(A_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2l−1}
ρ_{l}↓  ^{ρ_{l+1}}↓
ℤ^{3} ⟶^{L} ℤ^{3},

we obtain Proposition 7.5. K_{0}(O_{𝔏(S)}) ≅ 0. Proof. As L^{3} = 0, by Theorem 5.5, it follows that

K_{0}(O_{𝔏(S)}) = \underrightarrow{lim}\{ℤ^{2l+1}/(A_{l,l+1}^{t} − I_{l,l+1}^{t})ℤ^{2l−1}, Ī_{l+1,l+2}^{t}\} = \underrightarrow{lim}\{ℤ^{3}, L\} ≅ 0. □

Concerning the group K_{1}(O_{𝔏(S)}), one sees Proposition 7.6. K_{1}(O_{𝔏(S)}) ≅ ℤ. Proof. For l ≥ 5, put x(l) = [x_{i}]_{i=1}^{2l−1} ∈ ℤ^{2l−1} where

x_{1} = 1, x_{2} = −1, x_{3} = −2,
x_{i} = −1 for i = 4, 6, 8, …, 2l − 4, 2l − 3, 2l − 1,
x_{i} = 0 for i = 5, 7, 9, …, 2l − 5, 2l − 2.

It is easy to see that

Ker(A_{l,l+1}^{t} − I_{l,l+1}^{t}) = ℤx(l), I_{l,l+1}^{t}x(l) = x(l + 1).

Hence we obtain K_{1}(O_{𝔏(S)}) ≅ ℤ by Theorem 5.5. □ Therefore we conclude

Documenta Mathematica 7 (2002) 1–30

Theorem 7.7. The C^{∗}-algebra O_{𝔏(S)} is unital, simple, purely infinite, nuclear and generated by five partial isometries with mutually orthogonal ranges. Its K-groups are

K_{0}(O_{𝔏(S)}) ≅ 0, K_{1}(O_{𝔏(S)}) ≅ ℤ.

As the K_{1}-group of a Cuntz-Krieger algebra is the torsion-free part of its K_{0}- group, the algebra O_{𝔏(S)} lives outside the Cuntz-Krieger algebras (cf.[Ma3]).

Remark. M. Tomforde in [T] considered C^{∗}-algebras associated to labeled graphs as a generalization of Cuntz-Krieger algebras (cf.[T2]). He deals with labeled directed graphs with (generally) infinite vertices. If the labeled graphs have finite vertices, the resulting graphs are ones in the first examples of this section. In this case, his C^{∗}-algebras coincide with our C^{∗}-algebras. The referee informed to the author that his algebras in general are not ours of λ-graph systems.

References

[An] C. Anantharaman-Delaroche, Purely infinite C^{∗}-algebras arising from dynamical systems, Bull. Soc. Math. France 125(2) (1997), 199–225.

[Bl] B. Blackadar, K-Theory for operator algebras, Springer-Verlag, Berlin, Heidelberg and New York, 1986.

[Bra] O. Bratteli, Inductive limits of finite-dimensional C^{∗}-algebras, Trans. Amer. Math. Soc. 171 (1972), 195–234.

[Bro] L. G. Brown, Stable isomorphism of hereditary subalgebras of C^{∗}- algebras, Pacific. J. Math. 71 (1977), 335–348.

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

[Ca] T. M. Carlsen, On C^{∗}-algebras associated with sofic shifts, preprint 2000.

[CaM] T. M. Carlsen and K. Matsumoto, Some remarks on the C^{∗}-algebras associated with subshifts, preprint 2001.

[C] J. Cuntz, Simple C^{∗}-algebras generated by isometries, Commun. Math. Phys. 57 (1977), 173–185.

[C2] J. Cuntz, K-Theory for certain C^{∗}-algebras, Ann. Math. 113 (1981), 181–197.

[C3] J. Cuntz, A class of C^{∗}-algebras and topological Markov chains II: reducible chains and the Ext-functor for C^{∗}-algebras, Invent. Math. 63 (1980), 25–40.

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

[De] V. Deaconu, Groupoids associated with endomorphisms, Trans. Amer. Math. Soc. 347 (1995), 1779–1786.

[De2] V. Deaconu, Generalized Cuntz-Krieger algebras, Proc. Amer. Math. Soc. 124 (1996), 3427–3435.

[De3] V. Deaconu, Generalized solenoids and C^{∗}-algebras, Pacific J. Math. 190 (1999), 247–260.

[De4] V. Deaconu, Continuous graphs and C^{∗}-algebras, Operator Theoretical Methods (Timiç soara, 1998) Theta Found., Bucharest (2000), 137–149.

[EL] R. Excel and M. Laca, Cuntz-Krieger algebras for infinite matrices, J. reine. angew. Math. 512 (1999), 119–172.

[Fi] R. Fischer, Sofic systems and graphs, Monats. für Math. 80 (1975), 179–186.

[H] D. Huang, Flow equivalence of reducible shifts of finite type and Cuntz-Krieger algebras, J. reine angew. Math. 462 (1995), 185–217.

[KPW] T. Kajiwara, C. Pinzari and Y. Watatani, Ideal structure and simplicity of the C^{∗}-algebras generated by Hilbert modules, J. Funct. Anal. 159 (1998), 295–322.

[KPW2] T. Kajiwara, C. Pinzari and Y. Watatani, Hilbert C^{∗}-bimodules and countably generated Cuntz-Krieger algebras, J. Operator Theory 45 (2001), 3–18.

[KW] T. Kajiwara and Y. Watatani, Hilbert C^{∗}-bimodules and continuous Cuntz-Krieger algebras considered by Deaconu, J. Math. Soc. Japan 54 (2002), 35–60.

[Kat] Y. Katayama, Generalized Cuntz algebras O_{N}^{M}, RIMS kokyuroku 858 (1994), 87–90.

[Kir] E. Kirchberg, The classification of purely infinite C^{∗}-algebras using Kasparov’s theory, preprint,1994.

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

[Kr] W. Krieger, On dimension functions and topological Markov chains, Invent. Math. 56 (1980), 239–250.

[Kr2] W. Krieger, On dimension for a class of homeomorphism groups, Math. Ann 252 (1980), 87–95.

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

[Kr4] W. Krieger, On sofic systems II, Israel J. Math 60 (1987), 167–176.

[KM] W. Krieger and K. Matsumoto, Shannon graphs, subshifts and lambda-graph systems, to appear in J. Math. Soc. Japan.

[KPR] A. Kumjian, D. Pask and I. Raeburn, Cuntz-Krieger algebras of directed graphs, Pacific J. Math. 184 (1998), 161–174.

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

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

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

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

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

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

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

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

[Ma7] K. Matsumoto, C^{∗}-algebras associated with presentations of subshifts II. Ideal structure and lambda-graph subsystems, preprint, 2001.

[Pas] W. Paschke, The crossed product of a C^{∗}-algebra by an endomorphism, Proc. Amer. Math. Soc. 80 (1980), 113–118.

[Ph] N. C. Phillips, A classification theorem for nuclear purely infinite simple C^{∗}-algebras, Doc. Math. 5 (2000), 49–114.

[Pi] M. V. Pimsner, A class of C^{∗}-algebras, generalizing both Cuntz-Krieger algebras and crossed product by ℤ, in Free Probability Theory, Fields Institute Communications 12 (1996), 189–212.

[PV] M. Pimsner and D. Voiculescu, Exact sequences for K-groups and Ext-groups of certain cross-products C^{∗}-algebras, J. Operator Theory 4 (1980), 93–118.

[PWY] C. Pinzari, Y. Watatani and K. Yonetani, KMS states, entropy and the variational principle in full C^{∗}-dynamical systems, Commun. Math. Phys. 213 (2000), 331–381.

[Pu] I. Putnam, C^{∗}-algebras from Smale spaces, Canad. J. Math. 48 (1996), 175–195.

[Re] J. N. Renault, A groupoid approach to C^{∗}-algebras, Lecture Notes in Math. Springer 793 (1980).

[Ri] M. Rieffel, C^{∗}-algebras associated with irrational rotations, Pacific J. Math. 93 (1981), 415–429.

[Rø] M. Rørdam, Classification of Cuntz-Krieger algebras,, K-Theory 9

(1995), 31–58.

[Rø2] M. Rørdam, Classification of certain infinite simple C^{∗}-algebras,, J.

Funct. Anal. 131 (1995), 415–458.

[Ro] J. Rosenberg, Appendix to O. Bratteli’s paper “Crossed products of UHF algebras ”, Duke Math. J. 46 (1979), 25–26.

[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.

[T] M. Tomforde, C^{∗}-algebras of labeled graphs, preprint.

[T2] M. Tomforde, A unified approach to Exel-Laca algebras and C^{∗}- algebras associated to directed graphs, preprint.

[We] B. Weiss, Subshifts of finite type and sofic systems, Monats. Math. 77 (1973), 462–474.

Kengo Matsumoto Department of Mathematical Science Yokohama City University Sato 22-2, Kanazawa-ku, Yokohama 236-0027, Japan kengo@yokohama-cu.ac.jp