A shift of finite type  is a topological dynamical system defined from a square nonnegative integral matrix A; it is the shift map on the space of infinite walks through a directed graph with adjacency matrix A. The shifts of finite type are the fundamental building blocks of symbolic dynamics, useful in a variety of contexts (ergodic theory, data storage and transmission, hyperbolic dynamics, matrix theory). We'll develop the standard theory, in particular the "strong shift equivalence" setup of Williams, which is fundamental (but not completely adequate) for the central problem of understanding when two shifts of finite type are isomorphic. Then we will move to more recent advances, of which the next paragraphs give a flavor.

Following the strong shift equivalence theory, for a semiring R (especially, R=Z or R=Z⁺ or R=Q) Wagoner defined an infinite simplicial complex with the following properties: a vertex is a matrix; an edge from a vertex A to vertex B is a pair (U,V) of matrices over R such that A=UV and B=VU. For R=Z⁺, vertices A and B define isomorphic shifts of finite type if and only if they are connected by a path in the complex. It turns out that understanding homotopy classes of paths in this complex is the key to the best results we have on that central problem of  classifying the shifts of finite type.  These results come out of relating the paths to (i) induced isomorphisms of associated dimension groups and (ii) the abelianized combinatorics of actions on periodic points.

"Positive K-theory" presents the shifts of finite type by infinite polynomial matrices I-tA. In this presentation, isomorphisms of shifts of finite type are induced by multiplications of I-tA by elementary polynomial matrices subject to a positivity condition. (So, an isomorphism class of shifts of finite type resembles an element of K₁(Z) -- hence Wagoner's nickname "positive K-theory". The relation to K-theory is more than superficial; Wagoner has applied nontrivial K-theory to the classification problem.) The polynomial matrix presentations have also been used outside the classification framework to solve significant problems.