On the Complexity of Stable and Biased Majority

Pablo Concha-Vega, Eric Goles, Pedro Montealegre () and Martín Ríos-Wilson
Additional contact information
Pablo Concha-Vega: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal Las Torres 2640, Santiago 7941169, Chile
Eric Goles: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal Las Torres 2640, Santiago 7941169, Chile
Pedro Montealegre: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal Las Torres 2640, Santiago 7941169, Chile
Martín Ríos-Wilson: Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Av. Diagonal Las Torres 2640, Santiago 7941169, Chile

Mathematics, 2022, vol. 10, issue 18, 1-13

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.

Keywords: cellular automata; majority rule; prediction problem (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/18/3408/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/18/3408/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:18:p:3408-:d:919079

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().