16 citations · 46 across the 31 of their papers we have counts for
5 papers · 1 filter
Communication Complexity and Intrinsic Universality in Cellular Automata
Eric Goles Chacc, Pierre-Etienne Meunier, Ivan Rapaport +1
The notions of universality and completeness are central in the theories of computation and computational complexity. However, proving lower bounds and necessary conditions remains…
Subshifts as Models for MSO Logic
Emmanuel Jeandel, Guillaume Theyssier
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 characterizat…
Communications in cellular automata
Eric Goles, Pierre-Etienne Meunier, Ivan Rapaport +1
The goal of this paper is to show why the framework of communication complexity seems suitable for the study of cellular automata. Researchers have tackled different algorithmic pr…
Subshifts, Languages and Logic
Emmanuel Jeandel, Guillaume Theyssier
We study the Monadic Second Order (MSO) Hierarchy over infinite pictures, that is tilings. We give a characterization of existential MSO in terms of tilings and projections of tili…
On Local Symmetries And Universality In Cellular Autmata
Laurent Boyer, Guillaume Theyssier
Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and…