CHAPTER 8 - FINITE-TO-ONE CODES AND FINITE EQUIVALENCE

Summary

Recall from Chapter 6 that we regard two dynamical systems as being “the same” if they are conjugate and otherwise “different.” In Chapter 7 we concentrated on conjugacy for edge shifts, and found that two edge shifts are conjugate if and only if the adjacency matrices of their defining graphs are strong shift equivalent.

We also saw that it can be extremely difficult to decide whether two given matrices are strong shift equivalent. Thus it makes sense to ask if there are ways in which two shifts of finite type can be considered “nearly the same,” and which can be more easily decided. This chapter investigates one way called finite equivalence, for which entropy is a complete invariant. Another, stronger way, called almost conjugacy, is treated in the next chapter, where we show that entropy together with period form a complete set of invariants.

In §8.1 we introduce finite-to-one codes, which are codes used to describe “nearly the same.” Right-resolving codes are basic examples of finite-to-one codes, and in §8.2 we describe a matrix formulation for a 1-block code from one edge shift to another to be finite-to-one. In §8.3 we introduce the notion of finite equivalence between sofic shifts, and prove that entropy is a complete invariant. A stronger version of finite equivalence is discussed and characterized in §8.4.

Finite-to-One Codes

We begin this chapter by introducing finite-to-one sliding block codes.