|
Concha-Vega, P., Goles, E., Montealegre, P., & Rios-Wilson, M. (2022). On the Complexity of Stable and Biased Majority. Mathematics, 10(18), 3408.
Abstract: A majority automata is a two-state cellular automata, where each cell updates its state according to the most represented state in its neighborhood. A question that naturally arises in the study of these dynamical systems asks whether there exists an efficient algorithm that can be implemented in order to compute the state configuration reached by the system at a given time-step. This problem is called the prediction problem. In this work, we study the prediction problem for a more general setting in which the local functions can be different according to their behavior in tie cases. We define two types of local rules: the stable majority and biased majority. The first one remains invariant in tie cases, and the second one takes the value 1. We call this class the heterogeneous majority cellular automata (HMCA). For this latter class, we show that in one dimension, the prediction problem for HMCA is in NL as a consequence of the dynamics exhibiting a type of bounded change property, while in two or more dimensions, the problem is P-Complete as a consequence of the capability of the system of simulating Boolean circuits.
|
|
|
Goles, E., & Montealegre, P. (2015). The complexity of the majority rule on planar graphs. Adv. Appl. Math., 64, 111–123.
Abstract: We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule. (C) 2014 Elsevier Inc. All rights reserved.
|
|
|
Goles, E., & Montealegre, P. (2020). The complexity of the asynchronous prediction of the majority automata. Inf. Comput., 274(SI).
Abstract: We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete.
|
|
|
Goles, E., Montealegre, P., Perrot, K., & Theyssier, G. (2018). On the complexity of two-dimensional signed majority cellular automata. J. Comput. Syst. Sci., 91, 1–32.
Abstract: We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length. (C) 2017 Elsevier Inc. All rights reserved.
|
|
|
Goles, E., Montealegre, P., Salo, V., & Torma, I. (2016). PSPACE-completeness of majority automata networks. Theor. Comput. Sci., 609, 118–128.
Abstract: We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete. (C) 2015 Elsevier B.V. All rights reserved.
|
|
|
Goles, E., Montealegre, P., & Vera, J. (2016). Naming Game Automata Networks. J. Cell. Autom., 11(5-6), 497–521.
Abstract: In this paper we introduce automata networks to model some features of the emergence of a vocabulary related with the naming game model. We study the dynamical behaviour (attractors and convergence) of extremal and majority local functions.
|
|