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.

**Course dates:**every Thursday, 16:00-18:00, SEM 185/2 (1040 Wien, Favoritenstraße 9/staircase 1/4th floor(3.Stock)/yellow area)**Registration:**via TUWIS++, or if this fails, by email to salzer@logic.at.

*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:

Find necessary and sufficient conditions for the existence of certain types of encodings from one dynamical system to another.

Characterise the properties of dynamical systems, like entropy or the number of periodical states.

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.

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.

salzer@logic.at