Talk abstract:

Multi-dimensional Symbolic Dynamical Systems

Klaus Schmidt
Mathematics Institute
University of Vienna
Strudlhofgasse 4, A-1090
Vienna, Austria
and
Erwin Schrödinger Institute for Mathematical Physics
Boltzmanngasse 9, A-1090
Vienna, Austria
klaus.schmidt@univie.ac.at
http://radon.mat.univie.ac.at/People/KlausSchmidt.html

This lecture discusses multidimensional shifts of finite type and gives examples of such systems from statistical mechanics, cellular automata and other areas. Roughly speaking, a d-dimensional shift of finite type (SFT) is a closed, shift-invariant subset X ^AZd, where A is a finite set, and where a point x A^Zd belongs to X if and only if it satisfies certain purely local restrictions at each coordinate.

The purpose of the talk is to point out some of the new phenomena which arise in the transition from classical shifts of finite type (where d=1) to the case where d>1 .

The most notorious of these are certain undecidability problems which don't give much trouble in practice, but which effectively prevent a satisfactory general theory of multi-dimensional SFT's.

The main emphasis of the talk will, however, be on the rigidity properties of certain multi-dimensional SFT's which range from scarcity of isomorphism and shift-invariant measures to the appearance of unexpected intrinsic algebraic structures for certain classical SFT's.

References

[1] R. Berger, The undecidability of the Domino Problem, Mem. Amer. Math. Soc. 66 (1966).

[2] C. Cohn, N. Elkies and J. Propp, Local statistics for random domino tilings of the Aztec diamond, Duke Math. J. 85 (1996), 117-166.

[3]. W. Geller and J. Propp, The projective fundamental group of a Z²-shift, Ergod. Th. & Dynam. Sys. 15 (1995), 1091-1118.

[4]. B. Kitchens and K. Schmidt, Periodic points, decidability and Markov subgroups, in: Dynamical Systems, Proceeding of the Special Year, Lecture Notes in Mathematics, vol. 1342, Springer Verlag, Berlin-Heidelberg-New York, 1988, 440-454.

[5]. B. Kitchens and K. Schmidt, Markov subgroups of (Z_/2) ^Z2, Contemp. Math. 135 (1992), 265-283.

[6]. B. Kitchens and K. Schmidt, Mixing sets and relative entropies for higher dimensional Markov shifts, Ergod. Th. & Dynam. Sys. 13 (1993), 705-735.

[7]. W. Parry, Instances of cohomological triviality and rigidity, Ergod. Th. & Dynam. Sys. 15 (1995), 685-696.

[8]. R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177-209.

[9]. K. Schmidt, The cohomology of higher-dimensional shifts of finite type, Pacific J. Math. 170 (1995), 237-270.

[10]. K. Schmidt, Dynamical systems of algebraic origin, Birkhäuser Verlag, Basel-Berlin, 1995.

[11]. K. Schmidt, Tilings, fundamental cocycles and fundamental groups of symbolic Z^d-actions, Ergod. Th. & Dynam. Sys. 18 (1998), 1473-1525.

[12]. H. Wang, Proving theorems by pattern recognition II, AT&T Bell Labs. Tech. J. 40 (1961), 1-41.

Back to Codes, Systems and Graphical Models