The complexity of the asynchronous prediction of the majority automata

DOI10.1016/j.ic.2020.104537zbMath1460.68068OpenAlexW3009762763MaRDI QIDQ2201796

Eric Goles Chacc, Pedro Montealegre

Publication date: 17 September 2020

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2020.104537

zbMATH Keywords

computational complexitycellular automataNP-completenessparallel algorithmsbootstrap percolationprediction problemasynchronous updatingmajority automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Related Items

On the complexity of asynchronous freezing cellular automata, Computing the probability of getting infected: on the counting complexity of bootstrap percolation, Amoebae for clustering: a bio-inspired cellular automata method for data classification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of the bootstraping percolation and other problems
• Computational complexity of threshold automata networks under different updating schemes
• Decreasing energy functions as a tool for studying threshold networks
• Signal propagation in 2-dimensional threshold cellular space
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Self-organized societies: on the Sakoda model of social interactions
• The complexity of the majority rule on planar graphs
• Cell space approaches in biomathematics
• On periodical behaviour in societies with symmetric influences
• On the complexity of two-dimensional signed majority cellular automata
• The convergence of symmetric threshold automata
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks
• Neural networks and physical systems with emergent collective computational abilities.