2 citations · 2 across the 11 of their papers we have counts for
5 papers · 1 filter
The Two-Dimensional Majority Rule is P-Complete
Pedro Montealegre, Martín Ríos-Wilson
We prove that prediction for the synchronous two-dimensional majority rule is -complete under logspace many-one reductions, resolving a problem open for almost three de…
Impact of (a)Synchronism on ECA: Towards a New Classification
Isabel Donoso-Leiva, Eric Goles, Martin Rios-Wilson +1
In this paper, we study the effect of (a)synchronism on the dynamics of elementary cellular automata. Within the framework of our study, we choose five distinct update schemes, sel…
Dynamical Stability of Threshold Networks over Undirected Signed Graphs
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson +1
This paper, we explore the dynamics of threshold networks on undirected signed graphs. Much attention has been dedicated to understanding the convergence and long-term behavior of…
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…
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…