The Work of Kim and Roush in Symbolic Dynamics
- PDF / 457,635 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 180 Views
The Work of Kim and Roush in Symbolic Dynamics Mike Boyle
Received: 31 October 2012 / Accepted: 31 October 2012 / Published online: 5 March 2013 © Springer Science+Business Media Dordrecht 2013
Keywords Symbolic dynamics Mathematics Subject Classification (2010) Primary 37B10
1 Introduction About one fifth of the papers of Hang Kim were joint papers with Fred Roush addressing problems of symbolic dynamics. They were remarkable problem solvers who made huge contributions to the topic. This paper reviews those contributions, at the level of describing main results and giving some context. There isn’t room for the best part—the ideas behind the results—but I hope this survey is of some use for appreciating the contributions and knowing where to look to find more. The bibliography of references to their work lists papers in chronological order; the supplementary bibliography is ordered alphabetically by author. Many background definitions are omitted. Most basic background can be easily found in the very accessible book of Lind and Marcus [55]. I use the notation σA to represent a shift of finite type defined by a square nonnegative integral matrix A. For conciseness, I don’t try to reconcile notation or terminology with statements in the various papers. For exact statements one can consult the originals.
2 Decidability Results Shift Equivalence The first work of Kim and Roush for symbolic dynamics, begun in the 1979 paper [1] and completed in [3], was to prove that there is a decision procedure which takes two square matrices over Z+ and determines whether they are shift equivalent over Z+ . M. Boyle () Department of Mathematics, University of Maryland, College Park, MD 20742-4015, USA e-mail: [email protected]
18
M. Boyle
Williams [60] show that if A and B are shift equivalent over Z+ , then σA and σB are eventually conjugate (i.e., σAn and σBn are topologically conjugate for all but finitely many n). Kim and Roush proved the converse holds [1]. Shift equivalence is a very strong equivalence relation, and a very important one in the study of shifts of finite type. Stationary Dimension Groups and Modules This subsection gives some definitions to set notation used later. Suppose A is an n × n matrix over Z+ . We need to fix a convention of having A act on row vectors or column vectors; we choose rows. Then let GA denote the direct limit group defined from A by the action on Zn , A
A
A
GA = lim Zn = Zn −→ Zn −→ Zn −→ · · · . − → A
An element of the direct limit group is an equivalence class of elements {(v, k) : k ∈ Z+ , v ∈ Zn }, with equivalence classes generated by the relation (v, k) ∼ (vA, k + 1) for all v and k. So, [(v, k)] = [(w, j )] iff vAn+j = wAn+k for some (hence all large) n ≥ 0. The group GA becomes an ordered group (specifically, a stationary dimension group) by the m definition that the positive set G+ A is the set of [(v, k)] such that vA ≥ 0 for some m ≥ 0 (equivalently, the set [(v, k)] contains some (w, j ) such that w ≥ 0). The matrix A induces of this ordered group, defined by A : [(
Data Loading...
