Symbolic Dynamics and Linear Algebra

Lind & Marcus cover Kitchens cover Fogg cover

This is a course with few prerequisites aimed at people interested in:

how ideas from mathematics can be applied to problems in computer science and coding;
how models of data in computer science produce interesting mathematical problems;
how ideas from dynamical systems can be used to study the structure of 'symbolic' systems.

There are no formal prerequisites, but the basic material from the first year in MTH (elementary linear algebra, continuity) will be used. Most of the material will be developed from scratch.

The set book for the course is Symbolic Dynamics and Coding by Douglas Lind and Brian Marcus. (QA614.8 in the library). Other useful background texts are Symbolic Dynamics by Bruce Kitchens and Substitutions in Dynamics, Arithmetics and Combinatorics by N. Pytheas Fogg.

If you would like more details about this course, please either come and see Dr. Ward or e-mail t.ward@uea.ac.uk for more information.

2006-7 course materials on the web:

Coursework and Introduction

Summary of main theorems

Detailed description

1. Introduction: This course will introduce students to the language and methods of symbolic dynamics and coding theory. This is a rapidly growing area of dynamical systems and has many applications within mathematics and in computer science. Second year algebra is useful but not essential. The course relates to graph theory, computing, linear algebra, and dynamical systems.

2. Timetable Hours, Credits, Assessments: A 20 UCU course of 33 lectures, supported by seminars to be arranged informally. The overall mark comes from coursework (20%) and one three-hour examination (80%).

3. Overview: The first part of the course will describe shift spaces, languages and sliding block codes. We will go on to study shifts that are of finite type and shifts that are sofic. These may be described via graphs and their associated matrices. The basic idea of state splitting will be described, and applications to data storage and coding outlined.

The second part of the course will concentrate on sofic shifts and presentations for them.

The last part of the course will study symbolic systems as dynamical systems. The entropy and zeta function invariants will be introduced and computed. If time permits, some recent work on the conjugacy problem will be described.

4. Recommended Reading:

1) "An Introduction to Symbolic Dynamics and Coding", Douglas Lind & Brian Marcus, Cambridge Univ. Press (1995).

2) Papers (these will be made available to participants):

R. Adler, "The torus and the disk", IBM J. of Research and Development 31 (1987), 224-234.
B. Marcus, "The impact of Roy Adler's work on symbolic dynamics and applications to data storage", Contemp. Math. 135 (1992), 33-56.
M. Morse & G. Hedlund, "Symbolic dynamics", Amer. J. Math. 60 (1938), 815-866.

5. Lecture Contents (provisional):

Shift spaces: full shifts, shift spaces, languages, higher block shifts, sliding block codes, convolutional encoders. [6 lectures]

Shifts of finite type: finite constraints, graphs and their shifts, graph presentations, state splitting, data storage. [6 lectures]

Sofic shifts: presentations, characterization, minimal right-resolving presentation. [6 lectures]

Entropy and growth: basic properties, Perron-Frobenius theory, computing entropy. [6 lectures]

Dynamical systems: shifts as model dynamical systems, periodic points and zeta functions. [6 lectures]

Additional topic: chosen from road colourings, sliding block decoders, conjugacy problems. [3 lectures]

This page maintained by: t.ward@mth.uea.ac.uk