PSPACE-completeness of majority automata networks

DOI10.1016/j.tcs.2015.09.014zbMath1331.68129arXiv1501.03992OpenAlexW2150494024MaRDI QIDQ897867

Ilkka Törmä, Pedro Montealegre, Jarkko Peltomäki, Eric Goles Chacc

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)

Related Items (9)

A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton ⋮ Tracks from hell - When finding a proof may be easier than checking it ⋮ Tracks from hell -- when finding a proof may be easier than checking it ⋮ Unnamed Item ⋮ Universal safety for timed Petri nets is PSPACE-complete ⋮ 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 ⋮ On simulation in automata networks

Cites Work

• Unnamed Item
• Computational complexity of threshold automata networks under different updating schemes
• An introduction to sequential dynamical systems
• Decreasing energy functions as a tool for studying threshold networks
• Computational Complexity
• Neural networks and physical systems with emergent collective computational abilities.

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