Computational complexity of threshold automata networks under different updating schemes

DOI10.1016/J.TCS.2014.09.010zbMATH Open1360.68557OpenAlexW2065909799MaRDI QIDQ475388FDOQ475388

Authors: Pedro Montealegre, Eric Goles 

Publication date: 26 November 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.010

Recommendations

• PSPACE-completeness of majority automata networks
• The complexity of the bootstraping percolation and other problems
• The complexity of the asynchronous prediction of the majority automata
• The complexity of the majority rule on planar graphs
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules

zbMATH Keywords

computational complexityNP-hardnessthreshold functionsNCP-completenessautomata networksupdating scheme

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cellular automata (computational aspects) (68Q80)

Cites Work

• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Combinatorial matrix theory
• Computational Complexity
• Neural networks and physical systems with emergent collective computational abilities.
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decreasing energy functions as a tool for studying threshold networks
• The complexity of the bootstraping percolation and other problems
• An introduction to sequential dynamical systems
• On efficient parallel strong orientation
• No polynomial bound for the period of the parallel chip firing game on graphs

Cited In (18)

• On the effects of firing memory in the dynamics of conjunctive networks
• On the effects of firing memory in the dynamics of conjunctive networks
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• Existence and non existence of limit cycles in Boolean networks
• Intrinsic universality in automata networks. II: Glueing and gadgets
• Dynamics of neural networks over undirected graphs
• PSPACE-completeness of majority automata networks
• UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS
• The complexity of the asynchronous prediction of the majority automata
• Intrinsic universality in automata networks. III: On symmetry versus asynchrony
• Symmetrizable Boolean networks
• Invariance under the order of updating in automata networks
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• Eric Goles
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• Computing the probability of getting infected: on the counting complexity of bootstrap percolation
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• The hardness of local certification of finite-state dynamics

This page was built for publication: Computational complexity of threshold automata networks under different updating schemes

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