On the computational complexity of finite cellular automata
From MaRDI portal
Publication:1892208
DOI10.1006/jcss.1995.1009zbMath0827.68078OpenAlexW2076223914MaRDI QIDQ1892208
Publication date: 13 December 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1995.1009
Related Items (24)
On the complexity of occurrence and convergence problems in reaction systems ⋮ Complexity of reachability problems for finite discrete dynamical systems ⋮ Complexity of the dynamics of reaction systems ⋮ Reachability problems for sequential dynamical systems with threshold functions. ⋮ Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ Random number generation using decimal cellular automata ⋮ The predecessor-existence problem for \(k\)-reversible processes ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ The general \(\sigma \) all-ones problem for trees ⋮ HIGHER ORDER CELLULAR AUTOMATA ⋮ Computational complexity of finite asynchronous cellular automata ⋮ Predecessors and Garden-of-Eden configurations in parallel dynamical systems on maxterm and minterm Boolean functions ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ ITERATION OF INVERTIBLE TRANSDUCTIONS ⋮ Solution to the predecessors and gardens-of-Eden problems for synchronous systems over directed graphs ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Dynamical attraction in parallel network models ⋮ Reachability problem in non-uniform cellular automata ⋮ ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS ⋮ A Survey of the Game “Lights Out!” ⋮ Computational classification of cellular automata ⋮ Computation theoretic aspects of cellular automata ⋮ Classifying circular cellular automata
This page was built for publication: On the computational complexity of finite cellular automata
