PSPACE-completeness of majority automata networks

DOI10.1016/J.TCS.2015.09.014zbMATH Open1331.68129arXiv1501.03992OpenAlexW2150494024MaRDI QIDQ897867FDOQ897867

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)

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.

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

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 \(\mathbf P\)-completeness

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)

Cites Work

• Computational Complexity
• Neural networks and physical systems with emergent collective computational abilities
• Title not available (Why is that?)
• Decreasing energy functions as a tool for studying threshold networks
• An introduction to sequential dynamical systems
• Computational complexity of threshold automata networks under different updating schemes

Cited In (18)

• The complexity of the bootstraping percolation and other problems
• On simulation in automata networks
• 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
• Title not available (Why is that?)
• 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)