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

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)

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

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• An introduction to sequential dynamical systems
• 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
• Combinatorial matrix theory
• Computational Complexity
• Decreasing energy functions as a tool for studying threshold networks
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• Neural networks and physical systems with emergent collective computational abilities
• No polynomial bound for the period of the parallel chip firing game on graphs
• On efficient parallel strong orientation
• The complexity of the bootstraping percolation and other problems

Cited in

(22)

• The complexity of the bootstraping percolation and other problems
• Dynamics of neural networks over undirected graphs
• Complexity of inferring local transition functions of discrete dynamical systems
• Symmetrizable Boolean networks
• Computing the probability of getting infected: on the counting complexity of bootstrap percolation
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• Eric Goles
• The hardness of local certification of finite-state dynamics
• Intrinsic universality in automata networks. III: On symmetry versus asynchrony
• UNCERTAINTY VISUALIZATION FOR CHARACTERIZING HETEROGENEOUS HUMAN BEHAVIORS IN DISCRETE DYNAMICAL SYSTEM MODELS
• Intrinsic universality in automata networks. II: Glueing and gadgets
• Invariance under the order of updating in automata networks
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• On the effects of firing memory in the dynamics of conjunctive networks
• On the effects of firing memory in the dynamics of conjunctive networks
• 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
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• The complexity of the asynchronous prediction of the majority automata
• Existence and non existence of limit cycles in Boolean networks
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules

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)