INTRODUCTION xv

The subject of this memoir is developing into a long-term programme by the

authors, also in collaboration with Kim and Roush [13, 14, 15]. The results are of-

ten somewhat technical. The paper [92] provides a beautiful survey of the Williams

problem, its history, and its resolution. The subject of equivalences, strong, shift

equivalence, or weak equivalence, is situated neither directly in operator algebras,

nor perhaps precisely in dynamical systems or wavelet analysis, but rather inter-

mingles these, and more, areas of mathematics.

Let us now add more specific definitions and go into more details:

2. Three ways of measuring isomorphism. During the sixties and seven-

ties it was established that there is a one-to-one canonical correspondence between

the following three sets [6, 30, 32, 33, 34, 47]:

(i) the isomorphism classes of AF-algebras,

(ii) the isomorphism classes of certain ordered abelian groups, called dimen-

sion groups,

and finally

(iii) the equivalence classes of certain combinatorial objects, called Bratteli

diagrams.

In more recent times, this has led to an undercurrent of misunderstanding that

AF-algebras, which are complex objects, are classified by dimension groups, which

are easy objects, and that this is the end of the story. However, as anyone who has

worked with these matters knows, although for special subsets it may be easier to

work with one of the three sets mentioned above rather than another, in general the

computation of isomorphism classes in any of the three categories is equally difficult.

Although dimension groups are easy objects, their isomorphism classes in general

are not! One may even be tempted to flip the coin around and say that dimension

groups are classified by AF-algebras. If one thinks about isomorphism classes, this

is logically true, but the only completely general method to decide isomorphism

classes in all the cases is to resort to the computation of the equivalence relation

for the associated Bratteli diagrams. This problem is not only hard in general, it is

even undecidable: There is no general recursive algorithm to decide if two effective

presentations of Bratteli diagrams yield equivalent diagrams, see [67] and [66]. In

this memoir, we will encounter this problem in a very special situation, and try

to resolve it in a modest way by introducing various numerical invariants which

are easily computable from the diagram. In the situation that the AF-embeddings

are given by a constant primitive nonsingular matrix, the classification problem

has, after the writing of this monograph, been proved in general to be decidable

[13, 14, 15].

Recall that an AF-algebra is a separable C*-algebra with the property that for

any e 0, any finite subset of the algebra can be approximated with elements of

some finite-dimensional *-subalgebra with the precision given by e. An AF-algebra

is stable if it is isomorphic to its tensor product with the compact operators on a

separable Hilbert space. A dimension group is a countable abelian group with an

order satisfying the Riesz interpolation property and which is unperforated. The

Bratteli diagram is described in [6], [29], and [38], and the equivalence relation is

also described in detail in [7] and in Remark 5.6. (All these concepts will be treated

in some detail in Chapter 5, where it is also explained that the stability assumption