CYCLE OF SEMINARS
on

INTRODUCTION TO SYMBOLIC DYNAMICS

Speaker: Silvio Capobianco http://cs.ioc.ee/~silvio/

Motivation

The subject of symbolic dynamics originates from mathematical physics, as a way to study complex systems by reducing the number of states to finitely many. Today, with the developments in language theory and combinatorics on words, it is a precious tool in computer science, with applications to coding theory, image processing, and many more fields.

Subject

The cycle of seminars will cover the first five chapters of the textbook "An Introduction to Symbolic Dymanics and Coding" by Lind and Marcus. This includes:

• Subshifts and sliding block codes.
• Presentations of subshifts through graphs and matrices.
• Shifts of finite type.
• Sofic shifts.
• Entropy of a shift space.
• Perron-Frobenius theory for positive matrices.
• The finite-state coding theorem.

Prerequisites

Basic knowledge of linear algebra, graph theory, and automata theory should be sufficient.

Scheduling

Overall, from five to seven encounters should be considered. Frequency should be around one encounter every other week.

Slides

For slides in pdf format check http://www.cs.ioc.ee/~silvio/slides/

1. Wednesday, April 7, room B101, at 4 PM
   The talk shall be based on chapter 1 of Lind and Marcus' textbook (see slides).
   Topics covered: Introduction, Shift spaces, Basic constructions on shift spaces, Sliding block codes, A parallel with coding theory.
2. Wednesday, April 14, room B101, at 4 PM
   The talk shall be based on chapter 2 of Lind and Marcus' textbook (see slides).
   Topics covered: Shifts of finite type, Graphs and their shifts, Graphs as presentations of shifts, State splitting, An application to data recording.
3. Wednesday, April 28, room B101, at 4 PM (see slides).
   Topics covered: State splitting continues, sofic shifts presented by labeled graphs.
4. Wednesday, May 12, room B101, at 4 PM (see slides).
   Topics include: Constructions and algorithms on sofic shifts, entropy of a shift, Perron-Frobenius theory of nonnegative matrices.
5. Wednesday, May 19, room B101, at 4:15 PM (the last!)
   Topics include: Cyclic structure of irreducible matrices, the road problem, the finite-state coding theorem.