Publications
Descriptive Complexity of Sensitivity of Cellular Automata
preprint
We study the computational complexity of determining whether a cellular automaton is sensitive to initial conditions. We show that this problem is Pi^0_2-complete in dimension 1 and Sigma^0_3-complete in dimension 2 and higher. This solves a question posed by Sablik and Theyssier.
Local generation of tilings: the even bicolor Wang tilesets
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 intuitive idea that some subshifts admit a procedure that can generate any tiling and working in a local way. We classify all the Wang tilesets with two colors in which each tile has an even number of each color.
Local generation of tilings
preprint
In this article, we investigate the possibility of generating all the 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.