2026

Complexité descriptive des classes de Kurka sur les groupes

Juliette Favereau

Master Thesis

We study the computational complexity of Kurka classes over groups, with a focus on F2 and non ammenable groups. This was done under the supervision of Guillaume Theyssier and Pierre Guillon. The document is in French.

2025

Descriptive Complexity of Sensitivity of Cellular Automata

Juliette Favereau, Ville Salo

AUTOMATA 2025

We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Pi02-complete in dimension 1 and Sigma03-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.

2024

Local Generation of Tilings: The Even Bicolor Wang Tilesets

Juliette Favereau, Mathieu Hoyrup

Preprint

In this article, we apply the techniques developed in our previous article, “Local Generation of Tilings,” in which we introduced two definitions capturing the idea that some subshifts admit a procedure able to generate any tiling in a local way. We classify all Wang tilesets with two colors in which each tile has an even number of each color.

2024

Local Generation of Tilings

Juliette Favereau, Mathieu Hoyrup

Ergodic Theory and Dynamical Systems

We investigate the possibility of generating all configurations of a subshift in a local way. We propose two definitions of local generation, explore their properties, and develop techniques to determine whether a subshift satisfies these definitions. We illustrate the results with several examples.