PSPACE-Completeness of Majority Automata Networks
classification
💻 cs.DM
keywords
automatamajoritynetworksaccordingblockchangecomplexityconfiguration
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.