PSPACE-completeness of majority automata networks

DOI10.1016/J.TCS.2015.09.014MaRDI QIDQ897867zbMATH OpenOpenAlexFDO

Authors Pedro Montealegre, Ilkka A. Törmä, Eric Goles, Ville Salo

Publication date 8 December 2015

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

Full work available at URL https://arxiv.org/abs/1501.03992

zbMATH Keywords

Boolean networkPSPACEprediction problemmajority network

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete.

Recommendations

• Computational complexity of threshold automata networks under different updating schemes
• 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
• Majority-vote cellular automata, Ising dynamics, and P-completeness

Cites work

• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• An introduction to sequential dynamical systems
• Computational Complexity
• Computational complexity of threshold automata networks under different updating schemes
• Decreasing energy functions as a tool for studying threshold networks
• Neural networks and physical systems with emergent collective computational abilities

Cited in

(19)

• The complexity of the bootstraping percolation and other problems
• On simulation in automata networks
• Majority-vote cellular automata, Ising dynamics, and P-completeness
• Universal safety for timed Petri nets is PSPACE-complete
• On the effects of firing memory in the dynamics of conjunctive networks
• On the effects of firing memory in the dynamics of conjunctive networks
• scientific article; zbMATH DE number 7770053 (Why is no real title available?)
• On the complexity of two-dimensional signed majority cellular automata
• The complexity of the majority rule on planar graphs
• Intrinsic universality in automata networks. II: Glueing and gadgets
• Tracks from hell -- when finding a proof may be easier than checking it
• Computational complexity of threshold automata networks under different updating schemes
• Everything Is PSPACE-Complete in Interaction Systems
• The complexity of the asynchronous prediction of the majority automata
• Intrinsic universality in automata networks. III: On symmetry versus asynchrony
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• Eric Goles
• Tracks from hell -- when finding a proof may be easier than checking it
• Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)

This page was built for publication: PSPACE-completeness of majority automata networks

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