13 citations · 26 across the 10 of their papers we have counts for
3 papers · 1 filter
On the complexity of the generalized Q2R automaton
Eric Goles, Marco Montalva-Medel, Pedro Montealegre +1
We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous upda…
Freezing sandpiles and Boolean threshold networks: equivalence and complexity
Eric Goles, Pedro Montealegre Kévin Perrot
The NC versus P-hard classification of the prediction problem for sandpiles on the two dimensional grid with von Neumann neighborhood is a famous open problem. In this paper we mak…
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…