IoC :: Seminars :: INTRODUCTION TO SYMBOLIC DYNAMICS

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/

**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.**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.**Wednesday, April 28, room B101, at 4 PM**(see slides).

Topics covered: State splitting*continues*, sofic shifts presented by labeled graphs.**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.**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.