VO Special Topics in Stochastics: Symbolic Dynamic (2019W.25050.1)

Lecturer: Prof. Henk Bruin

Email H. Bruin for further information for this course.

Announcements

Schedule

Contents of the course

This course is meant as introduction to symbolic dynamic, which serves as symbolic coding of dynamical systems, but also has its own status, with connections to computability and formal automata. Among the topics likely to be discussed are:
- Language and (sub)shift spaces: basic notions and definitions.
- Subshifts of finite type and sofic subshifts; equivalence between subshifts.
- Automata approach and Turing machines
- Linguistic complexity and the Chomsky hierarchy.
- Entropy and word-complexity
- Minimal subshifts; uniform and linear recurrence.
- Sturmian subshifts
- Substitution subshifts and Toeplitz subshifts.
- Bratteli diagrams and the Vershik map
- Subshifts coming from one-dimensional dynamics (β-transformation, kneading theory).
- Cellular automata.

References/Background reading

• Bruce Kitchens, Symbolic dynamics: one-sided, two-sided and countable state Markov shifts, Springer Verlag. ISBN 3-540 -62738-3
• Douglas Lind & Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge Univ Press, ISBN 0-521-55900-6
• Martine Queffélec, Substitution dynamical systems and spectral analysis, Lect. Notes in Math 1294, Springer-Verlag. ISBN 3-540-18692-1.
• John Hopcroft and Jeffrey Ullman, Introduction to Automata Theory, Languages and Computation, Addision-Wesley Publ. ISBN 0-201-02988-X
• Topics in Symbolic Dynamics and Applications London Mathematical Society Lecture Note Series Editors: F. Blanchard, A. Maass, A. Nogueira, Cambridge Univ. Press 2000, ISBN 9780521796606
• Notes Karl Petersen's website

Assessment

Will be based on an oral exam (in English by default, aber auf Deutsch ist auch möglich ).

Material:

• Class notes. These notes are part of a longer text (still n progress) and therefore some cross-references are missing (usually indicated by ??).

Course material (Hand-outs)