16 citations · 46 across the 31 of their papers we have counts for
19 papers · 1 filter
Bootstrap percolation on rhombus tilings
S Esnay, V Lutfalla, G Theyssier
2-boostrap percolation on a graph is a diffusion process where a vertex gets infected whenever it has at least 2 infected neighbours, and then stays infected forever. It has been m…
FO logic on cellular automata orbits equals MSO logic
Guillaume Theyssier
We introduce an extension of classical cellular automata (CA) to arbitrary labeled graphs, and show that FO logic on CA orbits is equivalent to MSO logic. We deduce various results…
On the impact of treewidth in the computational complexity of freezing dynamics
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson +1
An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the networ…
Freezing, Bounded-Change and Convergent Cellular Automata
Nicolas Ollinger, Guillaume Theyssier
This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some o…
On the cost of simulating a parallel Boolean automata network by a block-sequential one
Florian Bridoux, Pierre Guillon, Kévin Perrot +2
In this article we study the minimum number of additional automata that a Boolean automata network (BAN) associated with a given block-sequential update schedule needs in order…
Pre-Expansivity in Cellular Automata
A. Gajardo, V. Nesme, Guillaume Theyssier
We introduce the property of pre-expansivity for cellular automata (CA): it is the property of being expansive on asymptotic pairs of configurations (i.e. configurations that diffe…