3.0/2.0 VU Symbolic Dynamics and Coding (185.336)

Given by: Gernot Salzer

Elective course (Wahllehrveranstaltung) in the master studies "Computational Intelligence" (066931) and "Software Engineering & Internet Computing" (066937).

The default language is German. However, if someone in the audience is not sufficiently fluent in German the course will be given in English.



Symbolic dynamics is a sub-area of dynamical systems, which initially was introduced to study general dynamical systems, but meanwhile found significant applications in data storage and transmission as well as linear algebra. In fact, hard disks, CDs, and DVDs rely on coding techniques developed (or justified) by methods from symbolic dynamics.

Traditionally, dynamical systems of, say, planets or gas molecules are modelled by differential equations. However, by discretising time as well as the states of a system (e.g., by dividing time into intervals and space into cells), the behaviour of a system can be described by an infinite sequence of symbols, where the symbols represent the states of the system and the sequence models the flow of time. This discrete view on systems helps to understand their quantitative as well as qualitative properties.

Another interesting application area of symbolic dynamics is data storage and transmission. E.g., for physical reasons any two "1"-bits on CDs and DVDs have to be separated by at least 2 and at most 10 "0"-bits. An important question now is how arbitrary data can be encoded efficiently such that it obeys this restriction. An important result of symbolic dynamics tells us under which conditions such encodings are possible and how they can be constructed.

Formally, symbolic dynamics deals with collections of infinite strings that are closed under the shift operation. For obvious reasons, such collections are called shift spaces or just shifts. Of particular importance are shifts of finite type, which can be characterised by a finite number of forbidden blocks, and sofic shifts, which can be defined by finite automatons. Symbolic dynamics investigates the properties and applications of such shifts.

This course addresses students of informatics, mathematics, and electrical engineering. It offers an introduction to the main ideas, methods, and problems of symbolic dynamics, with an emphasis on coding problems. In particular we will discuss the following two tasks:

Course dates

The course takes place every Thursday, 16:00-18:00, in the seminar room SEM 185/2 (1040 Wien, Favoritenstraße 9/staircase 1/4th floor(3.Stock)/yellow area).

Please register for the course via TUWIS++, or if this fails, via email to salzer@logic.at.

Course material

The course is based on the first six chapters of the book

Douglas Lind, Brian Marcus: An Introduction to Symbolic Dynamics and Coding.
Cambridge University Press, 1995.

For a detailed description of the book see www.math.washington.edu/SymbolicDynamics. Copies of the book are available in the math library (0400Fh / MAT:590 / 570078 I).

Some papers are available online. User name and password will be provided in the course.


The final grade will be based on the quality of the home works, the level of active participation in the course, and on the grade of the final written exam.

Valid XHTML 1.1! Viewable With Any Browser