Students are expected to know about basic notions of topology (open, closed and compact sets, distance) but also to be familiar with finite automata theory and computability theory.
The objective of this course is to illustrate how computability theory imposes some constraints -- computability obstructions -- on dynamical systems such as tiling systems, and how these obstructions often occur as the only ones.
Three homework assignments and an oral presentation of a research article (details concerning the oral presentation will depend on the number of students).
Homework assignment 1 [pdf], duedate 10.25.2015 !!
Cantor space, two definitions of subshifts, SFT.
Examples of SFTs, sofic subshifts.
One dimensional SFTs and sofic susbhifts.
Robinson's tiling, Mozes result (in a nutshell) [pdf].
- [LM95] Douglas A. Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York, NY, USA, 1995.
- [Kit98] Bruce P. Kitchens. Symbolic dynamics. Universitext. Springer-Verlag, Berlin, 1998. One-sided, two-sided and countable state Markov shifts.
- [Rob91] Arthur Robinson. Symbolic Dynamics and Tilings of Rd. Proceedings of Symposia in Applied Mathematics
- [Ber66] Robert Berger. The undecidability of the domino problem. American Mathematical Society, 1966.
- [Rob71] Raphael Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12(3):177–209, 1971.
- [GS98] Chaim Goodman-Strauss : Matching rules and substitution tilings. Annals of Mathematics, 157:181–223, 1998.
- [Moz89] Shahar Mozes. Tilings, substitution systems and dynamical systems generated by them. Journal d’Analyse Mathématique (Jerusalem), 53:139–186, 1989.
- [Kar96] Jarkko Kari. A small aperiodic set of wang tiles. Discrete Mathematics, 160(1-3):259–264, 1996.
- [pdf] E. Jeandel and G. Theyssier, Subshifts as models for MSO logic (2013)
- [pdf] J. Kari, The Nilpotency Problem of One-Dimensional Cellular Automata (1992)
- [pdf] and [pdf] W. Hanf and D. Myers, Nonrecursive Tilings of the Plane. I and II (1974)
Robert Ammann, Branko Grünbaum, G. C. Shephard, Aperiodic tiles (1992)(chosen by Antoine)
- [pdf] Antoine Julien, Complexity and cohomology for cut and projection tilings (2010)
- [pdf] P. Kasteleyn, The statistics of dimers on a lattice (1961)
R. Kenyon, Tiling a polygon wih parallelogram (1993)(chosen by Yassine)
M. Luby, D. Randall and A.J. Sinclair, Markov chain algorithms for planar lattice structures (2001)(chosen by Damien)
Dave Bayer, Persi Diaconis, Trailing the dovetail shuffle to its lair (1992)(chosen by Nam)
- [pdf] M. Hochman, Universality in Multidimensional Symbolic Dynamics (2009)
- [pdf] R. Pavlov and M. Schraudner, Entropies realizable by block gluing shifts of finite type
- [pdf] W. Jockusch, J. Propp , P. Shor, Random Domino Tilings and the Arctic Circle Theorem (1995)
- [pdf] Jarkko Kari and Michal Szabados, An Algebraic Geometric Approach to Nivat’s Conjecture (2015)
- [pdf] Van Cyr and Bryna Kra, Nonexpansive Z^2-Subdynamics and Nivat's Conjecture (2014)
- [pdf] Tom Meyerovitch, Growth-type invariants for Z^d subshifts of finite type and arithmetical classes of real numbers (2010)
- [pdf] Tom Meyerovitch and Ronnie Pavlov, Entropy and measures of maximal entropy for axial powers of subshifts (2014)
- [pdf] Nick Ormes and Ronnie Pavlov, Extender sets and multidimensional subshifts (2013)
- [pdf] Van Cyr and Bryna Kra, The automorphism group of a minimal shift of stretched exponential growth (2015)