Computational complexity of threshold automata networks under different updating schemes

DOI10.1016/J.TCS.2014.09.010MaRDI QIDQ475388zbMATH OpenOpenAlexFDO

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 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
• Complexity of inferring local transition functions of discrete dynamical systems
• 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
• The complexity of the majority rule on planar graphs
• Dynamics of neural networks over undirected graphs
• Intrinsic universality in automata networks. II: Glueing and gadgets
• 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
• On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
• Invariance under the order of updating in automata networks
• Symmetrizable Boolean networks
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• Eric Goles
• Computing the probability of getting infected: on the counting complexity of bootstrap percolation
• Sandpile toppling on Penrose tilings: identity and isotropic dynamics
• Complexity of limit cycles with block-sequential update schedules in conjunctive networks
• 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)