Computational complexity of threshold automata networks under different updating schemes

DOI10.1016/j.tcs.2014.09.010zbMath1360.68557OpenAlexW2065909799MaRDI QIDQ475388

Pedro Montealegre, Eric Goles Chacc

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 complexitythreshold functionsNP-hardnessNCP-completenessautomata networksupdating scheme

Mathematics Subject Classification ID

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

Related Items (12)

A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton ⋮ 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 ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Eric Goles ⋮ On the effects of firing memory in the dynamics of conjunctive networks ⋮ On the effects of firing memory in the dynamics of conjunctive networks ⋮ Sandpile toppling on Penrose tilings: identity and isotropic dynamics ⋮ Computing the probability of getting infected: on the counting complexity of bootstrap percolation ⋮ Existence and non existence of limit cycles in Boolean networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of the bootstraping percolation and other problems
• An introduction to sequential dynamical systems
• Decreasing energy functions as a tool for studying threshold networks
• On efficient parallel strong orientation
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• No polynomial bound for the period of the parallel chip firing game on graphs
• Computational Complexity
• Neural networks and physical systems with emergent collective computational abilities.

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