16 citations · 46 across the 31 of their papers we have counts for
4 papers · 2 filters
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…
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…