The complexity of the asynchronous prediction of the majority automata

DOI10.1016/J.IC.2020.104537zbMATH Open1460.68068OpenAlexW3009762763MaRDI QIDQ2201796FDOQ2201796

Authors Eric Goles, 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)

Recommendations

• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• PSPACE-completeness of majority automata networks
• The complexity of the bootstraping percolation and other problems
• The complexity of the majority rule on planar graphs
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1241089 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Cell space approaches in biomathematics
• Computational complexity of threshold automata networks under different updating schemes
• Decreasing energy functions as a tool for studying threshold networks
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Neural networks and physical systems with emergent collective computational abilities
• Number of fixed points and disjoint cycles in monotone Boolean networks
• On periodical behaviour in societies with symmetric influences
• On the complexity of two-dimensional signed majority cellular automata
• Self-organized societies: on the Sakoda model of social interactions
• Signal propagation in 2-dimensional threshold cellular space
• The complexity of the bootstraping percolation and other problems
• The complexity of the majority rule on planar graphs
• The convergence of symmetric threshold automata

Cited in

(11)

• On the complexity of asynchronous freezing cellular automata
• The complexity of the bootstraping percolation and other problems
• Amoebae for clustering: a bio-inspired cellular automata method for data classification
• Computing the probability of getting infected: on the counting complexity of bootstrap percolation
• The complexity of the majority rule on planar graphs
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• PSPACE-completeness of majority automata networks
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• On the complexity of two-dimensional signed majority cellular automata
• On the computational complexity of the freezing non-strict majority automata
• Computational complexity of threshold automata networks under different updating schemes

This page was built for publication: The complexity of the asynchronous prediction of the majority automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201796)