• A list of sections from Lind and Marcus which are testable exam material is below.
• I am available anytime Monday and Tuesday except 12-2 for appointments if you need any last-minute help.
• Solutions to Assignment 8 are posted below.
• Assignment 8 has been posted.
• Make a note of the errata list for the Lind and Marcus book, posted below!

Course meets every MW from 4:00 p.m. - 5:50 p.m. in John Greene Hall 219.

Instructor: Ronnie Pavlov
Office: John Greene Hall 304
e-mail: rpavlov@du.edu
Phone: (303)-871-4001
Office hours: Tuesday 1:00 p.m. - 3:00 p.m., Friday 11:00 a.m. - 12:00 p.m., or by appointment

Text: An Introduction to Symbolic Dynamics and Coding by Lind and Marcus.

IMPORTANT: This book does have some typos/errors. Click this link for the current list of errata, and please notify me if you find any new ones!

This book is available at the DU Bookstore.

Symbolic dynamics is the study of sets of sequences taken from a finite set (think zeroes and ones), and the dynamical properties of such a set when combined with the shift operation which moves a sequence one unit to its left. We will study various facets of symbolic dynamics, mostly concerning some simple classes of symbolic systems, namely shifts of finite type and sofic shifts.

We will focus mostly only Chapters 1-4 of the textbook, and some selected important results from later chapters. Topics will include various notions of isomorphism between symbolic systems, entropy theory, and connections to coding theory and information theory. If time permits, we will finish by discussing some topics in multidimensional symbolic dynamics (e.g. two-dimensional arrays of letters instead of sequences)

The prerequisites are basic linear algebra (MATH 2060 or equivalent) and a course in mathematical proof (MATH 2200 or equivalent). Knowledge of some point-set topology (e.g. definition of open/closed sets, compact space, metric space) is suggested.

Your term grade will consist of homework assignments (which will mostly be taken from the text), one midterm exam, and one final exam, broken down in the following way:

20% Homework
30% Midterm Exam
50% Final Exam

• Assignment 1: Exercises 1.2.4, 1.2.5, 1.2.12, 1.3.2, 1.3.8 from Lind and Marcus (due Wednesday, March 30th)
  Bonus challenge problem: 1.2.13
• Assignment 1 solutions
• Assignment 2: Exercises 1.5.3, 1.5.9, 1.5.10, 1.5.11, 1.5.16
• Assignment 2 solutions
• Assignment 3: Exercises 2.1.3, 2.1.5, 2.1.9, 2.2.3, 2.2.10
• Assignment 3 solutions
• Assignment 4: Exercises 2.2.12, 2.3.4, 2.4.7(b,d), 4.4.2(a)
• Assignment 4 solutions and associated figures
• Assignment 5: Exercises 3.1.1, 3.1.5, 3.2.3, 3.2.5(a), 3.2.7
• Assignment 5 solutions
• Assignment 6: Exercises 3.3.2(a,b), 3.3.3, 3.3.4, 3.3.8, 4.1.9
• Assignment 6 solutions
• Assignment 7: Exercises 4.1.5(c,d), 4.2.3, 4.3.1, 4.3.3(a,c,d), 4.3.7
• Assignment 7 solutions
• Assignment 8: Exercises 4.4.5, 4.5.3, 4.5.6, 4.5.7(1),(4), 4.5.16(a)
• Assignment 8 solutions
  Bonus challenge problem: 4.5.17 (This is a fun problem, and most of you should be able to come up with a guess as to the correct answer by playing around with examples. The proof is much more difficult, which is why this is only a bonus problem.)

You will have a midterm exam on Monday, May 2nd, and a final exam on May 31st. Both exams will be in our classroom during classtime (4:00 p.m. - 5:50 p.m.)

The exam will be over the following sections of the textbook: 1.1-1.5, 2.1-2.4, 3.1-3.3, 4.1-4.5. There were some topics that I covered slightly differently than the text, and places where I did not cover every result in a section; all problems on the exam should be doable using only concepts that I personally covered in class. For example, we didn't discuss several results from Chapter 4 about relationship of entropy to numbers of periodic points, so I wouldn't expect you to know these facts. None of the material on multidimensional symbolic systems will be on the exam.

Coming soon!