The geometry of tilings has a long history going back to antiquity as patterns occurred in architecture (the Alhambra and Alcazar palaces in Spain, for in- stance) and decorative art (the drawings of Cornelius Escher). The seventeen wallpaper groups provide a classification of the periodic tessellations. In modern times, digital geometry emerged as a research domain dealing with discrete point sets aiming at transposing notions of classical euclidean geometry to the digital plane Z × Z. It is generally agreed to place the birth of this field of research in the early 1970s with the founding articles of Azriel Rosenfeld illustrating perfectly the transposition of Euclidean geometry: "Connectivity in digital pictures” (1970); "Arcs and curves in digital pictures" (1973); and also "Digital straight line segments" (1974). However, as mentioned by R. Klette and Azriel Rosenfeld himself in the introduction of their article "Digital straightness" (2004),

"Related work even earlier on the theory of words, specifically, on mechanical or Sturmian words, remained unnoticed in the pattern recognition community."

Combinatorics on Words builds bridges between digital geometry and the combinatorics of tilings as tiles are represented by polyominoes.

In the last ten years, we have contributed to the field of digital geometry and particularly to the description of tilings obtained by translating a single tile, which corresponds to one of the seventeen wallpaper groups. Solving equations on words provides powerful tools for describing tiles:

— patterns such as palindromes and pseudo-palindromes describe the shapes of the tiles;
— enumeration and random generation;
— Lyndon factorizations and Christoffel words are useful for describing convexity.

This opens the way to the study of tessellations from a Combinatorics on Words point of view.

School

The main goal of the school is to give an introductory presentation of the topics from Combinatorics on Words necessary for the description of tilings of the plane, including current methods and soled problems; namely,

— equations on words;
— patterns: periodicity and palindromes;
— characterization of the tiles that tessellate the plane;
— enumeration and generation of tiles.

Workshop

There will be ten talks of one hour duration (including time for questions), 2 per morning, in areas including but not limited to the themes of the previous week's Spring School. The afternoons will be dedicated to group work around opens problems and Sage programming sessions.