-
Structural and computational properties of tilings
Colorings of the discrete plane (i.e., tilings) are a geometrical model which is intimately linked with computability theory. We show in this manuscript how many... -
Complexity of aperiodic tilings : computations and interpretations
Since the 1980s, the theory of aperiodic tilings developed quickly, motivated by the discovery of metallic alloys which crystallize in an aperiodic structure. This... -
Multidimensional extension of the Morse--Hedlund theorem
International audience -
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshi...
International audience -
At the intersection of combinatorics on words and discrete geometry : palindr...
In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in... -
Turing degrees of multidimensional subshifts
International audience -
Subshifts as models for MSO logic
International audience -
Subshifts as Models for MSO Logic
We study the Monadic Second Order (MSO) Hierarchy over colourings of the discrete plane, and draw links between classes of formula and classes of subshifts. We give a...
