Math-Info 2010

Towards new interactions between mathematics and computer science

 

Invited Seminars

Thematic month

The five weeks

Multi-dimensional Subshifts And Tilings

1.  Dates

From February 15 to February 19, 2010.

2.  Description of the week

A subshift in dimension 1 is a set of infinite words closed by the shift operator. Subshifts are widely used to study the behaviour of a dynamical system. They have been studied for long, and their dynamics and computational behaviors are now well understood. Techniques used in dimension 1 however do not translate easily to higher dimensions, where subshifts (especially subshifts of finite type) correspond to the well known concept of tilings from theoretical computer science. This week will focus on combining both dynamical and computational approaches to study these higher-dimensional objects.

3.  Confirmed morning lectures (3h each)

  • Mike Boyle: Multidimensional Shifts of Finite Type and Sofic Shifts
Abstract: A Z^d shift of finite type (SFT) is a topological dynamical system given by the shift action of Z^d on some locally defined subspace X of A^{Z^d}, where A is some finite alphabet and d is a positive integer. A Z^d sofic shift is simply a quotient of a Z^d SFT by some rule f:A-->B; an element (function) x in X is sent to the function y such that y(v)=f(x(v)), v in Z^d. These shifts are fundamental objects in symbolic dynamics. Their dynamics are closely related to the dynamics of cellular automata.
When d=1, X can be the space of infinite walks through a directed graph (with A the vertex set). When d=2, X can be a space of Wang tilings: tilings of the plane from a finite set of unit-square tiles with edge colorings, subject to the condition that corners hit Z^2 and neighboring edges have the same color.
The Z SFTs are to a large extent well understood and qualitatively homogeneous, with mutual coding relations largely determined by a strict entropy inequality. For d>1, the Z^d SFTs are much less tractable and far more structurally diverse. Generally, there do not (and cannot) exist algorithms to decide or compute a property or invariant of interest.
Nevertheless, there has been considerable recent progress in understanding some possible behaviors and invariants of these SFTs, following work of Hochman and Meyerovitch. Their results have dramatically sharpened our understanding of the recursion theoretic nature of results on general {$Z^d$} SFTs when {$d>1$}, and introduced techniques which have been exploited by subsequent work of themselves and others.
I will describe the general setting, and survey the recent results and open problems.
Abstract: Local constraints force global structure very broadly, often with unpredictable, even undecidable results. We will discuss two primary examples: first, the construction of local matching rules that force a given hierarchical non-periodic structure, and second, ``regular production systems" as a tool for modeling a range of phenomena, including tilings and growth of surfaces along fronts.
Abstract: Two-dimensional cellular automata (2D CA) are endomorphisms of two-dimensional full shifts: continuous and translation invariant transformations of S^{Z^2}. There are many fundamental differences between two-dimensional CA and their one-dimensional counter parts. Many of these differences are explained by the different nature of one- and two-dimensional tilings. Existence of aperiodic tile sets and the undecidability of the domino problem provide many dimension sensitive properties for cellular automata. We discuss such properties, including the undecidability of reversibility of 2D CA. The main tool used in the proof is a tile set with a particular "plane-filling property". We show how this tile set provides also other interesting results on two-dimensional symbolic dynamics, e.g., an example of a 2D CA with positive but finite entropy, due to T.Meyerovitch.

4.  Schedule

 MondayTuesdayWednesdayThursdayFriday
9h-10h30-KariGoodman-StraussGambaudo-
11h-12h30BoyleGambaudoBoyleKariGoodman-Strauss

5.  Proposed workshops (add your suggestions here)

  • Jean-Rene Chazottes.
  • Maria Isabel Cortez and Samuel Petite propose an afternoon session on Toeplitz systems and odometers for general group actions.
  • François Gautero.
  • Edmund Harriss: "How to create substitution rules on the plane and some ideas towards how to characterize them."
  • Uijin Jung proposes a short afternoon session on relations among certain properties of finite-to-one maps between multidimensional transitive subshifts.
  • Michael Schraudner proposes an afternoon session on (Non-)Uniqueness of measures of maximal entropy for multidimensional shifts of finite type.
  • Marc Monticelli : xDim, Interactive Numerical Experimentation software
  • Ricardo Gómez : I would like to discuss the possibility and relevance of considering quotients of multidimensional zeta functions as analogues of first return loop systems.
  • Christoph Bandt : Topology of multidimensional self-affine tiles.
  • Lorenzo Sadun : Understanding tilings without finite local complexity.

6.  General Schedule

  • Monday 15th
    • 11h-12h30 M. Boyle - Multidimensional Shifts of Finite Type and Sofic Shifts
    • 14h30-15h30 A. Ballier - An order on subshifts
    • 15h45-16h45 M.Schraudner -(Non-)Existence of full shift factors for Z^d shifts of finite type
    • 17h00-18h Uijin Jung - Fiber-mixing codes between Z-subshifts and relations of codes between Zd subshifts
    • 18h-19h15 Apéritif, IML.
  • Tuesday 16th
    • 09h-10h30 J. Kari - Cellular automata.
    • 11h-12h30 J.M. Gambaudo
    • 15h30-16h15 R. Gomez - Quotients of multidimensional zeta functions as analogues of first return loop systems.
    • 16h30-17h30 L. Sadun - Understanding tilings without finite local complexity.
    • 18h00-19h00 N. Pytheas Fogg - Open problems session : bring your favorite and personal open problem.
  • Wednesday 17th
    • 09h-10h30 C. Goodman Strauss - From local combinatorial constraints to global structure.
    • 11h-12h30 M. Boyle - Multidimensional Shifts of Finite Type and Sofic Shifts.
    • 15h30-16h S. Akiyama- Pisot conjecture session: Introductory talk.
    • 16h15-17h15: Introductory talks
      • M. Schraudner - Uniqueness and non-uniqueness of measures of maximal entropy for Zd subshift of finite type
      • R. Pavlov - Approximating topological entropy of Z2 shift of finite type: Introductory talk.
    • 17h30-19h: Two parallel sessions
      • R. Pavlov, M. Schraudner and others - Approximating topological entropy of Z2 shift of finite type and Uniqueness and non-uniqueness of measures of maximal entropy for Zd subshift of finite type: Informal discussions.
      • M. Barge and A. Siegel- Pisot conjecture session: Informal discussions.
    • 20h30-...J.M. Gambaudo et M. Monticelli- xdim: simulations numériques pour quasi-cristaux
  • Thursday 18th
    • 09h-10h30 J.M. Gambaudo
    • 11h-12h30 J. Kari. - Cellular automata.
    • 15h30-16h15 Proposed by A. Julien and J. Savinien - Tilings equivalence relation(s) Bratteli diagrams and orbit equivalence: Introductory talk.
    • 16h30-17h15: Parallel sessions
      • Proposed by J. Cassaigne-Universal counter example for complexity function.
      • M.I. Cortez and S. Petite-Toeplitz systems and odometers for general group actions
    • 17h45-19h: Parallel sessions
      • Proposed by A. Julien and J. Savinien and others - Tilings equivalence relation(s) Bratteli diagrams and orbit equivalence: Informal discussion.
      • Proposed by A. Shen- Every one dimensional effectively closed subshift is a projection of two dimensional finite type subshift.
      • Proposed by A. Hilion- Topological substitutions
  • Friday 19th
    • 09h-10h30 A. Dennunzio-Workshop on cellular automata.
    • 11h-12h30 C. Goodman Strauss. - From local combinatorial constraints to global structure.
    • 14h-14h30 C. Bandt- Topology of multidimensional self-affine tiles
    • 14h45-17h Substitution tiling and matching rules
      • C. Goodman Strauss
      • Th. Fernique and N. Ollinger ''A Robinson-like construction of matching rules for combinatorial substitutions"
      • E. Harriss - How to create substitution rules on the plane and some ideas towards how to characterize them

7.  Currently uploaded slides

8.  Participants

See the page Multi-dimensional Subshifts And Tilings Participants

 

For any technical question or comment regarding this wiki, you can contact the wemaster.