The complexity of the asynchronous prediction of the majority automata
DOI10.1016/J.IC.2020.104537zbMATH Open1460.68068OpenAlexW3009762763MaRDI QIDQ2201796FDOQ2201796
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
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
computational complexitycellular automataNP-completenessparallel algorithmsbootstrap percolationprediction problemasynchronous updatingmajority automata
Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)
Cites Work
- Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
- Neural networks and physical systems with emergent collective computational abilities.
- On periodical behaviour in societies with symmetric influences
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decreasing energy functions as a tool for studying threshold networks
- An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
- The complexity of the bootstraping percolation and other problems
- Title not available (Why is that?)
- The convergence of symmetric threshold automata
- Computational complexity of threshold automata networks under different updating schemes
- On the complexity of two-dimensional signed majority cellular automata
- Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks
- Signal propagation in 2-dimensional threshold cellular space
- Cell space approaches in biomathematics
- Self-organized societies: on the Sakoda model of social interactions
- The complexity of the majority rule on planar graphs
Cited In (4)
- On the complexity of asynchronous freezing cellular automata
- A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
- 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
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)
