Thematic Program on
Dynamical Systems
 School of Mathematics, IPM,
 February - May, 2017

School of Mathematics
 & Topology

Practical Information  

Mini Course

Fabien Durand
(Univ. Picardie, France)

Title: Cobham’s theorem and substitution subshifts

Date &
May 20-23, 2017 (4 lectures)

Lecture Hall 2,
IPM Niavaran Building,
Niavaran Square, Tehran
This lecture intends to propose a first contact with subshift dynamical systems through the study of a well known family: the substitution subshifts. This will include a short introduction to topological dynamical systems and combinatorics on words. We will focus on the unique ergodicity of substitution subshifts and we will obtain, as a corollary, a proof of a seminal result on automata theory: the Cobham's theorem.

J.-P. Allouche and J. O. Shallit. Automatic Sequences, Theory, Applications, Generalizations. Cambridge University Press, 2003.

A. Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory, 3:186–192, 1969.

A. Cobham. Uniform tag sequences. Math. Systems Theory, 6:164–192, 1972.

F. Durand. Linearly recurrent subshifts have a finite number of non-periodic subshift factors. Ergodic Theory Dynam. Systems, 20:1061–1078, 2000.

F. Durand. Infinite words and invariant measures. In V. Berthe and M. Rigo, editors, Combinatorics, Automata and Number Theory, volume 135 of Encyclopedia of Mathematics and its applications, pages 338–386. Cambridge Univ. Press, 2010.

S. Eilenberg. Automata, Languages, and Machines, volume A. Academic Press, 1974.

R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, Cambridge, 1990. Corrected reprint of the 1985 original.

C. Holton and L. Q. Zamboni. Descendants of primitive substitutions. Theory Comput. Systems, 32:133–157, 1999.

D. Lind and B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.

M. Morse and G. A. Hedlund. Symbolic dynamics. Amer. J. Math., 60:815–866, 1938.

J.-J. Pansiot. Decidability of periodicity for infinite words. RAIRO Inform. Theor. App., 20:43–46, 1986.

K. Petersen. Ergodic theory. Cambridge University Press, 1983.

Martine Queffelec. Substitution dynamical systems—spectral analysis.Second Edition, volume 1294 of Lecture Notes in Mathemat- ics. Springer-Verlag, Berlin, 2010.

School of Mathematics,
IPM - Institute for Research in Fundamental Sciences
Niavaran Building, Niavaran Square, Tehran, Iran
Tel: +98 21 222 90 928